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 posee 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 aprovecha estas relaciones es considerablemente más simple que los analizadores sintácticos de propósito general, como los analizadores LALR . Se pueden construir analizadores sintácticos de precedencia de operadores para una amplia clase de gramáticas libres de contexto.

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 sentenciales correctas :${\displaystyle \lessdot }$marca el extremo izquierdo,${\displaystyle \doteq }$aparece en el interior del mango, y${\displaystyle \gtrdot }$marca el extremo derecho. A diferencia de otros analizadores sintácticos de desplazamiento-reducción, todos los no terminales se consideran iguales a efectos de identificar manejadores. ^{[ 3 ]} Las relaciones no tienen las mismas propiedades que sus contrapartes sin puntos; p.  ej.${\displaystyle a\doteq b}$generalmente no implica${\displaystyle b\doteq a}$, y${\displaystyle b\gtrdot a}$no se deduce de${\displaystyle a\lessdot b}$. Además,${\displaystyle a\doteq a}$Generalmente no se cumple, y${\displaystyle a\gtrdot a}$es posible.

Supongamos que entre los terminales a _i y a _{i +1} siempre existe exactamente una relación de precedencia. Supongamos que $ es el final de la cadena. Entonces, para todos los terminales b definimos: ${\displaystyle \$\lessdot b}$y${\displaystyle b\gtrdot \$}$. Si eliminamos todos los no terminales y colocamos la relación de precedencia correcta: ${\displaystyle \lessdot }$,${\displaystyle \doteq }$,${\displaystyle \gtrdot }$Entre los terminales restantes, quedan cadenas que pueden ser analizadas por un analizador sintáctico ascendente de fácil desarrollo .

Tener relaciones de precedencia permite identificar los manejadores de la siguiente manera: ^{[ 4 ]}

• escanee la cadena de izquierda a derecha hasta que vea${\displaystyle \gtrdot }$
• escanee hacia atrás (de derecha a izquierda) sobre cualquier${\displaystyle \doteq }$hasta ver${\displaystyle \lessdot }$
• todo lo que hay entre las dos relaciones${\displaystyle \lessdot }$y${\displaystyle \gtrdot }$, incluyendo cualquier no terminal intermedio o circundante, forma el asa

Por lo general, no es necesario analizar toda la oración para encontrar el identificador.

El siguiente algoritmo es de Aho et al.: ^{[ 6 ]}

Si $ está en la parte superior de la pila y ip apunta a $, entonces regresa; de lo contrario Sea a el terminal superior de la pila y b el símbolo al que apunta ip. si un${\displaystyle \lessdot }$b o a${\displaystyle \doteq }$b luego agrega b a la pila avanzar ip al siguiente símbolo de entrada de lo contrario si un${\displaystyle \gtrdot }$b) luego repita explota la pila hasta que el terminal de pila superior esté relacionado por${\displaystyle \lessdot }$al terminal más recientemente abierto de lo contrario error() fin

Un analizador de precedencia de operadores normalmente no almacena la tabla de precedencia con las relaciones, que puede llegar a ser bastante grande. En su lugar, se definen las funciones de precedencia f y g . ^{[ 7 ]} Estas asignan símbolos terminales a 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 mantenerse si${\displaystyle a\lessdot b}$reservas, etc.

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, dichas funciones pueden diseñarse. ^{[ 8 ]}

 gur \ fid f* \ / gramo* / f+ | \ | g+ | | g$ f$

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 de pila . ^{[ 11 ]}

Los lenguajes de precedencia de operadores poseen 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 de vacuidad es decidible. Otra característica peculiar de los lenguajes de precedencia de operadores es su analizabilidad 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 ]}

• Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compiladores: principios, técnicas y herramientas . Addison-Wesley.
• Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Precedencia del operador y la propiedad de empuje visible" . Journal of Computer and System Sciences . 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" . Information and 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 .

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

• Nikolay Nikolaev: IS53011A Diseño e implementación de lenguajes Archivado el 2 de febrero de 2014 en Wayback Machine , notas del curso CIS  324, 2010.