Search

Parsers are omnipresent in almost all software systems. However, an operational implementation of parsers cannot answer many "how", "why" and "what if" questions, why does this parser not accept this string, or, can we have to parser for it to accept a set of strings? To lift the parsing theory to answer such questions, we build a symbolic encoding of parsing. Our symbolic encoding, that we referred to as a parse condition, is a logical condition that is satisfiable if and only if a given string w can be successfully parsed using a grammar G . We build an SMT encoding of such parse conditions for LL(1) grammars and demonstrate its utility by building three applications over it: automated repair of syntax errors in Tiger programs, automated parser synthesis to automatically synthesize LL(1) parsers from examples, and automatic root cause analysis of parser construction to debug errors in parse tables. We implement our ideas into a tool, Cyclops , that successfully repairs 80% of our benchmarks (675 buggy Tiger programs), clocking an average of 30 s per repair, synthesize parsers for interesting languages from examples, and ranks the ground truth as the topmost ranked reason for failure in more than 85% of our instances. On our deployment of Cyclops in a compiler design course, 91 of 128 students gave a positive response stating that assistance from Cyclops was indeed useful. [ABSTRACT FROM AUTHOR]

This paper presents a construction method for a deterministic one-symbol lookahead LR parser which allows non-terminals in the parser look-ahead. This effectively relaxes the requirement of parsing the reverse of the right-most derivation of a string/sentence. This is achieved by replacing the deterministic push down automata of LR parsing by a two-stack automata. The class of grammars accepted by the two-stack parser properly contains the LR(k) grammars. Since the modification to the table-driven LR parsing process is relatively minor and mostly impacts the creation of the goto and action tables, a parser modified to adopt the two-stack process should be comparable in size and performance to LR parsers. - [ABSTRACT FROM AUTHOR]

Grammar-checking is a concept of interest in many natural language environments. It typically involves the evaluation of the grammaticality of transmitted messages, be it written or verbal. Automated grammaticality evaluation is the examination of natural language text for grammatical accuracy using computer software. The current study examined the different approaches adopted in computational linguistics for evaluating the grammaticality of texts. The categories of approaches examined are those within the shallow parsing induced grammar approach. The study tried to show the trend so far and the possible direction for the future. [ABSTRACT FROM AUTHOR]

It is a major open problem whether the (min, +)-product of two n × n matrices has a truly subcubic (i.e., O(n3-ε) for ε > 0) time algorithm; in particular, since it is equivalent to the famous all-pairs-shortest-paths problem (APSP) in n-vertex graphs. Some restrictions of the (min,+)-product to special types of matrices are known to admit truly subcubic algorithms, each giving rise to a special case of APSP that can be solved faster. In this paper we consider a new, different, and powerful restriction in which all matrix entries are integers and one matrix can be arbitrary, as long as the other matrix has "bounded differences" in either its columns or rows, i.e., any two consecutive entries differ by only a small amount. We obtain the first truly subcubic algorithm for this bounded-difference (min, +)-product (answering an open problem of Chan and Lewenstein). Our new algorithm, combined with a strengthening of an approach of Valiant for solving context-free grammar parsing with matrix multiplication, yields the first truly subcubic algorithms for the following problems: language edit distance (a major problem in the parsing community), RNA folding (a major problem in bioinformatics), and optimum stack generation (answering an open problem of Tarjan). [ABSTRACT FROM AUTHOR]

This work presents the development and evaluation of an extended Urdu parser. It further focuses on issues related to this parser and describes the changes made in the Earley algorithm to get accurate and relevant results from the Urdu parser. The parser makes use of a morphologically rich context free grammar extracted from a linguistically-rich Urdu treebank. This grammar with sufficient encoded information is comparable with the stateof- the-art parsing requirements for the morphologically rich Urdu language. The extended parsing model and the linguistically rich extracted-grammar both provide us better evaluation results in Urdu/Hindi parsing domain. The parser gives 87% of f-score, which outperforms the existing parsing work of Urdu/Hindi based on the tree-banking approach. [ABSTRACT FROM AUTHOR]

The complexity of parsing with synchronous context-free grammars is polynomial in the sentence length for a fixed grammar, but the degree of the polynomial depends on the grammar. Specifically, the degree depends on the length of rules, the permutations represented by the rules, and the parsing strategy adopted to decompose the recognition of a rule into smaller steps. We address the problem of finding the best parsing strategy for a rule, in terms of space and time complexity. We show that it is NP-hard to find the binary strategy with the lowest space complexity. We also show that any algorithm for finding the strategy with the lowest time complexity would imply improved approximation algorithms for finding the tree width of general graphs. [ABSTRACT FROM AUTHOR]

