En informática , es necesaria una relación Wirth-Weber entre un par de símbolos para determinar si una gramática formal es una gramática de precedencia simple . En tal caso, se puede utilizar el analizador sintáctico de precedencia simple . La relación recibe su nombre de los científicos informáticos Niklaus Wirth y Helmut Weber.
El objetivo es identificar cuándo los prefijos viables tienen el pivote y deben reducirse. A significa que se encuentra el pivote , a significa que se está iniciando un pivote potencial y a significa que una relación permanece en el mismo pivote .
Definición formal
Algoritmo de cálculo de relaciones de precedencia
Definiremos tres conjuntos para un símbolo:
- Head * ( X ) es X si X es un terminal, y si X no es un terminal, Head * ( X ) es el conjunto con solo los terminales que pertenecen a Head + ( X ). Este conjunto es equivalente al primer conjunto o Fi( X ) descrito en el analizador LL .
- Cabeza + ( X ) y Cola + ( X ) son ∅ si X es un terminal.
El pseudocódigo para calcular relaciones es:
- Tabla de relaciones := ∅
- Para cada producción
- Para cada dos símbolos adyacentes XY en α
- agregar(TablaRelación, )
- agregar(TablaRelación, )
- agregar(TablaRelación, )
- add(RelationTable, ) donde S es el no terminal inicial de la gramática y $ es un marcador de límite
- add(RelationTable, ) donde S es el no terminal inicial de la gramática y $ es un marcador de límite
- y se utilizan con conjuntos en lugar de elementos como fueron definidos, en este caso se debe sumar todo el producto cartesiano entre los conjuntos/elementos.
Ejemplos
Ejemplo 1
- Cabeza + ( a ) = ∅
- Cabeza + ( S ) = { a, c }
- Cabeza + ( b ) = ∅
- Cabeza + ( c ) = ∅
- Cola + ( a ) = ∅
- Cola + ( S ) = { b, c }
- Cola + ( b ) = ∅
- Cola + ( c ) = ∅
- Cabeza * ( a ) = a
- Cabeza * ( S ) = { a, c }
- Cabeza * ( b ) = b
- Cabeza * ( c ) = c
- a Junto a S
- S al lado de S
- S Al lado de b
- Solo hay un símbolo, por lo que no se agrega ninguna relación.
- tabla de precedencia
Ejemplo 2
- Cabeza + ( S ) = { a, [ }
- Cabeza + ( a ) = ∅
- Cabeza + ( T ) = { b }
- Cabeza + ( [ ) = ∅
- Cabeza + ( ] ) = ∅
- Cabeza + ( b ) = ∅
- Cola + ( S ) = { a, T, ], b }
- Cola + ( a ) = ∅
- Cola + ( T ) = { b, T }
- Cola + ( [ ) = ∅
- Cola + ( ] ) = ∅
- Cola + ( b ) = ∅
- Cabeza * ( S ) = { a, [ }
- Cabeza * ( a ) = a
- Cabeza * ( T ) = { b }
- Cabeza * ( [ ) = [
- Cabeza * ( ] ) = ]
- Cabeza * ( b ) = b
- a Al lado de T
- [ Junto a S
- S Al lado de ]
- b Al lado de T
- tabla de precedencia
Lectura adicional
- Aho, Alfred V.; Ullman, Jeffrey D., La teoría del análisis sintáctico, la traducción y la compilación