# Why table-driven LL (1) parser does not work with division and subtraction?

Everywhere, one grammar is used as an example table-driven LL(1) parser.

### Grammar

S -> E | (epsilon)
E -> TE'
E' -> +TE' | (epsilon)
T -> FT'
T' -> *FT' | (epsilon)
F -> NUM | (E)


With this grammar you can only add and multiply. I wanted a little more so added subtraction and division operations.

### my Grammar

S -> E | (epsilon)
E -> TE'
E' -> +TE' | -TE' | (epsilon)
T -> FT'
T' -> *FT' | /FT' | (epsilon)
F -> NUM | (E)


### Parse table

|-------------------------------------------------------------------------------------|
|     |   NUM   |    +    |    -    |    *    |    /    |    (    |    )    |    $| |-------------------------------------------------------------------------------------| | S | S->E | | | | | S->E | | S->e | |-------------------------------------------------------------------------------------| | E | E->TE' | | | | | E->TE' | | | |-------------------------------------------------------------------------------------| | E' | | E'->+TE'| E'->-TE'| | | | E'->e | E'->e | |-------------------------------------------------------------------------------------| | T | T->FT' | | | | | T->FT' | | | |-------------------------------------------------------------------------------------| | T' | | T'->e | T'->e | T'->*FT'| T'->/FT'| | T'->e | T'->e | |-------------------------------------------------------------------------------------| | F | F->NUM | | | | | F->(E) | | | |-------------------------------------------------------------------------------------|  But I have a problem if used this grammar to build a parse tree the string 6*3/2, it turns out that the first operation is division and then the multiplication operation. I do not know why this is happening. Maybe this is because I have the wrong grammar or I'm doing something wrong. Help me. • Your parse table is wrong. Why does$E'$row contain the rules for$T$non-terminal, and$T$row contains the rules for$F\$? – Vladislav Mar 10 at 20:47
• @Vladislav Thank you for your remark. – none9632 Mar 10 at 22:01

If you naively generate a parse tree from

\begin{align}T\to& FT'\\ T'\to& *FT' \\ \mid&\; /FT' \\ \mid&\; \epsilon\\ \end{align}

then you're going to end up with something like this:

         T
/ \
/   \
/     \
F       T'
|      /|\
6     / | \
/  |  \
*   F   T'
|  /|\
3 / | \
/  |  \
÷   F   T'
|   |
2   ε


What you really want is this:

         T
/|\
/ | \
/  |  \
T   ÷   F
/|\      |
/ | \     2
/  |  \
T   *   F
|       |
F       3
|
2


But that belongs to a different, left-recursive grammar:

\begin{align}T\to& T * F\\ \mid&\; T / F\\ \mid&\; F \end{align}

To use the second grammar, you'd need to use a different parsing technique (not the end of the world :-). To get the second parse tree, you need to do a little surgery while constructing it (or in a post-parse tree-walk, but that seems like overkill).

Because LL grammars cannot deal with left-recursive grammars, they cannot directly represent left-associative operators (which is most operators). Without left-recursion, you only have one way to represent a repetition, which means you have to use the same style to represent both left-associative and right-associative operators. That's not an issue in practice -- you certainly know the associativity of all operators in your language -- but you might find it annoying that you need to annotate the parser in order to get the right parse. If you use a bottom-up parsing technique, this annoyance vanishes.

• That is, if I understand correctly, the table-driven LL (1) parser cannot correctly process the right-associative operator. – none9632 Mar 11 at 15:26
• @none9632: What I'm saying is that the restrictions imposed by LL parsing make it impossible for the grammar to distinguish between left- and right-associative operators. In effect, both are represented as operand (operator operand)*, which is the normal way of writing recursive descent parsers. A parser can handle both associativities, but it must rely on information which is not embodied in the grammar. (Right-associative operators certainly exist. Aside from exponentiation, the most common one is assignment.) – rici Mar 11 at 15:57
• Oops, I mean left-associative operator. – none9632 Mar 11 at 16:53
• @none9632: Same answer. – rici Mar 11 at 16:54