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.     

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.     

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.     

A platform for the automatic generation of attribute evaluation hardware systems

Attribute grammars (AG) allow the addition of context-sensitive properties into context free grammars, augmenting their expressional capabilities by using syntactic and semantic notations, making them in this way a really useful tool for a considerable number of applications. AGs have extensively been utilized in applications such as artificial intelligence, structural pattern recognition, compiler construction and even text editing. Obviously, the performance of an attribute evaluation system resides in the efficiency of the syntactic and semantic subsystems. In this paper, a hardware architecture for an attribute evaluation system is presented, which is based on an efficient combinatorial implementation of Earley's parallel parsing algorithm for the syntax part of the attribute grammar. The semantic part is managed by a special purpose module that traverses the parse tree and evaluates the attributes based on a proposed stack-based approach. The entire system is described in Verilog HDL (hardware design language), in a template form that given the specification of an arbitrary attribute grammar, the HDL synthesizable source code of the system is produced on the fly by a proposed automated tool. The generated code has been simulated for validation, synthesized and tested on an Xilinx FPGA (field programmable gate arrays) board for various AGs. Our method increases the performance up to three orders of magnitude compared to previous approaches, depending on the implementation, the size of the grammar and the input string length. This makes it particularly appealing for applications where attribute evaluation is a crucial aspect, like in real-time and embedded systems. Specifically, a natural language interface is presented, based on a question-answering application from the area of airline flights.     

Taming the PL/I syntax

Ideally the syntactic part of a PL/I compiler would be generated directly from the semi-formal definition of ANSI Standard PL/I. A practical approach to this is described, using finite state machines and an LALR parser generator. The parser uses a method due to Aoe which avoids list searching. Adapted for this method the PL/I grammar has 841 states. The parse table generator exploits the freedom to renumber states in a way that improves on previous algorithms for compacting the tables. The parser tables occupy less than 4K bytes.     

SQL测试用例集的自动生成

编写SQL语句是测试数据库管理系统的一个重要部分。自动生成SQL语句可以有效减少测试人员的工作量,而目前没有直接生成SQL语句的自动化工具。通过模拟产生式的直接推导过程,根据SQL文法,给出生成符合该文法的SQL语句,用作测试用例的方法;研究从表示文法的BNF文件生成SQL测试用例集合的自动化过程。这个过程包括几个阶段:将SQL文法的每一个非终结符转换成一个对应的解析函数,所有解析函数的集合构成规则库;遍历文法的产生式自动生成SQL测试用例;使用权值数组结合随机数,加大生成测试用例的灵活性;使用非终结符的最大调用次数来终止SQL测试用例的生成。通过介绍的工具原型,可以得到符合SQL语法的SQL测试用例。     

Compiler Hacking for Source Code Analysis

Many activities related to software quality assessment and improvement, such as empirical model construction, data flow analysis, testing or reengineering, rely on static source code analysis as the first and fundamental step for gathering the necessary input information. In the past, two different strategies have been adopted to develop tool suites. There are tools encompassing or implementing the source parse step, where the parser is internal to the toolkit, and is developed and maintained with it. A different approach builds tools on the top of external already-available components such as compilers that output the program abstract syntax tree, or that make it available via an API.This paper discusses techniques, issues and challenges linked to compiler patching or wrapping for analysis purposes. In particular, different approaches for accessing the compiler parsing information are compared, and the techniques used to decouple the parsing front end from the analysis modules are discussed.Moreover, the paper presents an approach and a tool, XOgastan, developed exploiting the gcc/g++ ability to save a representation of the intermediate abstract syntax tree. XOgastan translates the gcc/g++ dumped abstract syntax tree format into a Graph eXchange Language representation, which makes it possible to take advantage of currently available XML tools for any subsequent analysis step. The tool is illustrated and its design discussed, showing its architecture and the main implementation choices made.     

Modelling of space-efficient one-pass translation using attribute grammars

Automatic production of one-pass compilers from attribute grammars is considered. An examination of a one-pass grammar for the programming language Euclid shows that the present definition of one-pass grammars is too general: the space behaviour of the produced compilers differs from that found in conventional hand-written compilers. A new class of attribute grammars is defined. The class models naturally the use of space in a hand-written compiler. This implies that the compiler produced automatically on the basis of the grammar uses space in the same way as a practical hand-written recursive descent compiler. Furthermore, a graphical notation is introduced as a design tool for obtaining grammars in the proposed class.     

Syntax-Directed Pretty Printing—A First Step Towards a Syntax-Directed Editor

