Context free grammar to pushdown automata...

Question

<expr> −→ <term> | <expr> + <term> 
<term> −→ <factor> | <term> × <factor> 
<factor> −→ (<expr>) | b

things in pointy brackets are non-terminals and {b, +, ×,(,)} are terminals. I was thinking of changing this silly format to As Bs Cs and 0s to work with.

A −→ B | A0B B −→ C | B1C C −→ 0A1 | 0

where 1 = "+" and 0 = "x" but from here I would have no clue how to convert to pushdown automata as it would have more than 2 states.

Answer 1

The usual method constructs an automaton that has only one state. Initially, the stack has the nonterminal $\def\nt#1{\langle{#1}\rangle}\def\ntt#1{\nt{\text{#1}}}\ntt{expr}$ on it.

At each step the automaton should look at the top stack element.

• If it is a nonterminal, the automaton should remove it and replace it with its definition from the grammar. For example, when the automaton sees $\ntt{expr}$ it should remote that and replace it with either the one symbol $\ntt{term}$ or with the three symbols $\ntt{term}$, $\def\t#1{\mathtt{#1}}\t+$, and $\ntt{expr}$, in that order. a PDA is normally understood to be nondeterministic, so it should choose between the two alternatives nondeterministically.

• If the top stack element is a terminal, the automaton should check if the next symbol in the input stream matches the top of the stack. If so, it should pop the stack, and if not it should fail.

If the stack is empty, the automaton should halt and accept.

Converting the productions from $\ntt{expr} \to \ntt{term} \mid \ntt{expr}\t+\ntt{term}$ to an abstract form $A \to B\mid A0B$ is foolish; you are missing the point here. This algorithm is not an arbitrary exercise. It's the fundamental algorithm in computer parsing processes. When you program the computer and write something like x = y + z * (w + n) the computer needs to understand what you wrote, and to do that it uses is doing something very much like this algorithm. This is not an algorithm for converting a one useless abstraction to another. It's an algorithm for taking a description of the possible forms of a input, such as a programming language, and understanding expressions in that form, such as programs written in that language. The example you were given is about parsing arithmetic expressions. By converting to $A \to B\mid A0B$ form, you are obscuring this from yourself.