Search

Актуальность работы обусловлена необходимостью автоматизации процесса принятия решений по юридическим вопросам в различных областях человеческой деятельности. В связи с этим, данная статья направлена на раскрытие подхода к организации процесса синтаксического анализа текстов на естественном языке для последующего автоматического построения семантической сети в соответствии с заданными входными документами. В качестве предметной области рассматривается сфера правовой информации. Предлагаемый авторами подход открывает широкие возможности по смысловому анализу правовых документов и их сравнении между собой. В статье приводится алгоритм восходящего синтаксического разбора. Результаты работы рассмотренного алгоритма применимы для последующего формирования базы знаний по имеющимся текстам правовых документов. В качестве модели представления знаний предполагается использовать семантические сети, что открывает широкие перспективы по автоматизации обработки правовой информации. Помимо решения часто встречающихся на практике задач принятия решений по юридическим вопросам, рассмотренный подход позволит автоматизировать решение такой трудоёмкой задачи, как автоматизация проведения юридической экспертизы нормативно-правовых актов. Проведение этой процедуры необходимо для того, чтобы принимаемые нормативные правовые акты соответствовали принципам допустимости и правомерности включения их в действующую систему права., The need to automate the decision-making process on legal issues in various fields of human activity determines the relevance of this work. In this regard, this article is aimed at disclosing an approach to organizing the process of parsing texts in natural language for the automatic construction of a semantic network corresponding to the given input documents. The subject area is the field of legal information. The approach proposed by the authors opens up wide possibilities for the semantic analysis of legal documents and their comparison with each other. The article discusses the organization of the process of bottom-up parsing natural language texts for the further automatic building a semantic network. The authors propose the text parsing algorithm. Its results are applicable for the further formation of the knowledge base on the available texts of legal documents. Semantic networks are supposed to be used as a model for representing knowledge, which opens up broad prospects for the automation of legal information processing. In addition to solving the problems of making decisions on legal issues that are often encountered in practice, the considered approach will automate the solution of such a time-consuming task as the automation of the legal examination of regulatory legal acts. The implementation of this procedure is necessary in order for the adopted regulatory legal acts to comply with the principles of admissibility and legality of their inclusion in the current system of law., МОДЕЛИРОВАНИЕ, ОПТИМИЗАЦИЯ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, Выпуск 1 (32) 2021, Pages 1-2

Parsing is a process of analyzing the input string in a sentence to define the syntax structures according to rules of grammar. This task is performed by a parser which will produce a parse tree as output. However, a problem occurs when the parsing process produces two or more parse trees in which the parser unable to represent a precise parse tree. This limitation is caused by ambiguity in the structure of sentences. Ambiguity is occurred when a word is classified more than one category of syntax and its usage will affect the semantics of the sentence. Thus, the parser needs to have an approach to solve the ambiguity problem and is able to process the most appropriate parse tree to present a sentence. Like other languages in the world, Malay language, a national language for Malaysian, is not exempted from ambiguity problem. However, due to its grammar being context-free grammar, the probabilistic context-free grammar approach can be used to support the parser in determining a more accurate parse tree. This study focuses on the development of statistical parser using a bottom-up technique for Malay language. The training data, in the form of simple Malay language sentences, are collected from various sources. Based on this training data, a statistical lexical corpus of Malay language which consists of vocabulary, grammar rules and their probability was developed. The bottom up parsing will be supported by implementing Cocke–Younger–Kasami (CYK) algorithm. The parser’s performance is evaluated based on its effectiveness to overcome ambiguity by suggesting a more precise parse tree. In conclusion, the Malay Language Parser can be useful to help user identify the appropriate parse tree and solve ambiguity issues in Malay Language.

