Natural Language Processing, Shen, Shen Prolog

[Antti Ylikoski]

The author has been doing some work concerning Natural Language
Processing and Shen.

In this entry the author discusses one point as to that activity.

A book that I ordered, George F. Luger's Artificial Intelligence, 6th
Edition, arrived today by mail.  The book contains the description of
the Earley parser on Pages 627--632.

The Wikipedia has an article on the Earley parser, it is a relatively
good one:

https://en.wikipedia.org/wiki/Earley_parser

In short, the Earley parser is used in the NLP work, to parse
context-free grammars.  They are pretty useful in many NLP tasks.  It
is a chart parsing algorithm utilizing dynamic programming (Bellman).

The file earley1.pro (attachment) contains the Earley algorithm in the
standard Prolog; it has been written for the Dutch SWI-Prolog; it
comes from the (earlier) Luger textbook web site.  Translating it into
Shen Prolog would be easy.

The context free grammar for the Earley parser is in the file
earley.grammar.pro.

A sample run is in the file earley.grammar.txt.

An explanation as to the sample run: The parser, when it succeeds in
parsing the sentence given, outputs the chart.  If the chart ends with
an output line such as

s($,[sentence,@],[0,5])

then the start symbol of the grammar ("$") has been parsed; the
production "sentence" has been fully input and successfully processed;
the [0,5] is some parser bookkeeping.

If the parse fails, then the chart does not end with the note as to
the start symbol ("$") having been parsed.

There are there other parsing techniques that the author has studied,
such as Definite Clause Grammars in Shen Prolog; and, using the Shen
nondeterminism feature in transition network parsers.  I may want to
write more on those ones.


yours, A. J. Y.
HELSINKI
Finland, the E.U.