Tabular parsing and algebraic transformations
Tabular parsing is described by means of two homomorphic algebras. In this setting, the parsing problem is described as the computation of the inverse image of an input string with respect to the homomorphism. Tabulation is obtained by constructing a quotient of the first algebra and using a finite subalgebra of the second algebra. The valid parse items are the elements generated by the variable-free terms in the product of these two algebras. This yields an algebraic construction method for tabular algorithms. We demonstrate the method by constructing a tabular bottom-up head-corner algorithm for context-free grammars. We then use the algebraic description of this algorithm to construct a tabular algorithm for linear indexed grammars, using a correctness-preserving algebraic transformation. This transformation is a formalization of the idea of an efficient representation of the unbounded LIG stacks that is stated only informally in previous constructions of LIG algorithms. The main feature of this method is the modularity of the construction, by allowing simpler tabular algorithms to be reused for the construction of more complex ones. (C) 2002 Elsevier Science B.V. All rights reserved.
tabular parsing algebra transformation linear indexed grammars parser construction