Search code examples
compiler-constructionprogramming-languagesgrammarll-grammarlalr

Item set and SLR(1) Questions in Compiler


I ran into a Old Exam question that solved by our TA. anyone could help me?

when we create SLR(1) about S--> aSb | a grammar, one of the item set LR(0) is like as:

{ S-->a.Sb, S-->a., S-->.aSb, S-->.a}

about extracted rule from above set, which of them is True:

a) one reduced and 2 shift and 1 goto is produced.

b) one reduced and 2 shift and2 goto is produced.

c) two reduced and 1 shift and 1 goto is produced.

d) when we input a, we have conflict. 

anyone could say why (3) is correct? some detail about this question ?

EDIT: i think Goto refer to Action and goto tables. enter image description here


Solution

  • There are three possible lookahead symbols: a, b, and $ (the end-of-input marker). The transitions are:

     lookahead        action
     ---------        ------
         a            shift
         b            reduce S->a
         $            reduce S->a
    

    And one goto action is produced, on the non-terminal S, with the target being the state {S -> aS.b}