[lojban] Re: Is Lojban a CFG? (was Re: [lojban-beginners] Re: Enumerating in Lojban)

["Jorge Llambías" <lojban-out@lojban.org>]

Tell me see if I have this right.

A CFG is a formal grammar with *production* rules of the
form X -> x, (for example sumti -> LE BRIVLA), that tell us how
to produce the construct on the left from the expression on the right.

A PEG is a formal grammar with *parsing* rules of the form
X <- x, (for example sumti <- LE BRIVLA), that tell us how to
parse/interpret the expression on the right.

In other words, a CFG is what the speaker needs (I want to produce
a sumti, how can I construct it?) and a PEG is what the listener needs
(I'm given the expression {LE BRIVLA}, how do I interpret it?)

Now, the nice thing about a CFG is that the speaker, in order to
produce grammatical output, If they want to produce a sumti they need
only look at the production rule for "sumti". That's what context-free means.

The nice thing about a PEG is that the listener, given any grammatical string,
is guaranteed that it can only be parsed in one way. There is no risk of
there being more than one way of parsing it.

If I'm not mistaken, for any CFG, there is a PEG that will accept all and
only the strings generated by that CFG. If that's correct, then what Jonathan
wants (a CFG for Lojban) is compatible with what Robin wants (a PEG for
Lojban). At least in principle, because maybe the required PEG might be
way too complicated to write. Or maybe not, we can at least try.

I think this is, simplifying, the kind of thing we would need the PEG to
do in order to handle the {li pa pa pa pa moi} example:

Current PEG rules:

sentence <- sumti* selbri sumti*
selbri <- number MOI
sumti <- LI number LOhO?
number <- PA+

Possible modification to make it context-free:

sentence <- sumti* selbri sumti*
selbri <- moi-number MOI
sumti <- LI li-number LOhO?
li-number <- PA (PA !MOI)*
moi-number <- PA+

But I don't know how hard it would be to modify the whole PEG so that it
fully corresponds to a CFG.

(Disclaimer: I'm not completely sure all of the above is right, I'm not an
expert on any of this.)

mu'o mi'e xorxes


To unsubscribe from this list, send mail to lojban-list-request@lojban.org
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
you're really stuck, send mail to secretary@lojban.org for help.