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
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Carnegy Mellon University
- Note:
- Pages:
- 414–424
- Language:
- URL:
- https://aclanthology.org/W89-0243
- DOI:
- 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)
- PDF:
- https://preview.aclanthology.org/remove-xml-comments/W89-0243.pdf