Previous Up Next

Chapter 2  Left Associative Grammars

A formal grammar for a natural language can be used to check whether a sentence or a word form is grammatically well-formed (a word form is a special flectional form of a word, so ``book'' and ``books'' are two different word forms of the word ``book''). Furthermore, they can describe the structure and meaning of a sentence or a word form by a data structure that has been constructed in the analysis process.

The Left Associative Grammar (LAG) is such a kind of formal grammar. An LAG analyses a sentence (or a word form) step by step: its parts are concatenated from the left to the right, hence the name ``Left Associative Grammar''. A single LAG rule can only join two parts to a bigger one: it concatenates the Start part (which is the beginning of the sentence or word form that has already been analysed) and the Next part (which is the next word form or the next allomorph). Take a look at the following sentence:
Shakespeare liked writing comedies.
The sentence is being analysed by five rule applications:
``'' + ``Shakespeare''
``Shakespeare'' + ``liked''
``Shakespeare liked'' + ``writing''
``Shakespeare liked writing'' + ``comedies''
``Shakespeare liked writing comedies'' + ``.''
To apply a rule it's not sufficient to know the spelling of a word or an allomorph. A rule also requires morphological and syntactic information, such as word class, gender, meaning of a suffix and much more. This information associated with a part of speech (sentence, word form or allomorph) is called its category. The analysis of a sentence or a word returns such a category as result.

Now we'll take a closer look at how a sentence is analysed.
  1. Before we can start to analyse a sentence, the analysis automaton must be in an initial state. The initial state determines:
    1. the category of the empty sentence start, and
    2. the combination rule checking whether it is allowed to combine the empty sentence start with the first word form (which is yet to be read). This rule also determines the resulting category of the new sentence start (which consists of the old sentence start and the first word form concatenated).


  2. The next word form to be analysed is read and analysed morphologically. If there is no valid word form, the analysis process aborts.

  3. The category that morphology assigns to this word form is called the Next category. The category of the input that has been analysed syntactically so far is called the Start category.

  4. The active combination rule checks whether it is allowed to combine the sentence start (which may be empty), represented by the Start category, with the next word form, represented by the Next category. In a rule, categories can be compared by logical tests, and finally the category of the new sentence start (including the word form that has been read), the Result category, is constructed by the rule. The rule finally specifies which successor rule is active in the next step. Execution then continues at step 2.

    Instead of calling a successor rule a rule can also accept the analysed sentence. In this case the Result category of this rule is the category of the complete analysed sentence.
Morphological analysis operates analogously, except that a word form, composed from allomorphs, is being analysed. The next allomorph (step 2) is found in the allomorph lexicon.

This sketch is of course simplified. There can be ambiguities in an analysis, induced by several causes: These ambiguities are coped with by dividing the analysis into several subanalyses: if there are two lexicon entries for a word form, for example, the analysis continues using the first entry (and its category) as well as the second one. You can compare this with a branching path. The analyses will be continued independently of each other. So, one analysis can succeed while the other fails. Each analysis path can divide repeatedly, if another ambiguity is met. If several analysis paths are continued until they accept, the analysis process returns more than one result.


Previous Up Next