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
Editor:
Masaru Tomita
Venue:
IWPT
SIG:
SIGPARSE
Publisher:
Carnegy Mellon University
Note:
Pages:
414–424
Language:
URL:
https://aclanthology.org/W89-0243
DOI:
Bibkey:
Cite (ACL):
Masaru Tomita. 1989. Parsing 2-Dimensional Language. In Proceedings of the First International Workshop on Parsing Technologies, pages 414–424, Pittsburgh, Pennsylvania, USA. Carnegy Mellon University.
Cite (Informal):
Parsing 2-Dimensional Language (Tomita, IWPT 1989)
Copy Citation:
PDF:
https://aclanthology.org/W89-0243.pdf