The Gateway to Computer Science Excellence
0 votes
68 views
We know that a grammar is containe

1-left recursive

2-ambiguous

3-Common prefixe

Then grammar is not LL(1)

 

 

If let I constructed M-TABLE or PARSE TABLE

of grammar which is not contain left recursive and common prefixes .

 

Let consider I am not able to find out grammar is ambiguous or not ,

If LL(1) parse table contains multiple choice in  same  row and  column then

Can I said that grammar is ambiguous or not?
in Compiler Design by (21 points) | 68 views

1 Answer

0 votes
When is a CFG ambiguous?

If we can find an $x \in L(G)$ such that for that particular $x$ we can have at least 2 different parse trees , then we can say that the grammar is ambiguous.

In compilers , in the syntax analysis phase , a parse tree is constructed by the parser with the use of LL(1) parsing table [Considering only LL(1) parsers here ]and is passed on to the semantic analysis phase.

How does this parsing takes place?

String is kept into the input buffer and each symbol is read from left to right and accordingly stack is either pushed with the RHS of a production or is popped.[Assuming here that you know how the  process works].

Now where is the problem regarding ambiguity here?

Suppose i/p symbol is 'a' , and in a particular cell in the parsing table , say $Table[E][a]$ has two or more entries , this mean we've multiple choices here , using any might lead to an acceptance by the parser , but would lead to completely different parse trees , right?

Now can we say that grammar is ambiguous? No , we cannot always say that the grammar is Ambiguous. Why? By using a particular production , out of one possible production , might lead to acceptance , might not .

LL(1) parsers might get confused as to which production to be used in this case , and since LL(1) parsers are predictive parsers , it rejects grammar with multiple entries , so to reject the possibility of a possible backtracking while parsing .
by Loyal (5.8k points)
0
A grammar may be ambiguous even if there is no left recursion and non-determinism. is it possible to get multiple entries in parsing table considering this situation?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,458 answers
195,370 comments
100,256 users