Re: Parsing Expression Grammar

A Pietu Pohjalainen <pohjalai@cc.helsinki.fi>
7 Sep 2005 13:11:27 -0400

          From comp.compilers

Related articles
Parsing Expression Grammar skjaero@gmail.com (2005-08-31)
Re: Parsing Expression Grammar lfinsto1@gwdg.de (Laurence Finston) (2005-09-02)
Re: Parsing Expression Grammar rsc@swtch.com (Russ Cox) (2005-09-02)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-09-02)
Re: Parsing Expression Grammar pohjalai@cc.helsinki.fi (A Pietu Pohjalainen) (2005-09-02)
Re: Parsing Expression Grammar owong@castortech.com (Oliver Wong) (2005-09-03)
Re: Parsing Expression Grammar pohjalai@cc.helsinki.fi (A Pietu Pohjalainen) (2005-09-07)
Re: Parsing Expression Grammar paul@highpersoft.com (Paul Mann) (2005-09-07)
Re: Parsing Expression Grammar wclodius@lanl.gov (2005-09-10)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-09-10)
Re: Parsing Expression Grammar gneuner2@comcast.net (George Neuner) (2005-09-10)
Re: Parsing Expression Grammar DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-09-10)
Re: Parsing Expression Grammar paul@parsetec.com (Paul Mann) (2005-09-11)
[21 later articles]
| List of all articles for this month |

From: A Pietu Pohjalainen <pohjalai@cc.helsinki.fi>
Newsgroups: comp.compilers
Date: 7 Sep 2005 13:11:27 -0400
Organization: University of Helsinki
References: 05-08-115 05-09-013 05-09-015
Keywords: parse

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


Post a followup to this message

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