Some Aspects of Parsing Expression Grammar

Issue title: Concurrency Specification and Programming (CS&P)

Article type: Research Article

Authors: Redziejowski, Roman R.

Affiliations: Giraf's Research. [email protected]

Note: [] Address for correspondence: Ceremonimästarvägen 10, SE-181 40 Lidingö, Sweden

Abstract: Parsing Expression Grammar (PEG) is a new way to specify syntax, by means of a topdown processwith limited backtracking. It can be directly transcribed into a recursive-descent parser. The parser does not require a separate lexer, and backtracking removes the usual LL(1) constraint. This is convenient for many applications, but there are two problems: PEG is not well understood as a language specification tool, and backtracking may result in exponential processing time. The paper consists of two parts that address these problems. The first part is an attempt to find out the language actually defined by a given parsing expression. The second part reports measurements of backtracking activity in a PEG-derived parser for the programming language C.

Journal: Fundamenta Informaticae, vol. 85, no. 1-4, pp. 441-451, 2008