Search

Abstract This paper introduces sets of binary subtree representations as an alternative to shared packed parse forests as the output of a generalised parser, and shows how these may be generated by Earley's algorithm, by a new GLL-style parser and by Johnson's continuation passing combinator style parsers. The set based output removes the clerical overhead associated with graph constructions, making the parsers simpler. Highlights • Introduces BSR sets, an alternative to the SPPF representation of all derivations of a string. • General BSR combinator parsers and Earley-style parsers are presented. • A new BSR GLL-style parser (CNP) is presented which has a more efficient combined call stack. • Data structure size comparisons for GLL and CNP are given for C, C++ and Java grammars. [ABSTRACT FROM AUTHOR]

Let Σ be an alphabet having at least three symbols. Let C F L denote the family of all context-free languages over Σ , P E G denote the family of all parsing expression grammars over Σ , and P E L denote the family of all parsing expression languages over Σ. Let K satisfy K ⊆ C F L and " K ∩ P E L ≠ ∅ ", where we use the double-quoted " K ∩ P E L ≠ ∅ " in the sense that we can effectively find some G ∈ P E G such that L (G) ∈ K ∩ P E L. Then the following problem is shown to be undecidable: Given G ∈ P E G , decide if L (G) ∈ K. In particular, the following basic problem is shown to be undecidable: Given G ∈ P E G , decide if L (G) ∈ C F L. [ABSTRACT FROM AUTHOR]

Parser combinators offer a universal and flexible approach to parsing. They follow the structure of an underlying grammar, are modular, well-structured, easy to maintain, and can recognize a large variety of languages including context-sensitive ones. However, these advantages introduce a noticeable performance overhead mainly because the same powerful parsing algorithm is used to recognize even simple languages. Time-wise, parser combinators cannot compete with parsers generated by well-performing parser generators or optimized hand-written code. Techniques exist to achieve a linear asymptotic performance of parser combinators, yet there is a significant constant multiplier. The multiplier can be lowered to some degree, but this requires advanced meta-programming techniques, such as staging or macros, that depend heavily on the underlying language technology. In this work we present a language-agnostic solution. We optimize the performance of parsing combinators with specializations of parsing strategies. For each combinator, we analyze the language parsed by the combinator and choose the most efficient parsing strategy. By adapting a parsing strategy for different parser combinators we achieve performance comparable to that of hand-written or optimized parsers while preserving the advantages of parsers combinators. [ABSTRACT FROM AUTHOR]

The parsing is applied to the given c-language which is a context free grammar (CFG) language, i.e., any CFG language together with its productions could be parsed as an LL(1) grammar language giving its parsing table and the parsing results to any input string. [ABSTRACT FROM AUTHOR]

A syntax-correcting CIF parser, COD::CIF::Parser, is presented that can parse CIF 1.1 files and accurately report the position and the nature of the discovered syntactic problems. In addition, the parser is able to automatically fix the most common and the most obvious syntactic deficiencies of the input files. Bindings for Perl, C and Python programming environments are available. Based on COD::CIF::Parser, the cod-tools package for manipulating the CIFs in the Crystallography Open Database (COD) has been developed. The cod-tools package has been successfully used for continuous updates of the data in the automated COD data deposition pipeline, and to check the validity of COD data against the IUCr data validation guidelines. The performance, capabilities and applications of different parsers are compared. [ABSTRACT FROM AUTHOR]

We propose an enhancement to current parsing and transformation systems by leveraging the expressive power of Boolean grammars, a generalization of context-free grammars that adds conjunction and negation operators. In addition to naturally expressing a larger class of languages, Boolean grammars capture multiple parse trees of the same document simultaneously and the ability to switch between these parse “views”. In particular, source transformation and reengineering tasks can benefit from parse views by recasting the input text into whichever parse is most suitable for the task at hand. [ABSTRACT FROM AUTHOR]

