grammar - 文法&&LLパーサー

Question

ですから、宿題があり、この文法がLLパーサーで機能しない理由を調べるために2時間以上費やしました。

<A> → a <B>
<A> → a b <C>
<B> → b d <D>
<C> → d <E>
<D> → m n
<E> → x y

誰かが私を正しい方向に向けてくれませんか？LLがつまずく可能性がある方法の1つは、ここでは信じられない無限ループに遭遇した場合です。

ありがとう

score 2 · Accepted Answer

LLパーサーとは、LL（1）パーサー（先読みが1のLLパーサー）を意味すると思います

文法が LL(1) パーサーによって解析可能であるためには、それが LL(1) でなければなりません。文法が LL(1) であるために従わなければならないことがいくつかあります。これらのいずれかを破ると、LL(1) 競合と呼ばれます。

FIRST/FIRST 競合:

すべての非ターミナルについて、各プロダクションには互いに素な FIRST セットが必要です。(FIRST セットは、主語から派生した文を開始できるすべての端末のセットです。)

EG: 上記の例では、非ターミナルには 2 つのプロダクションがあります。
```
<A> -> a <B>
<A> -> a b <C>
```
各プロダクションの最初のセットは次のとおりです。
```
FIRST(a <B>) = {a}
FIRST(a b <C>) = {a}
```
これら 2 つのセットが交差していることがはっきりとわかります。<A> -> a <B>LL パーサーでは、A がスタック上にあるポイントに到達し、次に読み取られるシンボルが 'a' である場合、パーサーはとのどちらを選択するかを判断できないため、これは問題です<A> -> a b <C>。
FIRST/FOLLOW 競合:

これは、特定の非端末の場合に発生しAます。FOLLOW(A)とFIRST(A)交差とAですNULLABLE。この特定の競合は、あなたの例では発生しません。

FIRST、FOLLOW、NULLABLE の詳細については、

1 に答える 1