PEGs are a formal grammar foundation for describing syntax, and are not hard to generate parsers with a plain recursive decent parsing. However, the large amount of C-stack consumption in the recursive parsing is not acceptable especially in resource-restricted embedded systems. Alternatively, we have attempted the machine virtualization approach to PEG-based parsing. MiniNez, our implemented virtual machine, is presented in this paper with several downsizing techniques, including instruction specialization, inline expansion and static flow analysis. As a result, the MiniNez machine achieves both a very small footprint and competitive performance to generated C parsers. We have demonstrated the experimental results by comparing on two major embedded platforms: Cortex-A7 and Intel Atom processor.
PEGs @cite_12 are a relatively newer formalism than Context Free Grammars, and have received much popularity among many parser researchers. There are many PEG-based parser tools such as Pappy @cite_14 , Rats ! @cite_1 , Mouse @cite_6 , Leg Peg @cite_9 , PEGjs @cite_13 , LPeg @cite_16 , Waxeye @cite_11 and so on. Most of these tools are based on a parser generator as with in Lex Yacc. An important exception is LPeg, a pattern matching library for Lua @cite_16 @cite_17 . As with MiniNez, LPeg has adopted a virtual parsing machine @cite_7 instead of parser generations. MiniNez and LPeg significantly differ in terms of backtracking handling: local static jump vs. global dynamic jump. Since the failure jump address is not pushed on the stack, MiniNez achieves a fewer stack consumption. In addition, we add several specialized downsizing to the MiniNez design and implementation. LPeg, on the other hand, does not work standalone and requires a complementary Lua runtime, resulting in hard comparison on the same condition.
@cite_14 @cite_7 @cite_9 @cite_1 @cite_17 @cite_6 @cite_16 @cite_13 @cite_12 @cite_11
2046801051 2009706943 2044735303 2072750798
Current text pattern-matching tools are based on regular expressions. However, pure regular expressions have proven too weak a formalism for the task: many interesting patterns either are difficult to describe or cannot be described by regular expressions. Moreover, the inherent non-determinism of regular expressions does not fit the need to capture specific parts of a match. Motivated by these reasons, most scripting languages nowadays use pattern-matching tools that extend the original regular-expression formalism with a set of ad hoc features, such as greedy repetitions, lazy repetitions, possessive repetitions, ‘longest-match rule,’ lookahead, etc. These ad hoc extensions bring their own set of problems, such as lack of a formal foundation and complex implementations. In this paper, we propose the use of Parsing Expression Grammars (PEGs) as a basis for pattern matching. Following this proposal, we present LPEG, a pattern-matching tool based on PEGs for the Lua scripting language. LPEG unifies the ease of use of pattern-matching tools with the full expressive power of PEGs. Because of this expressive power, it can avoid the myriad of ad hoc constructions present in several current pattern-matching tools. We also present a Parsing Machine that allows a small and efficient implementation of PEGs for pattern matching. Copyright © 2008 John Wiley & Sons, Ltd. Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PEG libraries in several programming languages.A frequently missed feature of PEGs is left recursion, which is commonly used in Context-Free Grammars (CFGs) to encode left-associative operations. We present a simple conservative extension to the semantics of PEGs that gives useful meaning to direct and indirect left-recursive rules, and show that our extensions make it easy to express left-recursive idioms from CFGs in PEGs, with similar results. We prove the conservativeness of these extensions, and also prove that they work with any left-recursive PEG.PEGs can also be compiled to programs in a low-level parsing machine. We present an extension to the semantics of the operations of this parsing machine that let it interpret left-recursive PEGs, and prove that this extension is correct with regard to our semantics for left-recursive PEGs. We present a semantics for left-recursive Parsing Expression Grammars.A small extension adds precedence associativity declarations to operator grammars.We give a semantics for compilation of left-recursive PEGs to a parsing machine.Our semantics are conservative: non-left-recursive PEGs are unaffected. Parsing Expression Grammar (PEG) is a recognition-based foundation for describing syntax that renewed interest in top-down parsing approaches. Generally, the implementation of PEGs is based on a recursive-descent parser, or uses a memoization algorithm. We present a new approach for implementing PEGs, based on a virtual parsing machine, which is more suitable for pattern matching. Each PEG has a corresponding program that is executed by the parsing machine, and new programs are dynamically created and composed. The virtual machine is embedded in a scripting language and used by a patternmatching tool. We give an operational semantics of PEGs used for pattern matching, then describe our parsing machine and its semantics. We show how to transform PEGs to parsing machine programs, and give a correctness proof of our transformation. 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.