More DCGs
The code in this section includes extensions and bug-fixes to the Horn clause interpreter in Scheme and
extensions to the DCG rule notation.
Specialized Predicates for the Horn interpreter
horn.scm includes code to manipulate specialized predicates.
These predicates operate as "primitive" calls to the meta-language in which the interpreter is written.
For example, the number?
predicate is used to test whether an argument is a number in the
Scheme underlying representation.
The specialized predicates are:
- number?
- atom?
- if
- word (see below explanation)
The important point is: we have a small interpreter for our language; it is easy to extend it when we need to - go ahead and extend it when needed!
In addition, simple tracing methods are implemented, which can be turned on and off using the functions:
- trace-goals
- untrace-goals
- trace-words
- untrace-words
Extended DCG Rules notations
The DCG rules notation is expanded with the following syntax:
(rule (adjunct post noun ?agr ?x ?gap ?gap ?sem) ==>
(:ex (the man) "visiting me" (the man) "visited by me")
(:test (member ?infl (-ing passive)))
(clause ?infl ?x ? ?v (gap (NP ?agr ? ?x)) (gap ()) ?sem))
(rule (opt-rel-pronoun ?case ?x ?int-subj (?type ?x)) ==>
(:word ?rel-pro)
(:test (word ?rel-pro rel-pro ?case ?type)))
The (:ex ....) notation is used to document rules. It shows examples.
It is ignored in the translation into Horn clauses.
The (:word ...) can now appear in any position in the rules and more than one instance can appear in one rule.
The (:test ...) notation indicates calls to regular predicates - that do not "consume" words from the input
sequence of words. Tests are used to filter the acceptable parses.
Hashtable-based Lexicon Implementation
When a few thousands words are added to the DCG, we hit performance issues when looking up words.
To avoid this problem, the word lookup predicate is implemented in a special manner which looks up
a word in a hashtable. The supporting code that populates the hashtable is provided in
lexicon.scm.
CNF Normalization of Underspecified Logical Expressions
The code in normal.scm has been extended to normalize expressions
that include "generalized quantifiers" such as ex, forall and more (see code in the function ->cnf).
Download
All the required code:
- utils.scm
- tell-ask.scm
- unify.scm
- normal.scm
- horn.scm
- dcg-rule.scm
- load.scm
Available grammars:
- grammar.scm: An midsize grammar based on Norvig (1991) Paradigms of AI Programming, Chapter 21.
- grammar.scm: example of sentences analyzed (or not) by the grammar.
- lexicon.scm: Code to manipulate a lexicon in an efficient manner.
Last modified July 10th, 2007