Re: Grammar for optional elements

Tony Finch <dot@dotat.at>
19 Jun 2007 17:56:36 +0100 (BST)

          From comp.compilers

Related articles
[3 earlier articles]
Re: Grammar for optional elements bobduff@shell01.TheWorld.com (Robert A Duff) (2007-06-16)
Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-06-16)
Re: Grammar for optional elements 148f3wg02@sneakemail.com (Karsten Nyblad) (2007-06-17)
Re: Grammar for optional elements dot@dotat.at (Tony Finch) (2007-06-17)
Re: Grammar for optional elements torbenm@app-2.diku.dk (2007-06-18)
Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-06-19)
Re: Grammar for optional elements dot@dotat.at (Tony Finch) (2007-06-19)
Re: Grammar for optional elements lowell@coasttocoastresearch.com (Lowell Thomas) (2007-06-19)
Re: Grammar for optional elements dot@dotat.at (Tony Finch) (2007-06-20)
Re: Grammar for optional elements Meyer-Eltz@t-online.de (Detlef Meyer-Eltz) (2007-06-20)
Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-06-21)
Re: Grammar for optional elements dot@dotat.at (Tony Finch) (2007-06-21)
Re: Grammar for optional elements lowell@coasttocoastresearch.com (Lowell Thomas) (2007-06-22)
[1 later articles]
| List of all articles for this month |

From: Tony Finch <dot@dotat.at>
Newsgroups: comp.compilers
Date: 19 Jun 2007 17:56:36 +0100 (BST)
Organization: dotat labs
References: 07-06-019 07-06-029 07-06-038
Keywords: parse
Posted-Date: 19 Jun 2007 13:42:57 EDT

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/


Post a followup to this message

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