Re: Grammar for optional elements

Chris F Clark <>
Thu, 21 Jun 2007 00:48:02 -0400

          From comp.compilers

Related articles
[7 earlier articles]
Re: Grammar for optional elements (2007-06-18)
Re: Grammar for optional elements (Chris F Clark) (2007-06-19)
Re: Grammar for optional elements (Tony Finch) (2007-06-19)
Re: Grammar for optional elements (Lowell Thomas) (2007-06-19)
Re: Grammar for optional elements (Tony Finch) (2007-06-20)
Re: Grammar for optional elements (Detlef Meyer-Eltz) (2007-06-20)
Re: Grammar for optional elements (Chris F Clark) (2007-06-21)
Re: Grammar for optional elements (Tony Finch) (2007-06-21)
Re: Grammar for optional elements (Lowell Thomas) (2007-06-22)
Re: Grammar for optional elements (Chris F Clark) (2007-07-02)
A Grammar Writing Question (Lowell Thomas) (2007-07-23)
Re: A Grammar Writing Question (Chris F Clark) (2007-07-26)
Re: A Grammar Writing Question (glen herrmannsfeldt) (2007-07-26)
[4 later articles]
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: Thu, 21 Jun 2007 00:48:02 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 07-06-019 07-06-029 07-06-038 07-06-042
Keywords: parse
Posted-Date: 21 Jun 2007 01:26:16 EDT

Tony Finch <> writes:

> From: Tony Finch <>
> Subject: Re: Grammar for optional elements
> Keywords: parse
> Newsgroups: comp.compilers
> Date: 19 Jun 2007 17:56:36 +0100 (BST)
> Organization: dotat labs
> Chris F Clark <> wrote:
>>This is an interesting approach. It should work with predicate
>>grammars also, as long as they support negative predicates (negative
>>predicate = match this rule unless the lookahead is this regular
> Negative predicates have to be regular expressions in context-free
> languages - for example, ISO 14977 EBNF says:
> :NOTE -- If a syntactic-exception is permitted to be an arbitrary
> :syntactic-factor, Extended BNF could define a wider class of languages
> :than the context-free grammars, including attempts which lead to
> :Russell-like paradoxes, e.g.
> :
> : xx = "A" - xx;
> :
> :Is "A" an example of xx? Such licence is undesirable and the form of a
> :syntactic-exception is therefore restricted to cases that can be proved
> :to be safe. Thus whereas a syntactic-factor is in general equivalent to
> :some context-free grammar, a syntactic-exception is always equivalent
> :to some regular grammar. It may be shown that the difference between a
> :context-free grammar and a regular grammar is always another context-free
> :grammar; hence a syntactic-term (and hence any grammar defined according
> :to this standard) is equivalent to some context-free grammar.

Well, this is the first time I've ever heard of that restriction and
it doesn't describe any of the predicated parsing tools I've ever read
about. In particular, the entire point of accepting predicated
grammars is to allow grammars that are not context free. In fact,
every predicated parser generator (that I have seen) has an example of
parsing a**i b**i c**i which is a conanonical non-context free
language. (It should be noted that there are probably "predicated"
parsers that work differently than those I've read about, since I
haven't read about every parser generator in existence--I was unaware
of ABNF mentioned by Lowell Thomas in this thread, for example.)

So, the ISO people are probably trying to define a safe subset that is
strictly context free so that limited tools can handle it. (They also
seem to refer to it as a syntax exception rather than as a
predicate--I don't know if that is intentional as I haven't read that

However, that is definitely not what I mean by a predicated grammar,
and as one of the first users of the term--not the very first; Terence
Parr invented the term--I think I have the right to define what it
means and I'm certain Ter would agree with my definition as his PCCTS
example was also an a**i b**i c**i grammar--although his initial
predicates were positive in form only, but you could generally achieve
the negative effect by other means.

Moreover, as I recall from reading Bryan Ford's work, you will find
that he cites that it was inspired by predicates in PCCTS. In fact,
the basic characteristics of PEGs all derive from the way Ter
implemented predicates in PCCTS. Predicates allowed one rule to
depend on another rule (i.e. it allowed dependencies not just on a
regular expression, but an entire context-free and/or predicated
fragment). Second, predicates implied an ordering of alternatives,
which propogated to PEGs as the use of / for an ordered "OR" rather
than the traditional "|" which is an unordered "OR".

The genius of Bryan Ford's work was the realization that memoizing the
recognition guaranteed linear time performance. This is the key
feature that distinguishes a PEG from a predicated grammar. All of
the predicated parsers that I'm aware of allow predicates to cause
non-linear performance. However, aside from that characteristic,
there is essentially no difference between a PEG and a predicated
grammar. Well, to be precise the set of PEGs are a subset of the set
of predicated grammars. (And the reason for that is that there are
cases where you need the unordered | to express certain languages. In
addition, I believe there are also cases where some languages require
non-linear backtracking to express.)

Just trying to be clear,

Chris Clark Internet :
Compiler Resources, Inc. Web Site :
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.