recategorized by
6,548 views
23 votes
23 votes
  1. Translate the arithmetic expression $a^\ast -(b+c)$ into syntax tree.
  2. A grammar is said to have cycles if it is the case that $A \overset{+}{\Rightarrow} A$

    Show that no grammar that has cycles can be $\text{LL(1)}.$
recategorized by

4 Answers

15 votes
15 votes
A grammer having left recursion generates a cycle.

And no left recursive grammer is LL(1) grammer.
5 votes
5 votes

$a^∗−(b+c)$

We have the infix (inorder) expression.

This will be the equivalent postfix: $a^∗(bc+)-$

 

You have infix, you have postfix, now make the tree.


Cycle => Loop => Usage of Left Recursive Grammar. So, can't be LL(1)

4 votes
4 votes

A. Convert $a^∗−(b+c)$

How to check if the syntax tree is correct? Find inorder traversal of the tree it should give above expression. (infix expression)

Image source: Answer below.

B.

A context-free grammar is cyclic if there exists a non-terminal A and a derivation in one or more steps A⟹+   A. It is left-recursive if there exists a non-terminal A, a mixed sequence of terminals and non-terminals γ, and a derivation in one or more steps  A⇒+   Aγ.

Hence cyclic implies left-recursive, but the converse does not hold.

left recusion grammar cannot be LL(1).

Ref: https://cstheory.stackexchange.com/questions/18609/difference-between-a-cyclic-and-a-left-recursive-context-free-grammar

0 votes
0 votes
The tree will be

       *
      / \
     a   -
        / \
       b   +
          / \
         c   ε

Related questions

38 votes
38 votes
3 answers
2
44 votes
44 votes
1 answer
4