This paper presents a methodology for rule based bottom up parsing technique forModern Standard Arabic (MSA) inContext Free Grammar (CFG) formalism in Phrase Structure Grammar (PSG) representation, where the grammar isautomatically extracted from a syntactically annotated corpus.The extracted grammar is used to build an automatic lexicon andgrammar rules module. Furthermore, the extracted CFG is further transformed into Probabilistic Context Free Grammar (PCFG)that could be used in a hybrid approach, which is also calculated automatically. The used corpus is the Penn ArabicTreebank(PATB)and algorithm implementation is performed with Natural Language Processing Toolkit (NLTK).The parsershowed that automatic extraction of grammar improved the grammar building phase in both coverage of structures and timeneeded, but still needs further manual constrains addition. Automatic extraction of grammar is able to enhance rule basedgrammar parsers and it will enable a new paradigm of statistically directed symbolic parsing.

Deep Learning has been widely applied for dependency parsing in recent years. In this paper, we propose an effective deep neural network model for graph-based dependency parsing. In our model, first, a special feature extraction layer is elaborately designed by combining the bidirectional Long Short-Term Memory (BLSTM) and the segment-based Convolutional Neural Network (SCNN), which is able to capture rich contextual information of the sentence for parsing. Then, the features learnt in feature extraction layer are fed into the standard feed-forward network, which is trained with max-margin criteria and makes predictions for dependency labels. Finally, to search the best dependency structure for the sentence from the dependency graph, the classical dynamic programming algorithm is used. In our experiment, we test the proposed model on 14 different languages including English, Chinese and German, whose results show that the proposed model achieves competitive accuracies in unlabeled attachment scores and labeled attachment scores compared with state-of-the-art dependency parsers. What's more, the model shows better ability in recovering long-distance dependencies compared with common neural network models.

Transition-based models can be fast and accurate for constituent parsing. Compared with chart-based models, they leverage richer features by extracting history information from a parser stack, which consists of a sequence of non-local constituents. On the other hand, during incremental parsing, constituent information on the right hand side of the current word is not utilized, which is a relative weakness of shift-reduce parsing. To address this limitation, we leverage a fast neural model to extract lookahead features. In particular, we build a bidirectional LSTM model, which leverages full sentence information to predict the hierarchy of constituents that each word starts and ends. The results are then passed to a strong transition-based constituent parser as lookahead features. The resulting parser gives 1.3% absolute improvement in WSJ and 2.3% in CTB compared to the baseline, giving the highest reported accuracies for fully-supervised parsing.

In recent years, transition-based parsers have shown promise in terms of efficiency and accuracy. Though these parsers have been extensively explored for multiple Indian languages, there is still considerable scope for improvement by properly incorporating syntactically relevant information. In this article, we enhance transition-based parsing of Hindi and Urdu by redefining the features and feature extraction procedures that have been previously proposed in the parsing literature of Indian languages. We propose and empirically show that properly incorporating syntactically relevant information like case marking, complex predication and grammatical agreement in an arc-eager parsing model can significantly improve parsing accuracy. Our experiments show an absolute improvement of ∼2% LAS for parsing of both Hindi and Urdu over a competitive baseline which uses rich features like part-of-speech (POS) tags, chunk tags, cluster ids and lemmas. We also propose some heuristics to identify ezafe constructions in Urdu texts which show promising results in parsing these constructions.

The task of natural language parsing can naturally be embedded in the maximum-margin framework for structured output prediction using an appropriate joint feature map and a suitable structured loss function. While there are efficient learning algorithms based on the cutting-plane method for optimizing the resulting quadratic objective with potentially exponential number of linear constraints, their efficiency crucially depends on the inference algorithms used to infer the most violated constraint in a current iteration. In this paper, we derive an extension of the well-known Cocke-Kasami-Younger (CKY) algorithm used for parsing with probabilistic context-free grammars for the case of loss-augmented inference enabling an effective training in the cutting-plane approach. The resulting algorithm is guaranteed to find an optimal solution in polynomial time exceeding the running time of the CKY algorithm by a term, which only depends on the number of possible loss values. In order to demonstrate the feasibility of the presented algorithm, we perform a set of experiments for parsing English sentences.

