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.

**chart-parse.lisp**Chart Parser with Unification Augmentation

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

**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-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.

**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.

**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)

***e0*** *variable*

Lexicon and grammar for E_{0}in Figures 22.5, 22.6, page 665.

***e1*** *variable*

Lexicon and grammar for E_{1}in Figure 22.10, page 670.

***e2*** *variable*

Lexicon and grammar for E_{2}in Figure 22.19, page 680.

***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 |