日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

NezCC: A Cross-Language PEG Parser
Generator
Kimio Kuramitsu 倉光 君郎
Since Yacc was invented in 1970s, many parser generators have been designed to generate a language-specificparser written in a parser host language such as C and Java. This is a little mysterious design choice since
its grammar specification is based on a formal grammar such as LR(k), LL(k), and PEGs. We rethinka language agnostic parser generation from the beginning. First, a PEG-based grammar specification isdesigned in a way that any action code is unnecessary to generate a parser. Second, the parsing algorithm
is simplified so that we can write it with language constructs that commonly appear in most programming
languages. Finally, syntactic code template is also designed to switch a target source code. The resulting
NezCC parser generator can produce a variety of target languages such as C, Java, JavaScript, Python,Lua, Scala, Racket, and F#. The NezCC parser is full-fledged, which includes flexible tree construction,
extended context-sensitive parsing, and eﬃcient packrat parsing. More interestingly, our performance study
shows that NezCC is as fast as existing language-specific parser generators such as Yacc and ANTLR.

on a target programming language, we rarely reuse

1 Introduction

grammar specifications that are found on an open

Many might have asked themselves why a parser

source repository.

generator such as Lex/Yacc produces only C

The goal of Nez parser is, say, Write Grammarparsers despite a fact that the LALR(1) gram-Once, Parse Text Anywhere. A key challenge in-mar is by nature independent of a particular pro-cludes an elimination of action code from a gram-gramming language. Two reasons are considered.

mar specification and a language abstraction of anFirst, LALR(1) and other formal grammars can-eﬃcient parser runtime.

not specify a full specification of programming lan-

To begin with, we have designed OPEG [15], an

guage parsers. Indeed, the use of embedded code

extended Parsing Expression Grammar [5], whichcalled semantic actions is very common in mostprovides a small set of declarative operators inparser generators. Another reason is that an eﬃ-

a way that they enables major PEG’s impossi-

cient parser requires many language-specific coding

ble features, such as flexible construction of syn-techniques.

tax trees and context-sensitive pattern matching.

However the question eminds us a significant de-Since OPEG has no longer programmed code. wemand of parser generators: reusability of grammar

can generate a parser for any target languages in

specifications. As the parser generation depends

theory.

∗ This is an unrefereed paper.

Copyrights belong to
the Author(s).
YNU, 横浜国立大学, Graduate School of Electronic andComputer Engineering, Yokohama National University, JAPAN.

The cross-language generation of a parser runtime however is a remaining challenge. Especially,a practical PEG parser is more complicated thana plain recursive descent parser. The memoization

technique (called packrat parsing [4]) is required toThis paper reports an experience on a language

In addi-agnostic code generation throughout on the devel-tion, state changes (constructed trees and other ex-

opment of NezCC. Section 2 introduces OPEG andtended states) must be consistently managed whendemonstrates the NezCC tool. Section 3 describes

backtracking occurs [6].

As a result, the hand-a code structure of NezCC parser and Section 4

porting of the parser runtime is prone to errors anddescribes a design of the language profile. Section

requires many software engineering eﬀorts. In fact,

5 discuss performance evaluation, and experiences

parser runtimes that we have ported by hand areon language-agnostic code generators. Section 6

limited to C, Java, and JavaScript.

briefly reviews related work. Section 7 summarizes

avoid the worst-case time complexity.

NezCC is a language-agnostic parser genera-

this paper.

tor that maximizes the language independence ofOPEG. A key idea of the NezCC is an adaptive

2 A Short Tour of NezCC

generation of the parser runtime itself. A target

This section is a brief introduction of NezCC

language is specified as a language profile with a set

parser generator using our implemented openof syntactic code templates and type mappings. On

source tool and their sample grammars. The tool

the other hand, a NezCC parser runtime is coded

ORIGAMI is available online at:in abstracted language constructs that are common

http://github.com/kkuramitsu/origami.

in many programming languages. NezCC generates
a parser by selecting available language constructs

2. 1 OPEG

from a given language profile.

OPEG is a declarative grammar specification

The following is a list of the NezCC target language, which we have developed so far.

language, originally designed in Nez parser interpreter [15]. In OPEG, a PEG is extended in a

• C, Goway that we enable flexible tree construction and• Java8, C#, Kotlin, Scalacontext-sensitive parsing without any embedded• Python, JavaScript, Lua, PHP

action code. Table 1 shows a summary of PEG• F#, Racket, Haskell

and extended OPEG operators. The semantics of

The list above shows that NezCC generator in-

OPEG is presented in [15].

cludes a broad variety of programming languages

OPEG is a conservative dialect of PEG. All ex-

ranging from low-level system languages, dynamic

pressive PEG operators in ?[] are available as theylanguages, and functional languages. This indicatesare.

that NezCC can cover almost all practical programming languages.
The generated parsers are fast despite a fact that

SUM = NUM ’+’ NUM
NUM = DIGIT+
DIGIT = [0−9]they are based on high-level language abstraction.

PEG however is a syntactic specification of the

In our experiments, NezCC/C parser is as fast as

input string and not a schematic specification of theYacc-generated parser, while NezCC/Java parser is

output trees. OPEG provides a declarative opera-

faster than ANTLR’s generated parsers. Since Yacc

tor of a tree construction by enclosing the content

