The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Parsing-Based Methods <s> A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR( k ) algorithm and the familiar top-down algorithm. It has a time bound proportional to n 3 (where n is the length of the string being parsed) in general; it has an n 2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick. <s> BIB001 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Parsing-Based Methods <s> “Meaning” may be assigned to a string in a context-free language by defining “attributes” of the symbols in a derivation tree for that string. The attributes can be defined by functions associated with each production in the grammar. This paper examines the implications of this process when some of the attributes are “synthesized”, i.e., defined solely in terms of attributes of thedescendants of the corresponding nonterminal symbol, while other attributes are “inherited”, i.e., defined in terms of attributes of theancestors of the nonterminal symbol. An algorithm is given which detects when such semantic rules could possibly lead to circular definition of some attributes. An example is given of a simple programming language defined with both inherited and synthesized attributes, and the method of definition is compared to other techniques for formal specification of semantics which have appeared in the literature. <s> BIB002 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Parsing-Based Methods <s> This paper presents a semantic parsing and reasoning approach to automatically solving math word problems. A new meaning representation language is designed to bridge natural language text and math expressions. A CFG parser is implemented based on 9,600 semi-automatically created grammar rules. We conduct experiments on a test set of over 1,500 number word problems (i.e., verbally expressed number problems) and yield 95.4% precision and 60.2% recall. <s> BIB003
The work of BIB003 can be viewed as an extension of tree-based approaches to solve a math problem with multiple equations. Since the objective is no longer to build an equation tree, a meaning representation language called DOL is designed as the structural semantic representation of natural language text. The core component is a semantic parser that transforms the textual sentences into DOL trees. The parsing algorithm is based on context-free grammar (CFG) BIB002 , BIB001 , a popular mathematical system for modeling constituent structure in natural languages. For every DOL node type, the lexicon and grammar rules are constructed in a semi-supervised manner. The association between math-related concepts and their grammar rules is manually constructed. Finally, the CFG parser is built on top of 9, 600 grammar rules. During the parsing, a score is calculated for each DOL node and the derivation of the DOL trees with the highest score is selected to obtain the answer via a reasoning module.