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 las terminales de la gramática. Un analizador que explota estas relaciones es considerablemente más simple que los analizadores de propósito más general, como los analizadores LALR . Se pueden construir analizadores 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 identificadores en las formas oracionales derechas : marca el extremo izquierdo, aparece en el interior del identificador y marca el extremo derecho. A diferencia de otros analizadores de reducción de desplazamiento, todos los no terminales se consideran iguales a los efectos de identificar identificadores. ^[3] Las relaciones no tienen las mismas propiedades que sus contrapartes sin puntos; mi. gramo. generalmente no implica ni se deriva de . Además, generalmente no se cumple 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. Luego 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 ser analizadas por un analizador ascendente 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 derivan 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 vuelve

${\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]

• escanea la cadena desde la izquierda hasta ver ${\displaystyle \gtrdot }$
• escanear 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 , incluido cualquier no terminal intermedio o circundante, 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 siguiente algoritmo es de Aho et al.: ^[6]

Si $ está en la parte superior de la pila y ip apunta a $, entonces regrese en caso contrario Sea a el terminal superior de la pila y b el símbolo al que apunta ip si  a  b o a b entonces empuja b hacia la pila ${\displaystyle \lessdot }$     ${\displaystyle \doteq }$   avanzar ip al siguiente símbolo de entrada de lo contrario si  a  b entonces repite ${\displaystyle \gtrdot }$    pop la pila hasta que el terminal de la pila superior esté relacionado con el terminal emergente más recientemente else error() end ${\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 cambio, se definen las funciones de precedencia f y g . ^[7] Mapean 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 símbolos f _a y g _a para cada terminal gramatical a y para el símbolo de final de cadena;
2. Dividir 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 son los grupos. Para cada par ⁠ ⁠ ${\displaystyle (a,b)}$ de terminales haga: coloque una arista del grupo de g _b al grupo de f _a if , en caso contrario si coloque una arista del grupo de f _a al de g _b ; ${\displaystyle a\lessdot b}$ ${\displaystyle a\gtrdot b}$
4. Si el gráfico 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 del grupo de f _a y sea ⁠ ⁠ ${\displaystyle g(a)}$ la longitud del camino más largo del grupo de g _a .

Ejemplo

Considere la siguiente tabla (repetida desde arriba): ^[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:

 gimiendo \ fid carajo* \ / gramo* / f+  | \ | g+ | | g$f$

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

Idiomas de prioridad del operador

La clase de lenguajes descritos por las 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 cerrada más grande conocida bajo todas estas operaciones y para la cual el problema de vacío 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 hay 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 col. 2015
14. Lonati y col. 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 del operador y propiedad visiblemente pushdown". Revista de Ciencias de la Computación y de Sistemas . 78 (6): 1837–1867. doi : 10.1016/j.jcss.2011.12.006 .
• Crespi Reghizzi, Stefano; Mandrioli, Dino; Martín, 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 .

Otras lecturas

• 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: Diseño e implementación del lenguaje IS53011A, notas del curso para CIS 324, 2010.