Re: CYK & Context-Free Expressions

On Apr 28, 12:58 pm, Tegiri Nenashi <TegiriNena...@xxxxxxxxx> wrote:
I fail to inderstand the significance of Earley algorithm. Before
going to Earley, however, let's stop at the CYK method for a moment.
Consider Fernando Pereira perspecive "Parsing as Deduction". Every
nonterminal S becomes a binary predicate S(x,y) written informally as
a statement: "The nonterminal S is valid at semiopen interval starting
at x and ended at y". Then, there is predicate join: S(x,y) & Q(y,z) -

For each grammar a kind of universal CYK grammar formed along these
lines. If you think in terms of matrices then for each rule
q -> z1 z2 ... zn
and each i0 <= i1 <= ... <= in, one has a set of rules
q(i0,in) -> z1(i0,i1) z2(i1,i2) ... zn(i_{n-1} in).
For each terminal x, and each i, one has
x(i,i+1) -> x.

When including an output alphabet Y then for each y in Y, one also has
the rule
y(i,i) -> y.

The CYK algorithm, itself, is then a method of winnowing down the
minimal subset of these rules that processes a given input. One finds
all the A(i,i+D) for D = 0 and for all terminals and non-terminals A;
then the same for D = 1, then for D = 2.

The result is, itself, a grammar. Its complexity is O(n^{k+1}).

Now, what is the Earley method?

I'll post a description of this. There is one on the Wikipedia
already, but not as good or clear as I think ought to be.

These constructs (forests,"node packing", etc) are too awkward to
genuinely believe for them to be the answer...

That's also why I long ago moved away from all the tree-based methods
toward something more algebraic. Context-free expressions are much
easier to work with and less awkward. One sees already the algebraic
imprint in the REX utility and related regular expression software (in
the comp.compilers archive) ... which has (by the way) found
application or translation in various settings like Perl, Prolog, XML,
etc.

BTW, speaking of trees, what is algebraic definition of tree
structure?

A tree is an element of a free magma.

A magma is an algebra consising of a signature subject to no axioms.
It's the same thing as a pure signature. The archetypical example is
the magma whose only operation is binary. Its elements are then, in
effect, binary trees.

A more interesting case arises when one starts to consider magmas that
are not free, e.g. commutative magmas, or magmas that possess
solutions to fixed point systems.
.

Relevant Pages

  • The Magic Algebra -- The Algebraic Approach to Control Flow Analysis
    ... Control Flow by Infinitary Expressions ... Multiple Objects and the Extended Magic Algebra ... what's known as a MAGMA. ... For assignment statements involving simple variables, the context ...
    (comp.compilers)
  • Re: CYK & Context-Free Expressions
    ... A magma is an "algebra without axioms". ... comprising a signature plus no axioms. ...
    (comp.theory)
  • Re: Algebraic extensions of semirings
    ... deal with algebraic extensions of fields? ... the appropriate venue would be closer to Universal Algebra ... This is a magma. ... subject to the equivalence relations produced by the relation set r. ...
    (sci.math.research)
  • Re: What is a Complete Algebra!?
    ... Does the rank of supporting algebraic structure help in this!? ... I mean is an algebra based on a magma less complete than an algebra defined on a ring!? ...
    (sci.math)
  • What is a Complete Algebra!?
    ... Does the rank of supporting algebraic structure help in this!? ... I mean is an algebra based on a magma less complete than an algebra defined on a ring!? ...
    (sci.math)