A language-independent syntax-directed pretty printer has been implemented as the first step towards building a language-independent syntax-directed editor. The syntax-directed pretty printer works in two phases: the grammar processing phase and the program processing phase. In the grammar processing stage, a grammar which contains a context-free grammar and information for the parser and pretty printer is processed and all files needed by the second phase are written. With these files, the syntax-directed pretty printer works for the language of the grammar. The syntax-directed editor would use the same grammar processing phase to construct the files needed to make it work for a specific language. In the program processing phase, programs in the language of the grammar are parsed and parse trees are built. If syntax errors are found, error messages are produced and error recovery is done. The parse trees are pretty printed according to the pretty printer specifications given in the grammar, resulting in well-indented, syntactically clear programs.     

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.     

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.     

Interface Grammars for Modular Software Model Checking

Verification techniques relying on state enumeration (e.g., model checking) face two important challenges: the state-space explosion, an exponential increase in the state space as the number of components increases; and environment generation, modeling components that are either not available for analysis, or that cannot be handled by the verification tool in use. We propose a semi-automated approach for attacking these problems. In our approach, interfaces for the components not under analysis are specified using a specification language based on grammars. Specifically, an interface grammar for a component specifies the sequences of method invocations that are allowed by that component. We have built an compiler that takes the interface grammar for a component as input and generates a stub for that component. The stub thus generated can be used to replace that component during state space exploration, either to moderate state space explosion, or to provide an executable environment for the component under verification. We conducted a case study by writing an interface grammar for the Enterprise JavaBeans (EJB) persistence interface, and using the resulting stub to check EJB clients using the JPF model checker. Our results show that EJB clients can be verified efficiently with JPF using our approach.     

Agile Parsing in TXL

Syntactic analysis forms a foundation of many source analysis and reverse engineering tools. However, a single standard grammar is not always appropriate for all source analysis and manipulation tasks. Small custom modifications to the grammar can make the programs used to implement these tasks simpler, clearer and more efficient. This leads to a new paradigm for programming these tools: agile parsing. In agile parsing the effective grammar used by a particular tool is a combination of two parts: the standard base grammar for the input language, and a set of explicit grammar overrides that modify the parse to support the task at hand. This paper introduces the basic techniques of agile parsing in TXL and discusses several industry proven techniques for exploiting agile parsing in software source analysis and transformation.     

Dual syntax for XML languages

XML is successful as a machine processable data interchange format, but it is often too verbose for human use. For this reason, many XML languages permit an alternative more legible non-XML syntax. XSLT stylesheets are often used to convert from the XML syntax to the alternative syntax; however, such transformations are not reversible since no general tool exists to automatically parse the alternative syntax back into XML.

We present XSugar, which makes it possible to manage dual syntax for XML languages. An XSugar specification is built around a context-free grammar that unifies the two syntaxes of a language. Given such a specification, the XSugar tool can translate from alternative syntax to XML and vice versa. Moreover, the tool statically checks that the transformations are reversible and that all XML documents generated from the alternative syntax are valid according to a given XML schema.     

A methodology and notation for compiler front end design

A methodology and associated notation for designing compiler front ends, and in particular the interface between the parser and the semantic routines, is described. The methodology leads to a clean, easy to understand, documentable design. The notation is similar to an attribute grammar, but its purpose is to document the first pass of a specific compiler, rather than to describe the semantics of a language. It is designed to be accessible to non-specialists, easy to learn, and natural. It can be used with or without software support. The notation was used during the development of a large compiler, and to assist in the transfer of the compiler to the group that will maintain it. Experience with the notation indicates that it meets its goals.     

面向对象文法分析

针对编译中的文法分析部分进行了深入探讨，循序渐进地将文法分析面向对象方法实现。从理论根据及示例可以看出：用面向对象方法进行文法分析，可以彻底解决传统文法分析中的左递归、岐义性及回溯问题，且实现起来很方便、灵活，并具有良好的可操作性与可扩展性。     

The cost of a generated parser

The ‘fact’ that compilers employing generated parsers suffer significant performance degradation dis-a-vis recursive descent compilers is entrenched in the folklore of computing. We give detailed measurements that support this belief when the entire compiler is written in Pascal. We then define a general interface for a parsing module that hides significantly more information than usual, simplifying the process of generation and integration. This interface makes an assembly-coded parse table interpreter feasible without changing the language used for the remainder of the compiler. When the parse table interpreter is written in assembly language, the costs of the generated parser are essentially the same as those for recursive descent. (A minor space/time trade-off is possible, with the recursive descent implementation being slightly bigger and slightly faster.)