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

[Seth Gordon <sethg@ropine.com>]

Jorge Llambías wrote:
> 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?)

Both CFGs and PEGs define a grammar to be used in a parser, so they're
"what the listener needs", but the parsers that use them work in
different ways.

A PEG-based parser starts by saying to itself, "OK, I want to parse a
bridi.  Here's the first word of my input... 'le' ... well, that could
be part of a sumti ... let's see what the next word is ... 'broda' ...
OK, that's a sumti, now I'm looking for another sumti ... whoops, the
next word is 'be'...."  It formulates hypotheses as it goes about what
grammatical construction it's in the middle of.  When it reads a word
that invalidates its working hypothesis, it goes back to its grammar to
come up with the next  interpretation of the text that would be
consistent with the grammar.  This process continues until the whole
input is parsed (or fails to parse).

A CFG-based parser uses Deep Computer Science Magic to translate its
input grammar into a state machine, and then processes its input by
saying "OK, I'm in state 0.  Here's the first word of my input ...
'le'... that puts me in state 71 ... here's the next word ... 'broda'
... that puts me in state 96 and by the way, 'le broda' is a sumti ...
'be ... now I'm in state 32...."  It formulates no hypotheses about what
grammatical constructions it's in the middle of; it just follows the
state machine, and the elements of the parse tree pop out of there.
(See http://en.wikipedia.org/wiki/LR_parser for more grimy details.)

PEG-based parsers are less efficient than CFG-based ones, since the
parser might have to backtrack at any point up until the entire input
was read.  (Bryan Ford, in 2002, designed a "packrat parser" for parsing
with PEGs, which sacrifices memory for speed.)

> 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.

CFG and PEG are not just two different ways to express the same grammar.
 For example, a pure CFG can't determine how to parse "if a then if b
then s1 else s2" (is the "else" connected to the first "if", or the
second?); since PEGs are always unambiguous, they can.

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

Another complication is that the tools that build parsers from CFGs
cannot handle any arbitrary CFG; there are constraints on the
permissible grammars that are necessary to make the state tables manageable.


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.