Gramática de precedencia de operadores

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

Técnicamente, una gramática de precedencia de operador 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 que explota estas relaciones es considerablemente más simple que los analizadores más de propósito 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 del operador se basan en las siguientes tres relaciones de precedencia entre los terminales: ^[2]

Relación	Significado
${\displaystyle a\lessdot b}$	a cede precedencia a b
${\displaystyle a\doteq b}$	a tiene la misma precedencia que b
${\displaystyle a\gtrdot b}$	a tiene prioridad sobre b

Estas relaciones de precedencia de operadores permiten delimitar los tiradores en las formas oracionales derechas : marca el extremo izquierdo, aparece en el interior del tirador y marca el extremo derecho. A diferencia de otros analizadores sintácticos de reducción de cambios, todos los no terminales se consideran iguales a los efectos de identificar los identificadores. ^[3] Las relaciones no tienen las mismas propiedades que sus contrapartes sin puntos; mi. gramo. generalmente no implica y no se sigue de . Además, generalmente no se sostiene 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 las terminales a _i y a _{i +1} siempre hay exactamente una relación de precedencia. Suponga que $ es el final de la cadena. Entonces, para todas las terminales b definimos: y . Si eliminamos todos los no terminales y coloque la relación de precedencia correcta: , , entre los terminales restantes, aún existen cadenas que pueden ser analizados por una facilidad desarrollado analizador de abajo hacia arriba .${\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 * (de ahí y ).${\displaystyle +\lessdot *}$${\displaystyle *\gtrdot +}$
• Tanto + como * son asociativos a 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 operador

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

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

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

Algoritmo de análisis de precedencia de operador ^[6]

Inicializar: Configure ip para que apunte al primer símbolo de w $Repetir: Si $ está en la parte superior de la pila e ip apunta a $ entonces regresa demás Sea a la terminal superior de la pila yb el símbolo al que apunta ip si a bo a b entonces${\displaystyle \lessdot }$${\displaystyle \doteq }$ empuja b sobre la pila avanzar ip al siguiente símbolo de entrada si no a b entonces${\displaystyle \gtrdot }$ repetir hacer estallar la pila hasta que la terminal de la pila superior esté relacionada con la terminal que apareció más recientemente${\displaystyle \lessdot }$ más error () final

Funciones de precedencia

Un analizador de precedencia de operador no suele almacenar la tabla de precedencia con las relaciones, que pueden ser bastante grandes. En cambio, 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: debe cumplirse si se mantiene, etc.${\displaystyle f(a)<g(b)}$${\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, estas funciones pueden diseñarse. ^[8]

Algoritmo para construir funciones de precedencia ^[9]

1. Cree los símbolos f _a y g _a para cada terminal gramatical a y para el símbolo del final de la cadena;
2. Divida 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 gráfico dirigido cuyos nodos son los grupos. Para cada par de terminales: coloque una arista del grupo de g _b al grupo de f _a si , de lo contrario , coloque una arista del grupo de f _a al de g _b ;${\displaystyle (a,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 ​​la longitud del camino más largo del grupo de f _a y sea ​​la longitud del camino más largo del grupo de g _a .${\displaystyle f(a)}$${\displaystyle 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:

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

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

	identificación	+	*	PS
F	4	2	4	0
gramo	5	1	3	0

Idiomas de precedencia del operador

La clase de lenguajes descritos por gramáticas con precedencia de operadores, es decir, lenguajes con precedencia de operadores, está estrictamente contenida en la clase de lenguajes deterministas libres de contexto y contiene estrictamente lenguajes de inserción visible . ^[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 las que el problema de la vacuidad es decidible. Otra característica peculiar de los lenguajes con precedencia de operadores es su capacidad de análisis 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. 203.
2. Aho, Sethi y Ullman 1988, págs. 203-204.
3. Aho, Sethi y Ullman 1988, págs. 205-206.
4. Aho, Sethi & Ullman 1988, p. 205.
5. Aho, Sethi y Ullman 1988, p. 204.
6. Aho, Sethi y Ullman 1988, p. 206.
7. Aho, Sethi y Ullman 1988, págs. 208-209.
8. Aho, Sethi y Ullman 1988, p. 209.
9. Aho, Sethi y Ullman 1988, págs. 209-210.
10. Aho, Sethi y Ullman 1988, p. 210.
11. Crespi Reghizzi y Mandrioli 2012
12. Crespi Reghizzi, Mandrioli y Martin 1978
13. Barenghi y col. 2015
14. Lonati y col. 2015

Referencias

• Aho, Alfred V., Sethi, Ravi y Ullman, Jeffrey D. (1988). Compiladores: principios, técnicas y herramientas. Addison-Wesley.
• 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 .
• Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Precedencia del operador y la propiedad visiblemente pushdown" . 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 del operador" . 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). "Análisis en paralelo hecho práctico" . Ciencia de la Programación de Computadores . 112 (3): 245–249. doi : 10.1016 / j.scico.2015.09.002 .
• Lonati, Violetta; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Lenguajes de precedencia del operador: su caracterización lógica y teórico-autómata". Revista SIAM de Computación . 44 (4): 1026–1088. doi : 10.1137 / 140978818 . hdl : 2434/352809 .

Enlaces externos

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