Haskellians,<br><br>Here is an idea so obvious that someone else must have already thought of it and worked it all out. Consider the following grammar.<br><br>N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0 <br>N1 ::= T3 N0<br><br>where Ti (0 <= i < 4) are understood to be terminals.
<br><br>Using generics we can translate each production independently of the others. Like so:<br><br>[| N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0 |] <br>=<br>data N0 n1 = T0 n1 | T1 n1 (N0 n1) | T2 (N0 n1) (N0 n1) deriving (Eq, Show)
<br><br>[| N1 ::= T3 N0 |]<br>=<br>data N1 n0 = T3 n0 deriving (Eq, Show)<br><br>Then, we can compose the types to get the recursive grammar.<br><br>data G = N0 (N1 G) deriving (Eq, Show)<br><br>This approach has the apparent advantage of treating each production independently and yet being compositional.
<br><br>Now, let me de-obfuscate the grammar above. The first production should be very familiar.<br><br>Term ::= Var Name | Abstraction Name Term | Application Term Term<br><br>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 nicely.<br><br>The second production can be treated independently, but composes well with the first.<br><br>Name ::= Quote Term<br><br>This illustrates that a particularly interesting class of names is one that requires we look no further than our original (parametric) data type.
<br><br>So, my question is this. Does anyone have a reference for this approach to translation of grammars?<br><br>Best wishes,<br><br>--greg<br><br clear="all"><br>-- <br>L.G. Meredith<br>Managing Partner<br>Biosimilarity LLC
<br>505 N 72nd St<br>Seattle, WA 98103<br><br>+1 206.650.3740<br><br><a href="http://biosimilarity.blogspot.com">http://biosimilarity.blogspot.com</a>