Language (Subsystem of AIMA Code)

The language subsystem covers the natural language processing code from Chapters 22 and 23 of the book. The main parsing function is chart-parse, but it returns a chart, which is not very useful in itself, so most of the test examples call chart-parses, which returns a list of parses for the complete input string, or meanings which pulls out the semantic component of each parse.

Several sample grammars are shown. For the most part, they follow the notation from the book. The differences are:

Obviously, the grammars are in Lisp notation.
The symbol $w on the left-hand side of a lexical rule stands for the word itself on the right-hand side. This allows you to put multiple lexical entries on one line.
The grammar can specify a list of :unknown-word-cats. That means that when an unknown word is encountered in the input, it is assumed to be one of these categories.

language/:

test-language.lisp

language/algorithms/:

chart-parse.lisp Chart Parser with Unification Augmentation

language/domains/:

grammars.lisp Definition of Lexicons and Grammars: E0, E1, E2

File language/test-language.lisp

File language/algorithms/chart-parse.lisp

Chart Parser with Unification Augmentation

grammar type (lexicon rules start-symbol categories-for rewrites-for unknown-word-cats)

A grammar for a chart parser has rules indexed by word and LHS.

*grammar* variable

The currently used grammar. Defining a new grammar changes this, or you can set it yourself.

rule-lhs function (rule)

The left hand side.

rule-rhs function (rule)

The right-hand side.

chart type (ends-at)

A chart has a vector that holds the edges that end at vertex i.

edge type (start end lhs found remains bindings)

An edge represents a dotted rule instance. In the edge [i, j, L -> F . R], i is the start, j is the end, L is the lhs, (F) is found, and (R) remains.

Chart Parsing Algorithm

chart-parse function (words &optional *grammar*)

See if the string of words can be parsed by the grammar. (See page 702.)

scanner function (j word chart)

Add edges everywhere WORD is expected.

predictor function (edge chart)

Add edges saying what we expect to see here.

completer function (edge chart)

Use this edge to extend any edges in the chart.

add-edge function (edge chart &optional reason)

Put edge into chart, and complete or predict as appropriate.

Other Top-Level Functions

chart-parses function (words &optional *grammar*)

See if the string of words can be parsed by the grammar. If it can, look into the chart and pull out complete spanning strings.

meanings function (words &optional *grammar*)

Parse words, then pick out the semantics of each parse. Assumes the semantics will be the last element of the LHS.

Auxiliary Functions

spanning-edges function (chart)

Find the edges that span the chart and form the start symbol.

edge->tree function (edge)

Convert an edge into a parse tree by including its FOUND parts.

edge function (start end lhs found remains &optional bindings)

Construct a new edge.

grammar function (&rest args)

Take a list of rules, index them to form a grammar for chart-parse.

rewrites-for function (lhs grammar)

Find the rules in grammar with LHS as the left hand side.

categories-for function (word grammar)

Find what categories this word can be. For unknown words, use the grammar's unknown-word-cats field

edge-expects function (edge)

What does the edge expect next in order to be extended?

lhs-op function (edge)

Left hand side of an edge's category

complete? function (edge)

An edge is complete if it has no remaining constituents.

edge-equal function (edge1 edge2)

Are two edges the same, up to renaming of the parts with variables?

handle-augmentation method ((grammar grammar) edge)

There are two things to do: (1) When we start a new edge, rename vars. (2) When an edge is complete, substitute the bindings into the lhs.

print-structure method ((e edge) stream)

File language/domains/grammars.lisp

Definition of Lexicons and Grammars: E0, E1, E2

*e0* variable

Lexicon and grammar for E₀ in Figures 22.5, 22.6, page 665.

*e1* variable

Lexicon and grammar for E₁ in Figure 22.10, page 670.

*e2* variable

Lexicon and grammar for E₂ in Figure 22.19, page 680.

Other grammars: Arithmetic, Trivial

*arithmetic-grammar* variable

A grammar of arithmetic expressions, with semantics, from Figure 22.13, page 673.

*figure23.4* variable

A grammar that, with debugging on, produces output similar to that on page 700, Figure 23.4. The differences are: (1) Scanner does two steps in the book; here those steps are broken into Scanner and Completer. (2) Some 'irrelevant' edges were ommitted from Figure 23.4

Authors