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ář [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
