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.
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.