Existing grammar frameworks do not work out particularly well for controlled natural languages (CNL), especially if they are to be used in predictive editors. I introduce in this paper a new grammar notation, called Codeco, which is designed speci cally for CNLs and predictive editors. Two di erent parsers have been implemented and a large subset of Attempto Controlled English (ACE) has been represented in Codeco. The results show that Codeco is practical, adequate and e cient.
Controlled natural languages (CNL) like Attempto Controlled English (ACE) [
These requirements are not satis ed by existing grammar frameworks.
Natural language grammar frameworks like Head-driven Phrase Structure Grammars
(HPSG) [
The following example illustrates the di culty of lookahead in the case of complex nonlocal structures like anaphoric references. The partial ACE sentence \every man protects a house from every enemy and does not destroy ..." can be continued by several anaphoric structures referring to earlier objects in the sentence: \the man" or \himself" can be used to refer to \man"; \the house" or \it" can be used to refer to \house". It is not possible, however, to refer to \enemy", because it is under the scope of the quanti er \every" and such references from outside the scope of a quanti ed entity do not make sense logically.1 Thus, a predictive editor should in this case propose \the man" and \the house" as possible continuations of the given partial sentence, but not \the enemy". 2
In order to solve the problems sketched above, I created a new grammar notation called Codeco, which stands for \concrete and declarative grammar notation for controlled natural languages". This grammar notation is designed speci cally for CNLs to be used in predictive editors. Below is a brief description of the most important features of Codeco.
In a nutshell, grammar rules in Codeco consist of grammatical categories with at feature structures2. One of the important features of Codeco is that anaphoric references and their potential antecedents can be represented by special categories for backward references \<" and forward references \>", respectively. These special categories establish nonlocal dependencies across the syntax tree in the sense that each backward reference needs a matching (i.e. uni able) forward reference somewhere in the preceding text.
Furthermore, scopes can be de ned that make the contained forward
references inaccessible from the outside. In Codeco, scopes are opened by the special
category \ " and are closed by the use of scope-closing rules \ !". In contrast
to normal rules \ !:", scope-closing rules close at their end all scopes that have
1 The di erence between \every man" and \every enemy" in the given example is not
obvious. The scope that is opened by the quanti er \every" of \every enemy" closes
after \enemy", because the verb phrase ends there. In ACE, verb phrases | but not
only verb phrases | close at their end all scopes that are opened within (which is,
in general, also true for full natural English). Since \every man" is not part of that
verb phrase, the scope for \every man" is still open at the end of the partial sentence.
This is why \man" is accessible for anaphoric references, but \enemy" is not. See
also Fig. 1.
2 The restriction to at feature structures (instead of general ones) restricts the
expressive power of Codeco while making it easier to process and implement. The
results suggest that Codeco is su ciently expressive for common CNLs.
been opened by one of their child categories. In this way, Codeco allows us to
de ne the positions where scopes open and close in a simple and fully
declarative way. Other extensions that are not discussed here are needed to handle
pronouns, variables, and references to proper names in the desired way. See [
The following grammar rules are examples that show how the special structures of Codeco are used: np : ! det exist: +
noun text: Noun : ! ref [ the ] noun text: Noun
> tnyopuen::nNoouunn < tnyopuen::nNoouunn det exist: { : !
[ every ] vp num: Num ! v tnyupme:: tNrum np case: acc pp The rst rule represents existentially quanti ed noun phrases like \a house" and establishes a forward reference to de ne its status as a potential antecedent for subsequent anaphoric references. The second rule describes a de nite noun phrase like \the house" and declares its anaphoric property by a backward reference. The third rule describes the determiner \every" opening a scope through the use of the scope opener category. The last rule describes a verb phrase and is scope-closing, which means that the end of such a verb phrase also marks the end of all scopes that have been opened within.
Codeco grammars allow for the correct and e cient implementation of lookahead features. Figure 1 shows a possible syntax tree of the example above and visualizes how the possible anaphoric references can be found.
Two independent parsers have been implemented for Codeco: one that
executes Codeco grammars as Prolog DCGs and another one that is a chart parser
implemented in Java. These two implementations have been shown to be
equivalent and e cient [
The Codeco grammar that is used in the ACE Editor consists of 164 grammar rules and describes a large subset of ACE covering nouns, proper names, intransitive and transitive verbs, adjectives, adverbs, prepositions, variables, plurals, negation, prepositional phrases, relative clauses, modality, numerical quanti ers, various kinds of coordination, conditional sentences, questions, anaphoric pronouns, and more. Currently unsupported ACE features are mass nouns, measurement nouns, ditransitive verbs, numbers and strings as noun phrases, sentences as verb phrase complements, saxon genitive, possessive pronouns, noun phrase coordination, and commands. Nevertheless, this subset of ACE is | to 3 http://attempto.ifi.uzh.ch/webapps/aceeditor/ det noun > v tv vp np det noun > prep vp
conj pp det np noun > aux v vp tv np ref < ( Every man protects a house
from ( every enemy ) and ( does not destroy ... my knowledge | the broadest subset of English that has ever been de ned in a formal and fully declarative way and that includes complex issues like anaphoric references.
Codeco grammars can be checked for syntactic ambiguity by exhaustive language generation up to a certain sentence length. Due to combinatorial explosion, it is advisable not to check the complete language but to de ne a core subset thereof. Such a core subset should use a minimal lexicon and should have a reduced number of grammar rules, in a way that language structures that could possibly lead to complex cases of ambiguity are retained. For the ACE Codeco grammar introduced above, such a core subset has been de ned, consisting of 97 of the altogether 164 grammar rules. Exhaustive language generation of this core subset up to ten tokens leads to 2'250'869 sentences, which are all di erent. Since syntactically ambiguous sentences would be generated more than once (because they have more than one syntax tree), this proves that at least the core of the ACE Codeco grammar is unambiguous, at least for sentences up to ten tokens. In the same way, it can be proven that the core of the ACE Codeco grammar is indeed a subset of ACE.
See my thesis [
In summary, the Codeco notation allows us to de ne controlled subsets of natural languages in an adequate way. The resulting grammars are fully declarative, can be e ciently interpreted in di erent kinds of programming languages, and allow for lookahead features, which is needed for predictive editors. Furthermore, it allows for di erent kinds of automatic tests, which is very important for the development of reliable practical applications.
Codeco is a proposal for a general CNL grammar notation. It cannot be excluded that extensions become necessary to express the syntax of other CNLs, but Codeco has been shown to work very well for a large subset of ACE, which is one of the most advanced CNLs to date.