Left-Corner Parsing

Abstract:
In this lecture, we will

introduce left-corner parsing which combines bottom up and top down search steps, and
give a naive implementation of a left-corner recognizer.

Introduction Left-Corner Parsing
Let us first re-evaluate top-down and bottom-up processing. We will look at some examples of these two different strategies to show

what kind of information we use to make decisions,
what kind of information we ignore,
how it can happen that we go wrong (because of that).

A Left-Corner Recognizer in Prolog
Now, we will put the strategy that we have just described into Prolog.

Using Left-corner Tables
This left-corner recognizer handles the example that was problematic for the pure top down approach much more efficiently.

The Code
Code Summary for this Chapter.

Practical Session
Practical session.

Exercise

Download leftrec.pl , the left-recursive grammar that we already saw in the previous chapter. Can the left-corner recognizer cope with it? Why does it not have the same problems with it as the top-down algorithm?
Now, download epsilon.pl , the grammar with the empty production that we have seen before, as well. Write a left-corner table for it. (Note: ε is a kind of terminal symbol.).
[This is tricky] Turn the left-corner recognizer into a parser by adding an extra argument to collect the structure.
Hint:
Hint: you have to add two arguments ParseIn, ParseOut to the predicate complete.

Left-Corner Parsing

Table of Contents

Exercise