Re: Grammar for optional elements

Chris F Clark <cfc@shell01.TheWorld.com> wrote:
>Tony Finch <dot@dotat.at> writes:
>> 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: [...]
>
>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.


Ah, when you mentioned regular expressions it reminded me of the ISO
EBNF lookahead restriction, and I thought it notable that PEGs do not
have a similar restriction.


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


Interesting. Do you have any examples or citations? Ford's paper on the
formal properties of PEGs says that it is an open question whether there
are context-free languages that cannot be described with PEGs, and I
wonder if ordered choice is relevant.


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

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