Implementation of a Chomsky-Schützenberger n-best parser for weighted multiple context-free grammars

Proceedings of NAACL-HLT 2019, pages 178–191 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 178 Implementation of a Chomsky-Sch¨utzenberger n-Best Parser for Weighted Multiple Context-Free Grammars Thomas Ruprecht and Tobias Denkinger Faculty of Computer Science Technische Universit¨at Dresden 01062 Dresden, Germany {thomas.ruprecht,tobias.denkinger}@tu-dresden.de Abstract Constituent parsing has been studied ex- tensively in the last decades. Chomsky- Sch¨utzenberger parsing as an approach to con- stituent parsing has only been investigated the- oretically, yet. It uses the decomposition of a language into a regular language, a ho- momorphism, and a bracket language to di- vide the parsing problem into simpler subprob- lems. We provide the first implementation of Chomsky-Sch¨utzenberger parsing. It employs multiple context-free grammars and incorpo- rates many refinements to achieve feasibility. We compare its performance to state-of-the-art grammar-based parsers. 1 Introduction The description of the syntax of natural lan- guages (such as Danish, English, and German) with the help of formal grammars has been stud- ied since Chomsky (1956). With a formal gram- mar, computers can calculate a syntactic represen- tation (called parse) of a sentence in a natural lan- guage. Of the grammar classes in the Chomsky hi- erarchy (Chomsky, 1959), context-free grammars (short: CFGs) lack the expressive power necessary to model natural languages (Shieber, 1985) and parsing with context-sensitive grammars cannot be done efficiently (i.e. in polynomial time). This led to the introduction of a series of classes of mildly context-sensitive grammars (Joshi, 1985) that al- low parsing in polynomial time but also capture an increasing amount of phenomena present in nat- ural languages. Tree adjoining grammars (Joshi et al., 1975), linear context-free string-rewriting systems (short: LCFRSs, Vijay-Shanker et al., 1987), and multiple CFGs (short: MCFGs, Seki et al., 1991) are among those classes. Chomsky-Sch¨utzenberger (short: CS) parsing was introduced by Hulden (2011) for CFGs and extended to MCFGs by Denkinger (2017). It uses a classical theorem by Chomsky and Sch¨utzenberger (1963, or the generalisation by Yoshinaka et al., 2010), which states that the lan- guage L(G) of a CFG (or an MCFG) G can be represented by a regular language R, a homo- morphism h, and a Dyck language (resp. multiple Dyck language) D such that L(G) = h(R ∩ D). The elements of R ∩ D correspond to parses in G. For a sentence w, a CS parser calculates the ele- ments of h−1(w)∩R∩D and transforms them into parses. CS parsing can be viewed as a coarse-to- fine mechanism where R corresponds to the coarse grammar and R ∩ D to the fine grammar. The respective coarse-to-fine pipeline consists of (con- ceptually) simple operations such as h−1 or the in- tersection with R, which provides great flexibility. The flexibility is used to provide a fallback mech- anism in case a finer stage of the pipeline rejects all proposals of a coarser stage. It also permits CS parsing in a broader setting than usual (for pars- ing) with minimal modification (see sec. 6). We suspected that the coarse-to-fine view on CS parsing leads …

Content truncated to 500 words