Incorporating language processing into Java applications: a JavaCC tutorial

The Java Compiler Compiler is a tool for developing applications using Java. JavaCC is freely available and generates Java source code. Language processors that the tool generates thus derive the benefit of the language's platform independence. We walk through the process of using JavaCC to create language-enabled applications. This requires introducing us to Extended Backus Naur Form, a prerequisite to using JavaCC. EBNF is commonly used to specify the grammar of formal languages, including programming languages. JavaCC has many significant advantages, one of which is that is neatly blends EBNF and Java, making it easy for someone with knowledge of both to quickly exploit JavaCC's power.     

Multipass precedence analysis

Summary This paper defines a hierarchy of languages which is properly contained in the context sensitive languages and which starts with the context free family. The hierarchy is defined inductively by controlling labeled linear grammars with languages in one family to yield languages in the next larger family. The families of the hierarchy have properties analogous to those of the context free family, in particular, the new mechanism introduced is very suitable for parsing.A language in the n-th family is specified by a sequence of n — 1 labeled linear grammars and a context free grammar. By assuming that the reversals of the first n — 1 grammars and the last labeled linear grammar are precedence grammars, the concepts and parsing algorithm of Wirth and Weber extend to yield a parsing algorithm within the hierarchy. This considerably enhances the usefulness of the construction and allows much of the power of the context sensitive languages to become accessible in measured amounts for potential programming applications.     

Grammatical and context‐sensitive error correction using a statistical machine translation framework

Producing electronic rather than paper documents has considerable benefits such as easier organizing and data management. Therefore, existence of automatic writing assistance tools such as spell and grammar checker/correctors can increase the quality of electronic texts by removing noise and correcting the erroneous sentences. Different kinds of errors in a text can be categorized into spelling, grammatical and real‐word errors. In this article, we present a language‐independent approach based on a statistical machine translation framework to develop a proofreading tool, which detects grammatical errors as well as context‐sensitive spelling mistakes (real‐word errors). A hybrid model for grammar checking is suggested by combining the mentioned approach with an existing rule‐based grammar checker. Experimental results on both English and Persian languages indicate that the proposed statistical method and the rule‐based grammar checker are complementary in detecting and correcting syntactic errors. The results of the hybrid grammar checker, applied to some English texts, show an improvement of about 24% with respect to the recall metric with almost similar value for precision. Experiments on real‐world data set show that state‐of‐the‐art results are achieved for grammar checking and context‐sensitive spell checking for Persian language. Copyright © 2012 John Wiley & Sons, Ltd.     

Grammar‐based test generation with YouGen

Grammars are traditionally used to recognize or parse sentences in a language, but they can also be used to generate sentences. In grammar‐based test generation (GBTG), context‐free grammars are used to generate sentences that are interpreted as test cases. A generator reads a grammar G and generates L(G), the language accepted by the grammar. Often L(G) is so large that it is not practical to execute all of the generated cases. Therefore, GBTG tools support ‘tags’: extra‐grammatical annotations which restrict the generation. Since its introduction in the early 1970s, GBTG has become well established: proven on industrial projects and widely published in academic venues. Despite the demonstrated effectiveness, the tool support is uneven; some tools target specific domains, e.g. compiler testing, while others are proprietary. The tools can be difficult to use and the precise meaning of the tags are sometimes unclear. As a result, while many testing practitioners and researchers are aware of GBTG, few have detailed knowledge or experience. We present YouGen, a new GBTG tool supporting many of the tags provided by previous tools. In addition, YouGen incorporates covering‐array tags, which support a generalized form of pairwise testing. These tags add considerable power to GBTG tools and have been available only in limited form in previous GBTG tools. We provide semantics for the YouGen tags using parse trees and a new construct, generation trees. We illustrate YouGen with both simple examples and a number of industrial case studies. Copyright © 2010 John Wiley & Sons, Ltd.     

Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking

A wide range of parser generators are used to generate parsers for programming languages. The grammar formalisms that come with parser generators provide different approaches for defining operator precedence. Some generators (e.g. YACC) support precedence declarations, others require the grammar to be unambiguous, thus encoding the precedence rules. Even if the grammar formalism provides precedence rules, a particular grammar might not use it. The result is grammar variants implementing the same language. For the C language, the GNU Compiler uses YACC with precedence rules, the C-Transformers uses SDF without priorities, while the SDF library does use priorities. For PHP, Zend uses YACC with precedence rules, whereas PHP-front uses SDF with priority and associativity declarations.The variance between grammars raises the question if the precedence rules of one grammar are compatible with those of another. This is usually not obvious, since some languages have complex precedence rules. Also, for some parser generators the semantics of precedence rules is defined operationally, which makes it hard to reason about their effect on the defined language. We present a method and tool for comparing the precedence rules of different grammars and parser generators. Although it is undecidable whether two grammars define the same language, this tool provides support for comparing and recovering precedence rules, which is especially useful for reliable migration of a grammar from one grammar formalism to another. We evaluate our method by the application to non-trivial mainstream programming languages, such as PHP and C.     