and ANTLR are widely accepted in industries, we

pattern with { ... }. This notation is similar toconclude that our approach is practical in terms ofthe capturing (...) in PCRE, while the users canparser performance.

additionally specify a #Tag for a type of tree andmanages an extended parser state that is required
PEG
Description’ ’Matches text[]
Matches character class.
Any characterA
Non-terminal application(e)Groupinge?
Optione∗
Zero-or-more repetitionse+One-or-more repetitions&eAnd-predicate!eNegatione1 e2Sequencing
e1 /e2
Ordered Choice
AST{e}Constructor$(e)Connector{$ e }
Left-folding#t
Tagging‘ ‘
Replaces a string
Symbols<symbol A>
Symbolize Nonterminal A<exists A>
Exists symbols<exists A x>
Exists x symbol<match A>
Matches symbol<is A>
Equals symbol<isa A>
Contains symbol<block e>
Nested scope for e<local A e>
Isolated local scope for e
Conditional<on B e>e on B is defined<on !B e>e on B is undefined<if B>
If B is defined<if !B>If B is undefined
表 1 OPEG operators

in some context-sensitive parsing.

For example,<symbol NAME> ... <match NAME> represents a backreference that matches the second NAME exactly
matches the same symbol that is matched at thefirst NAME. Since such symbol operators wellmodel many patterns of context-sensitive syntax[16], OPEG can express many practical program-ming languages including typedef names, here documents, and indent-based code layouts.
Furthermore information on OPEG is presented
in [15]. Also, the ORIGAMI project provides many
grammar examples, which are available at:https://github.com/nez-peg/nez-grammar †1
2. 2 NezCC
NezCC parser generator is implemented as theorigami nezcc command. Here is an example ofgenerating a C parser with the JavaScript grammar (-g js.opeg).
$ origami nezcc −g js.opeg c.nezcc
tree: true
stateful: false
memosize: 53
funcsize: 1889
writing js.c ...

The c.nezcc is a NezCC language profile that$label for a sub node.

gives a set of syntactic templates. The js.c file isHere is a tree annotated version of SUM. Note thata generated parser source, containing all necessary

OPEG has the Camel-style naming convention forcode such as a parser runtime and converted parse

nonterminals involving a tree construction.

functions. Since the generated file also includes the

