GATE CSE 1995 | Question: 9

Question

• A. Translate the arithmetic expression $a^\ast -(b+c)$ into syntax tree.

• B. 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)}.$

Comments

cycle means infinite loop

infinite loop due to left recursion

left recursion is not allowed in LL(1)

Thus no grammar that has cycle is LL(1)

---

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.

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

Answer 1

A grammer having left recursion generates a cycle.

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

Comments

@Ayush Upadhyaya what is the meaning of extended transition??  Does that mean if any non terminal to the RHS of A is replaced by its value then it will be left recursive?

I mean

A => B b

B => Ac

which is indirectly A=> Acb

 

---

How to draw tree? * is binary operator (multiplication), but only single operand is given. IS this wrong

---

grammar has cycle means?

Answer 2

$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)

Comments

Why does loop imply Left Recursive Grammar? It could Right recursive too, I guess.

---

@neel do let me know if your doubt gets cleared, I am having same doubt.

---

same doubt!

Answer 3

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

Answer 4

The tree will be

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