Relación de precedencia Wirth-Weber

En la informática, una Wirth-Weber relationship entre un par de símbolos ()Vt∪ ∪ Vn){displaystyle (V_{t}cup V_{n}} es necesario determinar si una gramática formal es una simple gramática de precedencia. En tal caso, se puede utilizar el parser de precedencia simple. La relación es nombrada por los científicos informáticos Niklaus Wirth y Helmut Weber.

El objetivo es identificar cuando los prefijos viables tienen pivote y debe ser reducido. A ⋗ ⋗ {displaystyle gtrdot } significa que pivote se encuentra, un ⋖ ⋖ {displaystyle lessdot} significa que un potencial pivote está empezando, y un ≐ ≐ {displaystyle doteq } significa que una relación permanece en la misma pivote.

Definición formal

G=. . Vn,Vt,S,P. . {displaystyle G=langle V_{n},V_{t},S,Prangle

X≐ ≐ Y⟺ ⟺ {}A→ → α α XYβ β ▪ ▪ PA▪ ▪ Vnα α ,β β ▪ ▪ ()Vn∪ ∪ Vt)Alternativa Alternativa X,Y▪ ▪ ()Vn∪ ∪ Vt)X⋖ ⋖ Y⟺ ⟺ {}A→ → α α XBβ β ▪ ▪ PB⇒ ⇒ +Yγ γ A,B▪ ▪ Vnα α ,β β ,γ γ ▪ ▪ ()Vn∪ ∪ Vt)Alternativa Alternativa X,Y▪ ▪ ()Vn∪ ∪ Vt)X⋗ ⋗ Y⟺ ⟺ {}A→ → α α BYβ β ▪ ▪ PB⇒ ⇒ +γ γ XY⇒ ⇒ Alternativa Alternativa aδ δ A,B▪ ▪ Vnα α ,β β ,γ γ ,δ δ ▪ ▪ ()Vn∪ ∪ Vt)Alternativa Alternativa X,Y▪ ▪ ()Vn∪ ∪ Vt)a▪ ▪ Vt{displaystyle {begin{aligned} Xdoteq Y iff {begin{cases} Ato alpha XYbeta in PAin V_{n}\alphabeta in (V_{n}cup V_{t}}X,Yin (V_{n}cup V_{t})end{cases}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ Xlessdot Y pacienteiff {begin{cases} Ato alpha XBbeta in PBRightarrow ^{+}Ygamma \A,Bin ¿Qué? Xgtrdot Y pacienteiff {begin{cases}Ato alpha BYbeta in PBRightarrow ^{+}gamma XYRightarrow ^{*}adelta \A,Bin V_{n}\\\alphabetagammadelta in (V_{n}cup V_{t}x,Yin (V_{n}cup V_{t})ain ¿Qué?

Precedencia relaciones algoritmo de computación

Definiremos tres conjuntos para un símbolo:

Head+()X)={}Y▪ ▪ X⇒ ⇒ +Yα α }Tail+()X)={}Y▪ ▪ X⇒ ⇒ +α α Y}HeadAlternativa Alternativa ()X)=()Head+()X)∪ ∪ {}X})∩ ∩ Vt{displaystyle {begin{aligned}mathrm {Head} ^{+}(X) Alguien={Ymid XRightarrow ^{+}Yalpha }\mathrm {Tail} ^{+}(X) Alguien={Ymid XRightarrow ^{+}alpha Y\\\mathrm {cH00} {cH00} {cH00}cH00} {cH00}cup {X})cap V_{t}end{aligned}}}

Head^*()X) es X si X es un terminal, y si X es un no-terminal, Head^*()X) es el conjunto con sólo los terminales pertenecientes a Head⁺()X). Este conjunto es equivalente a Primera etapa o Fi(X) descrito en el analizador LL.

Head⁺()X) y Tail⁺()X) son ∅ si X es un terminal.

El pseudocódigo para calcular las relaciones es:

