|
Suppose that G is a grammar.
Recall that a sentential form of G is a sequence of tokens and nonterminals that can be derived from the start nonterminal.
Since a bottom-up parser does a rightmost derivation, it is to our advantage to focus attention on rightmost derivations.
Definition. A right-sentential form of G is a sequence of tokens and nonterminals that can be derived from the start nonterminal in a rightmost derivation.
Remember that the parser constructs a rightmost derivation backwards.
At any given point, it finds the right-hand side of a production, called a handle, and replaces the handle by the left-hand side of the production.
For example, let's use our simple expression grammar.
Suppose that the parser is currently working on right-sentential form F * n.
The handle is F. That is the right-hand side of production T → F. Replacing F by T yields T * n.
Here is a parse of n * n based on finding handles. The handle is shown in red.
| Right-sent. form | Production |
|---|---|
| n * n | F → n |
| F * n | T → F |
| T * n | F → n |
| T * F | E → T * F |
| E |
If you read off the right-sentential forms from the end to the start, you get
| E | ⇒ | T * F |
| ⇒ | T * n | |
| ⇒ | F * n | |
| ⇒ | n * n |
Notice that the derivation is rightmost.
An obvious issue is how the parser can know what the handle is. That is the subject of later pages.
For now, let's see a convenient way of carrying out a bottom-up parse, assuming that some way has been found to identify handles.
A shift-reduce parser keeps track of two things:
The handle is always the top one or more symbols in the stack.
There are two main kinds of actions.
A shift action moves a token from the input to the top of the stack.
A reduce action finds a handle α on the stack and a production N → α, and replaces α by N.
There are also two minor actions.
An accept indicates that the parser has sucessfully found a derivation.
An error action indicates a syntax error.
Let's do an example parse of n * n using our expression grammar.
The stack is shown with its top at the right end.
Also, I will follow the Dragon Book's convention of showing a $ at the bottom of the stack and at the end of the input.
Initially, the stack contains only its bottom marker, $.
The handle is shown in red. There is no handle for a shift action.
| Stack | Input | Action |
|---|---|---|
| $ | n * n $ | Shift |
| $ n | * n $ | Reduce by F → n |
| $ F | * n $ | Reduce by T → F |
| $ T | * n $ | Shift |
| $ T * | n $ | Shift |
| $ T * n | $ | Reduce by F → n |
| $ T * F | $ | Reduce by T → T * F |
| $ T | $ | Reduce by E → T |
| $ E | $ | Accept |
Now we need to turn to the issue of determining which action to perform.
|