This chapter consists of four sections. Section 17.1 conceptualizes two fundamental approaches to syntax analysis -top-down parsing and bottom-up parsing. Then, Section 17.2 describes the former approach, while Section 17.3 explores the latter. Section 17.4 explains how to implement a syntax-directed translation, which is completely driven by a parser when producing target machine language programs.

A major challenge of semantic parsing is the vocabulary mismatch problem between natural language and target ontology. In this paper, we propose a sentence rewriting based semantic parsing method, which can effectively resolve the mismatch problem by rewriting a sentence into a new form which has the same structure with its target logical form. Specifically, we propose two sentence-rewriting methods for two common types of mismatch: a dictionary-based method for 1-N mismatch and a template-based method for N-1 mismatch. We evaluate our entence rewriting based semantic parser on the benchmark semantic parsing dataset -- WEBQUESTIONS. Experimental results show that our system outperforms the base system with a 3.4% gain in F1, and generates logical forms more accurately and parses sentences more robustly., Accepted as ACL 2016 long paper

The previous chapter opened the door to side effects and in particular to saving data from your Haskell application on disk or sending it through the network. However, the only true serialization mechanism that was introduced was the binary one, through the binary package.

Parsing Expression Grammars (PEGs) describe top-down parsers. Unfortunately, the error-reporting techniques used in conventional top-down parsers do not directly apply to parsers based on Parsing Expression Grammars (PEGs), so they have to be somehow simulated. While the PEG formalism has no account of semantic actions, actual PEG implementations add them, and we show how to simulate an error-reporting heuristic through these semantic actions. We also propose a complementary error reporting strategy that may lead to better error messages: labeled failures. This approach is inspired by exception handling of programming languages, and lets a PEG define different kinds of failure, with each ordered choice operator specifying which kinds it catches. Labeled failures give a way to annotate grammars for better error reporting, to express some of the error reporting strategies used by deterministic parser combinators, and to encode predictive top-down parsing in a PEG., Comment: Preprint (plus appendix) submitted to Science of Computer Programming

We propose a novel approach to cross-lingual part-of-speech tagging and dependency parsing for truly low-resource languages. Our annotation projection-based approach yields tagging and parsing models for over 100 languages. All that is needed are freely available parallel texts, and taggers and parsers for resource-rich languages. The empirical evaluation across 30 test languages shows that our method consistently provides top-level accuracies, close to established upper bounds, and outperforms several competitive baselines.

Semantic parsing maps a sentence in natural language into a structured meaning representation. Previous studies show that semantic parsing with synchronous context-free grammars (SCFGs) achieves favorable performance over most other alternatives. Motivated by the observation that the performance of semantic parsing with SCFGs is closely tied to the translation rules, this article explores to extend translation rules with high quality and increased coverage in three ways. First, we examine the difference between word alignments for semantic parsing and statistical machine translation (SMT) to better adapt word alignment in SMT to semantic parsing. Second, we introduce both structure and syntax informed nonterminals, better guiding the parsing in favor of well-formed structure, instead of using a uninformed nonterminal in SCFGs. Third, we address the unknown word translation issue via synthetic translation rules. Last but not least, we use a filtering approach to improve performance via predicting answer type. Evaluation on the standard GeoQuery benchmark dataset shows that our approach greatly outperforms the state of the art across various languages, including English, Chinese, Thai, German, and Greek.

Referential translation machine (RTM) is a prediction engine used for predicting the performance of natural language processing tasks including parsing, machine translation, and semantic similarity pioneering language, task, and domain independence. RTM results for predicting the performance of parsing (PPP) in out-of-domain or in-domain settings with different training sets and types of features present results independent of language or parser. RTM PPP models can be used without parsing using only text input and without any parser or language dependent information. Our results detail prediction performance, top selected features, and lower bound on the prediction error of PPP.

International audience

