Syntax-Directed Implementation of Visual Languages Based on Automaton Graphical Grammars

A growing interest in visual languages results in the development of methods and means of their implementation. In this paper, a formalism for analyzing visual language diagrams in the form of an automaton graphical grammar and structure of a syntax-directed graphical editor are suggested.     

Sre—a syntax recognizing editor

This paper presents a syntax-directed editor dubbed SRE, for syntax recognizing editor. Unlike other syntax-directed editors, SRE enables the user to edit programs with nearly the same natural and unrestrictive ease as a conventional text editor. In addition, it helps identify syntax errors and many typing errors before leaving the editor and attempting to compile a program. Programs are also formatted during entry, thereby providing immediate visual feedback of the recognized structure. The editor replaces the scanner/parser pass of a conventional compiler and thus reduces compilation time substantially.     

基于JavaCC的抽象语法树生成错误处理技术研究

随着C++语言标准的不断演进,词法语法解析工具如JavaCC等对于很多扩充的新特性以及复杂的语法结构不能做到完全支持,这可能会导致抽象语法树生成错误且不完整;针对这一问题,提出一个针对抽象语法树生成错误的处理框架;首先,通过对JavaCC的扩充,实现一套可以解析C++语言的词法语法分析器,生成抽象语法树并记录报错行;其次,根据报错行寻找所在函数区间即不支持或不匹配的语法片段;最后,通过注释函数区间的方式来跳过不支持或不匹配的语法片段进行错误处理并迭代生成抽象语法树;实验结果表明,对抽象语法树生成进行错误处理后可以更全面的分析代码,抽象语法树完成率上升37.8%,分析行数提高3.9倍。     

RUGRAT: Evaluating program analysis and testing tools and compilers with large generated random benchmark applications

Benchmarks are heavily used in different areas of computer science to evaluate algorithms and tools. In program analysis and testing, open‐source and commercial programs are routinely used as benchmarks to evaluate different aspects of algorithms and tools. Unfortunately, many of these programs are written by programmers who introduce different biases, not to mention that it is very difficult to find programs that can serve as benchmarks with high reproducibility of results. We propose a novel approach for generating random benchmarks for evaluating program analysis and testing tools and compilers. Our approach uses stochastic parse trees, where language grammar production rules are assigned probabilities that specify the frequencies with which instantiations of these rules will appear in the generated programs. We implemented our tool for Java and applied it to generate a set of large benchmark programs of up to 5M lines of code each with which we evaluated different program analysis and testing tools and compilers. The generated benchmarks let us independently rediscover several issues in the evaluated tools. Copyright © 2014 John Wiley & Sons, Ltd.     

VinEd — Asystem for programmanipulation through user-definable simultaneous views

Programmers’ mental representations of programs do not obey the order and immediate content of program texts. Multiple visible representations, or views, of programs help programmers to construct mental representations needed in, e.g., maintenance tasks. We have implemented VinEd, a language-independent editor framework that supports an unlimited number of user-definable and editable views. Views are defined by transformation programs that construct views from the original representation. VinEd extends the notion of views to any activity that can be based on the original program, e.g., program compilation. Thus VinEd can be extended to include a complete set of programming tools.     

A Visual Syntax-directed Editor for the Descartes Specification Language

The front end of the software life cycle is an important phase in the development of quality software systems. Due to the interactive nature of the requirements specification phase, automated tools assist in capturing user concepts and conveying these concepts to the developers. This paper presents a syntax-directed editor developed for the Descartes software specification language. The editor helps in constructing the specifications by detecting and preventing syntactic and static semantic errors. The editor uses the visual notation of Nassi–Shneiderman charts for the external representation of Descartes specifications. The specifications are edited in their visual form directly within the editor. Use of a syntax-directed editor for the construction of Descartes specifications is expected to reduce specification errors, enhance constructibility, and in turn increase productivity. © 1997 John Wiley & Sons, Ltd.     

Object-oriented Tree Traversal with JJForester

We want to use the advanced language processing technology available in the asf+sdf Meta-Environment in combination with general purpose programming languages. In particular, we want to combine the syntax definition formalism sdf and the associated components that support generalized LR parsing, with the object-oriented language Java. To this end, we implemented JJForester, a tool that generates class structures from sdf grammar definitions. The generated class structures implement a number of design patterns to facilitate construction and traversal of parse trees represented by object structures. In a detailed case study, we demonstrate how program analyses and transformations can be constructed with JJForester.     

Syntax-directed compression of program files

Parsing can be applied to compress source programs. A suitably encoded parse tree, together with the symbol table, constitutes a very compact representation of the program. The paper reports a Prolog implementation of the method, including automatic, syntax-directed, encoder and decoder generators. The test results show compression gains of 50–60 per cent.     

Towards Effective Parsing with Neural Networks: Inherent Generalisations and Bounded Resource Effects

