Re: A Grammar Writing Question

Hi Chris,


Just thought I had to answer to two of your points, although that's a
bit of a shameless advertisement for my research work.


Chris F Clark wrote:
> However, with a PEG, you need something that looks at the grammar and
> tells you that you need something like:
>
> part1: "a" b" (! "c" )
> / "a"
> ;
>
> And, I haven't seen any PEG tools that give you that warning. Perhaps
> they do and I just don't know enough about them. However, I suspect
> that generally giving such a warning is impossible, because it
> requires determining the intersection of two PEG grammar fragments
> (i.e. part1-> "a" "b" and what follows vs. part1->"a" and what
> follows).


This issue is called "disjointness" in Brian Ford's paper and is indeed
undecidable.


> That is the point, one wants to write grammars fairly naively. But,
> then, one wants a formal tool to check and prove one hasn't composed
> nonsense. We don't have good tools for that beyond LL and LR. As far
> as I know, we specifically don't have good tools for that when writing
> OCP/PEG/predicated grammars and we don't have good tools for the for
> GLR grammars either.


There are some recent attempts at tools for ambiguity detection, by
myself <http://www.i3s.unice.fr/~schmitz/> and by Claus Brabrand at
BRICS <http://www.brics.dk/~brabrand/grambiguity/>.


--
Cheers,


      Sylvain

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