Modern software systems are continuously evolving, often because systems requirements change over time. Responding to requirements changes is one of the principles of agile methodologies. In this paper we envision the seamless integration of automated verification techniques within agile methodologies, thanks to the support for incrementality. Incremental verification accommodates the changes that occur within the schedule of frequent releases of software agile processes. We propose a general approach to developing families of verifiers that can support incremental verification for different kinds of artifacts and properties. The proposed syntactic-semantic approach is rooted in operator precedence grammars and their support for incremental parsing. Incremental verification procedures are encoded as attribute grammars, whose incremental evaluation goes hand in hand with incremental parsing. [ABSTRACT FROM AUTHOR]

In order to analyze software systems, it is necessary to model them. Static software models are commonly imported by parsing source code and related data. Unfortunately, building custom parsers for most programming languages is a non-trivial endeavor. This poses a major bottleneck for analyzing software systems programmed in languages for which importers do not already exist. Luckily, initial software models do not require detailed parsers, so it is possible to start analysis with a coarse-grained importer, which is then gradually refined. In this paper we propose an approach to “agile modeling” that exploits island grammars to extract initial coarse-grained models, parser combinators to enable gradual refinement of model importers, and various heuristics to recognize language structure, keywords and other language artifacts. [ABSTRACT FROM AUTHOR]

In this paper we present an application implemented entirely in Python programming language for automatic generation of speech from text gathered by parsing Internet electronic mail, a valuable assistive tool for visually impaired persons in exchanging messages. [ABSTRACT FROM AUTHOR]

Copyright of Procesamiento del Lenguaje Natural is the property of Sociedad Espanola para el Procesamiento del Lenguaje Natural and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Journal of King Abdulaziz University: Engineering Sciences is the property of King Abdulaziz University, Scientific Publishing Centre and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

There are parser generators that accept ambiguous context-free grammars, where ambiguities are resolved via disambiguation rules, with the outcome of smaller parse tables and more effcient parsers. However, the compiler writers are expected to develop compact ambiguous grammars and extract ambiguity-resolving information from the syntax and semantics of the language. The aforementioned tasks require considerable expertise, not often owned by casual compiler writers, or even expert programmers who are assigned a serious compiler-writing task, while programming language designers are usually capable of providing a concise and compact ambiguous description of the language that may include ambiguity-resolving information. In this paper, we aim to provide a powerful notation for syntax definition, which enables the language designer to assert some shifts and reduce sets associated with each production rule of the possibly ambiguous grammar. These sets of language tokens guide the parser generator to resolve the parse table conicts that are caused by the ambiguities in the grammar or by other sources. The practicality of the proposed asserted shift reduce notation is supported by several examples from the constructs of contemporary programming languages and is tested to work properly via developing a parser generator that constructs conict-free LALR (1) parse tables. [ABSTRACT FROM AUTHOR]

The article discusses the problems on entry parsing in a thesaurus-dictionary and provides solutions using Segmentation-Cohesion-Dependency (SCD). It says that entry parsing problems include recursive structures of lexicography, cyclicity, and the creation of hypergraph-driven dependencies on atomic and non-atomic sense definitions. It says that SCD uses procedural non-recursive calls to address recursive problems, while the Enumeration Closing Condition is used for dealing cyclicity.

In an earlier paper, the author adapted to Parsing Expression Grammars (PEGs) the properties FIRST and FOLLOW used in the construction of predictive top-down parsers. The purpose was to obtain warnings for possible 'language hiding'. It turned out that FIRST does not work well with lookahead expressions. To repair this, it is replaced here by a property named BITES that is a set of input strings instead of terminals. [ABSTRACT FROM AUTHOR]

