Computer Science 456/656: Automata and Formal Languages

Fall 1999

A Bottom-up Parser

This page is the supplementary to the lecture of November 4, 1999.

We present a deterministic bottom-up parser for the grammar G given below.
The terminal alphabet for G is {a,+,*}. The start symbol is S. The productions are:

0. S —> E$
1. E —> E+T
2. E —> T
3. T —> T*a
4. T —> a

The machine operates by steps, but one step of the parser is emulated by one or more steps of a DPDA that emulates the parser. We will discuss that emulation below.
The parser has a stack, with initial stack symbol Z0 and does not have states (although the DPDA that emulates it has states, as explained below).
The parser may examine the top symbol of the stack without popping it, and may examine the first unread symbol of the input file without reading it (this is the lookahead feature).

Initially, the stack has one symbol, the start symbol, and the input string is loaded onto the input file.
One step of the parser is excuted as follows.

  1. Examine the top symbol of the stack and the first unread symbol of the input file.
  2. Pop zero or more stack symbols.
  3. Examine the top symbol of the stack.
  4. Possibly read one symbol.
  5. Possibly push one symbol.
  6. Possibly output one symbol.
The parser halts when it outputs 0.

Each row of the table gives a possible step of the parser. If no step is possible before the parser halts, it hangs. It also hangs if, when it attempts to pop a given handle, the topmost symbols on the stack at that time do not match the handle. However, subscripts are ignored here. For example, in rows 9. and 10., the required handle is T*a, which may be either T1*a3 or T2*a3.
The first column is the index of the possible step.
The next column shows the top symbol of the stack before the step.
The next column shows the first unread symbol of the input file (the lookahead symbol). If this entry is blank, it means that it does not matter what this symbol is.
The next column shows the symbols to be popped. (If the stack contents do not allow this exact string to be popped, the parser hangs.) We refer to this string as the handle. If this entry is blank, nothing is popped.
The next column shows the top symbol of the stack after the handle has been popped. If this entry is blank, it means that it does not matter what this symbol is.
The next column shows the symbol that is read. If this entry is blank, it means that the parser does not read anything during this step.
The next column shows the symbol that is pushed.
The next column shows the symbol that is written. If this entry is blank, it means that the parser does not write anything during this step.

1.Z0a a a4
2.+a a a4
3.*a a a3
4. T1 * * *
5. T2 * * *
6. E + + +
7. E $ $ $
8.a4a +T14
9.a4a Z0 T24
10.a3T*a +T1 3
11.a3T*a Z0T2 3
12. T1 +E+T E1
13. T1 $E+T E1
14. T2 +T E2
15. T2 $T E2
16. $ E$ S 0 (halt)
The first 7 rows of the table are for shifts, while the other rows are for reductions.
I have implemented this parser. Here are the actual input and output of three runs.
input string output string
a 420
a*a+a 432410
a*a*a+a+a*a*a*a+a+a+a*a 4332414333141414310
Emulation by a DPDA. Each step of the parser is emulated by some number of steps of a DPDA. To emulate looking at the top of the stack, the DPDA pops the stack and pushes the same symbol back onto the stack. This requires storing the symbol in memory. To emulate popping several symbols, the DPDA must remember where it is in the sequence of pops.
The memory of the DPDA is implemented by its set of states. A simple way to do this is to determine that it can function with an n-bit memory, for some finite n. This memory then has 2n states, but usually fewer states are needed.
Disclaimer. As you take the compiler course, you will learn that bottom-up parsers are normally quite a bit more complex than this baby example. Given the above grammar, an automatic parser generator would probably create a parser which is more complex than the parser given above.

Back to Course Page