Task Build the Parse Table

Let $\mathcal{G}$ be the following context-free grammar: $$ \begin{aligned} E &\to TE' \\ E' &\to +TE'\; |\; \epsilon \\ T &\to F T' \; \\ T' &\to *FT'|\;\;\epsilon \\F &\to (E)\; | \;id \\ \end{aligned} $$

I calculated $ FIRST $ and $ FOLLOW $ sets \begin{aligned} FIRST(F) = FIRST(T) = FIRST(E) = \{ (,id \} \\ FIRST(T') = \{*,\epsilon\}\\ FIRST(E') = \{+,\epsilon\} \\FOLLOW(E) = FOLLOW(E') = \{ ),$ \} \\ FOLLOW(T)=FOLLOW(T') = \{+,),$\}\\ FOLLOW(F) = \{ +, * ,$ , )\} \end{aligned}

Here is the rule while constructing parse table\ $$For\; each\; terminal\; a\; in\; FIRST(A)\;,\; add \; A \to \alpha; to\; M[A,a]$$

When applying this rule to the production $$F\to(E)$$ I need to add this to $M[F,id]$ and $M[F,(]$ so when applying this rule again to $F\to id$, Should I need to add again to $M[F,id]$? Then ; It; is not LL(1) ]; grammar right? But it is given LL(1) . How , any mistake I have done?

  • $\begingroup$ It's a long time ago, but I thought F -> (E) together with the rule that F is reachable means E can be followed by ). $\endgroup$
    – gnasher729
    Aug 9, 2022 at 11:13
  • $\begingroup$ Yeah, Thanks for pointing it out I've edited it, I made an error while typing! $\endgroup$
    – bigstreet
    Aug 9, 2022 at 11:26

1 Answer 1


You have missed one important note. The rule is such

For each production $A→α$ of the grammar, do the following:
For each terminal $a$ in $FIRST(A)$, add $A→α;$ to $M[A,a]$

that is we only consider the elements in first set which is contributed by the production $A→α$ which here is $F→(E)$ ,

so for this rule ie $F→(E)$ the $FIRST(F) = \{(\}$ only

and for $F→id$ , $FIRST(F) = \{id\}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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