GLL (Generalised LL) parsing algorithms provide a sequentialisation of recursive-descent style parsing that yields efficient, compiled parsers which admit any context free grammar, including left recursive and non-left-factored rules. The resulting parsers retain the 'recursively decent' property that the structure of the parser closely follows the structure of the grammar; as such it is feasible to debug grammars by tracing the corresponding GLL parser using a conventional code debugger.In this paper we develop two variants of the GLL algorithm called FGLL and RGLL which respectively support (i) efficient parsing of factorised grammars and (ii) parsing using a reduced set of descriptors. Both techniques yield significant speed up on programming language grammars compared to the base GLL algorithm. We also discuss the ordering of descriptor processing and its effects on performance. Two new variants of the GLL algorithm.FGLL for efficient parsing of factorised grammars.RGLL for parsing using a reduced set of descriptors.Both techniques yield significant speed up on programming language grammars compared and can be used together.The modifications are all at algorithm level and do not depend on inplementation details of the GLL data structures.

Derivations under different grammar formalisms allow extraction of various dependency structures. Particularly, bilexical deep dependency structures beyond surface tree representation can be derived from linguistic analysis grounded by CCG, LFG, and HPSG. Traditionally, these dependency structures are obtained as a by-product of grammar-guided parsers. In this article, we study the alternative data-driven, transition-based approach, which has achieved great success for tree parsing, to build general dependency graphs. We integrate existing tree parsing techniques and present two new transition systems that can generate arbitrary directed graphs in an incremental manner. Statistical parsers that are competitive in both accuracy and efficiency can be built upon these transition systems. Furthermore, the heterogeneous design of transition systems yields diversity of the corresponding parsing models and thus greatly benefits parser ensemble. Concerning the disambiguation problem, we introduce two new techniques, namely, transition combination and tree approximation, to improve parsing quality. Transition combination makes every action performed by a parser significantly change configurations. Therefore, more distinct features can be extracted for statistical disambiguation. With the same goal of extracting informative features, tree approximation induces tree backbones from dependency graphs and re-uses tree parsing techniques to produce tree-related features. We conduct experiments on CCG-grounded functor–argument analysis, LFG-grounded grammatical relation analysis, and HPSG-grounded semantic dependency analysis for English and Chinese. Experiments demonstrate that data-driven models with appropriate transition systems can produce high-quality deep dependency analysis, comparable to more complex grammar-driven models. Experiments also indicate the effectiveness of the heterogeneous design of transition systems for parser ensemble, transition combination, as well as tree approximation for statistical disambiguation.

The backward-chaining inference strategy of Prolog is inefficient for a number of problems. The article proposes Contralog: a Prolog-conform, forward-chaining language and an inference engine that is implemented as a preprocessor-compiler to Prolog. The target model is Prolog, which ensures mutual switching from Contralog to Prolog and back. The Contralog compiler is implemented using Prolog's de facto standardized macro expansion capability. The article goes into details regarding the target model. We introduce first a simple application example for Contralog. Then the next section shows how a recursive definition of some problems is executed by their Contralog definition automatically in a dynamic programming way. Two examples, the well-known matrix chain multiplication problem and the Warshall algorithm are shown here. After this, the inferential target model of Prolog/Contralog programs is introduced, and the possibility for implementing the ReALIS natural language parsing technology is described relying heavily on Contralog's forward chaining inference engine. Finally the article also discusses some practical questions of Contralog program development.

In this study, the authors address the problem of parsing fashion images into mid-level semantic parts including upper-clothing, lower-clothing, skin, hair and background. These mid-level parts provide the regional information of fashion items and have potential value in high-level parsing process. The key idea of the method is to parse the mid-level parts by region expanding. Owing to the co-occurrence of pose skeleton and the proposed parts, the region expanding process starts from the super-pixels crossed by specific segments of pose skeleton. The super-pixels are then merged with their neighbours by conditional inference based on their position and perceptual similarity. To avoid the difficulties of training on arbitrary graph structures, conditional random fields (CRFs) are constructed on super-pixel chains, which are extracted from the generated expanding trees. This is followed by a voting stage to mix up the probabilities estimated by the chain-CRFs to obtain the final result. Experiments on two datasets show that the new method outperforms related approaches in regional accuracy and has good generalisation capability. Furthermore, the method can be easily employed to improve the performance of high-level parsing. Its effectiveness has been verified by another group of experiments on two state-of-the-art high-level parsing approaches.