• RelaciónTabla:= ∅
• Para cada producción A→ → α α ▪ ▪ P{displaystyle Ato alpha in P}
  • Para cada dos símbolos adyacentes X Y dentro α
    • add(RelationTable, X≐ ≐ Y{displaystyle X 'doteq Y')
    • add(RelationTable, X⋖ ⋖ Head+()Y){displaystyle Xlessdot mathrm {Head} {+}(Y)})
    • add(RelationTable, Tail+()X)⋗ ⋗ HeadAlternativa Alternativa ()Y){displaystyle mathrm {Tail} ^{+}(X)gtrdot mathrm {Head} ^{*}(Y)})
• add(RelationTable, $ $ ⋖ ⋖ Head+()S){displaystyle $lessdot mathrm {Head} ^{+}(S)}Donde S es el no terminal inicial de la gramática, y $ es un marcador límite
• add(RelationTable, Tail+()S)⋗ ⋗ $ $ {displaystyle mathrm {Tail} ^{+}(S)gtrdot $}Donde S es el no terminal inicial de la gramática, y $ es un marcador límite

⋖ ⋖ {displaystyle lessdot} y ⋗ ⋗ {displaystyle gtrdot } se utilizan con conjuntos en lugar de elementos según se definieron, en este caso debe añadir todo el producto cartesiano entre los conjuntos/elementos.

Ejemplos

S→ → aSSbSilencioc{displaystyle Sto aSSb

• Head⁺()a) = ∅
• Head⁺()S♪♪a, c}
• Head⁺()b) = ∅
• Head⁺()c) = ∅
• Tail⁺()a) = ∅
• Tail⁺()S♪♪b, c}
• Tail⁺()b) = ∅
• Tail⁺()c) = ∅
• Head^*()a) a
• Head^*()S♪♪a, c}
• Head^*()b) b
• Head^*()c) c
• S→ → aSSb{displaystyle Sto aSSb}
  • a Siguiente S
    • a≐ ≐ S{displaystyle adoteq S}
    • a⋖ ⋖ Head+()S){displaystyle alessdot mathrm {Head} {}(S)}
      • a⋖ ⋖ a{displaystyle alessdot a}
      • a⋖ ⋖ c{displaystyle alessdot c}
  • S Siguiente S
    • S≐ ≐ S{displaystyle Sdoteq S}
    • S⋖ ⋖ Head+()S){displaystyle Slessdot mathrm {Head} {+}(S)}
      • S⋖ ⋖ a{displaystyle Slessdot a
      • S⋖ ⋖ c{displaystyle Slessdot c}
    • Tail+()S)⋗ ⋗ HeadAlternativa Alternativa ()S){displaystyle mathrm {Tail} ^{+}(S)gtrdot mathrm {Head} ^{*}(S)}
      • b⋗ ⋗ a{displaystyle bgtrdot a}
      • b⋗ ⋗ c{displaystyle bgtrdot c}
      • c⋗ ⋗ a{displaystyle cgtrdot a}
      • c⋗ ⋗ c{displaystyle cgtrdot c}
  • S Siguiente b
    • S≐ ≐ b{displaystyle Sdoteq b}
    • Tail+()S)⋗ ⋗ HeadAlternativa Alternativa ()b){displaystyle mathrm {Tail} ^{+}(S)gtrdot mathrm {Head} ^{*}(b)}
      • b⋗ ⋗ b{displaystyle bgtrdot b}
      • c⋗ ⋗ b{displaystyle cgtrdot b}
• S→ → c{displaystyle Sto c}
  • sólo hay un símbolo, por lo que no se añade ninguna relación.

mesa anterior

Sabc$ $ S≐ ≐ ⋖ ⋖ ≐ ≐ ⋖ ⋖ a≐ ≐ ⋖ ⋖ ⋖ ⋖ b⋗ ⋗ ⋗ ⋗ ⋗ ⋗ ⋗ ⋗ c⋗ ⋗ ⋗ ⋗ ⋗ ⋗ ⋗ ⋗ $ $ ⋖ ⋖ ⋖ ⋖ {displaystyle {begin{rray}{c tuccccc} ################################################################################################################################################################################################################################################################