We study a range of syntactic processing tasks using a general statistical framework that consists of a global linear model, trained by the generalized perceptron together with a generic beam-search decoder. We apply the framework to word segmentation, joint segmentation and POS-tagging, dependency parsing, and phrase-structure parsing. Both components of the framework are conceptually and computationally very simple. The beam-search decoder only requires the syntactic processing task to be broken into a sequence of decisions, such that, at each stage in the process, the decoder is able to consider the top-n candidates and generate all possibilities for the next stage. Once the decoder has been defined, it is applied to the training data, using trivial updates according to the generalized perceptron to induce a model. This simple framework performs surprisingly well, giving accuracy results competitive with the state-of-the-art on all the tasks we consider. The computational simplicity of the decoder and training algorithm leads to significantly higher test speeds and lower training times than their main alternatives, including log-linear and large-margin training algorithms and dynamic-programming for decoding. Moreover, the framework offers the freedom to define arbitrary features which can make alternative training and decoding algorithms prohibitively slow. We discuss how the general framework is applied to each of the problems studied in this article, making comparisons with alternative learning and decoding algorithms. We also show how the comparability of candidates considered by the beam is an important factor in the performance. We argue that the conceptual and computational simplicity of the framework, together with its language-independent nature, make it a competitive choice for a range of syntactic processing tasks and one that should be considered for comparison by developers of alternative approaches. [ABSTRACT FROM AUTHOR]

We describe the application of the graph-theoretic property known as treewidth to the problem of finding efficient parsing algorithms. This method, similar to the junction tree algorithm used in graphical models for machine learning, allows automatic discovery of efficient algorithms such as the O(n4) algorithm for bilexical grammars of Eisner and Satta. We examine the complexity of applying this method to parsing algorithms for general Linear Context-Free Rewriting Systems. We show that any polynomial-time algorithm for this problem would imply an improved approximation algorithm for the well-studied treewidth problem on general graphs. [ABSTRACT FROM AUTHOR]

In this paper, we address the tasks of detecting, segmenting, parsing, and matching deformable objects. We use a novel probabilistic object model that we call a hierarchical deformable template (HDT). The HDT represents the object by state variables defined over a hierarchy (with typically five levels). The hierarchy is built recursively by composing elementary structures to form more complex structures. A probability distribution--a parameterized exponential model--is defined over the hierarchy to quantify the variability in shape and appearance of the object at multiple scales. To perform inference--to estimate the most probable states of the hierarchy for an input image--we use a bottom-up algorithm called compositional inference. This algorithm is an approximate version of dynamic programming where approximations are made (e.g., pruning) to ensure that the algorithm is fast while maintaining high performance. We adapt the structure-perceptron algorithm to estimate the parameters of the HDT in a discriminative manner (simultaneously estimating the appearance and shape parameters). More precisely, we specify an exponential distribution for the HDT using a dictionary of potentials, which capture the appearance and shape cues. This dictionary can be large and so does not require handcrafting the potentials. Instead, structure-perceptron assigns weights to the potentials so that less important potentials receive small weights (this is like a "soft" form of feature selection). Finally, we provide experimental evaluation of HDTs on different visual tasks, including detection, segmentation, matching (alignment), and parsing. We show that HDTs achieve state-of-the-art performance for these different tasks when evaluated on data sets with groundtruth (and when compared to alternative algorithms, which are typically specialized to each task). [ABSTRACT FROM AUTHOR]

Abstract: 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. [Copyright &y& Elsevier]

Traditional Earley parsers operate in two phases: first recognizing the input, then constructing the forest of parse trees. Practically speaking, this quirk makes it awkward to use in a compiler-compiler, because semantic actions attached to rules are only executed after the fact. We address this problem by identifying safe Earley sets, points during the recognition phase at which partial parse trees can be constructed; this means that semantic actions may be executed on the fly. A secondary benefit is that Earley sets can be deleted during recognition, resulting in a substantial savings of both space and time. [ABSTRACT FROM AUTHOR]

Abstract  Efficiency and flexibility are often mutually exclusive features in a code. This still prompts a large part of the Scientific Computing community to use traditional procedural languages. In the last years, however, new programming techniques have been introduced allowing for a high level of abstraction without loss of performance. In this paper we present an application of the Expression Templates technique introduced in (Veldhuizen in Expression templates. C++ Report magazine, vol 7, pp 26–31, 1995) to the assembly step of a finite element computation. We show that a suitable implementation, such that the compiler has the role of parsing abstract operations, allows for user-friendliness. Moreover, it gains in performance with respect to more traditional techniques for achieving this kind of abstraction. Both the cases of conforming and discontinuous Galerkin finite element discretization are considered. The proposed implementation is finally applied to a number of problems entailing different kind of complications. [ABSTRACT FROM AUTHOR]

