Several sample grammars are shown. For the most part, they follow the notation from the book. The differences are:
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 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.
*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 |