Affix Grammars over a Finite Lattice

The AGFL formalism (Affix Grammars over a Finite Lattice) [Koster, 1992] is a notation for Context-Free grammars enriched with finite set-valued features, acceptable to linguists of many different schools. For a computer scientist this means: syntax rules are procedures with parameters and a nondeterministic execution, like that of PROLOG.

No natural language can reasonably be described by a deterministic grammar, so that deterministic parser generators like YACC are useless for realistic NLP. Nondeterminism (ambiguity!) is an essential property of language, so that a completely different kind of parser generator is needed. The AGFL system is such a system.

For the interested reader we give two examples to convey some of the flavor of AGFL. The notation of AGFL is reminiscent of that of PROLOG, with which it is distantly related. This may help in reading (and understanding) the examples.