This article explores how the effectiveness of learning to parse with neural networks can be improved by including two architectural features relevant to language: generalisations across syntactic constituents and bounded resource effects. A number of neural network parsers have recently been proposed, each with a different approach to the representational problem of outputting parse trees. In addition, some of the parsers have explicitly attempted to capture an important regularity within language, which is to generalise information across syntactic constituents. A further property of language is that natural bounds exist for the number of constituents which a parser need retain for later processing. Both the generalisations and the resource bounds may be captured in architectural features which enhance the effectiveness and efficiency of learning to parse with neural networks. We describe a number of different types of neural network parser, and compare them with respect to these two features. These features are both explicitly present in the Simple Synchrony Network parser, and we explore and illustrate their impact on the process of learning to parse in some experiments with a recursive grammar.     

Incremental parsing without a parser

This article describes an algorithm for incremental parsing of expressions in the context of syntax-directed editors for programming languages. Since a syntax-directed editor represents programs as trees and statements and expressions as nodes in trees, making minor modifications in an expression can be difficult. Consider, for example, changing a “ + ” operator to a “1” operator or adding a short subexpression at a syntactically but not structurally correct position, such as inserting “) 1 (d“ at the # mark in” (a + b # + c)”. To make these changes in a typical syntax-directed editor, the user must understand the tree structure and type a number of tree-oriented construction and manipulation commands. This article describes an algorithm that allows the user to think in terms of the syntax of the expression as it is displayed on the screen (in infix notation) rather than in terms of its internal representation (which is effectively prefix), while maintaining the benefits of syntax-directed editing. This algorithm is significantly different from other incremental parsing algorithms in that it does not involve modifications to a traditional parsing algorithm or the overhead of maintaining a parser stack or any data structure other than the syntax tree. Instead, the algorithm applies tree transformations, in real-time as each token is inserted or deleted, to maintain a correct syntax tree.     

The parser generating system PGS

PGS is a parser generating system accepting LALR(1) and related grammars in extended BNF notation and producing parsers based on table-driven stack automata. To enable syntax-directed translation, semantic actions can be attached to rules of the input grammar. An attribution mechanism allows the transfer of information between rules. The generated parsers have an automatic error recovery which can be tailored to satisfy specific needs of the language to be accepted. PGS generates parsers written in Pascal, Modula-2, C or Ada. Compared with existing systems, e.g. YACC¹, a parser generated by PGS is twice as fast and the parse tables require 25 per cent less storage. This paper gives a survey of algorithms involved in the generator and the generated parsers, and compares them with algorithms used in other systems. In detail, it compares several parse-table representations and their implications for space and time efficiency of the generated parsers.     

Language modeling with probabilistic left corner parsing

We present a novel language model, suitable for large-vocabulary continuous speech recognition, based on parsing with a probabilistic left corner grammar (PLCG). The PLCG probabilities are conditioned on local and non-local features of the partial parse tree, and some of these features are lexical. They are not derived from another stochastic grammar, but directly induced from a treebank, a corpus of text sentences, annotated with parse trees. A context-enriched constituent represents all partial parse trees that are equivalent with respect to the probability of the next parse move. For computational efficiency the parsing problem is represented as a traversal through a compact stochastic network of constituents connected by PLCG moves. The efficiency of the algorithm is due to the fact that the network consists of recursively nested, shared subnetworks. The PLCG-based language model results from accumulating the probabilities of all (partial) paths through this network. Next word probabilities can be computed synchronously with the probabilistic left corner parsing algorithm in one single pass from left to right. They are guaranteed to be normalized, even when pruning less likely paths. Finally, it is shown experimentally that the PLCG-based language model is a competitive alternative to other syntax-based language models, both in efficiency and accuracy.     

PECAN: Program Development Systems that Support Multiple Views

This paper describes the PECAN family of program development systems. PECAN supports multiple views of the user's program. The views can be representations of the program or of the corresponding semantics. The primary program view is a syntax-directed editor. The current semantic views include expression trees, data type diagrams, flow graphs, and the symbol table. PECAN is designed to make effective use of powerful personal machines with high-resolution graphics displays and is currently implemented on APOLLO workstations.     

Scaling of program fitness spaces

We investigate the distribution of fitness of programs concentrating on those represented as parse trees and, particularly, how such distributions scale with respect to changes in the size of the programs. By using a combination of enumeration and Monte Carlo sampling on a large number of problems from three very different areas, we suggest that, in general, once some minimum size threshold has been exceeded, the distribution of performance is approximately independent of program length. We proof this for both linear programs and simple side effect free parse trees. We give the density of solutions to the parity problems in program trees which are composed of XOR building blocks. Limited experiments with programs including side effects and iteration suggest a similar result may also hold for this wider class of programs.     

一种实时手写数学方程编辑器

该文所述的数学方程编辑器,用户可用笔和书写板输入手写的数学公式,系统通过实时字符、符号识别和图形语法分析软件产生与输入相对应的语法分析树,并由此转换成诸如Latex、数学的或LISP-like符号等输出形式,与基于特殊方程描述语言的编辑系统相比,该手写方程编辑器相对简单且使用方便。