Shift-reduce parsing enjoys the property of efficiency because of the use of efficient parsing algorithms like greedy/deterministic search and beam search. In addition, shift-reduce parsing is much simpler and easy to implement compared with other parsing algorithms. In this article, we explore constituent boundary information to improve the performance of shift-reduce phrase-structure parsing. In previous work, constituent boundary information has been used to speed up chart parsers successfully. However, whether it is useful for improving parsing accuracy has not been investigated. We propose two different models to capture constituent boundary information, based on which two sets of novel features are designed for a shift-reduce parser. The first model is a boundary prediction model that uses a classifier to predict the boundaries of constituents. We use automatically parsed data to train the classifier. The second one is a Tree Likelihood Model that measures the validity of a constituent by its likelihood which is calculated on automatically parsed data. Experimental results show that our proposed method outperforms a strong baseline by 0.8% and 1.6% in F-score on English and Chinese data, respectively, achieving the competitive parsing accuracies on Chinese (84.8%) and English (90.8%). To our knowledge, this is the first time for shift-reduce phrase-structure parsing to advance the state-of-the-art with constituent boundary information.

Current shift-reduce parsers “understand” the context by embodying a large number of binary indicator features with a discriminative model. In this article, we propose the action n-gram model, which utilizes the action sequence to help parsing disambiguation. The action n-gram model is trained on action sequences produced by parsers with the n-gram estimation method, which gives a smoothed maximum likelihood estimation of the action probability given a specific action history. We show that incorporating action n-gram models into a state-of-the-art parsing framework could achieve parsing accuracy improvements on three datasets across two languages.

The performance of an English-Korean machine translation system depends heavily on its English parser. The parser in this paper is a part of the rule-based English-Korean MT system, which includes many syntactic rules and performs the chart-based parsing. The parser generates too many structures due to many syntactic rules, so much time and memory are required. The rule-based parser has difficulty in analyzing and translating the long sentences including the commas because they cause high parsing complexity. In this paper, we propose the 3-phase parsing method with sentence segmentation to efficiently translate the long sentences appearing in usual. Each phase of the syntactic analysis applies its own independent syntactic rules in order to reduce parsing complexity. For the purpose, we classify the syntactic rules into 3 classes and design the 3-phase parsing algorithm. Especially, the syntactic rules in the 3rd class are for the sentence structures composed with commas. We present the automatic rule acquisition method for 3rd class rules from the syntactic analysis of the corpus, with which we aim to continuously improve the coverage of the parsing. The experimental results shows that the proposed 3-phase parsing method is superior to the prior parsing method using only intra-sentence segmentation in terms of the parsing speed/memory efficiency with keeping the translation quality.

Dependency parsing is a way of syntactic parsing and a natural language that automatically analyzes the dependency structure of sentences, and the input for each sentence creates a dependency graph. Part-Of-Speech (POS) tagging is a prerequisite for dependency parsing. Generally, dependency parsers do the POS tagging task along with dependency parsing in a pipeline mode. Unfortunately, in pipeline models, a tagging error propagates, but the model is not able to apply useful syntactic information. The goal of joint models simultaneously reduce errors of POS tagging and dependency parsing tasks. In this research, we attempted to utilize the joint model on the Persian and English language using Corbit software. We optimized the model's features and improved its accuracy concurrently. Corbit software is an implementation of a transition-based approach for word segmentation, POS tagging and dependency parsing. In this research, the joint accuracy of POS tagging and dependency parsing over the test data on Persian, reached 85.59% for coarse-grained and 84.24% for fine-grained POS. Also, we attained 76.01% for coarse-grained and 74.34% for fine-grained POS on English.

