[Haskell-cafe] grammars and generics

[Greg Meredith]

Dusan,

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.

Best wishes,

--greg

On Dec 11, 2007 11:33 AM, Dušan Kolář <kolar at fit.vutbr.cz> wrote:

> Hello,
>
>  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
>
> Dusan
>
>
> 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
>
> --
>
>


-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071211/93ab14b8/attachment-0001.htm