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

["Jonathan Gibbons" <jonored@gmail.com>]

Just a couple quick points, more when I have time;

On 7/13/06, Seth Gordon <sethg@ropine.com> wrote:

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

While a pure CFG cannot determine a unique parse tree for that, it can
determine whether or not it is in the language. But that's more just a
nuance; CFGs define a language, and a language is just a set of
strings, whereas PEGs are set up to specify a one-to-one association
between a language and a set of parse trees as well as a language.

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

Only some of them are limited, because the algorithms that make them
more limited make them run much faster. There exist algorithms that
combine the ability to parse arbitrary CFGs with the effeciency of the
restricted versions when on inputs that they can handle; Generalised
LR, for instance, does this. It runs in O(n) time on LR inputs, and
O(n^3) on any input; to be impresice, which spot in between is
determined by the degree to which it is not LR.

-Jonathan