Gramática de precedencia de operadores

Una gramática de precedencia de operadores es un tipo de gramática para lenguajes formales .

Técnicamente, una gramática de precedencia de operadores es una gramática libre de contexto que tiene la propiedad (entre otras) ^[1] de que ninguna producción tiene un lado derecho vacío o dos no terminales adyacentes en su lado derecho. Estas propiedades permiten definir relaciones de precedencia entre los terminales de la gramática. Un analizador sintáctico que explota estas relaciones es considerablemente más simple que los analizadores sintácticos de propósito general, como los analizadores sintácticos LALR . Se pueden construir analizadores sintácticos de precedencia de operadores para una gran clase de gramáticas libres de contexto.

Relaciones de precedencia

Las gramáticas de precedencia de operadores se basan en las siguientes tres relaciones de precedencia entre los terminales: ^[2]

Estas relaciones de precedencia de operadores permiten delimitar los manejadores en las formas oracionales correctas : marca el extremo izquierdo, aparece en el interior del manejador y marca el extremo derecho. A diferencia de otros analizadores sintácticos de desplazamiento-reducción, todos los no terminales se consideran iguales para el propósito de identificar manejadores. ^[3] Las relaciones no tienen las mismas propiedades que sus contrapartes sin punto; p. ej., no implica generalmente y no se sigue de . Además, no se cumple generalmente y es posible. ${\displaystyle \lessdot }$ ${\displaystyle \doteq }$ ${\displaystyle \gtrdot }$ ${\displaystyle a\doteq b}$ ${\displaystyle b\doteq a}$ ${\displaystyle b\gtrdot a}$ ${\displaystyle a\lessdot b}$ ${\displaystyle a\doteq a}$ ${\displaystyle a\gtrdot a}$

Supongamos que entre los terminales a _i y a _{i +1} siempre hay exactamente una relación de precedencia. Supongamos que $ es el final de la cadena. Entonces, para todos los terminales b definimos: y . Si eliminamos todos los no terminales y colocamos la relación de precedencia correcta: , , entre los terminales restantes, quedan cadenas que pueden analizarse mediante un analizador sintáctico de abajo a arriba fácilmente desarrollado . ${\displaystyle \$\lessdot b}$ ${\displaystyle b\gtrdot \$}$ ${\displaystyle \lessdot }$ ${\displaystyle \doteq }$ ${\displaystyle \gtrdot }$

Ejemplo

Por ejemplo, se pueden introducir las siguientes relaciones de precedencia de operadores para expresiones simples: ^[4]

${\displaystyle {\begin{array}{c|cccc}&\mathrm {id} &+&*&\$\\\hline \mathrm {id} &&\gtrdot &\gtrdot &\gtrdot \\+&\lessdot &\gtrdot &\lessdot &\gtrdot \\*&\lessdot &\gtrdot &\gtrdot &\gtrdot \\\$&\lessdot &\lessdot &\lessdot &\end{array}}}$

Se desprenden de los siguientes hechos: ^[5]

• + tiene menor precedencia que * (por lo tanto y ). ${\displaystyle +\lessdot *}$ ${\displaystyle *\gtrdot +}$
• Tanto + como * son asociativos por la izquierda (por lo tanto y ). ${\displaystyle +\gtrdot +}$ ${\displaystyle *\gtrdot *}$

La cadena de entrada ^[4]

${\displaystyle \mathrm {id} _{1}+\mathrm {id} _{2}*\mathrm {id} _{3}}$

después de agregar marcadores finales e insertar relaciones de precedencia se convierte en

${\displaystyle \$\lessdot \mathrm {id} _{1}\gtrdot +\lessdot \mathrm {id} _{2}\gtrdot *\lessdot \mathrm {id} _{3}\gtrdot \$}$

Análisis de precedencia de operadores

Tener relaciones de precedencia permite identificar identificadores de la siguiente manera: ^[4]

• escanear la cadena desde la izquierda hasta ver ${\displaystyle \gtrdot }$
• Escanee hacia atrás (de derecha a izquierda) sobre cualquiera hasta ver ${\displaystyle \doteq }$ ${\displaystyle \lessdot }$
• Todo lo que se encuentra entre las dos relaciones y , incluidos los no terminales intermedios o circundantes, forma el identificador ${\displaystyle \lessdot }$ ${\displaystyle \gtrdot }$

Generalmente no es necesario escanear toda la oración para encontrar el identificador.

Algoritmo de análisis de precedencia de operadores

El algoritmo que aparece a continuación es de Aho et al.: ^[6]

Si $ está en la parte superior de la pila e ip apunta a $, entonces devuelve else Sea a la terminal superior de la pila y b el símbolo al que apunta ip. Si es  a  b o a b entonces empuja b a la pila ${\displaystyle \lessdot }$     ${\displaystyle \doteq }$   Avanzar ip al siguiente símbolo de entrada De lo contrario, si es  a  , entonces repita ${\displaystyle \gtrdot }$    revienta la pila hasta que la terminal de la pila superior esté relacionada con la terminal que apareció más recientemente, de lo contrario, error() fin ${\displaystyle \lessdot }$

Funciones de precedencia

Un analizador de precedencia de operadores normalmente no almacena la tabla de precedencia con las relaciones, que pueden llegar a ser bastante grandes. En su lugar, se definen las funciones de precedencia f y g . ^[7] Asignan símbolos terminales a números enteros, por lo que las relaciones de precedencia entre los símbolos se implementan mediante comparación numérica: ⁠ ⁠ ${\displaystyle f(a)<g(b)}$ debe cumplirse si se cumple, etc. ${\displaystyle a\lessdot b}$

