Nez is a PEG(Parsing Expressing Grammar)-based open grammar language that allows us to describe complex syntax constructs without action code. Since open grammars are declarative and free from a host programming language of parsers, software engineering tools and other parser applications can reuse once-defined grammars across programming languages. A key challenge to achieve practical open grammars is the expressiveness of syntax constructs and the resulting parser performance, as the traditional action code approach has provided very pragmatic solutions to these two issues. In Nez, we extend the symbol-based state management to recognize context-sensitive language syntax, which often appears in major programming languages. In addition, the Abstract Syntax Tree constructor allows us to make flexible tree structures, including the left-associative pair of trees. Due to these extensions, we have demonstrated that Nez can parse not all but many grammars. Nez can generate various types of parsers since all Nez operations are independent of a specific parser language. To highlight this feature, we have implemented Nez with dynamic parsing, which allows users to integrate a Nez parser as a parser library that loads a grammar at runtime. To achieve its practical performance, Nez operators are assembled into low-level virtual machine instructions, including automated state modifications when backtracking, transactional controls of AST construction, and efficient memoization in packrat parsing. We demonstrate that Nez dynamic parsers achieve very competitive performance compared to existing efficient parser generators.
In parallel, the problems of action code have been pointed out, for example, the lack of grammar reuse @cite_6 , decreased maintainability @cite_4 , and ad hoc behavior @cite_17 . There have been several attempts to decrease the disadvantage of action code. Terence Parr, the author of ANTLR, has proposed a prototype grammar, inspired by the revision control system @cite_6 . Elkhound @cite_13 , for instance, allows the users to write action code written in multiple programming languages. Despite these attempts, grammar reuse is still limited and arbitrary action inevitably requires porting to other languages.
@cite_13 @cite_4 @cite_6 @cite_17
1555637434 2097034742 2135907175 2112488502
Elkhound is an implementation of the Generalized LR (GLR) parsing algorithm [Tomita86, Rekers92] that allows the user to associate arbitrary C++ code with reduction actions, while retaining full control of sharing and disambiguation. Elkhound specifications are similar to those of YACC for LALR(1) grammar fragments, exposing the details of the GLR reduction process only where the grammar requires it. Further, the algorithm itself can switch on a token-by-token basis between GLR and simple LR, achieving very good performance for unambiguous portions of the input. The resulting system is familiar to even casual users of tools like YACC or Bison, but powerful enough to elegantly handle the dark corners of real-world languages. Does the use of DSL tools improve the maintainability of language implementations compared to implementations from scratch? We present empirical results on aspects of maintainability of six implementations of the same DSL using different languages (Java, JavaScript, C#) and DSL tools (ANTLR, OMeta, Microsoft "M"). Our evaluation indicates that the maintainability of language implementations is indeed higher when constructed using DSL tools. Reusing syntax specifications without embedded arbitrary semantic actions is straightforward because the semantic analysis phases of new applications can feed off trees or other intermediate structures constructed by the pre-existing parser. The presence of arbitrary embedded semantic actions, however, makes reuse difficult with existing mechanisms such as grammar inheritance and modules. This short paper proposes a mechanism based upon prototype grammars that automatically pushes changes from prototypes to derived grammars even in the presence of semantic actions. The prototype mechanism alone would be unsuitable for creating a new grammar from multiple preexisting grammars. When combined with grammar composition, however, the prototype mechanism would improve grammar reuse because imported pre-existing grammars could be altered to suit each new application. Several popular languages, such as Haskell, Python, and F#, use the indentation and layout of code as part of their syntax. Because context-free grammars cannot express the rules of indentation, parsers for these languages currently use ad hoc techniques to handle layout. These techniques tend to be low-level and operational in nature and forgo the advantages of more declarative specifications like context-free grammars. For example, they are often coded by hand instead of being generated by a parser generator. This paper presents a simple extension to context-free grammars that can express these layout rules, and derives GLR and LR(k) algorithms for parsing these grammars. These grammars are easy to write and can be parsed efficiently. Examples for several languages are presented, as are benchmarks showing the practical efficiency of these algorithms.