Sum = {$left(Num) ’+’ $right(Num) #Add}
Num = { DIGIT+ #Num}
DIGIT = [0−9]The above example shows a simple tree construction for readability.

main function as a sample parser, we can simply
build the file to run:$ make js CFLAGS=−O3
cc −O3 js.c −o js

By combing the tree con-struction operators with repetitions and recursions,

The compiled parser takes an input text (or an

variable-length trees such as lists and nested pairs

input file) from the command argument and thencan be constructed. As a result, a flexible form oftrees is specified without any action code.
In addition, OPEG provides a symbol table that

†1 This URL is an older version of grammar repository. The new repository is under construction
right now.

output the parsed trees:# Python nezcc fileextension= pycomment= # %s$ js ’ var x = 1’[#Source[#VarDecl$name=[#NameExpr ’x’]
$expr=[#IntExpr ’1’]]]

So far, what we have showed is just a C parser
generator. The new feature of NezCC is that a tar-

# TypeString→ Byte[] = %s.encode(’utf−8’)
Byte[]. get= ord(%s[%s])Byte[]. slice= %s[%s:%s]
Byte[]’’= ’%s’
Byte[]. quote=’
Byte[]. esc= \x%02x

get language can be switched by just giving anotherlanguage profile. Here is another example that are
generating a Python3 parser:$ origami nezcc −g xml.opeg python3.nezcc
tree: true
stateful: false
memosize: 53
funcsize: 2085
writing js.py ...
$ python3 js.py ’var x = 1’[#Source[#VarDecl$name=[#NameExpr ’x’]
$expr=[#IntExpr ’1’]]]

Figure 1 shows an excerpt of the NezCC language
profile. If we simply define such a profile for a favorite language, we can obtain a full-fledge parser
with the same code quality.

3 NezCC Parser
This section describes a code structure of NezCC
parser. Here, we use Scala to illustrate code frag-Array.size
Array.get
Array.new= len(%s)= %s[%s]= [None] ∗ %2$s

# Syntax
structconstructor
init
gettersetter= class %s := def __init__(self,%2$s):= self.%s = %s
= %s.%s= %s.%s = %s

constfunctionparam
return= %2$s = %3$s
= def %2$s(%3$s):= %2$s= return %svarassignif
while
ifexprlambda= %2$s = %3$s
= %s = %s= if %s:= while %s:= (%2$s if (%1$s) else (%3$s))= (lambda %s : %s)

and
or
not
true
false
null

= %s and %s= (%s) or (%s)= not (%s)= True= False= Nonements for better presentation, since Scala is richenough to show several features of NezCC parser

図1

code.

Example of Language Profile:python2.nezcc

3. 1 Parser Context

parser supports binary data parsing, inputs

Parser context is a main data structure thatrefers to an byte (unsigned 8-bit integer) ar-

maintains several states of a NezCC parser runtime.

ray.

Using Scala, the parser states are represented the• pos – a parser position

class ParserContext, as defined in Figure 2. Each of• length – the length of the input

the fields represents:• headpos – a maximum position that the parser• inputs – an input text.

Note that NezCC

moves forward while parsing. Note that this ise:: aclass ParserContext[T](inputs: Array[Byte],
length: Int,var pos: Int,var headpos: Int,var tree: T,
var treeLog: Option[TreeLog[T]],newFunc: (String,Array[Byte],Int,Int,Int) ⇒ T,
setFunc: (T, Int,String,T) ⇒ T,
var state: Option[State[T]],var memos: Array[MemoEntry[T]])図2

px.inputs[px.pos++] == ’a’e:: e1 e2e1(px) && e2(px)e:: e1 /e2{val p = px.pos; e1(px)|| backtrack(px, p) && e2(px)}e:: &e1{val p = px.pos; e1(px) && backtrack(px, p)}e:: !e1

Main Parser Context{val p = px.pos; !( e1(px) || ! backtrack(px, p))}used for syntax error reporting in PEG parsers.
• tree – a constructed tree, whose type is pa-

e:: {e1 }beginT(px,0) && e1(px) && endT(px, 0)

rameterized.
• newFunc, setFunc – tree constructor functions• treeLog – for tree construction logs represented
by a linked list of TreeLog data
• state – an extended state represented by ae:: $label(e1 )
e1(px) && linkT(px, "label")e:: #T ag
tagT(px, "Tag")

linked list of State data
• memos – memoization table (an array of

図3

Code Translation of PEG Operators

MemoEntry data)
ParserContext contains three other sub data

structures,

defined as TreeLog,

State,

anding. (Note that the true value represents the success of matching.)

MemoEntry, while it contains no specific tree data

Figure 3 shows translation rules that compose

structure. A parameterized type T is alternatively

parse expressions. In NezCC, we take a common

used to represent trees. The users may externallycode strategy to both imperative programming lan-

give constructor functions ((newFunc and setFunc)

guages and functional programming languages. All

to instantiate arbitrary format of trees.

functions (such as backtrack as depicted in Figure 4 and tree construction functions) are defined

3. 2 OPEG Translation

as a function returning a Boolean value, as well as

In general, a code generation of a PEG parser isthe parse function e. As a result, all OPEG pars-simply a replacement of parsing expressions withing expressions can be simple combined by booleanparse functions. In NezCC, an OPEG expression

operators (&&, ||, and !). Obviously, this leads toare replaced with a parse function e, which has aan expression style of code, except for local variablecommon interface:declarations. To handle code in a way that every-e(px: ParserContext) : Boolean

where the parse function e takes an instance ofParserContext and then return the result of match-thing is an expression, all generated functions are
sliced at the point where local variables are needed.
Based on an idea of parser combinators [11],we make a further abstraction of parser functions.

def backtrack(px, pos): Boolean = {px.pos = pos
true
}
図4

Backtrack in NezCC

That is, an operator function is in advance gener-class TreeLog[T](var op: Int,var pos: Int,var tree: T,)
def log[T]( px: ParserContext[T],memoPoint: Int): Int = {true}ated with a parameterized parse function, and theinner expression of the operator is evaluated by be-

図5Logging tree operations in NezCC

ing passed as a high-order function. In other words,
the repetition e1 ∗ is generated by a combination oflinked list allows a stack-based functional data

many1 operator function and a lambda function of

structure.

e1.

abort all operations when backtracking occurs.
many1(px, (p) → e1(p));

In NezCC, the generation of the combinator-stylecode is controlled by a cost-based analysis. Thus,
NezCC reduces the total size of generated code andthen improves the eﬃciency in code cache.

As with the parser position, we canvar p = px.pos
var treeLog = px.treeLog...
backtrack(px, p, treeLog)

An important exception of the tree operations is
the endT function. Since this function is called ata safe point where the consistency of subtrees is

3. 3 Tree Construction

guaranteed, we commit the transaction and thenIn OPEG, trees are specified in a declarative an-

update a tree in ParserContext. Note that NezCC

notation of parsing expressions. Tree constructions

parser constructs trees in a speculative way. This iscan be generated by inserting tree operation code

because it allows significant memory compaction on

before/after parse functions. As shown in Figure3,

tree logs. This also means that some constructed

the tree operation code is implemented in a func-

trees may be discarded when backtracking occurs.

tion returning a boolean value function, which is

However, the memoization (described in Section

easier to combine other functions.

3. 4) avoids redundant tree constructions.

The tree construction however is not so trivial

A data format of tree is another important design

due to backtracking. Let us suppose the parse func-

choice. Actually, trees can be formed in a variety oftion {e1 } fails.

data structures, which may diﬀer from languages tolanguages and, even if the same language, can diﬀer

beginT(px,0) && e1(px) && endT(px, 0)

The operation that is executed at beginT(px, 0)
must be cancelled in a way that nothing happens.
In NezCC, we take an transactional approach
to tree construction. That is, all operations arebuﬀered without any execution and the execution

to customize such a various data structure by tree
constructor functions in ParserContext:• newFunc(tag,inputs,spos,epos,nsubs) - creatinga new tree node with tag by extracting a substring from the input.

is controlled by commit/abort operations.
The TreeLog class (as defined in Figure ??) is adata structure that buﬀers a tree operation.

in types of parser application. NezCC is designedA• setFunc(parent,index,label,child) - adding achild node into a parent node with the spec-

ified label.
class MemoData[T](var result: Int,var pos: Int,var tree: T,
var state: Option[State[T]],)def lookup[T](px: ParserContext[T],memoPoint: Int): Int = {val m: = px.memos(longkey(px.pos,memoPoint))
if (m. key == key)
{ px.pos = m.pos; px.tree = m.tree; m.result } else 2}
def store[T](px: ParserContext[T],memoPoint: Int, pos: Int, matched: Boolean): Boolean = {val m: = px.memos(longkey(px.pos,memoPoint))
m. key = keym. result = (if (matched) 1 else 0)
m. pos = (if (matched) px.pos else pos)m. tree = px.tree
matched}Note that the setFunc function is called manytimes, while each time requires the mutation oftrees. Some languages are unlike to handle sucha mutation. In such cases, NezCC optionally provides immutable tree construction although tree
structures are not configurable at runtime.

3. 4 Memoization
Memoization is a standard technique to avoid theworst-case exponential parsing time in a backtracking parser. NezCC allows the user to switch the useof memoization when the parser is produced. Oncethe user chooses the use of memoization, NezCC
assigned an unique number, called memo point, toan parsing expression to be memoized.
In general, The memo points are assigned to non-

図6

Memoization (lookup and store functions)terminals in a OPEG grammar, while NezCC elim-in NezCC

inates some of cost-ineﬀective nonterminals for im4. 1 NezCC Generator

portant.
In NezCC parser, the memoization table is a 1-

NezCC generator is a code generator specialized

dimensional array of MemoEntry data. Let M be afor parser generation. At first, an OPEG grammar

set of memo points and m be a memo point such

file is parsed to syntax trees, which are traversedthat m ∈ M . The memo entry is located by theby an OPEG visitor. The core of NezCC generator

following key index:

is an OPEG visitor that calls code emitting APIs,

key = m + |M | × pos
This memoization table however requires the lin-which represent an abstract operation of NezCC
parser. Table 2 is a list of emiting APIs.

ear space in the length of the input. To make theEach of emitting APIs binds one and more tem-

constant space consumption, NezCC relies on theplates that synthesize a target code. The suﬃx ?

sliding window idea presented in [12]. That is, thestands for a fact that the template is optional. For

table index is recomputed by the modulo of the key

example, the emitIfExpr() API is associated withindex, and older entries are rewritten as the parser

the ifexpr template, which can be defined in C-likemove forwards. As a result, NezCC can generate alanguages:

simple and an eﬃcient packrat parsing.

4 NezCC Template
This section describes the design and the implementation of NezCC generator and templates.

ifexpr = %1$s ? %2$s : %3$s

Note that formatters such as %1$s and %s follows the Java’s formatter specification. Here, %1$s
stands for the first argument of formatter parameters. The users may change the order of parameters, which can allows the Python-style if expres-sion:

4. 3 Declarators

ifexpr = %2$s if %1$s then %3$s

There are many templates that are not explicitly
supported in a particular programming language.
We may undefine such code templates. Alternative, the NezCC generator tries to produce syntactic sugar code with other available templates. For
example, if ifexpr is undefined, the emitIfExpr()
synthesizes a lambda function that emulates an ifexpression by the if statement. Accordingly, theemitting APIs are designed to take some extra
parameters that enables synthesizing alternativecode.

4. 2 Types and Operators
In NezCC, basic types that are used in a
Nez parser are identified as language independent
names, and then mapped into target types. Hereare basic types and type mappings in the C profile.
Bool
Byte
Int
String
Array
Tree

= int
= unsigned char
= int
= char ∗= %s ∗= void ∗Once these basic types are set, NezCC composes
necessary data types recursively. For example, theBased on basic types, NezCC synthesizes data
structures, data constructors, constant values, andfunctions. The syntax of these code is defined withthe following declarator templates:• struct - complex data definition, optional• functype - function type definition, optional• const - constant definition, mandatory• prototype - prototype declaration, optional• function - function definition, mandatory
Here we focus on struct and functype to specify
the necessary syntax. In c.nezcc, the struct andfunctype are defined as follows.
structend struct
field
functype= struct %s {= };= %s %s;= typedef %1$s (*%2$s)(%3$s);

Here is the produced struct by NezCC.
struct ParserContext {unsigned char ∗ inputs;
long length;
long pos;long headpos;
void ∗ tree;
struct TreeLog ∗ treeLog;
TreeFunc newFunc;
TreeSetFunc setFunc;
struct State ∗ state;struct MemoEntry ∗ memos;};

type of a byte array Byte[] is derived from theNames such as inputs and pos are common acrossdefinition of Byte and Array above and set to betarget languages, while prefixes and suﬃxes can be

unsigned char *.

customized by varname template. Annotations on

As described in Section 3.1, NezCC parser handles a byte array for binary parsing. In several languages, however, the implementation of byte arraysis heavy and result in poor performance. In suchvariables are not user-controlled, but derived fromthe names.
NezCC resolve the dependency of definitions andproduces them in a topological order.

cases, NezCC allows a specialized type instead of
the automatically derived type.
Byte[]= const unsigned char∗

Note that no types are required in a dynamic
language.

4. 4 Controls
A PEG parser involves several control constructs(such as branches and iterations), while supports
for control constructs significantly diﬀer from languages to languages.

In NezCC, we take a minimum-common ap-

version of parse functions. If lambda is also un-

proach to handling the varieties of control con-defined, NezCC finally generates else if version,

structs. That is, all controls of a parser are written

which is slower than the first two versions.

in restricted constructs(i.e., function call, boolean
operators, and if−then−else branch), which are

4. 5 Code Replacement

considered to be common in almost all program-

The syntactic templates cover the core of allming languages. In other words, NezCC can gener-

NezCC parser code. However, there are several cor-

ate a parser if these three common constructs arener cases where template-based code generation is

supported in a target language.

hard in practice.

Here are code templates that produce control• Performance (faster code is available)

constructs in C.
ifelse if
returnwhile
switchcasedefault• Very unique language features= if(%s) {= else if(%s) {= return %s;= while(%s) {= switch(%s) {= case %s : %s
= default : %s

• Main function (due to many language-specificcode)
To integrate these corner cases, NezCC allows a
direct replacement with predefined code fragments.
Since the function names of a parser runtime are
fixed, we can replace some with the predefined func-

Note that there is no return statement in many
functional programming languages. In other words,
we have to define each function with a code fragment that can be controlled without explicit returnstatements. This results in many of small function
definitions.
The minimum-common approach however islikely to result in poor performance. To improve
the performance, we can selectively use whilelooping and switch dispatching, depending on language supports in each target.
A NezCC parser relies on many recursive calls,
assuming the absence of the while construct. However, thoughtless recursive calls may cause perfor-tions.
Here is an example of a function replacementin the C language. The replaced nextbyte function relies on a pointer-based px->pos, instead ofpx->inputs[px->pos++].
def nextbyte = ’’’static int nextbyte(struct ParserContext ∗px) {return ∗px→ pos++;}’’’

In principle, the code replacement is quite powerful. However, the strength of NezCC templates isthat we can generate a parser with the same code
quality. This results in reduced costs of software
testing.

mance degradation and stack overflows in many
languages. For this reason, NezCC synthesizes thewhile version of code only in very limited parts thatare required for performance consideration. The
while version of code is selected only if while is set.

5 Evaluation and Experience
In this section, we evaluate the NezCC generator
in terms of language supports, code quality, andperformance on generated code.

Likewise, NezCC generates dispatching code witha single character lookahead. If switch and case are
undefined, NezCC alternatively generates a function mapping from a lookahead character to lambda

5. 1 Languages
We would like to start by showing a list of programming languages that can generate a NezCC

parser without syntax and type errors†2 . The list
is in our development order, since the developmentof NezCC results from an iterative process of soft-

static int e6(struct ParserContext ∗ px) {return bits32(charset127,nextbyte(px));}

ware engineering in a such way that we add newcode templates for newly found unsupported lan-

図7

Parse function of [0-9]+ in C

guage features.
• Java – original (ported from hand-written Nez
parser)• C – malloc/free, prototype declaration, arrayprivate static <T> boolean e6(ParserContext<T> px) {return many9(px,(p0) → charset127[nextbyte(p0)]);}declaration• Python – untyped code, switch/case alterna-

図8Parse function of [0-9]+ in Javation
• JavaScript – nothing

diﬀerence mainly results from mutable data struc-• Scala – null alternation (Option[T])tures supported in F#.

• Perl – variable names($pos)• F# – ’let rec’ modifier (annotation for recursive functions), explicit type conversion

Rust, a new system language that Mozilla project
developed, is also our interesting target language
but we have not generated any working code yet.

• Lua – the staring index of array

The main diﬃculty is that Rust’s memory manage-• Racket – operator templates such as (+ pos 1),

ment is integrated with Rust’s type system such as

while-less version.
• Haskell – State monad, eliminating duplicatednames in records, and many others.
Table ?? shows a comparison of supported constructs in each of our developed languages.

ownership and lifetime concepts. This is bad compatibility with NezCC’s tree construction where external constructor function. We consider that Rust
1.18 is too strict and not suitable for code generation.

In the reminder of this subsection, we would liketo mention about languages that we have not ac-

5. 2 Code Adaptation

complished the full code generation yet.

Here, we examine the code adaptation of NezCC

Haskell was listed as a primary target language

parser generator. First, we would like to compare

from the beginning of the NezCC project, but at

the syntactic variations of generated code.

the same time it was considered to be the most dif-ure 7, 8, 9, 10, and ?? show parse functions officult one. Indeed, NezCC combinator ideas andthe same parsing expression ’-’? [0-9]+, where

function output units were introduced as a func-

charset127 is a boolean array encoding the [0-9]tional programming. Nonetheless, it took us several

pattern. Note that the numbering of parse func-

weeks to integrate the State monad into a NezCC

tions are sequentially automated, resulting in dif-code structure. The compilation has passed suc-

ferent numbers in each languges.

Fig-

cessfully, but we still need some rewrites to run.

As described in 4. 4, the while support switch dif-Compared to Haskell, F# could be ported in half

ferent versions of code. Figure 11 and 12 comparesa day work even if a F# beginner developed. This

the while version (in JavaScript) and the recursive†2 At this moment, bugs remain in some programming languages

version (in Racket).

(define (many7 px f)
def e6(px):return many9(px,(lambda p0:charset127[nextbyte(p0)])) (define pos (get−field _pos px))
(define treeLog (get−field _treeLog px))
(define tree (get−field _tree px))
図 9 Parse function of [0-9]+ in Python(define state (get−field _state px))
(if (f px) (begin (many7 px f))(begin (back7 px pos treeLog tree state))))func e3(px ∗ ParserContext) (ret bool) {var _ret interface{}defer func() bool{ret, _ = _ret.(bool)
return ret}()_ret = charset127[nextbyte(px)]return ret}

図 12Recursion version of many7 function in
Racketeach of tested parsers. We have parsed an XMark
10 MB file [25] and elapsed times are measured
in millisecond.

図 10

Parse function of [0-9]+ in Go

Tested parsers are labeled by atool/language pair. We run the same test sets several time and the average time is plotted on thegraph. All tests are measured on DELL XPS-8700

function many7(px,f){var pos = px.pos
var treeLog = px.treeLog
var tree = px.tree
var state = px.state
while (f(px)){
pos = px.pos;
treeLog = px.treeLog;
tree = px.tree;state = px.state;}
return back7(px,pos,treeLog,tree,state);}with 3.4GHz Intel Core i7-4700, 8GB of DDR3
RAM, and running on Linux Ubuntu 14.04.3 LTS.
The NezCC/C parser (nezcc/c) indicates thefastest parsing time in all the tested sets, including handwritten XML parsers and yacc-generated
parser.

This suggests that the C compiler(GCC4.5) can well handle a functional code styleof NezCC. In the comparison of the Java parsers,
we confirm that NezCC/java shows not the best
but competitive performance to the hand-written

図 11

While version of many7 function in
JavaScript

Xerce/java, and ANTLR3/4-generated parsers. In
JavaScript comparisons, NezCC/JS/ is also twotime as fast as PegJS/JS. As long as we have tested,

5. 3 Performance StudyNezCC generates a very eﬃcient parser code in ev-

We will turn to the performance evaluation of

ery language.

parsers that are generated by NezCC. Here, we fo-

Table 13 lists the parsing time of other parsers

cus on XML parsing. A reason for this is that XML

that are faster than the PegJS/JS parser.

parsing is easier to compare with hand-written opti-

slower parsers that are not listed are NezC-

mized parsers, such as Xerces [27] and libxml2 [17].

C/Lua5 in 7.2 [s], NezCC/Haskell in 8.2 [s], NezC-

Another reason is that the XML grammar is simple

C/Python2 in 9.7[s], NezCC/Racket in 60[m], andand easy to port into the existing parser generators.

NezCC/PHP in 74[m]. The reader might consider

In this experiment, we compare NezCC generator

that very slow parsers seem useless in practical.

with Yacc(Bison [3]), ANTLR3/4, and PegJS [18].

However, many applications need to parse not so

Figure 13 shows the parsing time of XML data inlarge but complex input data.

The

The strength of

Parsing Time for XMark 10MB [ms]pegjs/js
nezcc/julia
nezcc/kotolinnezcc/swift
nezcc/js
nezcc/f#
antlr3/java
nezcc/c#
antlr4/java
nezcc/scalanezcc/java
xerces/c
xerces/java
libxml2/java
yacc/cnezcc/c
0

200

400

図 13

600

800

1000

1200

1400

1600

Performance comparions: XMark 10MB

NezCC is that parsing is all the same way in any
language environments.

such as Scala and F#.
We prepared a test grammar (named testcase.opeg),
while most of a newly generated parser passed with-

5. 4 Experienceout serious failures. Compared to a hand-written

Finally, we summarize our experiences on cross-parser generator, the quality of initial code is highlanguage techniques that we have learnt throughand software testing seems unnecessary. Static typeour development of NezCC. Here, we start with two

checkers are always useful for finding mistakes inassumptions that we set before the development ofcode templates, while dynamic languages require

NezCC.

print debugging at the runtime. The most serious

Assumption 1: If we generate a parser code based

bug was caused by an integer overflow when parsing

on only common language features of C and Java,a very large input.

it would be easy to map to other languages.

In origin, NezCC is designed on an assumption

This is assumed simply because many existingthat all programming languages support, at least,

languages are influenced from C and Java. But,

function call, boolean operators, and if-expression

what we have experienced is the complexity of type

(ternary operator). However, the lack of our knowl-

mapping. In particular, richly-typed languages areedge is gradually clear since Lua and Go language

likely to be more diﬃcult. For example, many mod-have no if-expression support. Thus, there are noern languages provide some static null check sup-minimal common language features that allow pars-port. This requires us adding the Option-like typeing.

(Maybe in Haskell) template after all. However, theThis fact also led to a crisis of NezCC project,

Option-like type has little common operators acrosssince the code structure of NezCC relies largely on

languages, making it diﬃcult to design code tem-a functional style. What saved us was a lambda ex-

plate. (As a result, NezCC generates very miserablepression, which allows us to map imperative codecode).

into an expression. In the end, the lambda support

Assumption 2: Software test is unnecessary since a

is very important in developing a cross-language

generated parser is tested with strongly-typed code

code generation.

of PEGs and PEG parsers [5] [4]. Notably, we base

6 Related Workthe partial DFA conversion of PEGs [19], a transac-

Parser generator is a typical scenario of gener-

tional state management (tree construction) [6] [14],ative programming, and has a long history in theand cache-based eﬃcient packrat parsing [24] [12].

field of programming languages. Lex/Yacc [8] is thefirst modern parser generator, which has invented

7 Conclusion

semantic actions embedded on a formal grammar

We have addressed a language agnostic genera-

specification. Since the semantic action hits a sweettion of a full-edged parser, including flexible tree

spot [7] between the grammar expressiveness andconstruction, extended context-sensitive parsing,

the practical performance, most of parser genera-and eﬃcient packrat parsing. The NezCC genera-

tors inherit this idea from Yacc. However, seman-

tor is based on two levels of abstraction: a declara-

tic action code significantly reduces the reusabil-tive modeling of extended PEG-based parsing andity of grammar specifications, as many researchersa language abstraction of an eﬃcient parser run-[21] [10] [15] have been pointed out.

time. In this paper, we have focused mainly on

Generalization of semantic action code is the firstthe latter; a set of syntactic code templates andstep attempt toward a language agnostic genera-

type mappings allows us to generate parser code oftor. In this context, attribute grammars [20] or ab-very various target languages, including C, Java,

stracted operations [10] [2] [9] [1] [26] have been ad-

JavaScript, Python, Lua, Scala, Racket, and F#.

dressed instead of semantic action code. OPEG

Throughout this study, we have found thatin NezCC has been developed to eliminate arbi-

the parser generation is a good subject of cross-trary action code [15]. Even if a grammar is purely

language code generation, which would be increas-declarative, the porting problem remains.

ingly demanded in the current development of soft-

As of 2017, there are more than 140 kindsof parser

generatorware. In that respect, many interesting challenges

implementations on the
Wikipedia’s comparison list†3 . 26 of the listed

remained, including cross-language optimization,parser generators produces two or more target lan-

guages. We hope that this research will lead to fur-guages.

thermore generalized cross-language transpliation

Notably, ANTLR 3/4 [22] [23] provides

an abstract and standardized APIs between the
ANTLR parser runtime.

and code reliability and verification across lan-techniques.

Many parser runtimes

have been ported so far, while they relies on asignificant amount of software engineering eﬀorts

参 考 文 献[ 1 ] Adams, M. D.:
Principled Parsing forIndentation-sensitive Languages: Revisiting Landin’s
and strong community supports. To my knowledge,
Oﬀside Rule, Proceedings of the 40th Annual ACM
NezCC is the first template-based parser generator,
SIGPLAN-SIGACT Symposium on Principles ofProgramming Languages, POPL ’13, New York,
which enables a wide support of target languages
NY, USA, ACM, 2013, pp. 511–522.
at a very short period of the development time.
[ 2 ] Atkey, R.: The Semantics of Parsing with Semantic Actions, Proceedings of the 2012 27th AnLast not but least, NezCC totally relies on thenual IEEE/ACM Symposium on Logic in Computer
simple and eﬃcient parser runtime, which results
Science, LICS ’12, Washington, DC, USA, IEEE
Computer Society, 2012, pp. 75–84.
from many previous research eﬀorts in the context[ 3 ] Donnelly, C. and Stallman, R.: Bison. The
YACC-compatible Parser Generator, (2004).
[ 4 ] Ford, B.: Packrat Parsing:: Simple, Powerful,†3 https://en.wikipedia.org/wiki/Comparison of parser generators

Lazy, Linear Time, Functional Pearl, Proceedings of
the Seventh ACM SIGPLAN International Conference on Functional Programming, ICFP ’02, New
York, NY, USA, ACM, 2002, pp. 36–47.
[ 5 ] Ford, B.: Parsing Expression Grammars: A
Recognition-based Syntactic Foundation, Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,
POPL ’04, New York, NY, USA, ACM, 2004,
pp. 111–122.
[ 6 ] Grimm, R.: Better Extensibility Through Modular Syntax, Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’06, New York, NY,
USA, ACM, 2006, pp. 38–51.
[ 7 ] Jim, T., Mandelbaum, Y., and Walker, D.:
Semantics and Algorithms for Data-dependent
Grammars, Proceedings of the 37th Annual ACM
SIGPLAN-SIGACT Symposium on Principles ofProgramming Languages, POPL ’10, New York,NY, USA, ACM, 2010, pp. 417–430.
[ 8 ] Johnson, S. C.: Yacc: Yet another compilercompiler, Vol. 32, ell Laboratories Murray Hill, NJ,
1975.
[ 9 ] Johnstone, A. and Scott, E.: Tear-Insert-Fold
Grammars, Proceedings of the Tenth Workshop
on Language Descriptions, Tools and Applications,
LDTA ’10, New York, NY, USA, ACM, 2010,
pp. 6:1–6:8.
[10] Kats, L. C., Visser, E., and Wachsmuth, G.:
Pure and Declarative Syntax Definition: Paradise
Lost and Regained, Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications,OOPSLA ’10, New York, NY, USA, ACM, 2010,
pp. 918–932.
[11] Koopman, P. W. M. and Plasmeijer, M. J.: Eﬃcient Combinator Parsers, Selected Papers from the10th International Workshop on 10th International
Workshop, IFL ’98, London, UK, UK, SpringerVerlag, 1999, pp. 120–136.
[12] Kuramitsu, K.: Packrat Parsing with Elastic
Sliding Window, Journal of Infomration Processing, Vol. 23, No. 4(2015), pp. 505–512.
[13] Kuramitsu, K.: Packrat Parsing with Elastic
Sliding Window, Journal of Infomration Processing, Vol. 23, No. 4(2015), pp. 505–512.
[14] Kuramitsu, K.: Fast, Flexible, and Declarative Consturction of Abstract Syntax Trees with
PEGs, Journal of Infomration Processing, Vol. 24,
No. 1(2016), pp. 256264.
[15] Kuramitsu, K.: Nez: Practical Open Grammar
Language, Proceedings of the 2016 ACM Interna-

tional Symposium on New Ideas, New Paradigms,
and Reflections on Programming and Software, Onward! 2016, New York, NY, USA, ACM, 2016,
pp. 29–42.
[16] Kuramitsu, K.: A Symbol-Based Extensionof Parsing Expression Grammars and ContextSensitive Packrat Parsing, Proceedings of ACM
SIGPLAN International Conference on Software
Language Engineering, SLE 2017, 2017.
[17] Libxml2: Validation and DTDs, http://xmlsoft.org/xmldtd.html,
2015.
[18] Majda, D.: PEG.js - Parser Generator for
JavaScript, 2015.
[19] Nariyoshi, C. and Kuramitsu, K.: Linear Parsing Expression Grammar, Proceedings of 11th International Conference on Language and Automata
Theory and Applications, LATA 2017, New York,NY, USA, 2017, pp. (to appear).
[20] Paakki, J.: Attribute Grammar Paradigms&Mdash;aHigh-level Methodology in Language Implementation, ACM Comput. Surv., Vol. 27, No. 2(1995),
pp. 196–255.
[21] Parr, T.: The Reuse of Grammars with Embedded Semantic Actions, Proceedings of the 2008 The
16th IEEE International Conference on Program
Comprehension, ICPC ’08, Washington, DC, USA,IEEE Computer Society, 2008, pp. 5–10.
[22] Parr, T. and Fisher, K.: LL(*): The Foundationof the ANTLR Parser Generator, Proceedings of the
32Nd ACM SIGPLAN Conference on Programming
Language Design and Implementation, PLDI ’11,
New York, NY, USA, ACM, 2011, pp. 425–436.
[23] Parr, T., Harwell, S., and Fisher, K.: Adaptive
LL(*) Parsing: The Power of Dynamic Analysis,
Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems
Languages &#38; Applications, OOPSLA ’14, New
York, NY, USA, ACM, 2014, pp. 579–598.
[24] Redziejowski, R. R.: Parsing Expression Grammar As a Primitive Recursive-Descent Parser with
Backtracking, Fundam. Inf., Vol. 79, No. 3-4(2007),
pp. 513–524.
[25] Schmidt, A., Waas, F., Kersten, M., Carey,
M. J., Manolescu, I., and Busse, R.: XMark: A
Benchmark for XML Data Management, Proceedings of the 28th International Conference on Very
Large Data Bases, VLDB ’02, VLDB Endowment,
2002, pp. 974–985.
[26] Thielecke, H.: On the Semantics of Parsing
Actions, Sci. Comput. Program., Vol. 84(2014),
pp. 52–76.
[27] Xerces: Apache Xerces Project, http://xerces.apache.org/,
2015.

表2

List of Emitting APIs

Declarators

Templates

declStruct(name, fields)

structdeclFuncType(ret, name, params)

functype?

declConst(type, name, size, data)

const,const array?

declProtoType(ret, name, params)

prototype?

declFunc(acc,ret,name,params,block)function

Statements
beginBlock()

begin?

emitStmt(block, expr)

semicolon;

endBlock(block)end?

emitVarDecl(mut,name,expr,expr2)

letin?,var?

emitIfStmt(expr, elseIf, stmt)

if,else if?

emitWhileStmt(expr, stmt)

while?

Expressions
emitAssign(name, expr)

assign?

emitReturn(expr)

return?

emitOp(expr, op, expr2)+,-,*,%,eq,neemitConv(var, expr)

T->T

emitNull(name,)

null?

emitArrayIndex(self, index)

Array.get

emitNewArray(type, index)

Array.newemitGetter(self, name)getteremitSetter(self, name, expr)

setteremitNew(type, params)

object?

emitFunc(func, params)

funccallemitApply(func, params)

apply

emitNot(expr)

notemitSucc()

true

emitFail()

false

emitAnd(expr, expr2)

andemitOr(expr, expr2)

oremitIfExpr(expr, type, expr2, expr3)

ifexpr?

emitFuncRef(name)funcref?

emitLambdaExpr(params, body)lambda?

emitDispatch(index, cases)

switch?

表3Comparison of Supported Constructors in Languages

Languageconstructor

lambdaifexprwhile

switchnull

mutableC

malloc

x

o

o

o

o

o

C#

new

o

o

o

o

o

o

F#

record

o

o

o

match

x

o

Go

new

o

x

o

o

o

o

Haskellrecord

o

o

x

match

x

x

Java8

new

o

o

o

o

o

o

JavaScript

function

o

o

o

o

o

o

Lua

record

o

x

o

x

o

o

Perl

record

o

o

o

x

x

o

PHP5/7

new

o

o

o

o

o

o

Python2/3

new

o

o

o

x

o

o

Racketrecord

o

o

x

match

o

o

Scala

new

o

o

o

match

x

o

Swift

record

o

o

o

o

x

o