I'm about to make a parser for a fictional subset of XML with the following EBNF grammar:
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 The above is the grammar 'as is', without any changes. Here is my attempt at converting it to LL(1):
DOCUMENT ::= ELEMENT EOF ELEMENT ::= PREFIX CLOSE OPT_ELEMENT OPT_DATA END_TAG | PREFIX SLGT PREFIX ::= OPEN NAME OPT_ATTR OPT_ELEMENT ::= ELM_LIST| epsilon ELM_LIST ::= ELEMENT | ELEMENT ELM_LIST OPT_DATA ::= DATA_LIST | epsilon DATA_LIST ::= DATA | DATA DATA_LIST END_TAG ::= LTSL NAME CLOSE OPT_ATTR ::= ATTR_LIST | epsilon ATTR_LIST ::= ATTRIBUTE | ATTRIBUTE ATTR_LIST ATTRIBUTE ::= NAME ASSIGN STRING OPEN ::= < CLOSE ::= > LTSL ::= </ SLGT ::= /> ASSIGN ::= = EOF ::= &$ Is this an LL(1) version of the original? If not, where did I go wrong? And if so, is there any way to 'simplify' without changing the meaning? I'm not convincing I have the simplest possible version.
Hope this is clear.
No comments:
Post a Comment