We continue our investigation of the generative power of cooperating distributed grammar systems (CDGSs), using the previously introduced ≤k-, =k-, and ≥k-competence-based cooperation strategies and context-free components that rewrite the sentential form in a parallel manner. This leads to new characterizations of the languages generated by (random context) ET0L systems and recurrent programmed grammars. [ABSTRACT FROM AUTHOR]

This paper presents a combination of Reference Attributed Grammars (RAGs) and Circular Attribute Grammars (CAGs). While RAGs allow the direct and easy specification of nonlocally dependent information, CAGs allow iterative fixed-point computations to be expressed directly using recursive (circular) equations. We demonstrate how the combined formalism, Circular Reference Attributed Grammars (CRAGs), can take advantage of both these strengths, making it possible to express solutions to many problems in an easy way. We exemplify with the specification and computation of the nullable, first, and follow sets used in parser construction, a problem which is highly recursive and normally programmed by hand using an iterative algorithm. We also present a general demand-driven evaluation algorithm for CRAGs and some optimizations of it. The approach has been implemented and experimental results include computations on a series of grammars including that of Java 1.2. We also revisit some of the classical examples of CAGs and show how their solutions are facilitated by CRAGs. [Copyright &y& Elsevier]

We present the metafront tool for specifying flexible, safe, and efficient syntactic transformations between languages defined by context-free grammars. The transformations are guaranteed to terminate and to map grammatically legal input to grammatically legal output. We rely on a novel parser algorithm that is designed to support gradual extensions of a grammar by allowing productions to remain in a natural style and by statically reporting ambiguities and errors in terms of individual productions as they are being added. Our tool may be used as a parser generator in which the resulting parser automatically supports a flexible, safe, and efficient macro processor, or as an extensible lightweight compiler generator for domain-specific languages. We show substantial examples of both kinds. [Copyright &y& Elsevier]

In this paper, we proposed an efficient and accurate text chunking system using linear SVM kernel and a new technique called masked method. Previous researches indicated that systems combination or external parsers can enhance the chunking performance. However, the cost of constructing multi-classifiers is even higher than developing a single processor. Moreover, the use of external resources will complicate the original tagging process. To remedy these problems, we employ richer features and propose a masked-based method to solve unknown word problem to enhance system performance. In this way, no external resources or complex heuristics are required for the chunking system. The experiments show that when training with the CoNLL-2000 chunking dataset, our system achieves 94. 12 in F (β) rate with linear. Furthermore, our chunker is quite efficient since it adopts a linear kernel SVM. The turn-around tagging time on CoNLL-2000 testing data is less than 50s which is about 115 times than polynomial kernel SVM. [Copyright &y& Elsevier]

A deterministic parallel LL parsing algorithm is presented. The algorithm is based on a transformation from a parsing problem to parallel reduction. First, a nondeterministic version of a parallel LL parser is introduced. Then, it is transformed into the deterministic version—the LLP parser. The deterministic LLP( q, k) parser uses two kinds of information to select the next operation — a lookahead string of length up to k symbols and a lookback string of length up to q symbols. Deterministic parsing is available for LLP grammars, a subclass of LL grammars. Since the presented deterministic and nondeterministic parallel parsers are both based on parallel reduction, they are suitable for most parallel architectures. [ABSTRACT FROM AUTHOR]

The right nulled generalized LR parsing algorithm is a new generalization of LR parsing which provides an elegant correction to, and extension of, Tomita's GLR methods whereby we extend the notion of a reduction in a shift-reduce parser to include right nulled items. The result is a parsing technique which runs in linear time on LR(1) grammars and whose performance degrades gracefully to a polynomial bound in the presence of nonLR(1) rules. Compared to other GLR-based techniques, our algorithm is simpler and faster. [ABSTRACT FROM AUTHOR]

