Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


538 users

0 votes
Why do we need those columns? Doesnt the word that is parsed only contain Terminalsymbols?

Thanks for any response!
in * TF "Emb. Sys. and Rob." by (1.1k points)

1 Answer

+1 vote
Best answer

Check out slide 184, the parse table of an LR(0) parser actually consists of two tables, namely the action table and the goto table.

  1. The action table is indexed by a state qi and a terminal a ∈ T ∪ {$} and contains the action of the parser to be executed when the qi is the topmost symbol on the stack and a is the next letter read from the word. The action is either a shift or a reduce action. 
  2. The goto table is indexed by state qi and a nonterminal A ∈ N and contains the state that must be put onto the stack after a reduction that puts A onto the stack that had qi on top.

The goto table is needed since LR(0) parsers usually have many states in contrast to LL(1) parsers (which only have a single state). The goto table makes then a transition specified by the LR(0) automaton of LR(0) items. Usually, both tables are put together into a single table.

For instance (example on slide 183), if the stack content is $|q0|b|q4|b|q4|a|q3|a|q7 and the next letter of the word is b, we first look at the action table at entry (q7,b) and find a reduce action R(B->a). That means that we have to remove "a|q7" from the stack and have to put "B" instead of this there. But which state should be put on top of "B"? 

That is answered by looking at the goto table at entry (q7,B) and there, we find goto(q6) so that we know that your stack content after reading "b" is $|q0|b|q4|b|q4|a|q3|B|q6.

by (166k points)
edited by

Related questions

+2 votes
1 answer
asked Mar 27, 2021 in * TF "Emb. Sys. and Rob." by least (260 points)
0 votes
1 answer
asked Mar 25, 2021 in * TF "Emb. Sys. and Rob." by ballatma (1.2k points)
0 votes
2 answers
0 votes
1 answer
0 votes
1 answer
asked Dec 11, 2020 in * TF "Emb. Sys. and Rob." by nickjo (1.1k points)
Imprint | Privacy Policy