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 constructors:
| 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. Bob -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336.