One application of real-valued interpretation of formal power series

We define two natural properties of context-free grammars. The first property generalizes linearity and the second property strengthens nonlinearity. A language generated by an unambiguous grammar of the first type is called the language with weak linear structure and a language generated by an unambiguous grammar of the second type is called the language with strong nonlinear structure. Our main theorem states that the family of unambiguous grammars generating languages with weak linear structure and the family of unambiguous grammars generating languages with strong nonlinear structure are effectively separable.     

Parameter reduction and automata evaluation for grammar-compressed trees

Trees can be conveniently compressed with linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars which are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. A tree grammar is monadic if each nonterminal uses at most one context parameter. Based on this result, polynomial time algorithms are presented for testing whether a given (i) nondeterministic tree automaton or (ii) nondeterministic tree automaton with sibling-constraints or (iii) nondeterministic tree walking automaton, accepts a tree represented by a linear straight-line context-free tree grammar. It is also shown that if tree grammars are nondeterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size.     

Remarks on some aspects of language structure and their relevance to pattern analysis

Some specific aspects of language structure are examined in detail in the context of pattern analysis. In particular, a transformational grammar is constructed for a class of patterns, following the linguistic formulation very closely, by taking a simple example and working it out in detail. Many of the characteristics of the transformational grammars of linguists show up even in this simple example. The need for looking for grammars of different styles and the problem of making meaningful assignment of probabilities to sentences in the context of transformational grammars have also been briefly discussed.     

A Bi‐Directional Procedural Model for Architectural Design

It is a challenge for shape grammars to incorporate spatial hierarchy and interior connectivity of buildings in early design stages. To resolve this difficulty, we developed a bi‐directional procedural model: the forward process constructs the derivation tree with production rules, while the backward process realizes the tree with shapes in a stepwise manner (from leaves to the root). Each inverse‐derivation step involves essential geometric‐topological reasoning. With this bi‐directional framework, design constraints and objectives are encoded in the grammar‐shape translation. We conducted two applications. The first employs geometric primitives as terminals and the other uses previous designs as terminals. Both approaches lead to consistent interior connectivity and a rich spatial hierarchy. The results imply that bespoke geometric‐topological processing helps shape grammar to create plausible, novel compositions. Our model is more productive than hand‐coded shape grammars, while it is less computation‐intensive than evolutionary treatment of shape grammars.     

Defining,analysing and implementing communication protocols using attribute grammars

A new approach to describing communication protocols is introduced. In the style of a formal language, the protocol is considered as the set of all legal sequences of symbols that can be exchanged by the communicating processes. Although context free grammars cannot adequately describe such sequences, it is shown that attribute grammars may be used. Examples are given which show that common protocol features such as interleaving, windowing and flow control can be described by attribute grammars.It is shown how deadlock-proneness of a protocol can be formalised as a property of its attribute grammar specification, and the undecidability of deadlock-proneness for arbitrary grammars is proved. An algorithm is given for determining whether a protocol is deadlock-prone in the decidable case.A method of automatically implementing protocols from their specifications is described. The implementation takes the form of a pair of communicating attributed pushdown automata. These are based on LR(0) parsers, with attribute evaluation being performed in parallel with the parse; attribute values are used to help direct the parse. Consideration is also given to the handling of errors.     

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.     

A grammatical approach to self-organizing robotic systems

In this paper, we define a class of graph grammars that can be used to model and direct concurrent robotic self-assembly and similar self-organizing processes. We give several detailed examples of the formalism and then focus on the problem of synthesizing a grammar so that it generates a given, prespecified assembly. In particular, to generate an acyclic graph we synthesize a binary grammar (rules involve at most two parts), and for a general graph we synthesize a ternary grammar (rules involve at most three parts). In both cases, we characterize the number of concurrent steps required to achieve the assembly. We also show a general result that implies that no binary grammar can generate a unique stable assembly. We conclude the paper with a discussion of how graph grammars can be used to direct the self-assembly of robotic parts.     

Creating Specific Grammars with Generic Grammars: Towards Flexible Urban Design

The aim of the City Induction project is to develop an urban design tool consisting of 3 parts: an urban programme formulation module, a generation module and an evaluation module. The generation module relies on a very generic Urban Grammar composed of several generic grammars called Urban Induction Patterns (UIPs) corresponding to typical urban design moves. Specific grammars, such as the analytical grammars inferred from our case studies, can be obtained by defining specific arrangements of Urban Induction Patterns and specific constraints on the rule parameters. We show that variations on the UIP arrangements or rule parameters can provide design variations and specific grammars to be synthesised through design exploration. It is therefore seen as a process for synthesizing a specific design grammar within the field of urban design and has two main features: (1) it allows for the synthesis of specific grammars during the design process and (2) it allows for the customization of a personal design language within the broad scope of the generic grammar.     

