Abstract
We propose an algebraic method for the design of tabular parsing algorithms which uses parsing schemata [7]. The parsing strategy is expressed in a tree algebra. A parsing schema is derived from the tree algebra by means of algebraic operations such as homomorphic images, direct products, subalgebras and quotient algebras. The latter yields a tabular interpretation of the parsing strategy. The proposed method allows simpler and more elegant correctness proofs by using general theorems and is not limited to left-right parsing strategies, unlike current automaton-based approaches. Furthermore, it allows to derive parsing schemata for linear indexed grammars (LIG) from parsing schemata for context-free grammars by means of a correctness preserving algebraic transformation. A new bottom-up head corner parsing schema for LIG is constructed to demonstrate the method.- Anthology ID:
- 2000.iwpt-1.24
- Volume:
- Proceedings of the Sixth International Workshop on Parsing Technologies
- Month:
- February 23-25
- Year:
- 2000
- Address:
- Trento, Italy
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 242–253
- Language:
- URL:
- https://aclanthology.org/2000.iwpt-1.24
- DOI:
- Cite (ACL):
- Karl-Michael Schneider. 2000. Algebraic Construction of Parsing Schemata. In Proceedings of the Sixth International Workshop on Parsing Technologies, pages 242–253, Trento, Italy. Association for Computational Linguistics.
- Cite (Informal):
- Algebraic Construction of Parsing Schemata (Schneider, IWPT 2000)
- PDF:
- https://preview.aclanthology.org/nodalida-main-page/2000.iwpt-1.24.pdf