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

The Gateway to Computer Science Excellence

+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.

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

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?

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

@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.

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

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,366 answers

198,496 comments

105,265 users