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
1891842933 2091232155 2072750798 2135907175
ANTLR v3 is the most powerful, easy-to-use parser generator built to date, and represents the culmination of more than 15 years of research by Terence Parr. This book is the essential reference guide to using this completely rebuilt version of ANTLR, with its amazing new LL(*) parsing technology, tree construction facilities, StringTemplate code generation template engine, and sophisticated ANTLRWorks GUI development environment. Learn to use ANTLR directly from the author! ANTLR is a parser generator-a program that generates code to translate a specified input language into a nice, tidy data structure. You might think that parser generators are only used to build compilers. But in fact, programmers usually use parser generators to build translators and interpreters for domain-specific languages such as proprietary data formats, common network protocols, text processing languages, and domain-specific programming languages. Domain-specific languages are important to software development because they represent a more natural, high fidelity, robust, and maintainable means of encoding a problem than simply writing software in a general-purpose language. For example, NASA uses domain-specific command languages for space missions to improve reliability, reduce risk, reduce cost, and increase the speed of development. Even the first Apollo guidance control computer from the 1960s used a domain-specific language that supported vector computations. This book is the definitive guide to using the completely rebuilt ANTLR v3 and describes all features in detail, including the amazing new LL(*) parsing technology, tree construction facilities, StringTemplate code generation template engine, and sophisticated ANTLRWorks GUI development environment. You'll learn all about ANTLR grammar syntax, resolving grammar ambiguities, parser fault tolerance and error reporting, embedding actions to interpret or translate languages, building intermediate-form trees, extracting information from trees, generating source code, and how to use the ANTLR Java API. Despite the advances made by modern parsing strategies such as PEG, LL(*), GLR, and GLL, parsing is not a solved problem. Existing approaches suffer from a number of weaknesses, including difficulties supporting side-effecting embedded actions, slow and or unpredictable performance, and counter-intuitive matching strategies. This paper introduces the ALL(*) parsing strategy that combines the simplicity, efficiency, and predictability of conventional top-down LL(k) parsers with the power of a GLR-like mechanism to make parsing decisions. The critical innovation is to move grammar analysis to parse-time, which lets ALL(*) handle any non-left-recursive context-free grammar. ALL(*) is O(n4) in theory but consistently performs linearly on grammars used in practice, outperforming general strategies such as GLL and GLR by orders of magnitude. ANTLR 4 generates ALL(*) parsers and supports direct left-recursion through grammar rewriting. Widespread ANTLR 4 use (5000 downloads month in 2013) provides evidence that ALL(*) is effective for a wide variety of applications. Despite the power of Parser Expression Grammars (PEGs) and GLR, parsing is not a solved problem. Adding nondeterminism (parser speculation) to traditional LL and LR parsers can lead to unexpected parse-time behavior and introduces practical issues with error handling, single-step debugging, and side-effecting embedded grammar actions. This paper introduces the LL(*) parsing strategy and an associated grammar analysis algorithm that constructs LL(*) parsing decisions from ANTLR grammars. At parse-time, decisions gracefully throttle up from conventional fixed k>=1 lookahead to arbitrary lookahead and, finally, fail over to backtracking depending on the complexity of the parsing decision and the input symbols. LL(*) parsing strength reaches into the context-sensitive languages, in some cases beyond what GLR and PEGs can express. By statically removing as much speculation as possible, LL(*) provides the expressivity of PEGs while retaining LL's good error handling and unrestricted grammar actions. Widespread use of ANTLR (over 70,000 downloads year) shows that it is effective for a wide variety of applications. 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.