grammar - LL(1) 予測解析 -- 左再帰を避ける

Question

文法を定義するときは、算術式を評価する文法を言います。次のように、式を項と因子に分割します。

E ::= E + T  
T ::= T * F  
F ::= num  
    | (E)

次に、左再帰を解決する必要があります。

では、文法を次のように定義してみませんか。

E ::= T + E  
T ::= F * T  
F := num  
    | (E)

そして、右再帰のみを持ちます。

score 6 · Accepted Answer

問題は、結合性が間違っていることです。左再帰文法は左結合ですが、右再帰文法は右結合です。結合性は問題にならない+か*、問題が表示されないため、結合性が問題になる演算子 ( など-) を追加すると、問題が表示されます。

LL 文法で左再帰を処理する方法は、基本的に右再帰に変換してから、解析ツリーを後処理して左再帰に戻すことです。それを分解すると、次のように変換されます

E ::= T + E | T

次に、左因数分解します

E ::= T E'
E' ::= \epsilon | + E

T + T + Tこれは式を次のように解析します

  E
 / \
T   E'
   / \
  +   E
     / \
    T   E'
       / \
      +   E
         / \
        T   E'
            |
         \epsilon

次に、上から下 (左から右) に評価/実行する交互の用語と演算子のリンクされたリストとして扱うことによって評価します。

tmp1 = eval_term(pop list head)
while (list not empty)
    op = pop list head
    tmp2 = eval_term(pop list head)
    tmp1 = tmp1 op tmp2

score 0 · Accepted Answer

あなたが示す特定の例では、順序は重要ではないため、オペランドを交換できます。
しかし、他のすべての文法には当てはまりません。記号を移動すると意味が変わる可能性があるからです。そのため、左再帰を排除する別の方法を見つける必要があります。

2 に答える 2