A Grammar Writing Question

Chris F Clark <cfc@shell01.TheWorld.com> wrote: (07-06-053)
>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.)


Tony Finch <dot@dotat.at> wrote: (07-06-054)
>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.


Chris F Clark <cfc@shell01.TheWorld.com> wrote: (07-07-009)
>I've been trying to track down where I read about ordered choice using
>google and haven't had any luck yet ... perhaps the author
>of the paper/web page I was reading will happen to read this,
>recognize that I am refering to them, and chime in.


I'm also interested in this question. It may be a bit off topic for the
original thread these quotes are from, so I wanted to rephrase the question.
In my limited experience with grammar (re-)writing I have never come across
a language situation that I couldn't resolve with an ordered-choice parser
(OCP, one that tries alternates from an ordered list and accepts the first
match, ignoring any other possible matches in the list.) I've often
suspected that the reason Ford couldn't prove that there are context-free
languages that cannot be described with a PEG is that none exist. I've often
seen criticisms of OCP (but don't have any references handy) on the grounds
that they miss some of the valid language strings that the grammar allows.
This is, of course, true if your objective is to start with a grammar and
then ask for the complete language that it describes. But it seems to me
that most practical situations have it the other way around. Given a
specific problem, you first conceptualize the kinds of strings the language
must contain and then try to write a grammar that generates them. Grammar
writing is, so it seems to me, where the rubber meets the road between human
creativity and automata.


So the question is, can anyone point out a practical situation where the
language truly requires an exhaustive parser (one that pursues all possible
ambiguities)? Also, can anyone provide a practical example of an exponential
grammar (O(n**x), n = string length, x>1)?


Thanks,
Lowell Thomas
www.coasttocoastresearch.com


P.S. My limited experience suggests another possible benefit to OCP grammar
writing. The ambiguities that cause trouble for an OCP usually look to me
like they would create a lot thrashing, dead ends and backtracking for an
exhaustive parser. Working out those kinks in the grammar not only makes it
work with an OCP, but might also greatly improve it for use by any other
parser as well. Any comments on this?

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