Compiladores
-
Upload
george007777 -
Category
Documents
-
view
215 -
download
0
description
Transcript of Compiladores
GRAMATICAS DEL OPERADOR
Las gramáticas de operador describen lenguajes de propósito especial, o subconjuntos de lenguajes de programación típicos. Por ejemplo, las expresiones pueden describirse utilizando gramáticas de operador (así podemos continuar empleando el mismo ejemplo).
Definición de una gramática de operador
1) No tiene reglas Є, es decir, no hay reglas de la forma A -> Є2) No tiene no terminales adyacentes, es decir, no hay reglas de la forma A ->…XY…
GRAMATICAS DEL OPERADOR
EJEMPLO
E -> EAE | IdA -> + | -
Esta gramática no es una gramática de operador, puesto que la primera producción, tiene tres no terminales adyacentes.
Esta gramática puede reescribirse como:
E -> E + E | E – E | Id ; la cual es una gramática de procedencia de operador, aunque también es ambigua.
5.3.1 Análisis sintáctico de procedencia de operador
Las relaciones de precedencia pueden establecerse entre los operadores en una gramática de operador. En la precedencia de operadores, la cadena de caracteres se rastrea de izquierda a derecha como es usual y hay esencialmente dos estados:
Estado 1: ‘en espera de un operador’o
Estado 2: ‘en espera de un operando’
GRAMATICAS DEL OPERADOR
EJEMPLO Análisis sintáctico de precedencia simple
Considérese la cadena:
a + b * c $
Y la gramática
1. E -> E + E 2. E -> E * E3. E -> (E)4. E -> Id
5.3.2 Análisis sintáctico de precedencia de operador controlado por tabla Relaciones de precedenciaFormalizamos las relaciones de precedencia mediante la introducción de tres relaciones de precedencia disjuntas:
Donde α < • b significa que α tiene menor precedencia que b, α = b significa que α tiene la misma precedencia que b, y α • > b significa que α tiene mayor precedencia que b. De este modo, para expresiones, + <• •, (=), y • •> +.
GRAMATICAS DEL OPERADOR
GRAMATICAS DEL OPERADOR
EJEMPLO
Análisis sintáctico de precedencia de operador Considérese la gramática:E -> E + EE -> E * EE -> (E)E -> a
Y la cadena de entrada:(a + a)Es usual rodear la entrada con el signo $, y $ tiene la
precedencia más baja, es decir,$<•+, etcétera.
Como es común, la tabla se construirá por arte de magia para nosotros (y luego discutiremos como construir una)Tabla:
5.3.3 Construcción de la tabla
GRAMATICAS DEL OPERADOR
El método presentado aquí explota el hecho siguiente:
Lo operadores inferiores en el árbol de análisis sintáctico tienen precedencia mas alta.
Se alienta al lector para que estudie el siguiente árbol de análisis sintáctico y construya algunos propios, empleando la gramática de expresión para llegar convencerse de esto.
Definición 1: Inicial (N), donde N es un no terminal, es el conjunto de todos los terminales que pueden aparecer primero en una forma sentencial derivable de N.
Definición 2: Salida (N), donde N es un no terminal, es el conjunto de todos los terminales que pueden aparecer al final en una forma sentencial derivable de N.
EJEMPLO
GRAMATICAS DEL OPERADOR
Cálculo de los conjuntos inicial y de salida para la gramática de expresiones:
Considérese, una vez más, la gramática de expresiones:
1. E -> E + T2. E -> T3. T -> T * F4. T -> F5. F -> (E)6. F -> Id
Entonces, Inicial (E) = {+,*, (, Id}
+ está en inicial (E) porque E + T es una forma sentencial derivable (directamente) de E.
* está en inicial (E) porque T * F es una forma sentencial derivable de E (E -> T -> T * F), y * es el primer (y único) terminal.
( Esta en inicial (E) porque (E) es una forma sentencial derivable de E (E ->T ->F -> (E)), y ( es el primer terminal.