Re: Parsing Expression Grammar

Chris F Clark <cfc@world.std.com>
25 Sep 2005 23:44:50 -0400

          From comp.compilers

Related articles
[23 earlier articles]
Re: Parsing Expression Grammar rsc@swtch.com (Russ Cox) (2005-09-22)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-09-22)
Re: Parsing Expression Grammar schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-09-22)
Re: Parsing Expression Grammar paul@parsetec.com (Paul Mann) (2005-09-22)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-09-23)
Re: Parsing Expression Grammar gneuner2@comcast.net (George Neuner) (2005-09-25)
Re: Parsing Expression Grammar cfc@world.std.com (Chris F Clark) (2005-09-25)
Re: Parsing Expression Grammar cfc@TheWorld.com (Chris F Clark) (2005-09-27)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-09-27)
Re: Parsing Expression Grammar gneuner2@comcast.net (George Neuner) (2005-09-30)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-10-02)
Predicates (was: Parsing Expression Grammar) quinn-j@shaw.ca (Quinn Tyler Jackson) (2005-10-02)
Re: Predicates schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-10-04)
[2 later articles]
| List of all articles for this month |

From: Chris F Clark <cfc@world.std.com>
Newsgroups: comp.compilers
Date: 25 Sep 2005 23:44:50 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 05-09-023 05-09-045 05-09-053 05-09-107 05-09-121
Keywords: parse

I replied to George Neuner:
c>I think predicates are wonderful. I don't know that predicates
c>"require" mid-rule computations. Syntactic ones don't. Semantic
c>predicates "are" mid-rule computations, so yes they require them.


George Neuner <gneuner2@comcast.net> replied back:
g> That depends on your definitions ... syntactic predicates are extra
g> grammatic computation - meaning they are (generally) nicety rather
g> than necessity. Offhand I can't think of a case of a grammar that
g> could be written using a syntactic predicate but not without.


Syntactic predicates are far more than a nicety. There are two well
studied cases that one can parse with predicated grammars that one
can't (deterministically) parse with unpredicated ones: palindromes
{ w w**reverse } and multi-part matching { a**i b**i c**i }. Now,
perhaps those cases are mostly of theoretical importance.


However, syntactic predicates can also be used to resolve conflicts
(and ambiguities), which are a quite practical concern for compiler
writers. For example, If one has a context sensitive special case,
one can usually code the special case and the context up as a
predicate which is then used to parse only the special case part.
that way you tell the parser generator how much context and lookahead
to use to idetify the special case and make the parser generator's job
easier.


Moreover, predicates imply an ordering of the parsing space (just as
parsing expression grammars do), so that one can be certain that the
special case takes precedence over incidental matches with other
sequences. The advantage of predicates is that they apply this
ordering only in limited contexts, so that one knows eactly which
clauses to be careful with and not globally over the entire grammar.


My rule of thumb to Yacc++ users is first write your grammar without
any predicates or precedence rules. Then, look at the conflict
reports, and determine for each of the conflicts how you want the
problem resolved, and from that use either predicates or precedence
directives to guide the generator to parse those conflict situations
the way you want.


By the way, the C++ rule, of if it looks like a declaration it is, and
otherwise it is a statement can only be handled with a syntactic
predicate.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)


Post a followup to this message

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