I am studying LALR(1) parser and I have this question:

Consider the following Grammar

S - > V = E

E - > F | E+F

F - > V | int | (E)

V - > id

Construct the LALR(1) parsing table for this Grammar.

While generating the item-set DFA for this problem, I encountered a problem in the fifth set.

My attempt

According to this website, http://jsmachines.sourceforge.net/machines/lalr1.html, the lookaheads for productions with F and V on the LHS have only \$ in the lookahead whereas I am getting $ and + in all. Could someone please explain which is correct?

  • $\begingroup$ That's not what I got from the jsmachines site. Perhaps you entered your grammar incorrectly, or maybe you're misinterpreting its output. $\endgroup$
    – rici
    Commented Oct 26, 2021 at 23:26
  • $\begingroup$ Okay, I'll recheck. $\endgroup$
    – phoenix
    Commented Oct 27, 2021 at 3:28

1 Answer 1


I entered your grammar in that tool:

S -> V = E
E -> F
E -> E + F
F -> V
F -> int
F -> ( E )
V -> id

And it reported state 3 (GOTO(S1, =)) as (spaced out a bit for readability):

 [S -> V =.E,  $];
 [E -> .F,     $/+];
 [E -> .E + F, $/+];
 [F -> .V,     $/+];
 [F -> .int,   $/+];
 [F -> .( E ), $/+];
 [V -> .id,    $/+]

which seems to agree with your notebook.

Like most online grammar tools, that one is pretty picky about input format. Also, like most online grammar tools, there is no easily accessible documentation about what input format it expects. So I can't tell you exactly what format it wants, but I'm pretty sure that it doesn't accept the | operator, and that it requires syntactic elements to be separated by spaces.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.