0
$\begingroup$

I am going through the following lecture notes on LR parsing :

https://www3.nd.edu/~dthain/courses/cse40243/fall2016/chapter4b.pdf

For the following grammar :

enter image description here

The following LR automation has been done :

enter image description here

and the following is the LR parsing table drawn for it :

enter image description here

In the table I can see that the alphabets "R" ,"G" and "S" denote the action being taken and the number following them is the index number of the state to which the transition is taking place .

Now , what I am unclear about is what exactly is a "goto"action ? I can see that goto actions , "G1" , "G8" , "G3", "G6" are occurring only in response to non- terminals "'E" and "T" . And all of them have two rules by using which we can reduce the expression to the start symbol.

But I am unable to draw any further patterns to interpolate what exactly is a "Goto action " .

Nevertheless , when at state 4 an input of "(" results in shift but how does an input of ")" or "+" result in reduction , which I ,with certain degree of confidence, guess to be , the action of replacing few symbols with the left hand side of certain production .

So , how exactly to make sense of this table ? What exactly is a GOto and am I right about "reduction"?

$\endgroup$

1 Answer 1

0
$\begingroup$

Remember that a stack entry is a state and a symbol. (In fact, the symbols are not really important for the parser, but they will prove useful later on when you encounter semantic values.)

A reduction action consists of popping the right hand side of a production from the top of the stack and pushing the left hand side. (The number in the reduction action is the number of the production, so you know what the left- and right-hand sides are.)

When the right hand side is popped off the stack, a new state is revealed (at the top of the stack). The Goto action which corresponds to that state and the left-hand side non-terminal tells you which state to push along with the non-terminal.

The parser's actions are illustrated in the chart at the end of section 4.8 of your text, which I reproduce below. However, the reduction and subsequent goto action are combined in the chart:


Stack         Symbols       Input             Action
0                           id ( id + id) $   shift 4
0 4           id            ( id + id ) $     shift 5
0 4 5         id (          id + id ) $       shift 4
0 4 5 4       id ( id       + id ) $          reduce T → id
0 4 5 8       id ( T        + id ) $          reduce E → T
0 4 5 6       id ( E        + id ) $          shift 2
0 4 5 6 2     id ( E +      id ) $            shift 4
0 4 5 6 2 4   id ( E + id   ) $               reduce T → id
0 4 5 6 2 3   id ( E + T    ) $               reduce E → E + T
0 4 5 6       id ( E        ) $               shift 7
0 4 5 6 7     id ( E )      $                 reduce T → id ( E )
0 8           T             $                 reduce E → T
0 1           E             $                 accept

Let's look at what the parser does at the highlighted line in the above chart. We can see that the parser is in state 3 (which is the state at the top of the stack) and is about to perform a reduction. The right-hand side of the production to be reduced has three symbols – E + T – which we can also see at the top of the stack (in the Symbols column). So the first thing the parser does is pop the right-hand side of the production:

0 4 5 6 2 3   id ( E + T    ) $               pop E + T

Now, the parser is in state 5 and needs to do something with the E which was just reduced (that is, the left-hand non-terminal in the reduced production).

0 4 5         id (          ) $               push E

We consult the parser action chart, looking for the action for an E corresponding to state 5. That action is G6, meaning that the parser pushes state 6 onto the stack with the symbol E, giving us the next line:

0 4 5 6       id ( E        ) $               shift 7

Aside from the fact that it's a non-terminal rather than a terminal being pushed onto the stack, there is no difference between a shift and a goto action. Of course, the goto action does not consume the lookahead symbol, so that symbol is then used in the new state (resulting, in this case, in a shift action).

$\endgroup$
6
  • $\begingroup$ Could you elaborate a bit more about Goto action using one of the examples in the table given here ? please ? $\endgroup$ Commented Jan 1, 2018 at 12:00
  • $\begingroup$ When the right hand side is popped off,for example at state 3,with the advent of a T , the state to be pushed into the stack is state 3,i.e., the left hand side of the production in state 3 is to be pushed at the top of the stack . right ? However, could not exactly know what you meant by "the new revealed state " $\endgroup$ Commented Jan 1, 2018 at 12:21
  • $\begingroup$ So will it be right to say that a goto always co occurs with a reduce action ? Or does it always precede or succeed a reduce ? $\endgroup$ Commented Jan 1, 2018 at 12:24
  • $\begingroup$ @eddie: it always follows a reduce action. $\endgroup$
    – rici
    Commented Jan 1, 2018 at 14:13
  • $\begingroup$ So , the rest of my understanding is correct ? $\endgroup$ Commented Jan 1, 2018 at 17:35

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.