Extended BNF grammars (EBNF) allow regular expressions in the right parts of their rules. They are widely used to define languages, and can be represented by recursive Transition Networks (TN) consisting of a set of finite-state machines. We present a novel direct construction of efficient shift-reduce ELR(1) parsers for TNs. We show that such a parser works deterministically if the TN is free from the classical shift-reduce and reduce–reduce conflicts of the LR(1) parsers, and from a new conflict type called convergence conflict. Such a novel condition for determinism is proved correct and is more general than those proposed in the past for EBNF grammars or TNs. Such ELR(1) parsers perform fewer shift moves than the equivalent LR(1) parsers. A simple optimization of the reduction moves is described.

Programming languages grow over time that requires frequent changes in language manipulations such as compilation, interpretation, and analysis. Because the very first step of most language manipulations is parsing, whether parsing can adapt to changes easily, quickly, and correctly, it affects the scalability of language manipulations. Even though various parsing techniques have been well studied theoretically, their practical experiences in scalable frameworks have not been available.

We study the generalization of maximum spanning tree dependency parsing to maximum acyclic subgraphs. Because the underlying optimization problem is intractable even under an arc-factored model, we consider the restriction to noncrossing dependency graphs. Our main contribution is a cubic-time exact inference algorithm for this class. We extend this algorithm into a practical parser and evaluate its performance on four linguistic data sets used in semantic dependency parsing. We also explore a generalization of our parsing framework to dependency graphs with pagenumber at most k and show that the resulting optimization problem is NP-hard for k ≥ 2.

A natural language query builder interface retrieves the required data in structured form from database when query is entered in natural language. The user need not necessarily have sufficient technical knowledge of structured query language statements so nontechnical users can also use this proposed model. In natural language parsing, getting highly accurate syntactic analysis is a crucial step. Parsing of natural languages is the process of mapping an input string or a natural language sentence to its syntactic representation. Constituency parsing approach takes more time for parsing. So, natural language query builder interface is developed in which the parsing of natural language sentence is done by using dependency parsing approach. Dependency parsing technique is widespread in natural language domain because of its state-of-art accuracy and efficiency and also it performs best. In this paper, the buffering scheme is also proposed for natural language statements which will not load the whole sentence if it was done previously. Also there was a need of generalized access to all tables from database which is handled in this system.

The property of local parsability allows to parse inputs through inspecting only a bounded-length string around the current token. This in turn enables the construction of a scalable, data-parallel parsing algorithm, which is presented in this work. Such an algorithm is easily amenable to be automatically generated via a parser generator tool, which was realized, and is also presented in the following. Furthermore, to complete the framework of a parallel input analysis, a parallel scanner can also combined with the parser. To prove the practicality of a parallel lexing and parsing approach, we report the results of the adaptation of JSON and Lua to a form fit for parallel parsing (i.e. an operator-precedence grammar) through simple grammar changes and scanning transformations. The approach is validated with performance figures from both high performance and embedded multicore platforms, obtained analyzing real-world inputs as a test-bench. The results show that our approach matches or dominates the performances of production-grade LR parsers in sequential execution, and achieves significant speedups and good scaling on multi-core machines. The work is concluded by a broad and critical survey of the past work on parallel parsing and future directions on the integration with semantic analysis and incremental parsing.

Clauses and sentences rarely stand on their own in an actual discourse; rather, the relationship between them carries important information that allows the discourse to express a meaning as a whole beyond the sum of its individual parts. Rhetorical analysis seeks to uncover this coherence structure. In this article, we present CODRA— a COmplete probabilistic Discriminative framework for performing Rhetorical Analysis in accordance with Rhetorical Structure Theory, which posits a tree representation of a discourse. CODRA comprises a discourse segmenter and a discourse parser. First, the discourse segmenter, which is based on a binary classifier, identifies the elementary discourse units in a given text. Then the discourse parser builds a discourse tree by applying an optimal parsing algorithm to probabilities inferred from two Conditional Random Fields: one for intra-sentential parsing and the other for multi-sentential parsing. We present two approaches to combine these two stages of parsing effectively. By conducting a series of empirical evaluations over two different data sets, we demonstrate that CODRA significantly outperforms the state-of-the-art, often by a wide margin. We also show that a reranking of the k-best parse hypotheses generated by CODRA can potentially improve the accuracy even further.

