1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your parse table is wrong. Why does $E'$ row contain the rules for $T$ non-terminal, and $T$ row contains the rules for $F$? $\endgroup$ – Vladislav Mar 10 at 20:47
  • $\begingroup$ @Vladislav Thank you for your remark. $\endgroup$ – none9632 Mar 10 at 22:01
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That is, if I understand correctly, the table-driven LL (1) parser cannot correctly process the right-associative operator. $\endgroup$ – none9632 Mar 11 at 15:26
  • 1
    $\begingroup$ @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.) $\endgroup$ – rici Mar 11 at 15:57
  • $\begingroup$ Oops, I mean left-associative operator. $\endgroup$ – none9632 Mar 11 at 16:53
  • $\begingroup$ @none9632: Same answer. $\endgroup$ – rici Mar 11 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.