[Haskell-cafe] Re: What *is* a DSL?
bob.atkey at ed.ac.uk
Thu Oct 22 09:44:22 EDT 2009
On Sat, 2009-10-10 at 20:12 +0200, Ben Franksen wrote:
> Since 'some' is defined recursively, this creates an infinite production for
> numbers that you can neither print nor otherwise analyse in finite time.
Yes, sorry, I should have been more careful there. One has to be careful
to handle EDSLs that have potentially infinite syntax properly.
> I can see at least two solutions: One is to parameterize everything over the
> type of terminals, too.
> The second solution (which I followed) is to break the recursion by adding
> another nonterminal to the NT type:
A third solution is to add the Kleene star to the grammar DSL, so the
representation of productions becomes:
> data Production nt a
> = Stop a
> | Terminal Char (Production nt a)
> | forall b. NonTerminal (nt b) (Production nt (b -> a))
> | forall b. Star (Production nt b) (Production nt ([b] -> a))
You also need to add the necessary parts for Alternative to the
Production type too, because they may be nested inside Star
> | Zero
> | Choose (Production nt a) (Production nt a)
The type Production nt is now directly an Applicative and an Alternative
and also has the combinator:
> star :: Production nt a -> Production nt [a]
> star p = Star p $ Stop id
The type of grammars is changed to (with the additional of the starting
nonterminal, as you point out):
> type Grammar nt = forall a. nt a -> Production nt a
It is probably also possible to write a function that converts grammars
with “Star”s in to ones without by introducing new non-terminals in the
way you did.
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.
More information about the Haskell-Cafe