More About Converting BNF to PEG

Issue title: Concurrency, Specification and Programming

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) encodes a recursive-descent parser with limited backtracking. The parser has many useful properties. Converting PEG to an executable parser is a rather straightforward task. Unfortunately, PEG is not well understood as a language definition tool. It is thus of a practical interest to construct PEGs for languages specified in some familiar way, such as Backus-Naur Form (BNF). The problem was attacked by Medeiros in an elegant way by noticing that both PEG and BNF can be formally defined in a very similar way. Some of his results were extended in a previous paper by this author. We continue here with further extensions.

DOI: 10.3233/FI-2014-1075

Journal: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 257-270, 2014