In this paper I tackle the question of what basic form an analytical method for articulating and ultimately assessing visual representations should take. I start from the assumption that scientific images, being less prone to interpretive complication than artworks, are ideal objects from which to engage this question. I then assess a recent application of Nelson Goodman's aesthetics to the project of parsing scientific images, Laura Perini's ‘The truth in pictures’. I argue that, although her project is an important one, her Goodmanian conventionalism produces a method of analysis that is incapable of adequately parsing a certain class of pictures and her focus on truth is unnecessary. This speaks against the promise of Goodman's analytical strategy for elucidating visual content and reasoning in the sciences and elsewhere. As an alternative, I develop John Willats’ analytical method and compare it to Perini's through engaging three of her examples—a chemical diagram, a graph and an electron micrograph. Ultimately, a space remains open for a mixed system where Willats’ account provides pictorial analysis and the Goodman–Perini approach parses visual languages. [ABSTRACT FROM PUBLISHER]

We present a new approach for parsing two-dimensional input using relational grammars and fuzzy sets. A fast, incremental parsing algorithm is developed, motivated by the two-dimensional structure of written mathematics. The approach reports all identifiable parses of the input. The parses are represented as a fuzzy set, in which the membership grade of a parse measures the similarity between it and the handwritten input. To identify and report parses efficiently, we adapt and apply existing techniques such as rectangular partitions and shared parse forests, and introduce new ideas such as relational classes and interchangeability. We also present a correction mechanism that allows users to navigate parse results and choose the correct interpretation in case of recognition errors or ambiguity. Such corrections are incorporated into subsequent incremental recognition results. Finally, we include two empirical evaluations of our recognizer. One uses a novel user-oriented correction count metric, while the other replicates the CROHME 2011 math recognition contest. Both evaluations demonstrate the effectiveness of our proposed approach. [ABSTRACT FROM AUTHOR]

We present a constituency parsing system for Modern Hebrew. The system is based on the PCFG-LA parsing method of Petrov et al. (2006), which is extended in various ways in order to accommodate the specificities of Hebrew as a morphologically rich language with a small treebank. We show that parsing performance can be enhanced by utilizing a language resource external to the treebank, specifically, a lexicon-based morphological analyzer. We present a computational model of interfacing the external lexicon and a treebank-based parser, also in the common case where the lexicon and the treebank follow different annotation schemes. We show that Hebrew word-segmentation and constituency-parsing can be performed jointly using CKY lattice parsing. Performing the tasks jointly is effective, and substantially outperforms a pipeline-based model. We suggest modeling grammatical agreement in a constituency-based parser as a filter mechanism that is orthogonal to the grammar, and present a concrete implementation of the method. Although the constituency parser does not make many agreement mistakes to begin with, the filter mechanism is effective in fixing the agreement mistakes that the parser does make. These contributions extend outside of the scope of Hebrew processing, and are of general applicability to the NLP community. Hebrew is a specific case of a morphologically rich language, and ideas presented in this work are useful also for processing other languages, including English. The lattice-based parsing methodology is useful in any case where the input is uncertain. Extending the lexical coverage of a treebank-derived parser using an external lexicon is relevant for any language with a small treebank. [ABSTRACT FROM AUTHOR]

Integrated Development Environments (IDEs) increase programmer productivity, providing rapid, interactive feedback based on the syntax and semantics of a language. Unlike conventional parsing algorithms, scannerless generalized-LR parsing supports the full set of context-free grammars, which is closed under composition, and hence can parse languages composed from separate grammar modules. To apply this algorithm in an interactive environment, this article introduces a novel error recoverymechanism. Our approach is language independent, and relies on automatic derivation of recovery rules from grammars. By taking layout information into consideration it can efficiently suggest natural recovery suggestions. [ABSTRACT FROM AUTHOR]

