Greg Meredith wrote:
> Haskellians,
>
> 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. Like so:
>
> [| 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 very familiar.
>
> 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 nicely.
>
> The second production can be treated independently, but composes well
> with the first.
>
> 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?
>
> Best wishes,
>
> --greg
>
>
> --
> L.G. Meredith
> Managing Partner
> Biosimilarity LLC
> 505 N 72nd St
> Seattle, WA 98103
>
> +1 206.650.3740
>
>
http://biosimilarity.blogspot.com