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.
Extensions. With Rats @math , Robert Grimm has shown an elegant integration of PEGs with action code despite its speculative parsing @cite_9 . Many other PEG-based parser generators @cite_8 @cite_10 @cite_5 have adopted the semantic action approach for expressing syntax constructs that PEGs can not recognize. Yet, there have been several declarative attempts for PEG extensions. Adams has recently formalized Indent-Sensitive CFGs @cite_17 for the indentation-based code layout and has extended the PEG-version of IS-CFGs @cite_30 . have extended PEGs with the @math operator to combine a black-boxed parser for a natural language @cite_14 . Compared to these existing extensions, Nez more broadly covers various parsing aspects.
@cite_30 @cite_14 @cite_8 @cite_9 @cite_5 @cite_10 @cite_17
2115538819 2170086072 2098396599 1542200249 2112488502
Several popular languages including Haskell and Python use the indentation and layout of code as an essential part of their syntax. In the past, implementations of these languages used ad hoc techniques to implement layout. Recent work has shown that a simple extension to context-free grammars can replace these ad hoc techniques and provide both formal foundations and efficient parsing algorithms for indentation sensitivity. However, that previous work is limited to bottom-up, LR( @math ) parsing, and many combinator-based parsing frameworks including Parsec use top-down algorithms that are outside its scope. This paper remedies this by showing how to add indentation sensitivity to parsing frameworks like Parsec. It explores both the formal semantics of and efficient algorithms for indentation sensitivity. It derives a Parsec-based library for indentation-sensitive parsing and presents benchmarks on a real-world language that show its efficiency and practicality. This paper describes a novel framework for creating a parser to process and analyze texts written in a partially structured'' natural language. In many projects, the contents of document artifacts tend to be described as a mixture of formal parts (i.e. the text constructs follow specific conventions) and parts written in arbitrary free text. Formal parsers, typically defined and used to process a description with rigidly defined syntax such as program source code are very precise and efficient in processing the formal part, while parsers developed for natural language processing (NLP) are good at robustly interpreting the free-text part. Therefore, combining these parsers with different characteristics can allow for more flexible and practical processing of various project documents. Unfortunately, conventional approaches to constructing a parser from multiple small parsers were studied extensively only for formal language parsers and are not directly applicable to NLP parsers due to the differences in the way the input text is extracted and evaluated. We propose a method to configure and generate a combined parser by extending an approach based on parser combinator, the operators for composing multiple formal parsers, to support both NLP and formal parsers. The resulting text parser is based on Parsing Expression Grammars, and it benefits from the strength of both parser types. We demonstrate an application of such combined parser in practical situations and show that the proposed approach can efficiently construct a parser for analyzing project-specific industrial specification documents. We explore how to make the benefits of modularity available for syntactic specifications and present Rats!, a parser generator for Java that supports easily extensible syntax. Our parser generator builds on recent research on parsing expression grammars (PEGs), which, by being closed under composition, prioritizing choices, supporting unlimited lookahead, and integrating lexing and parsing, offer an attractive alternative to context-free grammars. PEGs are implemented by so-called packrat parsers, which are recursive descent parsers that memoize all intermediate results (hence their name). Memoization ensures linear-time performance in the presence of unlimited lookahead, but also results in an essentially lazy, functional parsing technique. In this paper, we explore how to leverage PEGs and packrat parsers as the foundation for extensible syntax. In particular, we show how make packrat parsing more widely applicable by implementing this lazy, functional technique in a strict, imperative language, while also generating better performing parsers through aggressive optimizations. Next, we develop a module system for organizing, modifying, and composing large-scale syntactic specifications. Finally, we describe a new technique for managing (global) parsing state in functional parsers. Our experimental evaluation demonstrates that the resulting parser generator succeeds at providing extensible syntax. In particular, Rats! enables other grammar writers to realize real-world language extensions in little time and code, and it generates parsers that consistently out-perform parsers created by two GLR parser generators. Two recent developments in the field of formal languages are Parsing Expression Grammar (PEG) and packrat parsing. The PEG formalism is similar to BNF, but defines syntax in terms of recognizing strings, rather than constructing them. It is, in fact, precise specification of a backtracking recursive-descent parser. Packrat parsing is a general method to handle backtracking in recursive-descent parsers. It ensures linear working time, at a huge memory cost. This paper reports an experiment that consisted of defining the syntax of Java 1.5 in PEG formalism, and literally transcribing the PEG definitions into parsing procedures (accidentally, also in Java). The resulting primitive parser shows an acceptable behavior, indicating that packrat parsing might be an overkill for practical languages. The exercise with defining the Java syntax suggests thatmore work is needed on PEG as a language specification tool. 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.