Re: Parsing Expression Grammar

Oliver Wong <owong@castortech.com> wrote:
> "A Pietu Pohjalainen" <pohjalai@cc.helsinki.fi> wrote in message
>> Uhm, using context free languages, it is always possible to write
>> ambiguous grammars, and actually there are context free languages that
>> are inherently ambiguous. So, you either have to deal with the
>> ambiguousity in the CFG's (e.g. precedence, associativity), or not use
>> context free languages.


> Sorry, I only know a bit about theory of computation, but I
> thought ambiguity was a property of grammars, and not of
> languages. Since a language is just a set of strings, how can a
> language itself be ambiguous? I understand that perhaps there exists a
> language which cannot be expressed by an unambiguous context free
> grammar, but might there not exist another way (i.e. not using CFGs)
> to express the language which is unambiguous?




Right.


I was writing this with the mindset that context-free languages = all
languages expressable by context-free grammars, and it is possible to
have languages, for which every (CF)-grammar is ambiguous - so the
language is inherently ambiguous, because every (CF)-grammar for that
language allows more than one parse tree on some strings in the
language.


An example of such language is (Taken from P. Linuz, 'An Introduction to
Formal Languages and Automata, pp. 144-145):
L = {a^n b^n c^m} \union {a^n b^m c^m}


Using context-free grammars to write recognizer for this language always
results an ambiguous grammar. I'd guess that e.g. the mentioned parsing
expression grammar could be used to unambiguously describe this
language.


br,
Pietu

Return to the comp.compilers page.
Search the comp.compilers archives again.