Paper: Parsing Linear Context-Free Rewriting Systems

ACL ID W05-1502
Title Parsing Linear Context-Free Rewriting Systems
Venue Workshop On Parsing Technology
Year 2005

We describe four different parsing algorithms for Linear Context-Free Rewriting Systems (Vijay-Shanker et al. , 1987). The algorithms are described as deduction systems, and possi- ble optimizations are discussed. The only parsing algorithms presented for linear context- free rewriting systems (LCFRS; Vijay-Shanker et al. , 1987) and the equivalent formalism multiple context-free grammar (MCFG; Seki et al. , 1991) are extensions of the CKY algorithm (Younger, 1967), more designed for their theoretical interest, and not for practical purposes. The reason for this could be that there are not many imple- mentations of these grammar formalisms. However, since a very important subclass of the Grammatical Framework (Ranta, 2004) is equivalent to LCFRS/MCFG (Ljunglöf, 2004a; Ljunglöf, 2004b...

  author    = {Burden, H{\aa}kan  and  Ljungl\"of, Peter},
  title     = {Parsing Linear Context-Free Rewriting Systems},
  booktitle = {Proceedings of the Ninth International Workshop on Parsing Technology},
  month     = {October},
  year      = {2005},
  address   = {Vancouver, British Columbia},
  publisher = {Association for Computational Linguistics},
  pages     = {11--17},
  url       = {}