Parsing 2-Dimensional Language

Masaru Tomita


Abstract
2-Dimensional Context-Free Grammar (2D-CFG) for 2-dimensional input text is introduced and efficient parsing algorithms for 2D-CFG are presented. In 2D-CFG, a grammar rule’s right hand side symbols can be placed not only horizontally but also vertically. Terminal symbols in a 2-dimensional input text are combined to form a rectangular region, and regions are combined to form a larger region using a 2-dimensional phrase structure rule. The parsing algorithms presented in this paper are the 2D-Ear1ey algorithm and 2D-LR algorithm, which are 2-dimensionally extended versions of Earley’s algorithm and the LR(O) algorithm, respectively.
Anthology ID:
W89-0243
Volume:
Proceedings of the First International Workshop on Parsing Technologies
Month:
August
Year:
1989
Address:
Pittsburgh, Pennsylvania, USA
Venues:
IWPT | WS
SIG:
SIGPARSE
Publisher:
Carnegy Mellon University
Note:
Pages:
414–424
Language:
URL:
https://www.aclweb.org/anthology/W89-0243
DOI:
Bib Export formats:
BibTeX MODS XML EndNote
PDF:
http://aclanthology.lst.uni-saarland.de/W89-0243.pdf