Dusan,<br><br>Excellent point. To close it off, you need to add an "empty" alternative. Thus, the corrected form would be<br><br>N0 ::= TEmpty | T0 N1 | T1 N1 N0 | T2 N0 N0<br>N1 ::= T3 N0<br><br>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
<a href="http://lambda-the-ultimate.org/node/1930">ltu posting</a> of a year ago.<br><br>Best wishes,<br><br>--greg<br><br><div class="gmail_quote">On Dec 11, 2007 11:33 AM, Dušan Kolář <<a href="mailto:kolar@fit.vutbr.cz">
kolar@fit.vutbr.cz</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Hello,<br><br> I can't help you with the Haskell question as I'm not really in that
<br>much. Nevertheless, your grammar is non-generating one - that means, it<br>cannot generate any sentence. If the starting non-terminal is N0 then<br>there is no production generating a string of terminals, thus, both<br>
non-terminals (even if reachable from the staring one) are so called<br>non-generating ones (they can be freely removed from the grammar and all<br>involved productions too).<br>Thus, you get empty grammar. Isn't that the problem? Shouldn't the
<br>grammar be like:<br><div class="Ih2E3d"><br>N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0<br></div>N1 ::= T3 T4<br><br>?<br><br>Best regards<br><br>Dusan<br><div><div></div><div class="Wj3C7c"><br><br>Greg Meredith wrote:<br>> Haskellians,
<br>><br>> Here is an idea so obvious that someone else must have already thought<br>> of it and worked it all out. Consider the following grammar.<br>><br>> N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0<br>> N1 ::= T3 N0
<br>><br>> where Ti (0 <= i < 4) are understood to be terminals.<br>><br>> Using generics we can translate each production independently of the<br>> others. Like so:<br>><br>> [| N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0 |]
<br>> =<br>> data N0 n1 = T0 n1 | T1 n1 (N0 n1) | T2 (N0 n1) (N0 n1) deriving (Eq,<br>> Show)<br>><br>> [| N1 ::= T3 N0 |]<br>> =<br>> data N1 n0 = T3 n0 deriving (Eq, Show)<br>><br>> Then, we can compose the types to get the recursive grammar.
<br>><br>> data G = N0 (N1 G) deriving (Eq, Show)<br>><br>> This approach has the apparent advantage of treating each production<br>> independently and yet being compositional.<br>><br>> Now, let me de-obfuscate the grammar above. The first production
<br>> should be very familiar.<br>><br>> Term ::= Var Name | Abstraction Name Term | Application Term Term<br>><br>> The generics-based translation of this grammar yields something we<br>> already know: we can use lots of different types to work as
<br>> identifiers. This is something that the nominal of Gabbay, Pitts, et<br>> al, have factored out nicely.<br>><br>> The second production can be treated independently, but composes well<br>> with the first.
<br>><br>> Name ::= Quote Term<br>><br>> This illustrates that a particularly interesting class of names is one<br>> that requires we look no further than our original (parametric) data<br>> type.<br>>
<br>> So, my question is this. Does anyone have a reference for this<br>> approach to translation of grammars?<br>><br>> Best wishes,<br>><br>> --greg<br>><br>><br>> --<br>> L.G. Meredith<br>
> Managing Partner<br>> Biosimilarity LLC<br>> 505 N 72nd St<br>> Seattle, WA 98103<br>><br>> +1 206.650.3740<br>><br>> <a href="http://biosimilarity.blogspot.com" target="_blank">http://biosimilarity.blogspot.com
</a><br></div></div>> ------------------------------------------------------------------------<br>><br>> _______________________________________________<br>> Haskell-Cafe mailing list<br>> <a href="mailto:Haskell-Cafe@haskell.org">
Haskell-Cafe@haskell.org</a><br>> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>><br><br>--<br><br> Dusan Kolar tel: +420 54 114 1238
<br> UIFS FIT VUT Brno fax: +420 54 114 1270<br> Bozetechova 2 e-mail: <a href="mailto:kolar@fit.vutbr.cz">kolar@fit.vutbr.cz</a><br> Brno 612 66<br> Czech Republic<br><font color="#888888"><br>--<br><br></font>
</blockquote></div><br><br clear="all"><br>-- <br>L.G. Meredith<br>Managing Partner<br>Biosimilarity LLC<br>505 N 72nd St<br>Seattle, WA 98103<br><br>+1 206.650.3740<br><br><a href="http://biosimilarity.blogspot.com">http://biosimilarity.blogspot.com
</a>