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
postinghttp://lambda-the-ultimate.org/node/1930of a year ago.
Best wishes,
--greg
On Dec 11, 2007 11:33 AM, Dušan Kolář
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 Kolar tel: +420 54 114 1238 UIFS FIT VUT Brno fax: +420 54 114 1270 Bozetechova 2 e-mail: kolar@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