Parsing 2-D Languages with Positional Grammars

Gennaro Costagliola, Shi-Kuo Chang


Abstract
In this paper we will present a way to parse two-dimensional languages using LR parsing tables. To do this we describe two-dimensional (positional) grammars as a generalization of the context-free string grammars. The main idea behind this is to allow a traditional LR parser to choose the next symbol to parse from a two-dimensional space. Cases of ambiguity are analyzed and some ways to avoid them are presented. Finally, we construct a parser for the two-dimensional arithmetic expression language and implement it by using the tool Yacc.
Anthology ID:
1991.iwpt-1.27
Volume:
Proceedings of the Second International Workshop on Parsing Technologies
Month:
February 13-25
Year:
1991
Address:
Cancun, Mexico
Venue:
IWPT
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
235–243
Language:
URL:
https://aclanthology.org/1991.iwpt-1.27
DOI:
Bibkey:
Cite (ACL):
Gennaro Costagliola and Shi-Kuo Chang. 1991. Parsing 2-D Languages with Positional Grammars. In Proceedings of the Second International Workshop on Parsing Technologies, pages 235–243, Cancun, Mexico. Association for Computational Linguistics.
Cite (Informal):
Parsing 2-D Languages with Positional Grammars (Costagliola & Chang, IWPT 1991)
Copy Citation:
PDF:
https://aclanthology.org/1991.iwpt-1.27.pdf