compiladores

Gramaticas

Tipo 3 o Regulares (AF: Automatas Finitos)

G = (VT, VN, P, S)

VT: Conjunto de Simbolos Terminales
VN: Conjunto de Simbolos No Terminales
SVN: Simbolo Inicial
P: Conjunto de Reglas de Produccion

Regular a Derecha: P VN x (VTVNVT{})
Regular a Izquierda: P VN x (VNVTVT{})
Notacion: ={}


Tipo 2 o Libres de Contexto (CFG) (AP: Automatas de Pila)

G = (VT,VN, P, S)

VT: Conjunto de Simbolos Terminales
VN: Conjunto de Simbolos No Terminales
SVN: Simbolo Inicial
P: Conjunto de Reglas de Produccion

P VN x (VTVn)*

Tipo 1 o Sensibles al Contexto (CSG) (ALA: Automata Linealmente Acotado)

G = (VT, VN, P, S)

VT: Conjunto de Simbolos Terminales
VN: Conjunto de Simbolos No Terminales
SVN: Simbolo Inicial
P: Conjunto de Reglas deProduccion

P (VTVn)* Vn (VTVn)* x (VTVn)*
  con ||  ||



Tipo 0 o Sin Restricciones o Estructuradas por Fase (MT: Maquinas de Turing)

G = (VT, VN, P, S)

VT: Conjunto de Simbolos Terminales
VN: Conjunto de Simbolos No Terminales
SVN: Simbolo Inicial
P: Conjunto de Reglas de Produccion

P (VTVn)* Vn (VTVn)* x (VTVn)*

Automatas

Automata Finito DeterministicoM = (Q, A, , q0, F)

Q: Conjunto de Estados (finito)
A: Alfabeto.
: Q x A  Q: Funcion de un (Estado, Simbolo) a Estado.
q0 Q: Estado Inicial.
F Q: Conjunto de Estdados de Aceptacion.

Extension de : *: Q x A*  Q

Automata Finito No Deterministico

M = (Q, A, , q0, F)

Q: Conjunto de Estados (finito)
A: Alfabeto.
  Q x A x Q: Funcion de un (Estado, Simbolo) aEstado.
q0 Q: Estado Inicial.
F Q: Conjunto de Estdados de Aceptacion.


Automata Finito Con Transiciones 

M = (Q, A, , q0, F, V)

Q: Conjunto de Estados (finito)
A: Alfabeto.
  Q x A x Q: Relacion de (Estados, Simbolo, Estado).
q0 Q: Estado Inicial.
F Q: Conjunto de Estdados de Aceptacion.
V Q x Q: Relacion de transicion 


Automata de Pila

M = (Q, AE, AP, , q0,z0, F)

Q: Conjunto de Estados (finito)
AE: Alfabeto de Entrada.
AP: Alfabeto de Pila.
: Q x (AE  {}) x (AP  {})  Subconjuntos Finitos de Q x AP*:
Funcion de un (Estado, Simbolo) a Estado.
q0 Q: Estado Inicial.
z0 AP: Simbolo Inicial de la Pila.
F Q: Conjunto de Estados de Aceptacion.

Restricciones Automata de Pila Deterministico

I. Para cada q  Q y z AP , cuando (q, ,Z) es no vacio, entonces (q,a,Z) es vacio para todo a  AE.
II. Para ningun q  Q, z  AP y a  AE  {}, (q,a,Z) contiene mas de un elemento.

Descripcion Instantanea:

(q,,)  Q x AE* x AP*


Automatas


Maquina de Turing

M = (Q, AE, AC, , q0, b, F)

Q: Conjunto de Estados (finito)
AE: Alfabeto de Entrada (AC - b).
AC: Alfabeto de Cinta.
:Q x AC  Q x AC x {L, R, N}: Funcion de un (Estado, Simbolo) a Estado
(En el libro de Hopcroft no aparece N).
q0 Q: Estado Inicial.
b AC: Blanco en la Cinta.
F Q: Conjunto de Estdados de Aceptacion.

Descripcion Instantanea

(,q,)  AC* x Q x AC*
Expresiones Regulares

1.  es una ER.
2.  es una ER.
3.  a  A, a es una ER.
4. Si  y  son ER  | y  son ER.5. Si  es ER  * es ER.
6. Toda ER se obtiene utilizando lo anterior.

Expresion Regular Lenguaje que Genera Observaciones
 L = 
 L = {}
a L = {a}
 L = {}
* L = (Leng())*
+=* L = (Leng())+
| L = (Leng()  Leng())
 L = (Leng() ^ Leng()) Concatenacion
[]=| L = (Leng() {})


Simplificacion de Gramaticas

Eliminacion de Reglas LexicograficasDado G = (VT, VN, P, S) quiero generar G’ = (VT’, VN’, P’, S’) sin reglas lexicograficas.

 VN’ = VN {Z} (Agrego un nuevo No Terminal)
 P’=
N ::= aB si N::=aB en P
N ::=  si N::= en P

N::=aZ si N::=a en P
Z::= 


Eliminacion de Reglas Borradoras

Dado G = (VT, VN, P, S) quiero generar G’ = (VT’, VN’, P’, S’) sin reglas borradoras
(excepto S=)

 VN’ = VN
 P’=
N ::=...