Semi‐automatic grammar recovery

We propose an approach to the construction of grammars for existing languages. The main characteristic of the approach is that the grammars are not constructed from scratch but they are rather recovered by extracting them from language references, compilers and other artifacts. We provide a structured process to recover grammars including the adaptation of raw extracted grammars and the derivation of parsers. The process is applicable to possibly all existing languages for which business critical applications exist. We illustrate the approach with a non‐trivial case study. Using our process and some basic tools, we constructed in a few weeks a complete and correct VS COBOL II grammar specification for IBM mainframes. In addition, we constructed a parser for VS COBOL II, and were the first to publish a (Web‐enabled) grammar specification so that others can use this result to construct their own grammar‐based tools for VS COBOL II or derivatives. Copyright © 2001 John Wiley & Sons, Ltd.     

Parallel generation of architecture on the GPU

In this paper, we present a novel approach for the parallel evaluation of procedural shape grammars on the graphics processing unit (GPU). Unlike previous approaches that are either limited in the kind of shapes they allow, the amount of parallelism they can take advantage of, or both, our method supports state of the art procedural modeling including stochasticity and context‐sensitivity. To increase parallelism, we explicitly express independence in the grammar, reduce inter‐rule dependencies required for context‐sensitive evaluation, and introduce intra‐rule parallelism. Our rule scheduling scheme avoids unnecessary back and forth between CPU and GPU and reduces round trips to slow global memory by dynamically grouping rules in on‐chip shared memory. Our GPU shape grammar implementation is multiple orders of magnitude faster than the standard in CPU‐based rule evaluation, while offering equal expressive power. In comparison to the state of the art in GPU shape grammar derivation, our approach is nearly 50 times faster, while adding support for geometric context‐sensitivity.     

A survey of grammatical inference in software engineering

Grammatical inference – used successfully in a variety of fields such as pattern recognition, computational biology and natural language processing – is the process of automatically inferring a grammar by examining the sentences of an unknown language. Software engineering can also benefit from grammatical inference. Unlike these other fields, which use grammars as a convenient tool to model naturally occurring patterns, software engineering treats grammars as first-class objects typically created and maintained for a specific purpose by human designers. We introduce the theory of grammatical inference and review the state of the art as it relates to software engineering.     

Nonterminal complexity of one-sided random context grammars

In the present paper, we study the nonterminal complexity of one-sided random context grammars. More specifically, we prove that every recursively enumerable language can be generated by a one-sided random context grammar with no more than ten nonterminals. An analogical result holds for thirteen nonterminals in terms of these grammars with the set of left random context rules coinciding with the set of right random context rules. Furthermore, we introduce the notion of a right random context nonterminal, defined as a nonterminal that appears on the left-hand side of a right random context rule. We demonstrate how to convert any one-sided random context grammar G to an equivalent one-sided random context grammar H with two right random context nonterminals. An analogical conversion is given in terms of (1) propagating one-sided random context grammars and (2) left random context nonterminals. In the conclusion, two open problems are stated.     

The metafront System: Extensible Parsing and Transformation

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.     

“Modeling with tools is easier, believe me”—The effects of tool functionality on modeling grammar usage beliefs

Increasingly, studies are reported that examine how conceptual modeling is conducted in practice. Yet, typically the studies to date have examined in isolation how modeling grammars can be, or are, used to develop models of information systems or organizational processes, without considering that such modeling is typically done by means of a modeling tool that extends the modeling functionality offered by a grammar through complementary features. This paper extends the literature by examining how the use of seven different features of modeling tools affects usage beliefs users develop when using modeling grammars for process modeling. We show that five distinct tool features positively affect usefulness, ease of use and satisfaction beliefs of users. We offer a number of interpretations about the findings. We also describe how the results inform decisions of relevance to developers of modeling tools as well as managers in charge for making modeling-related investment decisions.     

Continued use of process modeling grammars: the impact of individual difference factors

Process modeling grammars are used by analysts to describe information systems domains in terms of the business operations an organization is conducting. While prior research has examined the factors that lead to continued usage behavior, little knowledge has been established as to what extent characteristics of the users of process modeling grammars inform usage behavior. In this study, a theoretical model is advanced that incorporates determinants of continued usage behavior as well as key antecedent individual difference factors of the grammar users, such as modeling experience, modeling background and perceived grammar familiarity. Findings from a global survey of 529 grammar users support the hypothesized relationships of the model. The study offers three central contributions. First, it provides a validated theoretical model of post-adoptive modeling grammar usage intentions. Second, it discusses the effects of individual difference factors of grammar users in the context of modeling grammar usage. Third, it provides implications for research and practice.