Compilers - Ambiguity and LR(k)

Author

Ambiguity and LR(k)

Leonardo Teixeira Passos

2006-10-03, 7:04 pm

I would like to know if a grammar is ambiguous then there isn't a
LR(k) syntax analyser that can be generated from it. Is the other way
of thinking also true, i.e., if there isn't a k such that a LR(k)
syntax analyser can be automatically generated from a grammar G, then
G is definitly ambiguous?

Are there any hints or proofs for the given staments?

It seems to me that if a grammar is ambiguous, then there isn't a
LR(k) syntax analyser that can be generated for it. However, I cannot
prove or disprove this.
[As I recall, there are plenty of grammars that are unambiguous but cannot
be parsed by any technique that uses fixed lookahead. -John]

Sylvain Schmitz

2006-10-04, 7:03 pm

Leonardo Teixeira Passos wrote:
> I would like to know if a grammar is ambiguous then there isn't a
> LR(k) syntax analyser that can be generated from it.

Yes, this is true. You can find proofs of this for instance in Geller
and Harrison, _On LR(k) Grammars and Languages_, TCS 4:245--276, 1977,
or in most theory-oriented textbooks on parsing.

Intuitively, you cannot generate a deterministic parser for an ambiguous
grammar: if each parsing action done by the parser is chosen
deterministically, then there is a unique way to recognize the entire
input string, and the grammar is not ambiguous.

> Is the other way of thinking also true, i.e., if there isn't a k
> such that a LR(k) syntax analyser can be automatically generated
> from a grammar G, then G is definitely ambiguous?

> [As I recall, there are plenty of grammars that are unambiguous but cannot
> be parsed by any technique that uses fixed lookahead. -John]

There are. Counter examples in programming languages include for
instance the "modifiers conflict" of Java
<http://java.sun.com/docs/books/jls/....doc.html#44488>.

--
Hope that helps,

Sylvain

Saumya K. Debray

2006-10-04, 7:03 pm

Sylvain Schmitz wrote:
> Leonardo Teixeira Passos wrote:
>
> Yes, this is true. You can find proofs of this for instance in Geller
> and Harrison, _On LR(k) Grammars and Languages_, TCS 4:245--276, 1977,
> or in most theory-oriented textbooks on parsing.
>
> Intuitively, you cannot generate a deterministic parser for an ambiguous
> grammar: if each parsing action done by the parser is chosen
> deterministically, then there is a unique way to recognize the entire
> input string, and the grammar is not ambiguous.

Well, just to be pedantic, "nondeterminism" isn't the same as
"ambiguity." For example, consider the language of palindromes,

L = { ww^R | w \in {0,1}* }, where w^R denotes the reverse of w.

This language is generated by the following context-free grammar:

S --> 0 S 0
S --> 1 S 1
S --> 0
S --> 1
S --> epsilon

This language can't be parsed by a deterministic parser, since for any
input string the parser has to "guess" when it has reached the midpoint
of the input. However, the grammar is not ambiguous: each string in the
language has exactly one parse tree (which is how "ambiguity" is defined).

Wolfram Fenske

2006-10-06, 7:03 pm

"Saumya K. Debray" <debray@CS.Arizona.EDU> writes:

> Sylvain Schmitz wrote:
>
> Well, just to be pedantic, "nondeterminism" isn't the same as
> "ambiguity." For example, consider the language of palindromes,
>
> L = { ww^R | w \in {0,1}* }, where w^R denotes the reverse of w.
>
> This language is generated by the following context-free grammar:
>
> S --> 0 S 0
> S --> 1 S 1
> S --> 0
> S --> 1
> S --> epsilon
>
> This language can't be parsed by a deterministic parser, since for any
> input string the parser has to "guess" when it has reached the midpoint
> of the input. However, the grammar is not ambiguous: each string in the
> language has exactly one parse tree (which is how "ambiguity" is defined).

This is kind of what I wanted to say: a grammar's ambiguity and its
being LL(n)/LR(n) are related issues but they're are not the same. If
a grammar is unambiguous, that just means that for each word in the
accepted language there is exactly one parse-tree. If OTOH a grammar
is LL(n)/LR(n) it means that for each word of the accepted language
you must be able to tell from the first/last n *tokens* (i. e.
terminals) which rule to choose. This is more strict than unambiguity
because for a grammar that is just unambiguous, n might not be fixed.
The palindrome grammar is one example.

Wolfram

Sponsored Links