Re: [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
postingof a year ago.

Best wishes,

--greg

On Dec 11, 2007 11:33 AM, Dušan Kolář <[EMAIL PROTECTED]> 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@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
> --
>
>  Dusan Kolartel: +420 54 114 1238
>  UIFS FIT VUT Brno  fax: +420 54 114 1270
>  Bozetechova 2   e-mail: [EMAIL PROTECTED]
>  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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] grammars and generics

[Greg Meredith]

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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe