[Haskell-cafe] grammars and generics
lgreg.meredith at biosimilarity.com
Tue Dec 11 14:00:24 EST 2007
Here is an idea so obvious that someone else must have already thought of it
and worked it all out. Consider the following grammar.
N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0
N1 ::= T3 N0
where Ti (0 <= i < 4) are understood to be terminals.
Using generics we can translate each production independently of the others.
[| N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0 |]
data N0 n1 = T0 n1 | T1 n1 (N0 n1) | T2 (N0 n1) (N0 n1) deriving (Eq, Show)
[| N1 ::= T3 N0 |]
data N1 n0 = T3 n0 deriving (Eq, Show)
Then, we can compose the types to get the recursive grammar.
data G = N0 (N1 G) deriving (Eq, Show)
This approach has the apparent advantage of treating each production
independently and yet being compositional.
Now, let me de-obfuscate the grammar above. The first production should be
Term ::= Var Name | Abstraction Name Term | Application Term Term
The generics-based translation of this grammar yields something we already
know: we can use lots of different types to work as identifiers. This is
something that the nominal of Gabbay, Pitts, et al, have factored out
The second production can be treated independently, but composes well with
Name ::= Quote Term
This illustrates that a particularly interesting class of names is one that
requires we look no further than our original (parametric) data type.
So, my question is this. Does anyone have a reference for this approach to
translation of grammars?
505 N 72nd St
Seattle, WA 98103
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe