[Haskell-cafe] grammars and generics
lgreg.meredith at biosimilarity.com
Tue Dec 11 14:36:31 EST 2007
Excellent point. To close it off, you need to add an "empty" alternative.
Thus, the corrected form would be
N0 ::= TEmpty | T0 N1 | T1 N1 N0 | T2 N0 N0
N1 ::= T3 N0
In the lambda calculus, this would show up as a constant term, say 0, that
would have to be treated in the operational semantics. See my ltu
posting<http://lambda-the-ultimate.org/node/1930>of a year ago.
On Dec 11, 2007 11:33 AM, Dušan Kolář <kolar at fit.vutbr.cz> wrote:
> I can't help you with the Haskell question as I'm not really in that
> much. Nevertheless, your grammar is non-generating one - that means, it
> cannot generate any sentence. If the starting non-terminal is N0 then
> there is no production generating a string of terminals, thus, both
> non-terminals (even if reachable from the staring one) are so called
> non-generating ones (they can be freely removed from the grammar and all
> involved productions too).
> Thus, you get empty grammar. Isn't that the problem? Shouldn't the
> grammar be like:
> N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0
> N1 ::= T3 T4
> Best regards
> 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
> > ------------------------------------------------------------------------
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> Dusan Kolar tel: +420 54 114 1238
> UIFS FIT VUT Brno fax: +420 54 114 1270
> Bozetechova 2 e-mail: kolar at fit.vutbr.cz
> Brno 612 66
> Czech Republic
505 N 72nd St
Seattle, WA 98103
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe