A scheme for lr(k) parsing with error recovery part iii: error correction

The paper is the third in a series of three papers devoted to a detailed study of LR(k) parsing with error recovery and correction. A new class of syntax errors is introduced, called (k)-local parser defined errors, which suit better than the conventional minimum distance errors for characterization of error detection and recovery in LR(k) parsing. The question whether a given string has n k-local parser defined errors for some integer n is shown to be decidable. Using the formalization of LR(k) parsing and error recovery presented in the first and the second paper in the series it is shown that the canonical LR(k) parser of an LR(k) grammar always has an error recovering extension which is able to produce a correction for any terminal string containing only (k)-local parser defined errors.     

Conversion and parsing of tree transducers for syntactic pattern analysis

The conversion algorithms for two classes of tree transducers, i.e., simple generalized syntax-directed tree translation (SGSDTT) and generalized finite state transformation (GFST), are proposed. A top-down backtrack parsing algorithm for a GFST is presented. The minimum distance structure-preserved error-correcting tree automaton is also extended to be a parser for SGSDTT. Finally, the tree transducers are applied to modeling and analysis of human motion.This work was supported by the NSF Grant IST 79-18884.     

Parsing and translation of (attributed) expansive graph languages for scene analysis

In this paper, we suggest a class of (attributed) expansive graph grammars which generate languages contained in a graph family ?. It turns out that by means of node renumbering using a very effi-cient algorithm, any graph in ? can be converted into a standard form, which enables the use of related string representation for that graph to facilitate the syntax analysis. As a consequence, the syntax analysis of (attributed) expansive graph language is very efficient and almost like the parsing of tree languages. Furthermore, a syntax-directed transla-tion can be established for mapping one (attributed) expansive graph language to another. Finally, since many relational graphs for scene analysis can be considered as belonging to these graph languages, the proposed graph grammar model appears to be quite attractive from the application point of view.     

Syntax optimization for and parsing of patterns

Theory and algorithm for optimization of a directed and labeled tree are presented. Their application for optimizing any finite pattern grammar represented in the form of a tree is discussed. Tree optimization leads to loss information which is essential for identification of patterns. Special technique for preserving this information has been suggested.Finally, outlines of two different algorithms for the parsing of patterns are included. The tree parser uses the optimized tree and the table-driven parser uses the optimized syntax stored in four separate tables.     

VPGE:一个LALR(1)分析器的可视化生成和断点调试系统

LALR(1)分析程序生成系统在编译器构造领域以外被许多普通软件开发者学习和使用.为帮助用户理解LALR(1)分析器方法,编写出正确、完整、无语法分析冲突的文法规范,严格定义了使用LALR(1)分析器生成器时用户可能遇到的几类文法问题,描述一个为帮助用户解决这些问题而开发的LALR(1)分析器可视化和断点调试系统VPGE.VPGE以多种视图显示LALR(1)分析器的数据结构,包括状态栈、符号栈、输入符号串、分析树和底层的自动机,支持LR分析动作的单步执行和断点调试.性能实验结果表明,VPGE比GNU的Bison有更快的分析器生成速度,从而提供了一个LALR(1)文法及分析器的快速交互式调试环境.     

Software visualization of LR parsing and synthesized attribute evaluation

Visual YACC is a tool that automatically creates visualizations of the YACC LR parsing process and synthesized attribute computation. The Visual YACC tool works by instrumenting a standard YACC grammar with graphics calls that draw the appropriate data structures given the current actions by the parser. The new grammar is processed by the YACC tools and the resulting parser displays the parse stack and parse tree for every step of the parsing process of a given input string. Visual YACC was initially designed to be used in compiler construction courses to supplement the teaching of parsing and syntax directed evaluation. We have also found it to be useful in the difficult task of debugging YACC grammars. In this paper, we describe this tool and how it is used in both contexts. We also detail two different implementations of this tool: one that produces a parser written in C with calls to Motif; and a second implementation that generates Java source code. Copyright © 1999 John Wiley & Sons, Ltd.     

Component-based LR parsing

A language implementation with proper compositionality enables a compiler developer to divide-and-conquer the complexity of building a large language by constructing a set of smaller languages. Ideally, these small language implementations should be independent of each other such that they can be designed, implemented and debugged individually, and later be reused in different applications (e.g., building domain-specific languages). However, the language composition offered by several existing parser generators resides at the grammar level, which means all the grammar modules need to be composed together and all corresponding ambiguities have to be resolved before generating a single parser for the language. This produces tight coupling between grammar modules, which harms information hiding and affects independent development of language features. To address this problem, we have developed a novel parsing algorithm that we call Component-based LR (CLR) parsing, which provides code-level compositionality for language development by producing a separate parser for each grammar component. In addition to shift and reduce actions, the algorithm extends general LR parsing by introducing switch and return actions to empower the parsing action to jump from one parser to another. Our experimental evaluation demonstrates that CLR increases the comprehensibility, reusability, changeability and independent development ability of the language implementation. Moreover, the loose coupling among parser components enables CLR to describe grammars that contain LR parsing conflicts or require ambiguous token definitions, such as island grammars and embedded languages.     

Parsing Arabic using induced probabilistic context free grammar

The importance of the parsing task for NLP applications is well understood. However developing parsers remains difficult because of the complexity of the Arabic language. Most parsers are based on syntactic grammars that describe the syntactic structures of a language. The development of these grammars is laborious and time consuming. In this paper we present our method for building an Arabic parser based on an induced grammar, PCFG grammar. We first induce the PCFG grammar from an Arabic Treebank. Then, we implement the parser that assigns syntactic structure to each input sentence. The parser is tested on sentences extracted from the treebank (1650 sentences).We calculate the precision, recall and f-measure. Our experimental results showed the efficiency of the proposed parser for parsing modern standard Arabic sentences (Precision: 83.59 %, Recall: 82.98 % and F-measure: 83.23 %).     

On parsing arithmetic expressions in a multiprocessing environment

Summary Some decomposition of the parsing of the sentences of context-free grammars into sequences of independant sub-tasks is proposed. An example of grammar is presented, for which this decomposition provides an efficient parser for a multiprocessing environment. The average speed-up resulting from the parallelization of the parser of an arithmetic infix grammar is evaluated by means of probabilistic models and real world measurements.     

ANTLRWorks: an ANTLR grammar development environment

Programmers tend to avoid using language tools, resorting to ad hoc methods, because tools can be hard to use, their parsing strategies can be difficult to understand and debug, and their generated parsers can be opaque black‐boxes. In particular, there are two very common difficulties encountered by grammar developers: understanding why a grammar fragment results in a parser non‐determinism and determining why a generated parser incorrectly interprets an input sentence. This paper describes ANTLRWorks, a complete development environment for ANTLR grammars that attempts to resolve these difficulties and, in general, make grammar development more accessible to the average programmer. The main components are a grammar editor with refactoring and navigation features, a grammar interpreter, and a domain‐specific grammar debugger. ANTLRWorks' primary contributions are a parser non‐determinism visualizer based on syntax diagrams and a time‐traveling debugger that pays special attention to parser decision‐making by visualizing lookahead usage and speculative parsing during backtracking. Copyright © 2008 John Wiley & Sons, Ltd.     

An Operator Precedence Parser for Standard Prolog Text

Prolog is a language with a dynamic grammar which is the result of embedded operator declarations. The parsing of such a language cannot be done easily by means of standard tools. Most often, an existing parsing technique for a static grammar is adapted to deal with the dynamic constructs. This paper uses the syntax definition as defined by the ISO standard for the Prolog language. It starts with a brief discussion of the standard, highlighting some aspects that are important for the parser, such as the restrictions on the use of operators as imposed by the standard in order to make the parsing deterministic. Some possible problem areas are also indicated. As output is closely related to input in Prolog, both are treated in this paper. Some parsing techniques are compared and an operator precedence parser is chosen to be modified to deal with the dynamic operator declarations. The necessary modifications are discussed and an implementation in C is presented. Performance data are collected and compared with a public domain Prolog parser written in Prolog. It is the first efficient public domain parser for Standard Prolog that actually works and deals with all the details of the syntax.     

A predictive bottom-up parser

Despite all advances in parsing, parser size, conflict resolution and error recovery are still of important consideration. In this research, we propose a predictive bottom-up parser. The parser is implemented in two versions. Both versions constitute an algorithm that simulates the run of a shift–reduce automaton, defined and constructed in a way that integrates its parsing actions with reduction prediction, conflict resolution and error recovery. However, the first implementation version performs explicit shift–reduce parsing actions based on implicit prediction of the reduction sequences. The second one performs parsing actions based on explicit prediction of the reduction sequences with implied shift–reduce actions. The proposed parser has been experimented against the ones based on similar approaches. 10–20% reduction of the parser size has been achieved, with a parsing behaviour proportional to a factor reflecting the grammar ambiguity.     

The Grammar Deployment Kit — System Demonstration —

Grammar deployment is the process of turning a given grammar specification into a working parser. The Grammar Deployment Kit (for short, GDK) provides tool support in this process based on grammar engineering methods. We are mainly interested in the deployment of grammars for software renovation tools, that is, tools for software re- and reverse engineering. The current version of GDK is optimized for Cobol. We assume that grammar deployment starts from an initial grammar specification which is maybe still ambiguous or even incomplete. In practice, grammar deployment binds unaffordable human resources because of the unavailability of suitable grammar specifications, the diversity of parsing technology as well as the limitations of the technology, integration problems regarding the development of software renovation functionality, and the lack of tools and adherence to firm methods for grammar engineering. GDK helps to largely automate grammar deployment because tool support for grammar adaptation and parser generation is provided. We support different parsing technologies, among them btyacc, that is, yacc with backtracking. GDK is free software.     

Semantic and structural analysis of TV diving programs

Automatic content analysis of sports videos is a valuable and challenging task. Motivated by analogies between a class of sports videos and languages, the authors propose a novel approach for sports video analysis based on compiler principles. It integrates both semantic analysis and syntactic analysis to automatically create an index and a table of contents for a sports video. Each shot of the video sequence is first annotated and indexed with semantic labels through detection of events using domain knowledge. A grammar-based parser is then constructed to identify the tree structure of the video content based on the labels. Meanwhile, the grammar can be used to detect and recover errors during the analysis. As a case study, a sports video parsing system is presented in the particular domain of diving. Experimental results indicate the proposed approach is effective.     

FEATURE-BASED KOREAN GRAMMAR UTILIZING LEARNED CONSTRAINT RULES

In this paper, we propose a feature-based Korean grammar utilizing the learned constraint rules in order to improve parsing efficiency. The proposed grammar consists of feature structures, feature operations, and constraint rules; and it has the following characteristics. First, a feature structure includes several features to express useful linguistic information for Korean parsing. Second, a feature operation generating a new feature structure is restricted to the binary-branching form which can deal with Korean properties such as variable word order and constituent ellipsis. Third, constraint rules improve efficiency by preventing feature operations from generating spurious feature structures. Moreover, these rules are learned from a Korean treebank by a decision tree learning algorithm. The experimental results show that the feature-based Korean grammar can reduce the number of candidates by a third of candidates at most and it runs 1.5 ∼ 2 times faster than a CFG on a statistical parser.     

A syntactical approach to diagnosing multiple bugs in anintelligent tutoring system

This paper develops a buggy model-based intelligent tutoring system (ITS) capable of diagnosing multiple bugs, pinpointing not only their types but also their exact locations involved. The procedural grammar of context free type is used not only to decompose a complicated procedure involving possible steps of both correct and incorrect arithmetic into simplest, `primitive' procedures but also to express control knowledge essential to implementing an efficient parser. An efficient parser is implemented by narrowing down the search space, exploiting the control knowledge, the selection and consistency conditions in selecting rules in parsing. Parsing of superficial symptoms such as a student's errors in arithmetic essentially reveals the deep structure of the buggy knowledge of the student so that teachers may now devise and offer a more effective means of instructions for acquiring the correct skill of arithmetic     

Even faster generalized LR parsing

We prove a property of generalized LR (GLR) parsing – if the grammar is without right and hidden left recursions, then the number of consecutive reductions between the shifts of two adjacent symbols cannot be greater than a constant. Further, we show that this property can be used for constructing an optimized version of our GLR parser. Compared with a standard GLR parser, our optimized parser reads one symbol on every transition and performs significantly fewer stack operations. Our timings show that, especially for highly ambiguous grammars, our parser is significantly faster than a standard GLR parser. Received: 9 May 2000 / 5 March 2001     

A new parsing method for non-LR(1) grammars

One of the difficult problems that faces a compiler writer is to devise a grammar that is suitable for both efficient parsing and semantic attribution. This paper describes a system that resolves conflicts in LR(1) parsing by taking advantage of information in the parse tree. The system, which functions as part of a compiler generator, rewrites the user's grammar to remove parsing conflicts. It then places code into the generated compiler that rewrites the parse tree during parsing so as to produce the tree of the original grammar. The compiler writer can then write the semantic attribution to fit his or her original grammar without any knowledge of the changes made. The method is expected to be efficient in most cases, even in parsing systems that do not explicitly build the entire parse tree. The method complements previous work in its capabilities and advantages. The system has been implemented and integrated into a compiler generator system.     

A scheme for LR(k) parsing with error recovery part II: error recovery

The paper is the second in a series of three papers devoted to a detailed study of LR(k) parsing with error recovery and correction. Error recovery in LR(k) parsing of a context-free grammar is formalized by extending an LR(k) parser of the grammar such that it accepts all strings over the terminal vocabulary. The parse produced by this extension for a terminal string is a right parse if the string is in the language. In the case of a string not in the language the parse produced by the extension contains so-called error productions which represent the error recovery actions performed by the extension. The treatment is based on the formalization of LR(k) parsing presented in the first paper in the series and it covers practically all error recovery methods designed for LR(k) parsing.