Left-corner parsing

The left corner of a rule is the first symbol of its right-hand side. A left-corner parser finds the first daughter of a constituent bottom-up (starting from the word) and then uses a rule that begins with it to predict the remaining daughters top-down. It mixes the two strategies: the words decide which rules are tried, the rules decide what to look for next.

Configuration and operations

The parser keeps a list of tasks: find a G (a predicted goal) and turn this C into a G (a constituent that has been completed bottom-up and must be connected to the goal it was started for). It starts with the task “find an S”.

Shift: To find a goal G, read the next word and give it a category C. Then try to turn C into G.
Project: To turn C into G, choose a rule P → C Y₁ … Yₖ: build a P with C as its first daughter, predict Y₁ … Yₖ as new goals, and once they are found try to turn P into G.
Attach: If C is G itself, the goal is found: attach the constituent in its place.
Backtrack: As in the other backtracking parsers.

find(G, i):                       # all positions where a G starting at i can end
    for each category C with C → w[i]  (and C ∈ LC*(G)):      # SHIFT
        yield from complete(C, G, i + 1)

complete(C, G, j):                # a C ends at j; can it become a G?
    if C == G: yield j                                        # ATTACH
    for each rule P → C Y1 … Yk  (and P ∈ LC*(G)):            # PROJECT
        for each j2 in find_seq(Y1 … Yk, j):                  # predict the sisters
            yield from complete(P, G, j2)

find_seq(Ys, j): if Ys is empty: yield j
                 else for each j1 in find(Ys[0], j): yield from find_seq(Ys[1:], j1)

recognise(sentence) = n ∈ find(S, 0)

The oracle (left-corner table)

LC*(G) is the reflexive–transitive closure of the left-corner relation: the categories that can begin a G. For S → NP VP and NP → Det N, LC*(S) = {S, NP, Det}. Checking it before Shift and Project stops the parser from building constituents that can never lead to the current goal. The table depends only on the grammar and can be computed once. Untick “left-corner oracle” in the tool to see how much work it saves.

Arc-standard and arc-eager

The version implemented here is arc-standard: a projected node P is connected to its goal only when P is complete. In the arc-eager variant, when the projected category P is the goal itself, it is attached to the goal immediately, before its predicted sisters are found. The difference matters for memory: arc-standard left-corner parsing needs more and more memory on right-branching structures, while arc-eager left-corner parsing needs a bounded amount for both left- and right-branching structures and an unbounded amount only for centre-embedding, which is also what is hard for people (Johnson-Laird 1983; Abney & Johnson 1991; Resnik 1992).

Properties

Left recursion is handled: a rule NP → NP PP is used only after an NP has been built, so it cannot loop. Cycles of unit rules can still loop, and ε-rules need special treatment.
Fewer wasted predictions than top-down parsing (a rule is used only if its left corner is there) and fewer useless constituents than bottom-up parsing (with the oracle, only what can lead to the goal).
Still exponential with backtracking. The same idea underlies left-corner chart parsers and the left-corner grammar transform, which removes left recursion so that a top-down parser can be used.
Introduced for deterministic parsing by Rosenkrantz & Lewis (1970).

In this tool

A goal that is being worked on is drawn as a dashed box with a dashed line down to the sub-tree being built for it; when that sub-tree has the goal’s category it is attached (Attach) and the line becomes solid. The “To do” row lists the tasks: dashed boxes are goals to find, “C for G” means a C waiting to be turned into a G.

Try it on an example → Left recursion: no loop →

References

Rosenkrantz, D. J. & Lewis, P. M. II (1970). Deterministic left corner parsing. In IEEE Conference Record of the 11th Annual Symposium on Switching and Automata Theory.
Johnson-Laird, P. N. (1983). Mental Models: Towards a Cognitive Science of Language, Inference, and Consciousness. Cambridge: Cambridge University Press.
Abney, S. P. & Johnson, M. (1991). Memory requirements and local ambiguities of parsing strategies. Journal of Psycholinguistic Research, 20(3), 233–250.
Resnik, P. (1992). Left-corner parsing and psychological plausibility. In COLING 1992 Volume 1: The 14th International Conference on Computational Linguistics. aclanthology.org/C92-1032
Pereira, F. C. N. & Shieber, S. M. (1987). Prolog and Natural-Language Analysis. CSLI Lecture Notes 10. Stanford, CA: CSLI Publications.
Covington, M. A. (1994). Natural Language Processing for Prolog Programmers. Englewood Cliffs, NJ: Prentice-Hall.
Bird, S., Klein, E. & Loper, E. (2009). Natural Language Processing with Python. Sebastopol, CA: O’Reilly. Chapter 8, “Analyzing Sentence Structure”. Free online at nltk.org/book.
Aho, A. V. & Ullman, J. D. (1972). The Theory of Parsing, Translation, and Compiling. Vol. I: Parsing. Englewood Cliffs, NJ: Prentice-Hall.