I recently finished writing a recursive descent parser for this LL (1) grammar (which generates a tiny subset of XML):
document ::= element EOF element ::= < elementPrefix elementPrefix ::= NAME attribute elementSuffix attribute ::= NAME = STRING attribute attribute ::= EPSILON elementSuffix ::= > elementOrData endTag elementSuffix ::= /> elementOrData ::= < elementPrefix elementOrData elementOrData ::= DATA elementOrData elementOrData ::= EPSILON endTag ::= </ NAME >
I converted the grammar to LL (1) from this simple 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
Right now, I'm in the process of writing a parser with shift reduction that recognizes the same grammar. I understand that every LL (1) grammar is also LR (1). However, my professor tells me that “probably it would not be very convenient” to write a parser with a shift reduction for the above LL grammar (1). This makes me think that I need to convert it to LR (1) before starting to encode the parser.
Assuming it would not be a good idea to code the LR (1) parser using the LL (1) grammar above, how can I convert it to LR (1)? What would I need to change to make it more suitable for a hand-encoded LR (1) parser?
Addition: Signs NAME , STRING , DATA , > , < , /> , </ and = .
Update 11/3/16:
Obviously, the conversion was not necessary. Grammar was already in LR (1), and I was able to confirm this after further research. I have completed the implementation of both parsers, and I thank everyone who could help!
source share