Re: Grammar for optional elements

Tony Finch <dot@dotat.at> writes:


> From: Tony Finch <dot@dotat.at>
> 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 <cfc@shell01.TheWorld.com> 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
>>expression).
>
> 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
standard.)


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


*****************************************************************************
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)

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