Q1 (a) What is the concept of Left-recursion in CFG. Explain inmaximum 60 words.

Question

Q1 (a) What is the concept of Left-recursion in CFG. Explain inmaximum 60 words.

Note: extra words may cause deduction in yourmarks, so be careful     [5]

Q1 (b) Following grammar is left recursive; your task is toremove the left recursion from this grammar and give new non-leftrecursive grammar.   [10]

Q2 (a) What is ambiguous grammar, explain in maximum 50words.

Note: extra words may cause deduction in yourmarks, so be careful [5]

Q2 (b) Following grammar isambiguous                       [10]

num ---> num + num | num - num |0|1|2|3|4|5|6|7|8|9

Prove that this grammar is ambiguous.

Explanation / Answer

Any CFG which contains production like

Q1 (b) Following grammar is left recursive; your task is toremove the left recursion from this grammar and give new non-leftrecursive grammar.   [10]

S -->BA

B-->1

B-->2

Solution

num ---> num + num | num - num|0|1|2|3|4|5|6|7|8|9

Prove that this grammar is ambiguous.

Solution

Consider the following input

      2 / 3 / 4

By our CFG each of our digits are number. That means we donot know if we should group (2 / 3) or (3 / 4). Look at twodifferent parse trees.

            2 / 3 /4                                                    2 / 3 / 4

                     /                                                               /                            

        /                      4                                       2                    /

2               3                                                                   3                  4

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.