The adaptability of a conventional parser to patent claim parsing is improved.Six claim syntax peculiarities that increase the difficulty of claim parsing are highlighted.New dependency syntax is proposed to handle Long Distance Dependencies.The efficiency of parsing is obviously improved with a segmentation strategy.The improvement on effectiveness of parsing is also promising in a model extraction problem. Patent claim parsing can contribute in many patent-related applications, such as patent search, information extraction, machine translation and summarization. However, patent claim parsing is difficult due to the special structure of patent claims. To overcome this difficulty, the challenges facing the patent claim parsing were first investigated and the peculiarities of claim syntax that obstruct dependency parsing were highlighted. To handle these peculiarities, this study proposes a new two-level parser, in which a conventional parser is imbedded. A patent claim is pre-processed in order to remove peculiarities before passed to the conventional parser. The process is based on a new dependency-based syntax called Independent Claim Segment Dependency Syntax (ICSDS). This two-lever parser has demonstrated promising improvement for patent claim parsing on both effectiveness and efficiency over the conventional parser.

Previous research demonstrates that discourse relations can help generate high-quality summaries. Existing studies usually adopt existing discourse parsers directly with no modifications, hence cannot take full advantage of discourse parsing. This paper describes a new single document summarization system. In contrast to previous work, we train a discourse parser specially for summarization by using summaries. The training data are dynamically changed during the training phase to enable the parser to grab the text units that are important for summaries. A special tree-based summary extraction algorithm is designed to work with the new parser. The proposed system enables us to combine discourse parsing and summarization in a unified scheme. Experiments on both the RST-DT and DUC2001 datasets show the effectiveness of the proposed method.

Writing a parser remains remarkably painful. Automatic parser generators offer a powerful and systematic way to parse complex grammars, but debugging conflicts in grammars can be time-consuming even for experienced language designers. Better tools for diagnosing parsing conflicts will alleviate this difficulty. This paper proposes a practical algorithm that generates compact, helpful counterexamples for LALR grammars. For each parsing conflict in a grammar, a counterexample demonstrating the conflict is constructed. When the grammar in question is ambiguous, the algorithm usually generates a compact counterexample illustrating the ambiguity. This algorithm has been implemented as an extension to the CUP parser generator. The results from applying this implementation to a diverse collection of faulty grammars show that the algorithm is practical, effective, and suitable for inclusion in other LALR parser generators.

our dependency parsing experiments on two Indian Languages, Telugu and Hindi. We first explore two most popular dependency parsers namely, Malt parser and MST parser. Considering pros of both these parsers, we develop a hybrid approach combining the output of these two parsers in an intuitive manner. For Hindi, we report our results on test data provided in the for gold standard track of Hindi Shared Task on Parsing at workshop on Machine Translation and parsing in Indian Languages, Coling 2012. Our system secured unlabeled attachment score of 95.2% and labelled attachment score 90.7%. For Telugu, we report our results on test data provided in the ICON 2010 Tools Contest on Indian Languages Dependency Parsing. Our system secured unlabeled attachment score of 92.0% and labelled attachment score 69.5%.

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 state-of-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.

Gap parsing is an algorithm for parsing incomplete input strings which include some gaps. Gap parsing is different from conventional parsing, and as known results, one-gap parsing algorithms for arbitrary context-free grammar and LL(1) grammar have and time complexity, respectively. This paper presents a one-gap parsing algorithm for extended PLR(1) grammars. Extended PLR(1) grammars are the class of grammars smaller than LR(1) but much larger than LL(1). The one-gap parsing algorithm of the grammar class is shown to have the time complexity of , which is equal to the complexity of one-gap parsing algorithms for LL(1) grammars.