Gramática de precedencia del operador

Una gramática de precedencia del operador es una especie de gramática para lenguas formales.

Técnicamente, una gramática de precedencia del operador es una gramática sin contextos que tiene la propiedad (entre otros)

que ninguna producción tenga un lado derecho vacío o dos no terminales contiguos en su

lado derecho. Estas propiedades permiten que relaciones de precedencia sean

definido entre los terminales de la gramática. Un analizador sintáctico que explota estas relaciones es bastante más simple que más analizadores sintácticos de uso general como analizadores sintácticos de LALR. Los analizadores sintácticos de precedencia del operador se pueden construir para una clase grande de gramáticas sin contextos.

Relaciones de precedencia

Las gramáticas de precedencia del operador confían en las tres relaciones de precedencia siguientes

entre los terminales:

Estas relaciones de precedencia del operador permiten delimitar los mangos

en el derecho sentential formas:

analizadores sintácticos, todos los no terminales se consideran iguales para la identificación

mangos.

Las relaciones no tienen las mismas propiedades que sus equivalentes no punteados;

e. g. un = • el b no implica generalmente b = • a, y b •> no siguen

de a

Vamos a

suponer que entre los terminales a y un hay

siempre exactamente una relación de precedencia. Suponga que el $ es el final de la cuerda.

Entonces para todos los terminales b definimos: $

quite todos los no terminales y coloque la relación de precedencia correcta:

esto puede ser analizado por un analizador sintáctico del fondo fácilmente desarrollado.

Ejemplo

Por ejemplo, las relaciones de precedencia del operador siguientes pueden

preséntese para expresiones simples:

Siguen de los hechos siguientes:

La cuerda de la entrada

: id + id * id

después de añadir marcadores del final e insertar relaciones de precedencia se hace

: $ •> + •> * •> $\

Análisis sintáctico de precedencia del operador

Tener relaciones de precedencia permite identificar mangos así:

No es

generalmente necesario explorar la forma de sentential entera para encontrar el mango.

Algoritmo de análisis sintáctico de precedencia del operador

Inicialice: Juego ip para señalar al primer símbolo de w$\

Repetición:

Si el $ está en la cumbre de la pila e ip señala al $ entonces devuelven

más

Deje un ser el terminal superior en la pila y b al cual el símbolo señaló por ip

si a

repita

haga reventar la pila

hasta que el terminal de la pila superior sea relacionado por

Trazan un mapa de símbolos terminales a números enteros, y por tanto las relaciones de precedencia

entre los símbolos son puestos en práctica por la comparación numérica:

f (a)

Algoritmo para construir funciones de precedencia

  1. Cree símbolos f y g para cada terminal a de la gramática y para el final del símbolo de la cuerda;
  2. Divida los símbolos creados en grupos de modo que f y g estén en el mismo grupo si un = • b (pueden haber símbolos en el mismo grupo aun si sus terminales no son relacionados por esta relación);
  3. Cree un gráfico dirigido cuyos nodos son los grupos, después para cada par (a, b) de terminales haga: coloque un borde del grupo de g al grupo de f si a
  1. Si el gráfico construido tiene un ciclo entonces ningunas funciones de precedencia existen. Cuando no haya ningunos ciclos, deje a f (a) ser la longitud del camino más largo del grupo de f y dejar a g (a) ser la longitud del camino más largo del grupo de g.

Ejemplo

Considere la mesa siguiente (repetida desde encima):

La utilización del algoritmo lleva al gráfico siguiente:

gid

\

fid f *

\/

g *

/

f +

| \

| g+

| |

g$ f$\

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

Notas

Enlaces externos



Buscar