Search code examples
parsingcompiler-constructiongrammartheorylr-grammar

How to do I parse a input string in SLR(1) parser with grammar having epsilon?

This is my Grammar: S → (S)S | ε

while my input string, which I want to parse using SLR(1): ()()

I tried making DFA with the method specified in this question, but I wasn't able to parse it :(

SLR(1) Parser and epsilon involved

This is the DFA which i made This is my DFA, sorry for bad handwriting

Solution

  • Your DFA looks okay to me, but it's only the LR(0) automaton. To make the SLR(1) automaton/parser, you need the 1-symbol lookaheads for each nonterminal (i.e., S). That will tell the parser when it must reduce to S. (To get this right, your augmenting production should have an end-of-input symbol.)