We present methods for reducing the worst-case and typical-case complexity of a context-free parsing pipeline via hard constraints derived from finite-state pre-processing. We perform O(n) predictions to determine if each word in the input sentence may begin or end a multi-word constituent in chart cells spanning two or more words, or allow single-word constituents in chart cells spanning the word itself. These pre-processing constraints prune the search space for any chart-based parsing algorithm and significantly decrease decoding time. In many cases cell population is reduced to zero, which we term chart cell "closing." We present methods for closing a sufficient number of chart cells to ensure provably quadratic or even linear worst-case complexity of context-free inference. In addition, we apply high precision constraints to achieve large typical-case speedups and combine both high precision and worst-case bound constraints to achieve superior performance on both short and long strings. These bounds on processing are achieved without reducing the parsing accuracy, and in some cases accuracy improves. We demonstrate that our method generalizes across multiple grammars and is complementary to other pruning techniques by presenting empirical results for both exact and approximate inference using the exhaustive CKY algorithm, the Charniak parser, and the Berkeley parser. We also report results parsing Chinese, where we achieve the best reported results for an individual model on the commonly reported data set. [ABSTRACT FROM AUTHOR]

Parsing of Arabic sentences is a necessary mechanism for many natural language processing applications such as machine translation, question answering, knowledge extraction and information retrieval. In this study, we present a top-down chart parser for parsing simple Arabic sentences, including nominal and verbal sentences within specific domain Arabic grammar. We used the Context Free Grammar (CFGs) to represent the Arabic grammar. We first developed the Arabic grammar rules that give precise description of grammatical sentences. Then, we implemented the parser that assigns grammatical structure to the input sentence. The parser is tested on sentences extracted from real documents. Experimental results showed the effectiveness of the proposed top-down chart parser for parsing modern standard Arabic sentences. From a practical perspective, the parser is able to satisfy syntactic constraints and reduce parsing ambiguity. [ABSTRACT FROM AUTHOR]

Bilexical context-free grammars (2-LCFGs) have proved to be accurate models for statistical natural language parsing. Existing dynamic programming algorithms used to parse sentences under these models have running time of O(|w|4), where w is the input string. A 2-LCFG is splittable if the left arguments of a lexical head are always independent of the right arguments, and vice versa. When a 2-LCFGs is splittable, parsing time can be asymptotically improved to O(|w|³). Testing this propertyis therefore of central interest to parsing efficiency. In this article, however, we show the negative result that splittability of 2-LCFGs is undecidable. [ABSTRACT FROM AUTHOR]

Noun phrases (NPs) are a crucial part of natural language, and can have a very complex structure. However, this NP structure is largely ignored by the statistical parsing field, as the most widely-used corpus is not annotated with it. This lack of gold-standard data has restricted previous efforts to parse NPs, making it impossible to perform the supervised experiments that have achieved high performance in so many Natural Language Processing (NLP) tasks. We comprehensively solve this problem by manually annotating NP structure for the entire Wall Street Journal section of the Penn Treebank. The inter-annotator agreement scores that we attain dispel the belief that the task is too difficult, and demonstrate that consistent NP annotation is possible. Our gold-standard NP data is now available for use in all parsers. We experiment with this new data, applying the Collins (2003) parsing model and find that its recovery of NP structure is significantly worse than its overall performance. The parser's F-score is up to 5.69% lower than a baseline that uses deterministic rules. Through much experimentation, we determine that this result is primarily caused by a lack of lexical information. To solve this problem we construct a wide-coverage, large-scale NP Bracketing system. With our Penn Treebank data set, which is orders of magnitude larger than those used previously, we build a supervised model that achieves excellent results. Our model performs at 93.8% F-score on the simple task that most previous work has undertaken, and extends to bracket longer, more complex NPs that are rarely dealt with in the literature. We attain 89.14% F-score on this much more difficult task. Finally, we implement a post-processing module that brackets NPs identified by the Bikel (2004) parser. Our NP Bracketing model includes a wide variety of features that provide the lexical information that was missing during the parser experiments, and as a result, we outperform the parser by 9.04% F-score. These experiments demonstrate the utility of the corpus, and show that many NLP applications can now make use of NP structure. [ABSTRACT FROM AUTHOR]

We introduce dependency parsing schemata, a formal framework based on Sikkel's parsing schemata for constituency parsers, which can be used to describe, analyze, and compare dependency parsing algorithms. We use this framework to describe several well-known projective and non-projective dependency parsers, build correctness proofs, and establish formal relationships between them. We then use the framework to define new polynomial-time parsing algorithms for various mildly non-projective dependency formalisms, including well-nested structures with their gap degree bounded by a constant k in time O(n5+2k), and a new class that includes all gap degree k structures present in several natural language treebanks (which we call mildly ill-nested structures for gap degree k) in time O(n4+3k). Finally, we illustrate how the parsing schema framework can be applied to Link Grammar, a dependency-related formalism. [ABSTRACT FROM AUTHOR]

