このXMLサブセットのLL（1）文法はありますか？

Question

私は、次のEBNF文法とXMLの架空のサブセットのためのパーサを作ることを約だ：

DOCUMENT ::= ELEMENT 
ELEMENT ::= START_TAG (ELEMENT | DATA)* END_TAG | EMPTY_TAG 
START_TAG ::= < NAME ATTRIBUTE* > 
END_TAG ::= </ NAME > 
EMPTY_TAG ::= < NAME ATTRIBUTE* /> 
ATTRIBUTE ::= NAME = STRING 

上記は変更せず、「そのまま」の文法です。ここはLLに変換で私の試みである（1）：

DOCUMENT   ::= ELEMENT EOF 
ELEMENT   ::= PREFIX > ELEMENT_OR_DATA END_TAG 
         | PREFIX /> 
PREFIX   ::= < NAME OPT_ATTR 
ELEMENT_OR_DATA ::=  OPT_ELEMENT ELEMENT_OR_DATA 
         | OPT_DATA ELEMENT_OR_DATA 
         | epsilon 
OPT_ELEMENT  ::= ELM_LIST | epsilon 
ELM_LIST   ::= ELEMENT | ELEMENT ELM_LIST 
OPT_DATA   ::= DATA_LIST | epsilon 
DATA_LIST  ::= DATA | DATA DATA_LIST 
END_TAG   ::= </ NAME > 
OPT_ATTR   ::= ATTR_LIST | epsilon 
ATTR_LIST  ::= ATTRIBUTE | ATTRIBUTE ATTR_LIST 
ATTRIBUTE  ::= NAME = STRING 
EOF    ::=   &$ 

これは、元のLL（1）バージョンですか？そうでない場合、どこが間違っていたのですか？もしそうなら、意味を変えずに「単純化」する方法はありますか？私は、可能な限りシンプルなバージョンを持っていると確信していません。

これは明らかです。

Answer 1

LL（1）パーサーは、次のトークンを調べるだけで、ELEMENTの2つのルールの正しいルールを選択できません。 文法によると、パーサは最初のルール試してみてください： ELEMENT ::= PREFIX > ELEMENT_OR_DATA END_TAG をそして、それが動作しない場合、それは二番目のルールをしようとするために、再帰（バックトラック）から返す必要があります。 ELEMENT ::= PREFIX />

問題があります両方の規則が同じ "オブジェクト" PREFIXから始まるということです。 この場合、端末ではないので「悪い」さえあります。

間違いなく、LL（1）文法ではありません。それを構築しようとしましょう。

私たちは、最初のタグのを除去することで、元の文法を簡素化： DOCUMENT ::= ELEMENT ELEMENT ::= < NAME ATTRIBUTE* > (ELEMENT | DATA)* </ NAME > ELEMENT ::= < NAME ATTRIBUTE* /> ATTRIBUTE ::= NAME = STRING

次のステップは、正しいルールを選択するために、パーサーに役立つ最初のトークンを取得するために、ELEMENTのルールを分割することです。 DOCUMENT ::= ELEMENT ELEMENT ::= < NAME ATTRIBUTE* ELEMENT1 ELEMENT1 ::= > (ELEMENT | DATA)* </ NAME > ELEMENT1 ::= /> ATTRIBUTE ::= NAME = STRING

パーサーは、要素の解析を正常に開始できます。それは、それが拡張されているか短い要素かにかかわらず、決定を「延期」し、この質問をELEMENT1ルールに委ねる。後のトークンは、次のトークンが>か/>かどうかを調べることによって、どのタイプの要素が解析されているかを判断できます。

はのは、変革を続けましょう： DOCUMENT ::= ELEMENT ELEMENT ::= < NAME ATTRIBUTES ELEMENT1 ELEMENT1 ::= > ELEMENT_OR_DATA </ NAME > ELEMENT1 ::= /> ELEM_OR_DATA ::= ELEMENT ELEM_OR_DATA ELEM_OR_DATA ::= DATA ELEM_OR_DATA ELEM_OR_DATA ::= epsilon ATTRIBUTES ::= NAME = STRING ATTRIBUTES ATTRIBUTES ::= epsilon

私達はちょうど置き換え*適切LL構文と演算子は。 この最後の文法には依然として問題があります。最初の2つのELEM_OR_DATAルールは、どちらが当てはまるのか推測できないため、パーサを「混乱させる」可能性があります。

はのは、パーサーにヒントを与えることによって、この問題を解決してみましょう： DOCUMENT ::= ELEMENT EOF ELEMENT ::= < ELEMENT0 ELEMENT0 ::= NAME ATTRIBUTES ELEMENT1 ELEMENT1 ::= > ELEMENT_OR_DATA </ NAME > ELEMENT1 ::= /> ELEM_OR_DATA ::= < ELEMENT0 ELEM_OR_DATA ELEM_OR_DATA ::= DATA ELEM_OR_DATA ELEM_OR_DATA ::= epsilon ATTRIBUTES ::= NAME = STRING ATTRIBUTES ATTRIBUTES ::= epsilon

我々はELEMENT1を分割さと第一ELEM_OR_DATAルールで要素0を使用しました。 DATAがトークンであると仮定すると、パーサーは次のトークンのみを調べることによって適用するルールを簡単に判別できます。