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
- Editors:
- Alberto Lavelli, John Carroll, Robert C. Berwick, Harry C. Bunt, Bob Carpenter, John Carroll, Ken Church, Mark Johnson, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Alon Lavie, Anton Nijholt, Christer Samuelsson, Mark Steedman, Oliviero Stock, Hozumi Tanaka, Masaru Tomita, Hans Uszkoreit, K. Vijay-Shanker, David Weir, Mats Wiren
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 242–253
- Language:
- URL:
- https://aclanthology.org/2000.iwpt-1.24
- DOI:
- Bibkey:
- 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)
- Copy Citation:
- PDF:
- https://aclanthology.org/2000.iwpt-1.24.pdf
Export citation
@inproceedings{schneider-2000-algebraic,
title = "Algebraic Construction of Parsing Schemata",
author = "Schneider, Karl-Michael",
editor = "Lavelli, Alberto and
Carroll, John and
Berwick, Robert C. and
Bunt, Harry C. and
Carpenter, Bob and
Carroll, John and
Church, Ken and
Johnson, Mark and
Joshi, Aravind and
Kaplan, Ronald and
Kay, Martin and
Lang, Bernard and
Lavie, Alon and
Nijholt, Anton and
Samuelsson, Christer and
Steedman, Mark and
Stock, Oliviero and
Tanaka, Hozumi and
Tomita, Masaru and
Uszkoreit, Hans and
Vijay-Shanker, K. and
Weir, David and
Wiren, Mats",
booktitle = "Proceedings of the Sixth International Workshop on Parsing Technologies",
month = feb # " 23-25",
year = "2000",
address = "Trento, Italy",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2000.iwpt-1.24",
pages = "242--253",
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.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="schneider-2000-algebraic">
<titleInfo>
<title>Algebraic Construction of Parsing Schemata</title>
</titleInfo>
<name type="personal">
<namePart type="given">Karl-Michael</namePart>
<namePart type="family">Schneider</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2000-feb 23-25</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the Sixth International Workshop on Parsing Technologies</title>
</titleInfo>
<name type="personal">
<namePart type="given">Alberto</namePart>
<namePart type="family">Lavelli</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">John</namePart>
<namePart type="family">Carroll</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Robert</namePart>
<namePart type="given">C</namePart>
<namePart type="family">Berwick</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Harry</namePart>
<namePart type="given">C</namePart>
<namePart type="family">Bunt</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Bob</namePart>
<namePart type="family">Carpenter</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ken</namePart>
<namePart type="family">Church</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Mark</namePart>
<namePart type="family">Johnson</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Aravind</namePart>
<namePart type="family">Joshi</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ronald</namePart>
<namePart type="family">Kaplan</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Martin</namePart>
<namePart type="family">Kay</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Bernard</namePart>
<namePart type="family">Lang</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Alon</namePart>
<namePart type="family">Lavie</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Anton</namePart>
<namePart type="family">Nijholt</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Christer</namePart>
<namePart type="family">Samuelsson</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Mark</namePart>
<namePart type="family">Steedman</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Oliviero</namePart>
<namePart type="family">Stock</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Hozumi</namePart>
<namePart type="family">Tanaka</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Masaru</namePart>
<namePart type="family">Tomita</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Hans</namePart>
<namePart type="family">Uszkoreit</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">K</namePart>
<namePart type="family">Vijay-Shanker</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">David</namePart>
<namePart type="family">Weir</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Mats</namePart>
<namePart type="family">Wiren</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Trento, Italy</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<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.</abstract>
<identifier type="citekey">schneider-2000-algebraic</identifier>
<location>
<url>https://aclanthology.org/2000.iwpt-1.24</url>
</location>
<part>
<date>2000-feb 23-25</date>
<extent unit="page">
<start>242</start>
<end>253</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings %T Algebraic Construction of Parsing Schemata %A Schneider, Karl-Michael %Y Lavelli, Alberto %Y Carroll, John %Y Berwick, Robert C. %Y Bunt, Harry C. %Y Carpenter, Bob %Y Church, Ken %Y Johnson, Mark %Y Joshi, Aravind %Y Kaplan, Ronald %Y Kay, Martin %Y Lang, Bernard %Y Lavie, Alon %Y Nijholt, Anton %Y Samuelsson, Christer %Y Steedman, Mark %Y Stock, Oliviero %Y Tanaka, Hozumi %Y Tomita, Masaru %Y Uszkoreit, Hans %Y Vijay-Shanker, K. %Y Weir, David %Y Wiren, Mats %S Proceedings of the Sixth International Workshop on Parsing Technologies %D 2000 %8 feb 23 25 %I Association for Computational Linguistics %C Trento, Italy %F schneider-2000-algebraic %X 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. %U https://aclanthology.org/2000.iwpt-1.24 %P 242-253
Markdown (Informal)
[Algebraic Construction of Parsing Schemata](https://aclanthology.org/2000.iwpt-1.24) (Schneider, IWPT 2000)
- Algebraic Construction of Parsing Schemata (Schneider, IWPT 2000)
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.