Parsing 2-dimensional language

Research output: Contribution to conferencePaperpeer-review

7 Citations (Scopus)


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.

Original languageEnglish
Number of pages11
Publication statusPublished - 1989
Externally publishedYes
Event1st International Workshop on Parsing Technologies, IWPT 1989 - Pittsburgh, United States
Duration: 1989 Aug 281989 Aug 31


Conference1st International Workshop on Parsing Technologies, IWPT 1989
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Linguistics and Language
  • Language and Linguistics
  • Computer Science Applications


Dive into the research topics of 'Parsing 2-dimensional language'. Together they form a unique fingerprint.

Cite this