Several sample grammars are shown. For the most part, they follow the notation from the book. The differences are:
grammartype (lexicon rules start-symbol categories-for rewrites-for unknown-word-cats)
A grammar for a chart parser has rules indexed by word and LHS.
The currently used grammar. Defining a new grammar changes this, or you can set it yourself.
The left hand side.
The right-hand side.
A chart has a vector that holds the edges that end at vertex i.
edgetype (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-parsefunction (words &optional *grammar*)
See if the string of words can be parsed by the grammar. (See page 702.)
scannerfunction (j word chart)
Add edges everywhere WORD is expected.
predictorfunction (edge chart)
Add edges saying what we expect to see here.
completerfunction (edge chart)
Use this edge to extend any edges in the chart.
add-edgefunction (edge chart &optional reason)
Put edge into chart, and complete or predict as appropriate.
chart-parsesfunction (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.
meaningsfunction (words &optional *grammar*)
Parse words, then pick out the semantics of each parse. Assumes the semantics will be the last element of the LHS.
Find the edges that span the chart and form the start symbol.
Convert an edge into a parse tree by including its FOUND parts.
edgefunction (start end lhs found remains &optional bindings)
Construct a new edge.
grammarfunction (&rest args)
Take a list of rules, index them to form a grammar for chart-parse.
rewrites-forfunction (lhs grammar)
Find the rules in grammar with LHS as the left hand side.
categories-forfunction (word grammar)
Find what categories this word can be. For unknown words, use the grammar's unknown-word-cats field
What does the edge expect next in order to be extended?
Left hand side of an edge's category
An edge is complete if it has no remaining constituents.
edge-equalfunction (edge1 edge2)
Are two edges the same, up to renaming of the parts with variables?
handle-augmentationmethod ((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-structuremethod ((e edge) stream)
Lexicon and grammar for E0 in Figures 22.5, 22.6, page 665.
Lexicon and grammar for E1 in Figure 22.10, page 670.
Lexicon and grammar for E2 in Figure 22.19, page 680.
A grammar of arithmetic expressions, with semantics, from Figure 22.13, page 673.
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|