Re: Extensible grammars

> My thinking is that this is a more 'well principled' way to extend
> grammars than textual modification. So the basic idea is to add a
> concept of 'nonterminal variable' and allow grammars to be
> parameterised, then provide a method of extension, and one for
> fixation, as in the Ocaml polymorphic variant example above.
>
> It's hard to believe I invented this idea, so:
>
> Are there any papers on this? Any hints or comments?


Tim Sheard's 2-level types come to mind (he attributes the idea to
Erik Meijer and gives other related references):


Two-Level Types and Parameterized Modules. With Emir Pasalic.
Expanded version of Generic Unification via Two-Level Types
and Parameterized Modules, with new examples.
JFP 14 (5):547-587, Sept. 2004
http://www.cs.pdx.edu/~sheard/papers/JfpPearl.ps


The idea has been used in several projects he has been involved
with. One project not mentioned in the paper is Programatica


http://www.cse.ogi.edu/PacSoft/projects/programatica/


which includes a complete Haskell 98 frontend, written in Haskell,
and uses the trick to share code between the Haskell frontend and
the Haskell+extensions frontend they need for their project.


>From what I've seen, the idea works, but there's a lot of clutter -
for large sets of mutually recursive grammar rules, you need some
way to hide the clutter. Compare, e.g., the standard Haskell 98
grammar/AST distributed in the Haskell libraries with the AST for
essentially the same language in the Programatica sources (eg,
HsExp in the former and the modules in line 7 in base/AST in the
latter) ..


http://www.haskell.org/ghc/docs/latest/html/libraries/haskell-src/Language.Haske
ll.Syntax.html


http://www.cse.ogi.edu/~hallgren/Programatica/tools/pfe.cgi


Essentially, you want the extra flexibility of open recursion and
explicit knot-tying only when you extend the grammar, and you
don't want to pay for that whenever you do any recursion over
the grammar. Tim suggests some basic helpers in the paper,
Programatica uses a lot more (hence multiple modules for each
group of grammar rules). There is still the feeling that they
ended up doing too much copy&paste in the traversal code,
which may partly be a matter of not using the opportunity (time
always presses, and copy&paste is tempting..).


When reusing Programatica's frontend for our Haskell Refactorer
HaRe (http://www.cs.kent.ac.uk/projects/refactor-fp/), we were
less interested in the extensibility (apart from being able to use
a sub-language of the one they are working on), and found it
essential to hide the clutter for analysis and transformation
traversals. We're happily using Strafunski for that purpose


http://www.cs.vu.nl/Strafunski/


which provides support for generic AST-traversals with
reduction strategies. So when we need a bottom-up or top-down
or whatever-until-some-condition traversal of the AST, we don't
need to bother with the recursive structure of the 2-level AST -
all the boilerplate code remains behind the scenes.


just one view,
claus

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