0

命題論理の次の文法を考慮します。

<A> ::= <B> <-> <A> | <B> 
<B> ::= <C>  -> <B> | <C> 
<C> ::= <D>  \/ <C> | <D> 
<D> ::= <E>  /\ <D> | <E> 
<E> ::= <F> | -<F>
<F> ::= <G> | <H>
<G> ::= (<A>)
<H> ::= p | q | r | ... | z

conectives の優先順位は、-、/\、/、->、<-> です。

結合性も考慮されます。たとえばp\/q\/r、 と同じにする必要がありますp\/(q\/r)。他のコネクティブも同様です。

Java で予測トップダウン パーサーを作成するふりをします。ここにはあいまいさや直接左再帰は見られませんが、これを LL(1) 文法と見なす必要があるかどうかはわかりません。たぶん、間接的な左再帰ですか？

これが LL(1) 文法ではない場合、私の意図のためにそれを変換するために必要な手順は何ですか?

4

1 に答える 1

3

LL(1)ではありません。理由は次のとおりです。

LL(1) 文法の最初の規則は次のとおりです。

A --> C | D文法 G が LL(1)であるのは、G の 2 つの異なる生成が常に次の条件を満たしている場合のみです。

  1. 端子aがない場合は、C と D の両方で で始まる文字列を派生させますa。

このルールは、このコードの解析中に競合がないようにするためのものです。パーサーが に遭遇すると(、どのプロダクションを使用するかわかりません。

あなたの文法は、この最初の規則に違反しています。同じプロダクション の右側にあるすべての非終端記号、つまりすべての C と D は、最終的に G と H に還元されるため、それらのすべてが で始まる少なくとも 1 つの文字列を導出し(ます。

于 2013-12-19T19:55:21.690 に答える