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ář <[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 > > [email protected] > > 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: [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 [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
