Re: Grammar for optional elements

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.


However PEG languages are not necessarily context-free - arbitraty
lookaheads are permitted. There are many ways of screwing up a PEG
parser, including left recursion as well as paradoxes.


>The attr1 rule uses a ! which should mean it applies unless the
>lookahead is "attr* attr1 attr*". Ok, so if there is another attr1
>later in the sequence it won't apply, so a sequence like attr1 attr2
>attr1 is rejected. However, now such a sequence is not an attr. Does
>that mean that a sequence like attr1 attr1 attr2 attr1 can match (for
>one token), since the second attr1 is not matched as one, which means
>the first attr is not followed by the prohibited sequence? I guess
>the point I'm asking is whether the proposed grammar has the
>(desirable) fails on first error property. It definitely fails
>whenever there is an error. However, does it point out the first
>occurence?


I believe what will happen is that it will fail right at the start
(or rather, succeed consuming no input since the grammar I posted did
not have an EOF anchor on its right hand end), since the attr1 rule
will fail (because of the lookahead) and therefore consume no input,
and no other attr rule will succeed because of the initial keyword. To
get good error messages in the presence of this backtracking, the parser
needs a bit more machinery (as described in Bryan Ford's thesis).


Tony.
--
f.a.n.finch <dot@dotat.at> http://dotat.at/

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