This letter presents a modified Pegasos algorithm for graphbased dependency parsing. We show that the modified Pegasos algorithm outperforms the margin infused relaxed and passive aggressive algorithms in three languages. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm based on collocational data for word sense disambiguation (WSD). The aim of this algorithm is to maximize efficiency by minimizing (1) computational costs and (2) linguistic tagging/annotation. The formalization of our WSD algorithm is based on discriminant function analysis (DFA). This statistical technique allows us to parametrize each collocational item with its meaning, using just bare text. The parametrized data allow us to classify cases (sentences with an ambiguous word) into the values of a categorical dependent (each of the meanings of the ambiguous word). To evaluate the validity and efficiency of our WSD algorithm, we previously hand sense-tagged all the sentences containing ambiguous words and then cross-validated the hand sense-tagged data with the automatic WSD performance. Finally, we present the global results of our algorithm after applying it to a limited set of words in both languages: Spanish and English, highlighting the points we consider relevant for further analysis. [ABSTRACT FROM AUTHOR]

Recent developments in computational terminology call for the design of multiple and complementary tools for the acquisition, the structuring and the exploitation of terminological data. This paper proposes to bridge the gap between term acquisition and thesaurus construction by offering a framework for automatic structuring of multi-word candidate terms with the help of corpus-based links between single-word terms. First, we present a system for corpus-based acquisition of terminological relationships through discursive patterns. This system is built on previous work on automatic extraction of hyponymy links through shallow parsing. Second, we show how hypernym links between single-word terms can be extended to semantic links between multi-word terms through corpus-based extraction of semantic variants. The induced hierarchy is incomplete but provides an automatic generalization of single-word terms relations to multi-word terms that are pervasive in technical thesauri and corpora. [ABSTRACT FROM AUTHOR]

This article presents a study which investigates the extent of grammatical variation between late Middle English and present-day English. In the study, ambiguity is not considered disadvantageous at all since the shallower the parsing process and the lower the number of ad-hoc constraints at work, the better. The study made use of the Functional Dependency Grammar (FDG) automatic parser so as to examine the results of its application to two version of the same text, namely, chapters 20 to 25 of The Book of Margery Kempe, totaling 9,694 running words, an electronic version of which can be extracted from the Helsinki Corpus of English Texts, sample 1 of The Book. The goal of the pilot study is to check whether a parser which has been fully trained for the analysis of present-day English (PDE) texts, and is based on surface rules and not on abstract axioms will do successfully when applied to older texts or not. The differences between the analyses produced by the parser affect the whole scale of linguistic categorization, namely, the lexical/categorial, phrasal and sentential level. The ensuing description of the linguistic phenomena triggering the different analyses will thus be organized according to the syntactic layers on which the parser has acted distinctly

Grammatical Framework (GF) is a special-purpose functional language for defining grammars. It uses a Logical Framework (LF) for a description of abstract syntax, and adds to this a notation for defining concrete syntax. GF grammars themselves are purely declarative, but can be used both for linearizing syntax trees and parsing strings. GF can describe both formal and natural languages. The key notion of this description is a grammatical object, which is not just a string, but a record that contains all information on inflection and inherent grammatical features such as number and gender in natural languages, or precedence in formal languages. Grammatical objects have a type system, which helps to eliminate run-time errors in language processing. In the same way as a LF, GF uses dependent types in abstract syntax to express semantic conditions, such as well-typedness and proof obligations. Multilingual grammars, where one abstract syntax has many parallel concrete syntaxes, can be used for reliable and meaning-preserving translation. They can also be used in authoring systems, where syntax trees are constructed in an interactive editor similar to proof editors based on LF. While being edited, the trees can simultaneously be viewed in different languages. This paper starts with a gradual introduction to GF, going through a sequence of simpler formalisms till the full power is reached. The introduction is followed by a systematic presentation of the GF formalism and outlines of the main algorithms: partial evaluation and parser generation. The paper concludes by brief discussions of the Haskell implementation of GF, existing applications, and related work. [ABSTRACT FROM AUTHOR]

A context-free grammar, a stochastic grammar, and a context-free tree grammar have been used in the past in the synthetic approach to pattern recognition. However, since a pattern is primarily context-dependent, some top-down and bottom-up parsers have been proposed for context-sensitive language (CSL). Although the bottom-up version of the error-correcting parser for CSL has been known, it has a disadvantage in that it converts an input staring of length n into a string of length (n = ) k + n (k is the maximum number of consecutive deletions of terminal symbols). As a result, this paper proposes a top-down ECP (error-correcting-parser) for a context-sensitive language. [ABSTRACT FROM AUTHOR]