LL(k)構文解析について

Question

構文解析に関する質問です。
ある文法で、
P=｛S→B,
B→E | if(E)B | if(E)B else B,
E→E+T | T,
T→n | -T | (E)｝
というのがあったのですが、
この場合、if(E)B というのはどう扱えばい
いのですか？
一応、自分が考えたのは、S→B→EB→EEB→...です。ご教授お願いします。

Answer 1

ご質問の文法には4つの規則があります。終端記号をこのように表してみました (nは実際は非終端記号なのではないかと思いますが、簡単のため終端記号とみなします)。

1. S → B
2. B → E | if ( E ) B | if ( E ) B else B
3. E → E + T | T
4. T → n | - T | ( E )

規則 2. は、「B」から「E」、「if ( E )」、「if ( E ) B else B」のいずれかを得ることができる、という意味です。ですからたとえば

• 規則1. により、S → B
• 規則2. により、B → if ( E ) B
• ……

などとすることができます。さらに続ければ、たとえば

• 規則2. により、if ( E ) B → if ( E ) if ( E ) B else B
• 規則2. により、if ( E ) if ( E ) B else B → if ( E ) if ( E ) E else B
• ……

などとすることもできます (同じ規則は可能な限り何回でも適用できますし、同じ規則でいつも同じものが得られるとも限りません)。最終的に終端記号のみを含むものができれば、それは文法Pに適合する文であるということになります。たとえば次のようなものです (適宜改行しています)。

if(-n+n)
  if(n)
    n+n
  else
    if(--n)
      n
    else
      n+-(n+n)

これはひとつの例でしかありません。文法Pが生成できる文は無限にあるということが分かりますね。

---

一方、冒頭の規則には B から E B を得ることができるものは含まれていませんから、ご質問のように

• S → B
• B → E B
• E B → E E B
• ……

などとすることはできません。

---

LL構文解析では、上の例とは逆に、実際の文から規則に合った構文木を作成し、最終的に最初の非終端記号Sを導出することで文法Pに適合していることを確認します。

【おまけ】上の生成された文の例には、構文解析をしようとすると問題が起きる箇所があります。どういう問題が起きるのか、考えてみて下さい。