Re: Grammar for optional elements

Tony Finch <dot@dotat.at>
21 Jun 2007 10:22:26 +0100 (BST)

          From comp.compilers

Related articles
[8 earlier articles]
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)
Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-07-02)
| List of all articles for this month |

From: Tony Finch <dot@dotat.at>
Newsgroups: comp.compilers
Date: 21 Jun 2007 10:22:26 +0100 (BST)
Organization: dotat labs
References: 07-06-019 07-06-038 07-06-042 07-06-053
Keywords: parse
Posted-Date: 22 Jun 2007 00:57:32 EDT

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/


Post a followup to this message

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