Lambda the Ultimate

I find combining parsing and type checking to be interesting, as you can have a typed stack for type-safe parsing, however the downside is that the algorithms for parsing and type checking become conflated, increasing the complexity of code in a single module. There is something to be said for separating concerns and keeping parsing and type inference/checking as separate passes.

Thank you for your comment.

On this, though:

keeping parsing and type inference/checking as separate passes

sorry for the confusion, maybe I should have put it more explicitly in my post. It's actually not about mixing parsing and type inference in the usual sense of both. It's more about leveraging what is known about strong normalization in the latter towards the former.

It's only about a CFL parsing objective in the post, and only for grammars in CNF, specifically. There's nothing about type inference going on further, semantically / interpretatively speaking (eg, that would in turn be used to guide some subsequent parse tree transformation, eg, for code generation, or, etc)

But true, at the core, the (admittedly, strange?) curiosity I had is to explore the applicability of the strong normalization property of the β-reduction rule found in the STLC (and the likes) to the a priori unrelated problem of CFL parsing, thru this S-expr rewriting scheme I've described.

The latter sort of / so to speak "type-annotates" a reification (thru mutating S-exprs after Lc) of the ongoing parsing progress itself, as it also carries out its traditional primary operation -- parse tree construction.

Hence, the genuine question, btw:

is it known whether (or not) the parsing of sentences that belong to a language described by an (unambiguous) CFG is in fact computably equivalent(?) or nearly, to finding the principal type of a well-formed term in a type system having the principal type property?

There is something to be said for separating concerns and keeping parsing and type inference/checking as separate passes.

I think you can accomplish this via shallow transformations. That is, you parse and type check totally separately, but interleave them level-by-level, node-by-node as you traverse the syntax tree. This means you actually have three separate concerns: 1) parsing 2) type checking and 3) AST traversal.

