Parsing Expression Grammars are a popular foundation for describing syntax. Unfortunately, several syntax of programming languages are still hard to recognize with pure PEGs. Notorious cases appears: typedef-defined names in C C++, indentation-based code layout in Python, and HERE document in many scripting languages. To recognize such PEG-hard syntax, we have addressed a declarative extension to PEGs. The "declarative" extension means no programmed semantic actions, which are traditionally used to realize the extended parsing behavior. Nez is our extended PEG language, including symbol tables and conditional parsing. This paper demonstrates that the use of Nez Extensions can realize many practical programming languages, such as C, C #, Ruby, and Python, which involve PEG-hard syntax.
@cite_14: In this paper, we report our experience with parsing the syntax of the Fortress programming language. Fortress is a new programming language designed for scientific and high-performance computing. Features include: implicit parallelism, transactions, and concrete syntax that emulates mathematical notation. Fortress is intended to grow over time to accommodate the changing needs of its users. Parsing the Fortress syntax is nontrivial due to its support for mathematical syntax and growable syntax. Mathematical syntax is highly ambiguous and growable syntax allows a program itself to define how it is parsed. Fortress currently runs entirely on the JVM, which requires internal representation of Fortress as Java classes. We describe our trials to parse the entire Fortress syntax, in the presence of constant changes of the language syntax and its internal representation. and the lessons we learned from the experience.
@cite_13: For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ambiguity is crucial to their original purpose of modelling natural languages, but this very power makes it unnecessarily difficult both to express and to parse machine-oriented languages using CFGs. Parsing Expression Grammars (PEGs) provide an alternative, recognition-based formal foundation for describing machine-oriented syntax, which solves the ambiguity problem by not introducing ambiguity in the first place. Where CFGs express nondeterministic choice between alternatives, PEGs instead use prioritized choice. PEGs address frequently felt expressiveness limitations of CFGs and REs, simplifying syntax definitions and making it unnecessary to separate their lexical and hierarchical components. A linear-time parser can be built for any PEG, avoiding both the complexity and fickleness of LR parsers and the inefficiency of generalized CFG parsing. While PEGs provide a rich set of operators for constructing grammars, they are reducible to two minimal recognition schemas developed around 1970, TS TDPL and gTS GTDPL, which are here proven equivalent in effective recognition power.
Due to the popularity of PEGs, many grammar developers have attempted the grammar specification for their interesting languages. While PEGs, in some sense, are more powerful than CFGs, several limitations on their expressiveness have been pointed out in @cite_13 @cite_14 .