# 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 E0 in Figures 22.5, 22.6, page 665.

*e1*

variable

> Lexicon and grammar for E1 in Figure 22.10, page 670.

*e2*

variable

> Lexicon and grammar for E2 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

AIMA Home | Authors | Lisp Code | AI Programming | Instructors Pages