Relación de precedencia de Wirth-Weber

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. ${\displaystyle (V_{t}\cup V_{n})}$

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 . ${\displaystyle \gtrdot }$ ${\displaystyle \lessdot }$ ${\displaystyle \doteq }$

Definición formal

${\displaystyle G=\langle V_{n},V_{t},S,P\rangle }$

${\displaystyle {\begin{aligned}X\doteq Y&\iff {\begin{cases}A\to \alpha XY\beta \in P\\A\in V_{n}\\\alpha ,\beta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\lessdot Y&\iff {\begin{cases}A\to \alpha XB\beta \in P\\B\Rightarrow ^{+}Y\gamma \\A,B\in V_{n}\\\alpha ,\beta ,\gamma \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\gtrdot Y&\iff {\begin{cases}A\to \alpha BY\beta \in P\\B\Rightarrow ^{+}\gamma X\\Y\Rightarrow ^{*}a\delta \\A,B\in V_{n}\\\alpha ,\beta ,\gamma ,\delta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\\a\in V_{t}\end{cases}}\end{aligned}}}$

Algoritmo de cálculo de relaciones de precedencia

Definiremos tres conjuntos para un símbolo:

${\displaystyle {\begin{aligned}\mathrm {Head} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}Y\alpha \}\\\mathrm {Tail} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}\alpha Y\}\\\mathrm {Head} ^{*}(X)&=(\mathrm {Head} ^{+}(X)\cup \{X\})\cap V_{t}\end{aligned}}}$

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 ${\displaystyle A\to \alpha \in P}$
  • Para cada dos símbolos adyacentes XY en α
    • agregar(TablaRelación, ) ${\displaystyle X\doteq Y}$
    • agregar(TablaRelación, ) ${\displaystyle X\lessdot \mathrm {Head} ^{+}(Y)}$
    • agregar(TablaRelación, ) ${\displaystyle \mathrm {Tail} ^{+}(X)\gtrdot \mathrm {Head} ^{*}(Y)}$
• add(RelationTable, ) donde S es el no terminal inicial de la gramática y $ es un marcador de límite ${\displaystyle \$\lessdot \mathrm {Head} ^{+}(S)}$
• add(RelationTable, ) donde S es el no terminal inicial de la gramática y $ es un marcador de límite ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \$}$

${\displaystyle \lessdot }$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. ${\displaystyle \gtrdot }$

Ejemplos

Ejemplo 1

${\displaystyle S\to aSSb|c}$

• 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
• ${\displaystyle S\to aSSb}$
  • a Junto a S
    • ${\displaystyle a\doteq S}$
    • ${\displaystyle a\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle a\lessdot a}$
      • ${\displaystyle a\lessdot c}$
  • S al lado de S
    • ${\displaystyle S\doteq S}$
    • ${\displaystyle S\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle S\lessdot a}$
      • ${\displaystyle S\lessdot c}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(S)}$
      • ${\displaystyle b\gtrdot a}$
      • ${\displaystyle b\gtrdot c}$
      • ${\displaystyle c\gtrdot a}$
      • ${\displaystyle c\gtrdot c}$
  • S Al lado de b
    • ${\displaystyle S\doteq b}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(b)}$
      • ${\displaystyle b\gtrdot b}$
      • ${\displaystyle c\gtrdot b}$
• ${\displaystyle S\to c}$
  • Solo hay un símbolo, por lo que no se agrega ninguna relación.

tabla de precedencia

${\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&\doteq &\lessdot &\doteq &\lessdot &\\a&\doteq &\lessdot &&\lessdot &\\b&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}}$

Ejemplo 2

${\displaystyle S\to a|aT|[S]}$

${\displaystyle T\to b|bT}$

• 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

• ${\displaystyle S\to aT}$

• • a Al lado de T
    • ${\displaystyle a\doteq T}$
    • ${\displaystyle a\lessdot \mathrm {Head} ^{+}(T)}$
      • ${\displaystyle a\lessdot b}$

• ${\displaystyle S\to [S]}$

• • [ Junto a S
    • ${\displaystyle [\doteq S}$
    • ${\displaystyle [\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle [\lessdot a}$
      • ${\displaystyle [\lessdot [}$

• • S Al lado de ]
    • ${\displaystyle S\doteq ]}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(])}$
      • ${\displaystyle a\gtrdot ]}$
      • ${\displaystyle T\gtrdot ]}$
      • ${\displaystyle ]\gtrdot ]}$
      • ${\displaystyle b\gtrdot ]}$

• ${\displaystyle T\to bT}$

• • b Al lado de T
    • ${\displaystyle b\doteq T}$
    • ${\displaystyle b\lessdot \mathrm {Head} ^{+}(T)}$
      • ${\displaystyle b\lessdot b}$

tabla de precedencia

${\displaystyle {\begin{array}{c|ccccccc}&S&T&a&b&[&]&\$\\\hline S&&&&&&\doteq &\doteq \\T&&&&&&\gtrdot &\gtrdot \\a&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\b&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\{\text{[}}&\doteq &&\lessdot &&\lessdot &&\\]&&&&&&\gtrdot &\gtrdot \\\$&\doteq &&\lessdot &&\lessdot &&\end{array}}}$

Lectura adicional

• Aho, Alfred V.; Ullman, Jeffrey D., La teoría del análisis sintáctico, la traducción y la compilación