Syntax and Syntactic Processors

This part is about:

The sections are:

The adequacy of Finite State Automata for syntactic processing
It is possible to use Finite State Networks to recognise many valid sequences of English sentences. However, it is possible to show that any Finite State Automata cannot model some language constructions, for instance centre-embedded phrases. Also Finite State Automata do not account for our intuitions about the structure of phrases in syntax.

Introduction to the terminology of syntax and context-free grammars
Syntactic grammars are codifications of knowledge about language that are usually written in the form of rewrite rules. When applied to individual sentences, the rules can be used to show the phrase structure of the sentences.

Search and control in parsing
Search is either a top-down (hypothesis-driven) or bottom-up (data-driven). Control of the search can be either depth-first or breadth-first.

A first top-down parser in Prolog
Prolog lends itself naturally to writing parsers for NLP. Here we give a step-by-step introduction to writing a parser in Prolog, using the Definite Clause Grammar formalism. This is a top-down parser, with depth-first control.

Implementing depth-first or breadth-first control
Prolog has depth-first control built-in. When we want to implement a choice between depth-first and breadth-first control, we have to use an explicit data structure to store choice points.

The programs in this part are written in Prolog and should work with any Edinburgh flavour implementation, for instance SICStus Prolog, Quintus Prolog and Open Prolog.