The Gateway to Computer Science Excellence
+1 vote
441 views

in Compiler Design by Active (1.7k points)
edited by | 441 views

1 Answer

+4 votes
Best answer

yes option 3) is true .

1) Every regular grammar may or may not be LL1. Regular grammar can be left linear or right linear grammar and though righ linear grammar is guaranteed to be recursion free as well as factoring free, left linear grammar allows both and such a grammar cannot be parsed by LL1 parser. So it is false. (Even not all right linear grammars can be parsed by LL(1)- see part 3)

2) this is false ...

by this picture (given in Stanford-CS143 ) it is clear every LL1 Is not LALR(1).

3) Ambiguity can even come from inherent property of language. So it need not be true always. counter eg : 

s--> iEts/iEtses/a

s-->b 

after removing left factoring 

s--> iEtss'/a

s'---> E/es

E--->b  after removing left factoring we still come with ambiguity ..so this is true 


for more clear picture 

1) if it is ambiguous and right linear then also it will not be parsed by LL1 ..becoz LL1 does not parse ambiguous and left recursive grammer

2)this is LL1 but not LALR

S ::= '(' X 
    | E ']' 
    | F ')'
X ::= E ')' 
    | F ']'
E ::= A
F ::= A
A ::= ε 

3) if language is not inherently ambiguous after then it could be ambiguous ..bcoz inherently ambiguous property says for given grammar , every language derived from it will be ambiguous .. while without this property , may also ambiguous ... bcoz ambiguous means for same language or string we have 2 or more parse tree structure .. so if there is single language from given grammar , for which we have more than 1 parse tree then it will be ambiguous.

by Boss (17.1k points)
edited by
0
cannot understand ur 3rd explaination

Would u like to prove CFG is unambiguous after left recursion and left factoring ,

But here CFG is unambiguous without left factoring as well as with left factoring?

Is ur eg. correct? plz check
0

i mean to say after removing left factoring in this eg  we still have ambiguity ...

for string iEtiEtsses it is ambiguous for both cases (with left factoring and without )..

0
@Sonam

For 1, No left linear grammar is LL(1)?

For 2, that pic is sufficient, still any example?

For 3, You gave a grammar for an inherently ambiguous language without left factoring and left recursion. This is also sufficient here. Still, can we have such a grammar for an non-inherently ambiguous language?
+3

1) if it is ambiguous and right linear then also it will not be parsed by LL1 ..becoz LL1 does not parse ambiguous and left recursive grammer

2)this is LL1 but not LALR

S ::= '(' X 
    | E ']' 
    | F ')'
X ::= E ')' 
    | F ']'
E ::= A
F ::= A
A ::= ε 

3) if language is not inherently ambiguous after then it could be ambiguous ..bcoz inherently ambiguous property says for given grammar , every language derived from it will be ambiguous .. while without this property , may also ambiguous ... bcoz ambiguous means for same language or string we have 2 or more parse tree structure .. so if there is single language from given grammar , for which we have more than 1 parse tree then it will be ambiguous .. rt ..

+1
thank u ,I got it now
+1
@sonam you meant left linear in the original answer?

2 is correct :)

For 3, yes thats correct. But can there be an example CFG for an non-inherently ambiguous grammar which is not left recursive and without left recursion but still ambiguous.
+1
same as left recursion means left most symbol in right side is same as left side symbol ...

for 3rd one .. i just made it :P

S-->aS/b/A

A-->aA/b i know here is useless product but its ambiguous for ab string :)
0
But left linear doesn't imply left recursion. Because the left most non-terminal can be a different one from the production non-terminal and thus not causing left recursion. But right linear grammar does imply no left recursion.
+1
yes , in case of different non terminal there is no left recursion .,, i have to update .. :)
+1
@Arjun sir @Sonam

1)Left linear grammar is not LL(1) .

eg- say, for a(a+ab)*ab

A⤑Bb

B⤑Ca

C⤑Ca/Cab/a

.............................................................................

Right Linear grammar is not LL(1)

eg-a(a+b)*ab

A⤑aB

B⤑aB / bB /aC

C⤑b

........................................................................................

But there must be some  left linear or right linear grammar which will be LL(1)

So, option (1) is false

............................................................................................

But

3) @sonam eg.

S-->aS/b/A

A-->aA/b

it is left factored .right?

which should not be an example of (3)

 

Some regular grammar is LL(1). CFG can be converted to LL(1). To convert CFG to a LL(1) it should be not left recursive, deterministic, unambiguous and I think even not left factored. So,For some CFG option (3) must be true
+1
yes, and in ur 1eg 3rd production left recursive , 2 nd eg , 2nd production has left factoring and 3rd also left factoring ..
0
yes

and 3rd is your example :)
+1

O sorry ..  cheeky

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,737 questions
57,366 answers
198,496 comments
105,265 users