Bottom-up Parsing

tags: compiler design, systems

Bottom-up parsing is the opposite of top-down, it starts from the leaves go to the root.

The bottom-up parser only does shift and reduce actions. We shift an input symbol to the parsing stack and then reduce a group of terminals and non-terminals into a grammar rule or another non-terminal. The bottom-up parser can also be called a shift-reduce parser.

NOTE: A compare question between top-down and bottom-up parser can come.

Grammar Augmentation

First we have to augment our grammar, we add a start symbol that produces our old start symbol. The purpose of this is that our algorithm can know when to accept, this is the only way we can tell that the string has finished without having to look at a look-ahead token.

If we didn’t augment our grammar there will be no way to tell which reduction in the stack is the “last reduction”. Later we will notice that is the reduction of our start symbol only happens at state 0, this is to indicate we have finished all the intermediate reductions.

Bottom-up does rightmost derivation, if we look at the stack from bottom up we can the right-most derivation, it is not obvious in this example but it can be noticed in other examples.

I think i should write lol

LR(0) Parsing

$LR(0)$ parsing algorithm is a bottom up parser, it has a similar idea to the top-down LL(1), we also build a table here.

An LR(0) item is a production rule but we add period in rule to distinguish position or shifted and reduced symbols.

NOTE: If dot comes before then it is an initial item, in the end means a complete item or it has shifted these symbols before the period.

Example of items for a grammer: I need to understand this one more.

LR(0) NFA and table building

We use the new grammar items to build LR(0) NFA, since the items kind represent what I should do next, the arrow represent the next action. A really good example is on slide 14-15 The start state of the NFA will correspond to the initial state of the parser, where we have an empty stack. After the NFA we do subset construction to transform this NFA to a DFA which will enable us to build the table. We will also store the state number we are in after every action and the first thing in the stack is the number 0 to indicate we are in our initial state. Example slide 23.

NOTE: an arrow with a non-terminal indicates reduction and an epsilon production is considered a complete state. Also reduce state must only contain one complete item. This is only for LR(0) parser.

We can now start to see why we augmented the grammar, our initial state is the augmented first symbol and any action will lead to recognizing this symbol, i.e. our complete input string.

Grammars that are not LR(0)

If after building the DFA from the NFA, I notices that a state can be a reduce state (the dot in on the right of the production(complete item)) and also a shift state then this grammar can not be LR(0).

Examples

NOTE: Non-terminals are only in the goto column and any arrow that has a non-terminal indicate REDUCTION, and getting the non-terminal on the stack means we reduced and are transitioning to the state that has the dot after the non-terminal in this rule. Please remember this.

References:

1. https://drive.google.com/drive/folders/1p7Lb4BBXPN7h3l9wjWmYS9S9_0wj4PA6 - Chapter 5 part 1