A high-throughput lossless data compression IP core built around a CAM-based dictionary whose number of available entries and data word width adjust to the characteristics of the incoming data stream is presented. These two features enhance model adaptation to the input data, improving compression efficiency, and enable greater throughputs as a multiplicity of bytes can be processed per cycle. A parsing mechanism adjusts the width of dictionary words to natural words while the length of the dictionary grows from an initial empty state to a maximum value defined as a run-time configuration parameter. The compressor/decompressor architecture was prototyped on an FPGA-based PCI board. An ASIC hard-macro was subsequently implemented and achieved a throughput of more than 1 gigabyte per second when clocking at 277 MHz on a high-performance, 0.13 µm, eight-layer copper CMOS process. [ABSTRACT FROM AUTHOR]

Focuses on a study which analyzed the reduction of non-determinism in right nulled GLR (RNGLR) parsers. Information on GLR computer algorithms; Concepts underlying GLR parsers; Development of a shared packed parse forest through RNGLR.

Discusses the incorporation of XML for data binding, processing, and persistence. Focus on object-oriented programming languages such as Java, and Python; Use of a standard parser to automatically build object trees entirely from application-specific classes; Practical use of XML; XML parsing; Data-binding technologies for XML documents. INSETS: Data-Binding Technologies for XML Documents.;SCHOLARZHEIMERS..

This article presents XML-based tools for parser generation and data binding generation. The underlying concept is that of transformation between formal languages, which is a form of meta-programming. We discuss the benefits of such a declarative approach with well-defined semantics: productivity, maintainability, verifiability, performance and safety. [ABSTRACT FROM AUTHOR]

Incremental integrated programming environments are a promising approach toward the goal of improved programmer productivity. Consistently rapid environment response is an obvious goal. Efficient use of storage has also been determined to be an important issue. This paper presents the algorithms and techniques used for incremental scanning and parsing of the Galaxy language. The algorithms guarantee minimal rescanning and reparsing and are also space and time efficient. Notably, the methods are easily adapted to any language of equivalent class, i.e., RL(1)∩LR(1), including such languages as C and Pascal. [ABSTRACT FROM AUTHOR]

A model for the operation of bottom-up parallel parsing using asynchronous processors is proposed. The model is based on an extension of shift-reduce parsers which are able to merge the information they keep on their stacks. The main objective of the paper is to provide estimates of the speedup attainable when using the proposed model. Three programs were written to measure the speedup. The first is a classical simulator which keeps track of the times spent performing the shift, reduce, and merge operations for each processor. The second is a program which generates "typical" strings in a language and simultaneously keeps track of the number of operations needed to parse the generated strings. The third is a program capable of deducing the number of parsing operations by counting the number of selected terminals appearing in an input string. The results, applicable to the parallel parsing of programs written in a Pascal-like language, show how the speedup varies with the number of processors for different ratios of the times to shift, reduce, and merge. Although the speedup falls considerably below that predicted by theory, substantial gains are still attainable by using a fairly large number of parallel processors. With the decreasing costs of processors, parallel parsing and parallel compilation will become increasingly important and should allow considerable gains in speedup. [ABSTRACT FROM AUTHOR]

LR is an LR(1) parser generation system. It is written entirely in portable ANS1 standard Fortran 66 and has been successfully operated on a number of computers. LR uses a powerful algorithm of Pager's to generate a space efficient parser for any LR(1) grammar. Generated parsers have been used in a variety of compilers, utility programs, and applications packages. [ABSTRACT FROM AUTHOR]

A new parsing algorithm of context-free languages using bottom-up computation of lookahead information is presented. Earley's algorithm uses a great number of items during enumeration to recognize a context-free language. If items with lookahead fields are used, the number of items can be reduced, but item spacing is considerably increased. The method presented here may reduce the number of items during enumeration without using lookahead fields of items. The computation of lookahead information takes place in a bottom-up manner It is not necessary to compute lookahead information until it is required during enumeration. [ABSTRACT FROM AUTHOR]