2

I'm trying to learn compiler construction and I just read through the Dragon Book chapter on SLR parsers. So, I decided to make a simple grammar and try to hand code the parser. The grammar looks like this:

S -> A
A -> (A)A
A -> e,

where e is the empty string production.

According to another question on StackOverflow, the items in the starting state should look like

S -> .A
A -> .(A)A
A -> .e,

but what would the GOTO functions look like. I know that GOTO( '(' ) = *some state with A -> (.A)A*, but I cannot really wrap my head around GOTO(e). It does not really make sense for a parser to see an empty string. Does it?

Thank you all in advance!

Michael

Community
  • 1
  • 1
pongad
  • 33
  • 4

1 Answers1

0

No, the parser does not see an empty string. What it sees is the incoming symbol (the next token). If the incoming symbol does not cause a goto action (go to a new state), then the parser is forced to make a reduction (A -> e) and then do a goto based on A (a nonterminal transition). 

In State:   

A -> '(' . A ')' A
A -> . '(' A ')' A 
A -> e

if the input symbol is not '(', then the parser will make the reduction:

A -> e

and go to the new state:

A -> '('  A . ')' A