No todas las tablas de relaciones de precedencia tienen funciones de precedencia, pero en la práctica para la mayoría de las gramáticas se pueden diseñar dichas funciones. ^[8]

Algoritmo para construir funciones de precedencia

El siguiente algoritmo es de Aho et al.: ^[9]

1. Cree los símbolos f _a y g _a para cada terminal gramatical a y para el símbolo de final de cadena;
2. Particionar los símbolos creados en grupos de modo que f _a y g _b estén en el mismo grupo si (puede haber símbolos en el mismo grupo incluso si sus terminales no están conectados por esta relación); ${\displaystyle a\doteq b}$
3. Crea un grafo dirigido cuyos nodos sean los grupos. Para cada par de terminales ${\displaystyle (a,b)}$ haz lo siguiente: coloca una arista del grupo de g _b al grupo de f _a si , en caso contrario si coloca una arista del grupo de f _a al de g _b ; ${\displaystyle a\lessdot b}$ ${\displaystyle a\gtrdot b}$
4. Si el grafo construido tiene un ciclo entonces no existen funciones de precedencia. Cuando no hay ciclos, sea ⁠ ⁠ ${\displaystyle f(a)}$ la longitud del camino más largo desde el grupo de f _a y sea ⁠ ⁠ ${\displaystyle g(a)}$ la longitud del camino más largo desde el grupo de g _a .

Ejemplo

Considere la siguiente tabla (repetida de la anterior): ^[10]

${\displaystyle {\begin{array}{c|cccc}&\mathrm {id} &+&*&\$\\\hline \mathrm {id} &&\gtrdot &\gtrdot &\gtrdot \\+&\lessdot &\gtrdot &\lessdot &\gtrdot \\*&\lessdot &\gtrdot &\gtrdot &\gtrdot \\\$&\lessdot &\lessdot &\lessdot &\end{array}}}$

El uso del algoritmo conduce al siguiente gráfico:

 Gíralo \ joder \ / gramo* / F+  | \ | g+ | | $g$f$

de donde extraemos las siguientes funciones de precedencia de las alturas máximas en el grafo acíclico dirigido :

Lenguajes con precedencia de operadores

La clase de lenguajes descritos por gramáticas de precedencia de operadores, es decir, lenguajes de precedencia de operadores, está estrictamente contenida en la clase de lenguajes deterministas libres de contexto , y contiene estrictamente lenguajes visiblemente pushdown . ^[11]

Los lenguajes de precedencia de operadores disfrutan de muchas propiedades de cierre: unión, intersección, complementación, ^[12] concatenación, ^[11] y son la clase más grande conocida cerrada bajo todas estas operaciones y para la cual el problema del vacío es decidible. Otra característica peculiar de los lenguajes de precedencia de operadores es su capacidad de análisis local, ^[13] que permite un análisis paralelo eficiente.

También existen caracterizaciones basadas en una forma equivalente de autómatas y lógica monádica de segundo orden. ^[14]

Notas

1. Aho, Sethi y Ullman 1988, pág. 203
2. Aho, Sethi y Ullman 1988, págs. 203-204
3. Aho, Sethi y Ullman 1988, págs. 205-206
4. Aho, Sethi y Ullman 1988, pág. 205
5. Aho, Sethi y Ullman 1988, pág. 204
6. Aho, Sethi y Ullman 1988, pág. 206
7. Aho, Sethi y Ullman 1988, págs. 208-209
8. Aho, Sethi y Ullman 1988, pág. 209
9. Aho, Sethi y Ullman 1988, págs. 209-210
10. Aho, Sethi y Ullman 1988, pág. 210
11. Crespi Reghizzi y Mandrioli 2012
12. Crespi Reghizzi, Mandrioli y Martín 1978
13. Barenghi y otros, 2015
14. Lonati y otros, 2015

Referencias

• Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compiladores: principios, técnicas y herramientas . Addison-Wesley.
• Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Precedencia de operadores y la propiedad de empuje visible". Revista de Ciencias de la Computación y Sistemas . 78 (6): 1837–1867. doi : 10.1016/j.jcss.2011.12.006 .
• Crespi Reghizzi, Stefano; Mandrioli, Dino; Martin, David F. (1978). "Propiedades algebraicas de los lenguajes de precedencia de operadores". Información y control . 37 (2): 115–133. doi : 10.1016/S0019-9958(78)90474-6 .
• Barenghi, Alessandro; Crespi Reghizzi, Stefano; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "El análisis paralelo se hace práctico". Ciencia de la programación informática . 112 (3): 245–249. doi : 10.1016/j.scico.2015.09.002 . hdl : 11311/971391 .
• Lonati, Violetta; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Lenguajes de precedencia de operadores: su caracterización lógica y teórica de autómatas". Revista SIAM de Computación . 44 (4): 1026–1088. doi :10.1137/140978818. hdl : 2434/352809 .

Lectura adicional

• Floyd, RW (julio de 1963). "Análisis sintáctico y precedencia de operadores". Revista de la ACM . 10 (3): 316–333. doi : 10.1145/321172.321179 . S2CID  19785090.

Enlaces externos

• Nikolay Nikolaev: IS53011A Diseño e implementación del lenguaje, notas del curso CIS 324, 2010.