Wednesday, 12 October 2016

XML : Do I Have an LL(1) Grammar for This Subset of XML?

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