TR93-04

Lexicalized Context-Free Grammar: A Cubic-Time Parsable, Lexicalized Normal Form for Context-Free Grammar That Preserves Tree Structure

    •  Yves Schabes, Richard C. Waters, "Lexicalized Context-Free Grammar: A Cubic-Time Parsable, Lexicalized Normal Form for Context-Free Grammar That Preserves Tree Structure", Tech. Rep. TR93-04, Mitsubishi Electric Research Laboratories, Cambridge, MA, June 1993.
      BibTeX TR93-04 PDF
      • @techreport{MERL_TR93-04,
      • author = {Yves Schabes, Richard C. Waters},
      • title = {Lexicalized Context-Free Grammar: A Cubic-Time Parsable, Lexicalized Normal Form for Context-Free Grammar That Preserves Tree Structure},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR93-04},
      • month = jun,
      • year = 1993,
      • url = {https://www.merl.com/publications/TR93-04/}
      • }
Abstract:

Lexicalized context-free grammar (LCFG) is a tree-based formalism that makes use of both tree substitution and a restricted form of tree adjunction. Because of its use of adjunction, LCFG allows sufficient freedom in the way derivations can be performed that lexicalization of context-free grammars (CFGs) is possible while preserving the structure of the trees derived by the CFGs. However, the tree adjunction permitted is sufficiently restricted that LCFGs are string-wise equivalent to CFGs and have the same cubic-time complexity bounds for recognition and parsing.