Assume you're parsing independently from reading, so you've already got some s-expr in memory. For example, you may parse (if b (f x) (g y)) in to something like (if-node (symbol "b") (list (symbol "f") (symbol "x") ... without recursively parsing the arguments. Then a full-parse is defined by (traverse shallow-parse sexpr). Then you can also do something like (traverse (compose shallow-check shallow-parse) sexpr). The tricky part, of course, is that you need to thread context through and the traversal needs to be able to change the shape of the result, etc.

Why do they become conflated?

In my (as yet unimplemented) design the type checking is static and done entirely by the compiler (i.e. the host language type checker). Instead, the burden is on the grammar writer to get the types right. Obviously, one has to actually compile such a parser.

Basically the parser at present uses an untyped parser stack, and AST nodes are essentially S-expressions. If instead we switch to a typed stack, the stack type is determined by the compiler from the action codes in the productions.

I have had this working in a weak way but the type combinators were not representable. Since then I have added GADTs to the language so that typed pushes and pops from the parser stack are representable.

[I have some extra tricky stuff to handles since the data types associated with a symbol are not the attribute type, but channels which transmit that attribute. So when generating AST terms, I'm dealing with a parser stack of typed channels which have synchronisation requirements above and beyond a standard spatial product]

By conflated I mean you cannot write one algorithm without knowledge of how the other one works. In a clean multi-pass system the parser outputs an AST of untyped nodes (and type annotations), and the type inference/checker is in a separate pass. No knowledge of the parser node generation order is needed to write the checker, and no knowledge of the checker is needed to write the parser. They can be written by deferent people and take different approaches to order, parallelism, etc. The only commonality is the agreed AST format. You can even completely change the parsing or checking algorithm independently with no problems.

It should be clear that any attempt to type the stack requires the parser to check as it goes along, which precludes separating the passes, and prevents the independent selection of algorithms.

This is only non-deterministic to parse in a logic that does not allow for probabilities. If you abandon the black and white of binary logic , you can construct a graph representing the situation. The 'I' object is linked to the 'elephant' object by a 'shot' relationship (in the direction "I ---shot--> elephant" with a probability of 100%. 'pajamas' is linked to both 'I' and 'elephant' with a 'worn by' relation, with a probability of say 50% each. At this point the weighting can be adjusted based on prior experience, say for example the number of times thus sentence structure has been used, and subsequent information has resolved the bifurcation one way or the other (let's guess 80% 'I', 20% 'elephant').

In any case, there is not necessarily any non-determinism here, there need not be different parse orders, nor multiple outputs of complete parses). This only occurs if you view the output with a binary understanding of truth.

Sorry, no, I'm not interested in dealing with ambiguous grammars. Or parse forests.

More humbly, I'm just exploring how far can we go with non-ambiguous CFGs and for hopefully cheaper in time / space complexity (of parsing).

As far as I can tell, you've reinvented RL(0) parsing. If you try the reverse grammar, you should see why it doesn't always work.

I don't know about RL(0) parsing and I don't see what you mean by "reverse" the grammar? Can you provide an example in CNF?

Knuth introduced it in the first paper on LR parsing from 1965, "On the translation of languages from left to right." (I cannot over-emphasize the importance of reading original sources.) It's defined symmetrically to LR(0); you can think of it as LR(0) on the reversed grammar and input. The "reversed" grammar just means reverse the symbols on the right hand side of every production rule. E.g., the reverse of (G2) is:

S -> Q H
H -> A C
Q -> U B
Q -> V B
U -> Y X
V -> Z X

with the same rules for A, B, C, X, Y, Z as before. It describes the reversed language, { yxbac, zxbac }. This should be the hard case for your method as it's not RL(0) or even RL(1), although it's LR(0).

Ah ok, thanks for the pointer. Now I see. So you were alluding to what could possibly be a right-to-left vs. left-to-right input processing sensitivity of the method.

Fair concern, that needs to be checked, yes.

Given,

yxbac

can we parse it against,

(G3)

S -> Q H
H -> A C
Q -> U B
Q -> V B
U -> Y X
V -> Z X
C -> c
A -> a
B -> b
X -> x
Y -> y
Z -> z

with the same algorithm?

With Lc = all of the input s, and Rc empty initially;

R1: whenever Lc ends in w, and there is U -> w in the grammar, rewrite:

Lc , Rc ~> Lc \ w     , ( U w )  Rc
(shorter by w)^                  ^(same)

R2: whenever Rc = ( P x ) ( R y ) ... and there is U -> P R in the grammar, rewrite:

Lc , Rc ~> Lc , ( U ( P x ) ( R y ) ) ...
     (same)^                          ^tail(tail(Rc))

Stop when either Lc is empty and/or neither of R1 or R2 is applicable;

s is a word of the language iff Rc = ( S ... ) where S is the grammar start symbol.

Here is the full derivation:

Lc            Rc

( y x b a c ) ( ) init.
( y x b a )   ( C c ) via R1
( y x b )     ( A a ) ( C c ) via R1
( y x b )     ( H ( A a ) ( C c ) ) via R2
( y x )       ( B b ) ( H ( A a ) ( C c ) ) via R1
( y )         ( X x ) ( B b ) ( H ( A a ) ( C c ) ) via R1
( )           ( Y y ) ( X x ) ( B b ) ( H ( A a ) ( C c ) ) via R1
( )           ( U ( Y y ) ( X x ) ) ( B b ) ( H ( A a ) ( C c ) ) via R2
( )           ( Q ( U ( Y y ) ( X x ) ) ( B b ) ) ( H ( A a ) ( C c ) ) via R2
( )           ( S ( Q ( U ( Y y ) ( X x ) ) ( B b ) ) ( H ( A a ) ( C c ) ) ) via R2

Success, yxbac is a word of the language generated by (G3), as we have a final Rc representation of the parse tree, with S at the root:

y   x b   a   c
|   | |   |   |
Y   X |   |   |
 \ /  |   |   |
  U   B   A   C
   \ /     \ /
    Q       H
     \     /
        S

My mistake. I didn't bother to check that your transformation of G1 to CNF preserved the property of not being LR(1); I think G2 is actually LR(0) so that G3 is RL(0). Try G4:

S -> Q
Q -> Y P
Q -> Z R
P -> X A
R -> X B
A -> a
B -> a
X -> x
Y -> y
Z -> z

which generates "yxa" and "zxa". I made sure this one isn't RL(0).

Granted, your grammar isn't usable as-is for my algorithm if only because of productions like these:

A -> a

B -> a

(I was already aware of that, at least.)

But we can rewrite it in this grammar (arguably, simpler also), in the same LL / LR / RL classes (unsure?)

S -> Q
Q -> Y P
Q -> Z P
P -> X A
A -> a
X -> x
Y -> y
Z -> z

which generates the same language, and still without ambiguity --

both points obviously desirable (as I had no interest in parsing against inherently ambiguous grammars or languages anyway).

Then,

Lc        Rc

( y x a ) ( ) init.
( y x )   ( A a ) via R1
( y )     ( X x ) ( A a ) via R1
( y )     ( P ( X x ) ( A a ) ) via R2
( )       ( Y y ) ( P ( X x ) ( A a ) ) via R1
( )       ( Q ( Y y ) ( P ( X x ) ( A a ) ) ) via R2
( )       ( S ( Q ( Y y ) ( P ( X x ) ( A a ) ) ) ) via R2

(Success)

and

Lc        Rc

( z x a ) ( ) init.
( z x )   ( A a ) via R1
( z )     ( X x ) ( A a ) via R1
( z )     ( P ( X x ) ( A a ) ) via R2
( )       ( Z z ) ( P ( X x ) ( A a ) ) via R1
( )       ( Q ( Z z ) ( P ( X x ) ( A a ) ) ) via R2
( )       ( S ( Q ( Z z ) ( P ( X x ) ( A a ) ) ) ) via R2

(Success)

I really should take the time to write a minimal implementation finally, instead of executing this by hand.

Thanks for stressing it, though.

Right. I mainly wanted to point out that you're on well trodden ground here. Your earlier posts made it sound like you were claiming to have a linear algorithm capable of parsing arbitrary unambiguous CFGs in CNF. In fact, what you have is something strictly weaker than RL(0), I think (because the state stack provides more opportunities to determine which of two applicable reductions is the right one). This is a perfectly respectable approach, but you should expect to run into all of the same issues that deterministic left to right parsers run into, just in their symmetric form. In particular, determining whether a given "naturally" expressed CFG is unambiguous and can be refactored somehow to the class of grammars accepted by your parser is in general a far from trivial problem.

I mainly wanted to point out that you're on well trodden ground here. Your earlier posts made it sound like you were claiming to have a linear algorithm capable of parsing arbitrary unambiguous CFGs in CNF.

Be reassured I took all your comments here that way. And I did make a hasty claim that I know by now is false. Thank Andrew who was quick to make me think harder. And you, pointed out to me good, relevant knownledge I must keep in mind, so thank you.

What I still don't know is if I put the finger on something new anywhere between (excluded) linear time and cubic time.

But, code is fun anyway :)

The example is somewhat synthetic as the grammar is a pathological case of describing the language. The language itself is LL(0), although the grammar is artificially constructed to make a non-LR(1) representation of it.

How would your algorithm handle cleaner cases: for example \( L = \{ x^i\cdot y^j | i>y \} \), where the language itself is LR, rather than LL.

And another great point you make, thank you for that.

Well, as you can see, James is stressing it against the RL cases, while so far I had only played with a few LL / non-LL / LR / non-LR toy grammars. But I must reckon I haven't done much checking yet on the intrinsic properties of the languages themselves.

If you have some examples readily expressed in CNF and parseable only thru the most general methods such as CYK (because too difficult to express with LL / LR / RL grammars otherwise) I'll be glad, in fact, very interested, to check them out.

I'll think about this one you just gave.

Thank you!

Okay, so that was a bit tedious (for me, anyway) to get it right in CNF, but I couldn't resist / was feeling too itchy to not know:

For the language { a^i b^j, i > j > 0 } described by,

S -> a S | a P
P -> a P b | a b

(which Grammophone reports as SLR(1), LALR(1), and LR(1), but not LL(1) and not LR(0))

here's a possible CNF version of it, for the same language:

S -> A S
S -> A P
P -> A Q
P -> A B
Q -> P B
A -> a
B -> b

(maybe there's a simpler one?)

which generates, eg,

a a b
a a a b
a a a b b
a a a a b
a a a a b b
a a a a a b
a a a a b b b

(... etc)

And for the input,

s = a a a b b

the full derivation is:

 ( a a a b b ) ( ) init. 
 ( a a a b )   ( B b ) via R1
 ( a a a )     ( B b ) ( B b ) via R1
 ( a a )       ( A a ) ( B b ) ( B b ) via R1
 ( a a )       ( P ( A a ) ( B b ) ) ( B b ) via R2
 ( a a )       ( Q ( P ( A a ) ( B b ) ) ( B b ) ) via R2
 ( a )         ( A a ) ( Q ( P ( A a ) ( B b ) ) ( B b ) ) via R1
 ( a )         ( P ( A a ) ( Q ( P ( A a ) ( B b ) ) ( B b ) ) ) via R2
 ( )           ( A a ) ( P ( A a ) ( Q ( P ( A a ) ( B b ) ) ( B b ) ) ) via R1
 ( )           ( S ( A a ) ( P ( A a ) ( Q ( P ( A a ) ( B b ) ) ( B b ) ) ) ) via R2

(Success)

I think you've described an RR parser. The processing rules for the tail of Lc are definitely describing a right-to-left processing of the input string. It looks like it builds rightmost derivations in that example, as part of the process of applying a new root to the tree in the Rc looks like the handle reduction in an LR parser.

Boundary cases for language classes are somewhat difficult to find. I actually found that one on stackoverflow a few months ago as I've been looking at ways to implement something a little bit more sane than bison to give to students to work with. That has slowly morphed into reimplementing parsec in c++, which seems to be interesting enough in its own way.

If anybody knows of any more boundary cases, e.g. a simple language that is context-free but not in LR then I would also be very interested in seeing them. There a slightly more complex version of your natural language example on the wiki page for CYK. I guess its well known which class it is in, but I would have to think about it for a while to try to work it out.

The notes about complexity at the bottom imply that the minimum complexity for parsing should be \( \mathcal{O}(n^2\cdot|G|) \) - I think, from memory the predicted best case for binary matrix multiplication is \( \mathcal{O}(n^2) \), but it is not known how to achieve it as it would yield a linear time multiplication algorithm for the integers. I have to repeat this is from memory, so I'm entirely sure. But I suspect this means there is a missing term in your complexity analysis. It would probably show up on an example of a grammar from a hard language....

Well, I shall know soon about that, with an actual implementation, less toy-ish grammars, and much longer inputs.

Both CYK and my algorithm are easy to implement and are mostly of theoretical interest, I'd agree with that.

Just to be clear, myself, I'm still not quite 100% sure about the generality of my method or its actual complexity, so I can surely understand the skepticism here.

But just like a naive recursive Fibonacci can eat the entire computer stack or take days to terminate as opposed to milliseconds for the non-recursive version, a few actually executable and less trivial test cases should tell us in a more definitive way (eg, when compared to CYK's) what this algorithm's actual O(...) looks like eventually.

I'm a little skeptical about the complexity - but I would emphasize the word "little" rather than the word skeptical. I think what you've done looks really interesting and I would definitely like to see more about it. The traces that you've shown to illustrate how the algorithm works are very clear and easy to follow. Looking at the way it folds up the parse tree for the LR boundary case gives me the feeling that you have something very interesting here. The steps that it goes through to consume the string from Lc, and build up the tree in Rc, are very simple. This suggests that small set of evaluation steps could be quite powerful.

Definitely looking forward to reading more about it as you work out the details.

Thanks for the encouragement. I'll try to find time over the next few days, if the domestic allows...

Btw, on your other comment re: the traditional state stack as found in bottom up LR methods, my feeling is mine gets its information flow over time embedded in fact in that S expr that it builds as that parse tree's right-most derivative, sort of (just my intuition). My algorithm eats the input's terminals from one end to the other, and in the process refines the parse at the point Lc \ w by digging into the prior state of that parse on the right, not just by a lookahead token, because there isn't any, really, as we've already noticed.

Yet, this does seem enough to actually parse against grammars from various classes, just as CYK does. Arguably, CYK doesn't have any look ahead either, does it? Hence why I believe that I'm closer to have found a variant of CYK if anything, than to have a weaker or stronger LR or RL. The right-to-left direction I chose doesn't seem to matter in fact, to effectively get a correct parse tree, before or after reversing a grammar. (James made a good point it's something to be aware of potentially impacting the generality and effectiveness, though.) So, that's what I find intriguing from the start, this independence to the grammar "shape", and made me think of an analogy with the inside-out information flow of the App rule in H-M type inference, that doesn't care about the order in which the argument types have been introduced (relative to one another), before calling Unify(...) -- but okay, no idea if that'll make sense to anyone else but me so far.

More practically, what ballpark of test grammar sizes and input lengths would you recommend me to prepare and feed the unbiased computer to answer us more convincingly and definitively, either way?

(Toys may be important to test ideas, but are rather boring when it's demo time, so while I'm at it...)

After editing the above comment, that finally sunk in:

why the effectiveness of my algorithm seems independent to the choice of direction for eating the input?

Well, I suspect it's simply because of the shape of a CFG in CNF with respect to shift and reduce operations: it is totally symmetric for both of them (ie, the computations they carry out). "Duh."

Indeed, for the CYK algorithm also, it just doesn't matter for building the parse tree, which direction you used to reduce the terminals on the diagonal of the matrix... The other steps don't need to care... because the CNF will still be symmetric in essence anyway, modulo the pair: language described vs. input being processed.

And you know what is also the invariant location where to find (or not) the reduction to the grammar start symbol, if the word belongs to the language (or not) -- for CYK, it's "in that corner, over there, facing the diagonal", can be nowhere else; for my algorithm, it's that last, single outer S-expr, can be nowhere else.

I'm thinking of benchmarking it vs. CYK for |G| ~ 20 to 50 productions, and input lengths ~ 1,000 to 10,000 terminals (*)

Thoughts?

(* typical of what a human can grok in minutes throughout a few pages, be it in a natural or computer language)

The failure that James was looking for:

The reverse of this language is,

{ b^i a^j, 0 < i < j }

Here's the (obviously) working CNF version:

S -> S A
S -> P A
P -> Q A
P -> B A
Q -> B P
A -> a
B -> b

(interestingly enough, btw: still not LL(1) or LR(0), but still SLR(1), LALR(1), and LR(1), says Grammophone)

So, my algorithm lamentably fails on it... while it worked like a charm on its mirror, and other mirrored languages. Was just "bad-good luck".

But this language is "nastily" anti symmetric so to speak.

So, I made another false claim earlier in my "Why the independence" comment.

Thus, as it stands in the post, the algorithm is in fact, not independent of the direction of eating the terminals, for such pairs of mirrored languages.

Thank you Andrew and James, that's team work, now :)

But, guess what, there is a way to amend (almost trivially) the algorithm, to make it parse correctly against both grammars / recognize words from either mirrored languages.

Just... guess how! :)

Hint: time vs space (but not in complexity, in logic, rather).

At each step, we have a left context Lc consisting of n-i terminals if n is the input's length, for i varying from 0 to n-1.

The right context Rc is an evolving S-expr capturing what has already been reduced from either forms of productions in the CNF.

At each iteration, from the one (or two) S-exprs cached at the head of Rc (ie, the leftmost ones, S1 and S2 in Rc = S1 S2... Sk) we know which right hand side, eg, P and R, in productions of the form

U -> P R

we need to look up in G.

That's because S1 and S2 will be of the form (P (some child S-expr...)) and (R (some child S-expr...)) assuming P and R have already been reduced from former states of Rc (from past greater values of n-i, or smaller ones of i, equivalently).

The look up of the pair P R is bounded in proportion to / linear in |G|, but can be improved if we have provisioned for instance with an inverse map with keys that are those pairs onto values that are the productions. We cannot avoid this lookup of course throughout all of the input, but it needs to be done no more than once at each iteration, hence my O(|G| * n) estimates.

but it needs to be done no more than once

(Wrong. See Andrew's comment below.)

My bad Andrew. I finally got your point. Thank you. I'm slow. You're right in that this lookup wouldn't be only in O(|G|).

Actually, the per iteration-cost would be more likely in O(|G| * log n) for the parse trees induced by the general shape of the CNF, because, at each step, as you point out, we have on average a potential of applicable reductions proportional to the depth of what is the actual parse (always binary) tree, not just one (reduction).

So, I'd re-estimate overall as O(|G| n log n). I'll try to lay it out more thoroughly using the usual T(n) formulas with a complexity analysis more worth of the name.

E.g., just looking at the non-LR(1) example (as I should have noticed much earlier) :

n = 5

depth of parse tree = 4

5 * log24 = 10

corresponding, seemingly, to the 9 or 10 steps of what turns out to be the actual derivation (only excluding the lookups over G, for an extra time complexity factor in O(|G|)).

So, I'd re-estimate overall as O(|G| n log n)

Heck, not. Revised below.

Your attentive criticism is the sort of feedback I was / am hoping for. Thank you.

Tests updated with two more languages found in the literature; cf. 06-basic-grammar.txt / 06-basic-input.txt and 07-basic-grammar.txt / 07-basic-input.txt.

Interesting results for the longest inputs; cf. test-results-CYK-20170228.txt vs. test-results-CJ2-20170228.txt.

See the notes, btw.

I think I'm just going to continue fishing for a bunch of grammars mentioned by LL / LR / GLR users and see where that takes us after CNF conversion.

Informally

The kernel of a (context-free) language relative to a (context-free) grammar that describes it, is the set of pairs of terminals at least one element of which (aka, "a kernel witness") appears at least once, for any word of the language; IOW, any word of the language thus contains at least one witness instance, or more, from that kernel (different words containing different witnesses);

further, there is this exactly one witness instance in the word which leads to the full parse tree (via the given grammar's applicable reductions), after computing both the rightmost and leftmost parse tree derivatives, at the point of that witness instance (that we may call, say, "the parse witness", among possibly other witnesses also present) of the input word.

More formally

Given a context-free language L described by a context-free grammar G (in CNF),

G = (N, T, P, S) where N is the set of nonterminals, T is the set of terminals, P is the set of productions, and S is the start symbol,

we define,

the kernel K(L/G) of L relative to G,

K(L/G) = { A . B in N2, such that (starting from the production(s) S -> U V), A is in dL(U) and B is in dR(V) }

with, for all X in N,

dL(X) = {
  if X -> w in P, and there is Y -> C X in P
  reachable from U in S -> U V:
  include X
or
  if X -> A B in P, and there is Y -> C X in P
  reachable from U in S -> U V:
  include all of dL(B) (by transitive closure)
}

dR(X) = {
  if X -> w in P, and there is Y -> X D in P
  reachable from V in S -> U V:
  include X
or
  if X -> A B in P, and there is Y -> X D in P
  reachable from V in S -> U V:
  include all of dR(A) (by transitive closure)
}

Eg, with the Wikipedia example:

https://en.wikipedia.org/wiki/CYK_algorithm#Example

K(L/G) = { N . V, NP . V }

(ie, the set of two pairs (in N2) which generates the finite L's kernel's terminal pairs { "she eats", "fish eats", "fork eats" })

I will put this idea to test in the next version of the algorithm; roughly:

in the input, the instance(s) (*) of terminal pairs generated by the language's kernel (aka, its witnesses in the input) shall give us (a lot?) useful information wrt. answering about the membership of the input word to the language and/or about its possible parse(s), "simply" by "looking" at what appears on both sides, left and right, for some or all of these witnesses.

(* clearly potentially multiple, in the case of recursive languages)

And what makes the CFL of palindromes so "hard" (impossible) to reject a non-word without having to read the entire input?

Simple:

that's because (one or more) words from its kernel -- { a a, b a, a b, b b } -- (ie, witnesses thereof) are found "all over the place" in the input.

Actually, inherent to the language itself, a non-empty subset of that kernel is guaranteed to always appear throughout all of it, all the way long of the entire input.

IOW, "always too much information is the same as never enough information," in this case.

No wonder / hence another way to see why we need more computational power on that one (ie, beyond pushdown automata).

L1 = { a^n b^n, n > 0 }

K(L1/G1) = { a b }

Expected witness occurrences: exactly one

L2 = { a^n b^n c, n > 0 }

K(L2/G2) = { a b }

Expected witness occurrences: exactly one

or,

K(L2/G2) = { b c }

Expected witness occurrences: exactly one

(depending on how we design / write L2's grammar G2 in CNF)

Etc, etc.

At the languages level, I believe the size of L1 and L2's kernels, combined with the trivial multiplicity of those (expected to be only 1 for all words in the respective languages), make it much easier / a non-issue for the known LL or LR algorithms to reject non-words, as soon as is visible (to a pushdown automaton).

(At the exact opposite from the palindromes)

Upper bound

for an input s of length n, and if s is in L(G), s may contain at most n-1 occurrences of words generated by the language's kernel.

This is by very construction: the words generated as the finite L's kernel are pairs of terminals, and there are at most n-1 possible locations to find such pairs of adjacent terminals throughout the input.

Eg, in the ("extreme") case of L = the palindromes of even length,

given G,

P -> a P a | b P b | a a | b b

or, in CNF, as G':

P -> AP A
P -> BP B
AP -> A P
BP -> B P
P -> A A
P -> B B
A -> a
B -> b

we have:

K(L/G') = { p1, p2, p3, p4 }

where,

p1 = a a

p2 = b a

p3 = a b

p4 = b b

Significance of the kernel

Eg, let,

s = b a b a a b a b

be the input to recognize and parse.

Thus, after computing K(L/G'), we can match s against it in one pass, yielding,

s = b      a      b      a      a      b      a      b
    --(p2)--      --(p2)--      --(p3)--      --(p3)--
           --(p3)--      --(p1)--      --(p2)--

Now let us simply index these witnesses of K(L/G'), throughout their locations,

s = b      a      b      a      a      b      a      b
    --(k1)--      --(k3)--      --(k5)--      --(k7)--
           --(k2)--      --(k4)--      --(k6)--

Let us pick, say, k3 ( = p2 = b a ) and compute the rightmost parse tree derivative of the prefix found on k3's left (as described in the post):

initial Lc = b a b

            b      a      b          (empty)
(init.) Lc> \_____________/          ( ) <Rc

            b      a
        Lc> \______/                  B <Rc (via R1)

            b
        Lc>                           A B <Rc (via R1)

            (empty)           
        Lc>                           B A B <Rc (via R1)

So far, this doesn't seem to get us anywhere.

Maybe we didn't pick a useful witness of the kernel. Or, did we?

So, nevertheless, let's just continue with computing, this time, the (dual) leftmost parse tree derivative of the suffix found on k3's right.

initial Rc = a a b a b

    (empty)        a      a      b      a      b
        Lc> ( )    \___________________________/ <Rc (init.)                  

                          a      b      a      b
        Lc> A             \____________________/ <Rc (via R1)

                                 b      a      b
        Lc> A A                  \_____________/ <Rc (via R1)

                                 b      a      b
        Lc> ( P A A )            \_____________/ <Rc (via R2)

                                        a      b
        Lc> ( P A A ) B                 \______/ <Rc (via R1)

                                               b
        Lc> ( P A A ) B A                        <Rc (via R1)

                                         (empty)
        Lc> ( P A A ) B A B                      <Rc (via R1)

Still, nothing exciting, it seems.

Certainly, though, we could record which reduction outcomes we got last, for each derivative, respectively -- B and ( P A A ) in this example -- and try to bridge both ends / S-expr lists from there.

That is, using, on the left:

      B      A      B

and, on the right:

      ( P A A )     B      A      B

we will further reduce, from now on, by exploiting only, either the immediate, adjacent left, or the immediate, adjacent right, obtained at the last reduction's outcome (ie, of previous iteration) starting from the chosen kernel witness' location:

      B      A      B      ( P A A )      B      A      B
                  ( found: BP -> B P )

can reduce to:
      B      A    ( BP B ( P A A ) )      B      A      B

      B      A    ( BP B ( P A A ) )      B      A      B
                  ( found: P -> BP B )

can reduce to:
      B      A    ( P ( BP B ( P A A ) ) B )     A      B

      B      A    ( P ( BP B ( P A A ) ) B )     A      B
           ( found: AP -> A P )

can reduce to:
      B    ( AP A ( P ( BP B ( P A A ) ) B ) )   A      B

      B    ( AP A ( P ( BP B ( P A A ) ) B ) )   A      B
                                ( found: P -> AP A )

can reduce to:
      B    ( P ( AP A ( P ( BP B ( P A A ) ) B ) ) A )  B

      B    ( P ( AP A ( P ( BP B ( P A A ) ) B ) ) A )  B
    ( found: BP -> B P )

can reduce to:
    ( BP B ( P ( AP A ( P ( BP B ( P A A ) ) B ) ) A ) ) B

    ( BP B ( P ( AP A ( P ( BP B ( P A A ) ) B ) ) A ) ) B
    ( found: P -> BP B )

can reduce to:
( P ( BP B ( P ( AP A ( P ( BP B ( P A A ) ) B ) ) A ) ) B )

(Success)

and, indeed:

      b    a    b    a    a    b    a    b
      B    A    B    A    A    B    A    B
                B(k3)P.....
                BP.........    B
                P...............
           AP...................    A
           P.........................
      BP.............................    B
      P...................................

Or, in CYK-flavored layout:

   ((b((a((b (a  a))b))a))b)
   
     b----------------BP--P
                       |  |
        a----------AP--P  |
                    |  |  |
           b----BP--P  |  |
          (k3)   |  |  |  |
              a--P  |  |  |
                 |  |  |  |
                 a  |  |  |
                    |  |  |
                    b  |  |
                       |  |
                       a  |
                          |
                          b

We would have failed parsing it, if we had picked any of the other witnesses: k1, k2, k4, k5, k6, or k7, to carry out our kernel-directed reductions.

Conjecture:

given a grammar G, in CNF, of a context-free language L whose words have a single parse tree (relative to G),

computing (and exploiting) the kernel K(L/G) of L relative to G should allow us to parse words of L against G in:

O(|G| |U|² n² log n)

time.

Quick rationale:

a) the kernel witnesses present in the input can be as many as n-1 (as shown above); obviously, there is at least one of such witnesses, if the input is a word of the language (b/c witnesses generated at the meet of dL(U) with dR(V), from a production S -> U V, where S is the start symbol), but there can't be more than n-1 of those in any input of length n, anyway -- and, as we've seen, the language of palindromes is one CFL example (are there others, btw?) which exhibits the upper bound / worst case in that respect;

b) computing the input's left or right derivatives at some terminal location w (wrt. Lc and Rc as described in the post) is believed to be in O(|G| n log n) (cf. other comments and some non-contradicting empirical results on GitHub);

c) the size of the kernel is bounded in O(|U|²) (|U| being the number of distinct nonterminals on the left-hand side of the unary productions U -> w of the grammar);

d) hence, combining (a), (b), and (c),

( n - 1 ) * |G| * n * log n * |U|²

~

O(|G| |U|² n² log n)

(in worst case).

Eg, as in the post:

S  -> NP  VP
VP -> Vt  NP
NP -> Det N
N  -> Adj N

Det-> a
Det-> the
Adj-> young
N  -> boy
N  -> dragon
Vt -> saw

we have,

|G| = 10, |U| = 4 (Det, Adj, N, Vt)

note that in practice, though, we can reasonably expect, in many cases, Card(K(L/G)) to be smaller, or much smaller, than its upper bound, |U|²;

in this example, it's just the singleton:

K(L/G) = { N . Vt }

which generates the witnesses,

{ "boy saw", "dragon saw" }

Ingenuous question:

has anybody else noticed what I call the kernel for the particular class of context-free languages that can be described by unambiguous grammars, before?

If yes, then clearly I must have missed it; so, pointers welcome.

If not, then I also welcome whoever is interested in picking up and carrying this investigation on; to help me with finding a solid (formal) completeness proof (assuming of course that any such would only exist).

(ysharp \dot\ design |at| gmail /dot/ com)

Thank you.

Complete CYK implementation and ATIS sample committed.