Implementing a Small Parsing Virtual
Machine on Embedded Systems
Shun Honda1 and Kimio Kuramitsu1
1 GraduateSchool

of Electronic and Computer Engineering, Yokohama National

University

arXiv:1511.03406v1 [] 11 Nov 2015

ABSTRACT
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.

Keywords:

Schema validation, XML/DTD, parsing expression grammars, and performance

1 INTRODUCTION
In recent years, the increased use of text data on the Web and IoTs raises new demands for processing
texts on embedded systems. Text data are flexible in data representation, and can carry a variety of data
formats such as XML and sensor logs. To make the use of such various formats, we need advanced text
processing, that is, parsing and syntactic analysis.
In developing embedded systems, C is a popular programming language. In parallel, it is a known
fact that C suffers from poor language supports for strings. Unfortunately, the poorness has enforced C
developers to heavily use low-level pointer operations, resulting in a major source of bugs and security
vulnerability. Regular expression libraries, such as PCRE libraryHazel (2015), have reduced such
error-prone coding, but still suffers from its limited expressiveness for handling structured data.
We address the use of Parsing Expression GrammarsFord (2004) on resource-restricted embedded
systems. PEGs are a new recognition-based formal grammar and more expressive than regular expressions,
so that the use of PEGs would enable us to parse and extract various text data, including HTML, XML,
JSON and various logs, without any program code.
The main challenge of this paper is that we attempt to an small implementation of virtual parsing
machine. The reason is that the recursive decent parsing, a common algorithm of PEG-based parsing,
requires the uncontrolled size of the C stack consumption for recursion. A large amount of C stack
consumption is not definitively suitable for embedded systems since the maximum stack size is limited to
4K-16K bytes. To avoid uncontrolled C stack consumption, the support of a controllable specialized stack
is attempted with a machine virtualization.
MiniNez is a small virtual machine designed for PEG parsing. The MiniNez works with optimized
bytecode that is produced by a MiniNez compiler. Due to the separation of compiler and code optimizer,
the resulting MiniVM machine achieves a very small footprint, implemented with approximately 100
lines in C source code. Despite such compactness, MiniNez provides us with rich parsing capability for
various type of text data, including CSV, XML, JSON, Syslog, and others. In addition, MiniNez achieves
a competitive performance, compared to generated C parsers.
The remainder of the paper is structured as follows. Section 2 introduce PEGs and opportunities for
text data. Section 3 presents the design of stackless virtual machine. Section 4 describes the detailed
implementation of MiniNez machine with several compilation techniques for reduced code size. Section
5 demonstrates the experimental results. Section 6 reviews related work. Section 7 concludes the paper.

Table 1. PEG Operators
PEG
’ ’
[]
.
A
(e)
e?
e∗
e+
&e
!e
e1 e2
e1 /e2

File
CSV
Value

Type
Primary
Primary
Primary
Primary
Primary
Unary suffix
Unary suffix
Unary suffix
Unary prefix
Unary prefix
Binary
Binary

Proc.
5
5
5
5
5
4
4
4
3
3
2
1

Description
Matches text
Matches character class
Any character
Non-terminal application
Grouping
Option
Zero-or-more repetitions
One-or-more repetitions
And-predicate
Negation
Sequencing
Prioritized Choice

= CSV*
= Value ( ’,’ Value )* ’\n’
= (![,\n] .)*

Figure 1. Syntax Definition of CSV

2 PARSING EXPRESSION GRAMMARS
Parsing Expression Grammars (PEGs) are recognition-based foundation for describing syntax, formalized
by FordFord (2004).
2.1 Notion and Operators
A PEG is a collection of production rules, which take an EBNF-like form A = e, where A is a nonterminal
and e is a parsing expression. Parsing expressions are composed by PEG operators, which looks like
regular expressions.
Table 1 shows a summary of PEG operators that compose an expression. The string ’abc’ exactly
matches the same input, while [abc] matches one of these characters. The . operator matches any single
character. The lexical match consumes the matched size of characters and moves forward a position of
matching. The e?, e∗, and e+ expressions behave as in common regular expressions, except that they are
greedy and matches until the longest position. The e1 e2 attempts two expressions e1 and e2 sequentially,
backtracking the starting position if either expression fails. The choice e1 / e2 first attempt e1 and then
attempt e2 if e1 fails. The expression &e attempts e without any character consuming. The expression !e
fails if e succeeds, but fails if e succeeds. Furthermore information on PEG notations are referred as to
Ford (2004).
2.2 Opportunities for Text Data
PEGs have been originally formalized for programming language parsers. However, the formalism of
PEGs is composed by several desirable properties for parsing text data. Here we introduce the properties
of PEGs with example several grammars for text data.
Figure 1 shows a PEG grammar for the syntax of Comma Separated Value, or simply CSV, where
values are simply parsed by the separation character such as ’,’ and ’\n’. Although this grammar is
fairly simplified for readability, this suggests how small set of productions make possible a lot. Note that
PEGs are a scanner-less parsing, so that both lexical and syntax analysis are specified in an integrated
way.
Figure 2 shows a PEG grammar for the XML 1.0 syntax. Due to EBNF-like nonterminal calls, PEG
can recognize recursively nested structures, which is hardly recognized by regular expressions. In addition,
PEG’s unlimited look-aheads by syntactic predicates (such as &e and !e) allow recognizing such a nested
structure as {an bn cn |n > 0}, which cannot be recognized in CFGs.
Figure 3 is a grammar fragment for the syslog format. PEGs can describe the content of data elements
2/15

TopLevel
PROLOG
DTD
Element

= PROLOG? _* DTD? _* Element _*
= ’<?xml’ (!’?>’ .)* ’?>’
= ’<!’ (!’>’ .)* ’>’
= ’<’ Name (_+ Attribute)* (’/>’ / ’>’
Content ’</’ Name ’>’) _*
Name
= [A-Za-z:] (’-’ / [A-Za-z0-9:._])*
Attribute = Name _* ’=’ _* String
String
= ’"’ (!’"’ .)* ’"’
Content
= (Element / CDataSec / CharData)*
CDataSec = ’<![CDATA[’ (!’]]>’ .)* ’]]>’ _*
COMMENT
= ’<!--’ (!’-->’ .)* ’-->’ _*
CharData = (!’<’ .)+
_
= [ \t\r\n]

Figure 2. Syntax Definition of XML
File
Log
DAY
MONTH
TIME
HOST
PROCESS
PID
DATA

= Log*
= MONTH ’ ’ DAY ’ ’ TIME ’ ’ HOST ’ ’
PROCESS ’[’ PID ’]’ Misc ’: ’ DATA
= [0-3 ][0-9]
= ’Jan’/’Feb’/’Mar’/’Apr’/’May’/’Jun’
/’Jul’/’Aug’/’Sep’/’Oct’/’Nov’/’Dec’
= [0-9][0-9] ’:’ [0-9][0-9] ’:’ [0-9][0-9]
= (!’ ’ .)*
= (!’[’ .)*
= [0-9]+
= (!(’\n’ (MONTH / !.)) .)*

Figure 3. Grammar of Syslog Format
such as DATE and TIME with lexical patterns, as well as the syntactic structure. This feature helps analyze
unstructured text data. In addition, it is allowed to compose defined nonterminals from other PEGs, since
PEGs are closed under composition (notably, intersection and complement). This means we can easily
compose two different grammars to parse a mixed content such as log entries containing an XML element.
The last example comes from an application to the information extraction. Figure 4 is a PEG for
finding all emails from a text. Unlike the traditional parser construction defining a complete set of syntax
rules, we can treat an interesting part of text data. Note that PEGs provide the recognition capability
only. That is, another complemental trick is needed to extract from the results of the recognition. Several
approaches Grimm (2006); Ierusalimschy (2009); ? have been proposed and implemented in contexts of
PEG-based tools.
2.3 Problems
PEGs have been mostly used in a parser generation scenario. That is, the grammar specification is
converted to a parser source code written in C or other general-purpose programming language. Since
PEGs can be simply implemented with a recursive decent parsing, the parser generation is easier than that
in other formal grammars such as LALR, and fits in compaction requirements for embedded systems.
To illustrate the parser generation, let us consider the following simple production rule:
A = ’a’ A / ’’
File
EMAIL
LOCAL
DOMAIN
SUBDOMAIN

=
=
=
=
=

((!EMAIL .)* EMAIL )*
LOCAL ’@’ DOMAIN
([A-Za-z0-9] / ’-’)+ (’.’ LOCAL)?
SUBDOMAIN (’.’ SUBDOMAIN)+
([A-Za-z0-9] / ’-’)+

Figure 4. Example of Information Extraction
3/15

The production A is converted into a nonterminal function which looks like:
bool A() {
if(match(’a’)) {
return A();
}
return true;
}

A problem with a recursive decent parsing is that every nonterminal call requires the C stack consumption. Let us take a look back at the above example; the necessary amount of C stack depends on
the length of a given input ’a’ character sequence. That is, we need 5 recursive nonterminal calls of A
to match ’aaaaa’. In reality, the grammar developer mostly uses non-recursive expression ’a’* for
repetition, the total amount of stack consumption can fit in a standard C stack size. However, in embedded
settings that are characterized in common by very limited C stack space (such as 4KB), the recursive
decent parser would easily consume all available C stack during parsing.

3 PARSING VIRTUAL MACHINE
The parsing virtual machine is an alternative implementation that makes no use of C stack. Nonterminal
calls are replaced with VM instructions that operate over independently-allocated VM stacks. The
consumption of VM stacks can be smaller than that of C stacks, since we can specialize VM stack
operations based on PEG parsing. Moreover, the user can control the size of VM stack allocation in order
to fit the grammar specification.
In this section we describe our motivation of stackless virtual machine, a set of designed VM
instructions, and the conversion from parsing expressions to designed instructions. Note that the term
”stackless” in this paper implies that no C stacks are consumed when parsing.
3.1 Parsing Instructions
Parsing instruction is an abstract VM instruction that is selected to compose a minimum instruction set to
execute all PEGs operators. Our designed instruction set consists of 12 instructions, summarized in Table
2.
In the past, LPegMedeiros and Ierusalimschy (2008), another parsing machine implementation,
defines a similar set of parsing instructions. However, the design principle differ from ours in terms of
backtracking handling. LPeg’s instruction set has adopted dynamic global indirect jump to alternative.
As in an exception handling, a jump address to alternative code is pushed on the stack and looked up at
backtracking time. On the contrary, our instruction set is based on static local direct jump to alternative.
The jump address is determined at the compilation time. As a result, we expect that the amount of stack
consumption can be further reduced.
The semantics of parsing instructions can be defined as a state transition of a parser instance. The
instance has four states, denoted pos, pc, sp, r, which are defined respectively:
• pos – a position at which the parser matches the input stream
• pc – program counter
• sp – an index of the operand stack top
• r – a Boolean value for representing either > (success) or • (failure).
Let I be a input characters and I[pos] be a character at pos-th position. We use L, L0 , L00 to range over
labels for a jump pointer. Figure 5 shows the operational semantics of parsing instructions.
Backtracking is a notorious behavior in PEG-based parsing. The parsing machine must move back
to a parsing position to execute alternative instructions. In our instruction set, we save a current parsing
position pos by push, and restore it by peek. The pop is used to rollback the stack status. All parsing
4/15

Table 2. Instruction set in parsing machine
Opcode
Argument Description
nop
Do nothing
succ
Succed always
fail
Fail always
char
c
Match the character c
any
Match any character
jump
L
Branch always
iffail L
Branch if the result is F
call
L
Call the nonterminal call
ret
Return the nonterminal call
push
Push pos to the stack
pop
Pop the top operand stack value
peek
Store the top operand stack value
L: Label representing a position of code point

expressions that need to handle backtracking are surrounded by push and pop. In backtracking cases,
we restore the pushed position, and use succ() to turn the parsing result into success. Figure 6 depicts a
basic flow of success and failure case of parsing.
3.2 Converting Parsing Expressions
The conversion from parsing expressions to parsing instructions can be defined in an inductive manner. Let
τ(e, L) be a conversion function that maps from a given parsing expression e to an instruction sequence.
The second argument L is a jump address that is performed in the failure evaluation case of e. Figure ?? is
a definition of an abstract syntax of parsing expression e. Figure 7 shows a full conversion of all parsing
expressions to sequence of parsing instructions.
As described in Section 3.2, our parsing instructions are based on the static jump to alternative.
The failure-case jump to L is invoked by the execution of iffail(L). For example, iffail(L) is
executed after char(c) to check the failure of matching. The failure status is preserved until the explicitly
controlled by succ(). This is why we need to recheck the failure status in cases of nonterminal calls. The
jump analysis is closed within a production local scope.
The choice expression e / e0 is a typical case of involving backtracking handling. Likewise, the option
e? and e∗ encode the similar backtracking handling. Note that these operators by nature are a syntax sugar
of the choice expressions in PEGs. The & and ! predicates always consume no character. This means we
need to rollback the parsing position in cases of either success or failure. In the not-predicate, we turn
over the result status.

4 MININEZ
MiniNez is a PEG virtual machine for processing text on embedded systems. In this section we describe
the implementation of MiniNez.
4.1 Architectural Overview
The machine virtualization approach requires the pre-compilation to parsing instructions. As we described
in Section 3.3, converting parsing expressions into parsing instructions is fairly simple. However,
converted code is neither the best nor good enough in reality. Advanced code refinement, or optimization,
is required both to improve the performance and to reduce code size. The integrated compilation on the
machine might be desirable in terms of usability, but perhaps too costly in embedded system environments.
Instead, we have adopted the decoupled architecture of virtual machine from bytecode compiler. As
in Java virtual machine and other embedded virtual machine implementationsShida et al. (2013), we can
expect a smaller footprint of implemented virtual machine. As a result, our implemented MiniNez tool
consists of the following two parts:
5/15

nop() (pc, pos, sp, r)
(pc + 1, pos, sp, r)
char(c) (pc, pos, sp, >) I[pos] = c
char(c) (pc, pos, sp, >) I[pos] 6= c
,
(pc + 1, pos + 1, sp, >)
(pc + 1, pos, sp, •)
call(L) (pc, pos, sp, >)
(L, pos, stack.push(pc + 1), >)

ret() (pc, pos, sp, r)
(stack[sp], pos, sp − 1, r)

iffail(L) (pc, pos, sp, >)
,
(pc + 1, pos, sp, >)

iffail(L) (pc, pos, sp, •)
(L, pos, sp, •)

succ() (pc, pos, sp, r)
,
(pc + 1, pos, sp, >)

fail() (pc, pos, sp, r)
(pc + 1, pos, sp, •)

push() (pc, pos, sp, r)
(pc + 1, pos, stack.push(pos), r)

pop() (pc, pos, sp, r)
(pc + 1, pos, sp − 1, r)

peek() (pc, pos, sp, r)
(pc + 1, stack[sp], sp, r)
Figure 5. Operational Semantics of Parsing Instructions

[SUCCESS]
push()
...
pop()

[FAIL]

peek()
pop()
succ()

Figure 6. A Basic Flow of Failure Handling
• MiniNez compiler
• MiniNez machine
Figure 8 shows the architectural overview of MiniNez. The users use a PEG language to specify their
grammars. The MiniNez compiler loads the specified grammar file and produces a compiled code file.
The MiniNez machine loads the compiled code and instantiates a parser runtime when parsing the input
string. Unlike parser generators, any C code generation and C compilation are necessary for loading new
grammars.
MiniNez compiler is written in Java and based on our developed Nez parsing tool kit, including a
PEG parser, a grammar analysis framework, and code generator framework. That is, we generate some
optimized MiniNez code, instead of C code generation for the specified parser. In Section 5, we perform
the comparative study with C parsers that are generated by Nez parsing toolkit?. MiniNez machine is
written in C and in a very portable manner without any library dependencies. Since MiniNez code is a
platform-independent, MiniNez can run in many resource-restricted computing environments, including
Linux Kernel.
6/15

τ(ε, L)
τ(c, L)

=
=

τ(., L)

=

τ(A, L)

=

τ(e e0 , L)

=

τ(e / e0 , L)

=

L’

L”
τ(&e, L)

=
L’

τ(!e, L)

=

L’

nop
char c
iffail(L)
any
iffail(L)
call A
iffail(L)
τ(e, L)
τ(e0 , L)
push
τ(e, L0 )
pop
jump L00
peek
pop
succ
τ(e0 , L)
nop
push
τ(e, L0 )
peek
pop
iffail L
push()
τ(e, L0 )
peek
pop
fail
jump L
peek
pop
succ

Figure 7. Definition of the conversion function τ(e)

4.2 MiniNez Compiler
MiniNez compiler integrates optimization opportunities to refine converted code. In this section, we focus
mainly on downsizing optimizations, including instruction specialization, cost-based inlining, and static
flow analysis.
4.2.1 Instruction Specialization

Instruction specialization is an optimization technique that replaces frequently appearing instruction
sequences, or sequence patterns, with a single specialized instruction. Apparently, this optimization
allows the size reduction of compiled code. Figure 9 shows an example of instruction specialization in
case of !c. The left-hand side is a code fragment converted by τ(!c, L), and the right-hand side is the
same code replaced with a specialized instruction nchar(c), standing for not-character matching. In this
example, 10 instructions are reduced into a single instruction.
As shown above, the instruction specialization has a huge effect on code reduction. On the other hand,
an indiscriminate increase of specialized instructions simply fatten the virtual machine footprint. We
have carefully designed by three approaches: peephole specialization, lexical specialization, and unary
specialization.
Peephole specialization is based on the frequency analysis of paired instructions. To begin with, we
pose the (at-most) one-argument constraint in designing specialized instructions. The reason is that the
constraint makes it easier for us to minimize a fixed-length instruction layout, as we will describe in
7/15

PEG	


Nez/PEG	
  parsing	
  library	

MiniNez Compiler	

Compiler	
  	


Nez	
  bytecode	


Loader	
  	

MiniNez Machine	

Machine	
  	


Figure 8. MiniNez architectural overview

L’

unspecialized
push()
char(0 c0 )
iffail(L0 )
peek()
fail()
jump(L)
peek()
pop()
succ()
nop()

specialized
nchar(0 c0 , L)

Figure 9. Example of instruction specialization
the next subsection. That is, for example, a sequence char(a) iffail(L), encoded from a character
terminal ’a’, can be not specialized due to two arguments. On the other hand, a sequence peek() pop()
can be specialized into a single peekpop() instruction.
Lexical specialization is an enhancement of char(c) instruction, which improves lexical matching
capability. The instruction design is based on the analysis of the terminal equality, as follows:
• str(s) – string matching, specialized from the sequence of characters ’a’ ’b’ ’c’
• cmap(m) - character bitmap-based matching, specialized from the choice of characters ’a’ / ’b’
/ ’c’
Unary specialization is based on the observation that unary expressions are likely converted with many
instructions. To start, we focus on unary expressions including lexical patterns such as char, str, and
cmap. Table3 shows the selected combinations in each unary expression. The instruction in the gray cell
stands for unimplemented due to fewer appearance in real grammars.
4.2.2 Cost-based Inlining

The inline expansion replaces a non-terminal call with the body of associated expressions. Simply, it can
remove the cost of two instructions: call and ret. While inlining is a known technique for a significant
performance improvementGrimm (2006), the indiscriminate lining enlarges the resulting code size due
to code duplication. We highlight the downsizing effect in this paper, and then apply inlining on the
following conditions:
8/15

Table 3. The selection of unary specialization
unary
not
and
option
repetition

char
nchar
achar
ochar
rchar

Opcode	
  
5	
  bits	


str
nstr
astr
ostr
rstr

cmap
ncmap
acmap
ocmap
rcmap

Operand	
  
11	
  bits	


Figure 10. structure of MiniNez instruction

• Associated expressions can be compiled to less than two instructions
• Nonterminals are referred from a single unique context.
Due to the above conditions, the inlining process reduces compiled code size.
4.2.3 Static Flow Analysis

Static flow analysis is an optimization technique based on the control flow of failure cases. Intuitively,
the conversion creates redundant instructions such as duplicated push and jump. The following is the
converted code for (e1 /e2 )∗. The left-hand is the plain conversion by τ((e1 /e2 )∗, L). The duplicated
push instructions are generated before the evaluation of the first subexpression e1 . However, it is
unnecessary to push the same position. The right-hand is a redundant-removed version of the left-hand.
The flow analysis allows us to eliminate such duplicated operations.

L1

L2

L3
L4

plain code
push()
push()
τ(e1 , L2)
pop()
jump(L3)
peek()
pop()
succ()
τ(e2 , L4)
pop()
jump(L1)
peek()
pop()
succ()
nop()

L1
L2

L3
L4

removed
push()
τ(e1 , L2)
jump(L3)
peek()
succ()
τ(e2 , L4)
pop()
jump(L1)
peek()
pop()
succ()
nop()

4.3 MiniNez Machine
MiniNez machine is a small virtual machine that specifically performs parsing instructions. The major
difference from application virtual machines such as JavaVMs is that MiniNez provides no instruction
supports for general-purpose operations. Table 4 lists the full instructions of MiniNez. Currently, only 20
instructions including extended instructions in Section 4.2 are implemented on MiniNez.
The small set of the supported instructions enables us to reduce the opcode layout down to 5 bits. In
addition, we make the fixed length of all instructions 2-byte in length by carefully designing instruction
arguments. Pointers to strings and long jump points are all reduced to 11-bit length. Figure 10 shows the
layout of instructions.
The body of the MinNez machine is implemented with a single C function that iterates instruction
executions. Figure 11 illustrates our implemented code that is excerpted from the virtual machine function.
9/15

Table 4. Full instructions
Opcode
nop
succ
fail
char
any
jump
iffail
call
ret
push
pop
peek
str
cmap
nchar
nstr
ostr
ocmap
rcmap
peekpop

Argument

c
L
L
L

s
m
c
s
s
m
m
s:

Description
Do nothing
Succed always
Fail always
Match the character c
Match the any character
Branch always
Branch if the result is F
Call the nonterminal call
Return the nonterminal call
Push pos to the stack
Pop the top operand stack value
Store the top operand stack value
Match the string
Match the character bitmap map
Not-character matching
Not-string matching
Optional string matching
Optional character map
Repetition of character map
peek and pop
string, m: character bitmap

All paring states are bounded as local variables, (pc, pos, sp, result), which can be statically allocated
to registers by modern C compilers. The dispatch method of instructions that we have adopted is the
indirect threaded codingPiumarta and Riccardi (1998), a table-based mapping from an opcode to the
jump address. In total, the size of a virtual machine is approximately 100 lines in C source code, which
contains no function calls to external libraries.
The first argument Instruction is a reference to a loaded bytecode, and the second argument
Context is a reference to a runtime information that is required to parse an input. The parsing context
includes an input string and a VM stack to be operated by parsing instructions. The stack is allocated with
a given size by the user at each parser instantiation time. The default size is set to 2K, which corresponds
to more than 500 recursive nonterminal calls.

5 EXPERIMENTAL RESULTS
This section describes the memory consumption and parsing performance of MiniNez.
5.1 Experimental Setup
We assume that main parser applications on embedded systems are data parsing and input validations. To
obtain practical insights on such applications, we prepare 6 distinct grammars (CSV, LOG, XML, JSON,
Email, and UTF8), where the former four grammars are intended for data parsing and the latter two are
for input validations. Data sets that we set up are collected:
• CSV – open data distributed from usgs.gov.
• LOG – syslog files randomly collected from MacOS X.
• XML – synthetic and scalable XML files that are provided by XMarkSchmidt et al. (2002) benchmark project.
• JSON – open data formatted in GeoJSON, distributed from usgs.gov.
• Email – EDRM Enron email data sets
10/15

int run(Instruction *code , Context *ctx) {
Instruction *pc;
long pos;
long *sp;
int r;
/* result */
void *jump_table[]
= {&&I_char, &&I_iffail ... };
I_char:
if (pc->arg != *ctx->inputs[pos++]) {
--pos;
r = 1;
}
goto *(jump_table[(pc++)->op]);
I_iffail:
if (!r) {
goto *(jump_table[(pc+=pc->arg)->op]);
}
goto *(jump_table[(pc++)->op]);
...
return r;
}

Figure 11. The C Virtual Machine Function (Excerpted)
• UTF8 – Japanese Wikipedia articles that is provided by Wikipedia.
It is important to note that PEGs’s backtracking causes an potential exponential parsing time in worst
cases. However, it is a known fact that such exponential cases rarely happen in practice. We have selected
grammars that involves no exponential parsing behaviors as reported in Kuramitsu (2015b).
MiniNez is written in a portable C and compiled by GCC4.4 on a Linux operating system. To compare,
we set up two C generated parsers by LegPiumarta (2015) and our Nez-C parsing toolKuramitsu (2015b).
These generated parsers are implemented with a plain recursive decent parsing. Note that C generated
parser were executed with a standard stack size of Linux operating system (8MB) in order not to consume
C stack by recursion.
Tested computing environments cover the following popular architectures:
• Raspberry Pi 2 Model B, with 900MHz quad-core ARM Cortex-A7, 1GB RAM, running on Linux
• Edison, with 500MHz dual-core Intel Atom, 1GB RAM, running on Linux
5.2 Memory Consumption
To begin with, we examine the memory consumption of MiniNez. Table 5 shows the size of compiled
code in each grammar. The column labeled ”Rules” indicates for the size of production rules in the
grammar. The column labeled ”Plain” indicates no optimized code, while the column ”Reduced” indicates
fully deployed code reduction described in Section 4.2.
Figure 12 shows the effects of downsizing by comparing the size of compiled code in proportion to
the ”plain” results. The data point labeled ”non-opt” indicates no optimization, while other data points
indicates each optimizations. The data points labeled inline, flow, peephole, lex, and unary,
respectively, indicate the deployment of cost-based inlining (in Section 4.2.2), static flow analysis (in
Section 4.2.3), peephole specialization, lexical specialization and unary specialization (in Section 4.1).
The graphed optimization effects are cumulative from left to light. That is, the data point labeled flow
includes inlining and flow. We confirm that lexical and unary specialization are two best effective
for code reduction.
11/15

Table 5. Size of compiled code
Grammar
CSV
LOG
JSON
XML
Email
UTF8

Rules
4
11
16
21
5
2

Plain code[byte]
198
1458
2288
2048
1146
1626

Reduced code[byte]
84
350
368
366
66
38

100.0%	
  
90.0%	
  
80.0%	
  
70.0%	
  
60.0%	
  
50.0%	
  
40.0%	
  
30.0%	
  
20.0%	
  
10.0%	
  
0.0%	
  
plain	
  

inlining	
  

CSV	
  

LOG	
  

ﬂow	
  
JSON	
  

peephole	
  
XML	
  

lex	
  
Email	
  

unary	
  
UTF8	
  

Figure 12. Downsizing effects of each optimization

We will turn to the runtime memory consumption of MiniNez. Since MiniNez is based on a recursive
decent parsing, the stack consumption in nonterminal calls is a major factor. Table 6 shows the VM stack
consumption of MiniNez. The column labeled ”file” indicates the input size of tested file, and the ”used
stack” indicates the maximum consumption of VM stack during parsing. We confirm that the VM stack of
at most 320 bytes can parse even the large files. Note that the necessary stack size depends on grammars,
not the size of inputs.
Table 7 shows a comparison of the binary size of MiniNez and C parsers that is generated by Leg
and Nez. MiniNez includes the size of bytecode to compare each grammar. We confirm that MiniNez is
approximately 20KB smaller than each of generated parsers. Since MiniNez can switch syntax by only
loading bytecode, MiniNez achieves a very small footprint in parsing tasks.
5.3 Performance Evaluation
Finally, we will examine the parsing performance. Table 8 shows the CPU time required for each type of
analysis, giving the average times measured across 5 runs. We also show the throughput in mega-bytes/sec.
Table 6. Stack consumption of MiniNez
Grammar
CSV
LOG
JSON
XML
Email
UTF8

File size
1.3MB
3.1MB
6.1MB
5.0MB
144MB
82MB

Used stack [byte]
24
28
128
208
340
12

12/15

Table 7. Binary size of MiniNez, Leg, and Nez-C
Environment

Raspberry Pi 2

Edison

Grammar
CSV
LOG
JSON
XML
Email
UTF8
CSV
LOG
JSON
XML
Email
UTF8

MiniNez [KB]
9.0
9.3
9.3
9.3
9.0
8.9
10.0
10.3
10.3
10.3
10.0
10.0

Leg[KB]
18.7
24.0
32.0
32.6
24.6
18.3
24.6
33.9
37.6
40.9
29.3
22.4

Nez-C[KB]
21.4
28.3
34.6
37.5
30.5
24.6
25.1
34.2
35.4
36.7
31.2
26.5

Table 8. Throughputs in byte per sec [MiB/s]
Environment
Raspberry Pi 2

Edison

Parser
MiniNez
Nez
leg
MiniNez
Nez
leg

CSV
6.18
5.28
3.90
6.07
5.14
3.71

LOG
4.82
3.45
3.70
4.11
3.72
3.60

JSON
2.99
2.73
2.86
2.42
2.02
2.37

XML
5.88
4.02
3.46
5.71
3.68
3.39

Email
1.68
1.34
1.55
0.95
0.81
0.89

UTF8
6.11
5.88
3.74
3.81
3.26
3.43

MiniNez has throughput 4.2[MB/s] on the average, while Leg parsers have 3.1[MB/s] and Nez-C parsers
have 3.4[MB/s] against the same inputs. This result suggests that MiniNez has practical and competitive
performance, compared to generated parser.

6 RELATED WORK
Parsing and syntactic analysis is ubiquitous and an integral part of text processing. Since the development
of Lex/Yacc, the parser generator has increasingly adopted as a standard approach to formal grammar
engineering. In contexts of data parsing, binpacPang et al. (2006) and XMLScreamerKostoulas et al.
(2006) notably extend Yacc to produce efficient protocol parsers and XML parsers, respectively. However,
Yacc and its extended tools do not guarantee its availability on resource-restricted embedded systems,
while they produce a portable parser code. To our knowledge, the parser generation that is specialized for
embedded systems has been unexplored, and then is an important open problem to be addressed.
PEGsFord (2004) 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
PappyFord (2002), RatsGrimm (2006), MouseRedziejowski (2007), Leg/PegPiumarta (2015), PEGjsMajda
(2015), LPegIerusalimschy (2009), WaxeyeHill (2014) 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
LuaIerusalimschy (2009); Ierusalimschy et al. (2007). As with MiniNez, LPeg has adopted a virtual
parsing machine Medeiros and Ierusalimschy (2008) 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.

13/15

7 CONCLUSION
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.
The applications of PEGs on embedded systems would provide several opportunities for protocol
filtering and schematic data validations. Future work that we will investigate includes a declarative extraction of structured data from parsed results, enabling an alternative standard tool to regular expressions.
Linear parsing guarantee is not visited in this paper, an efficient packrat parsing in restricted-memory
environments is still an open challenge. The prototype implementation of the MiniNez is available online
at http://github.com/nez-peg/nezvm1.

ACKNOWLEDGMENT
The authors thank the IPSJ/SIGPRO members for their feedback and discussions.

REFERENCES
Ford, B. (2002). Packrat parsing:: Simple, powerful, lazy, linear time, functional pearl. In Proceedings of
the Seventh ACM SIGPLAN International Conference on Functional Programming, ICFP ’02, pages
36–47, New York, NY, USA. ACM.
Ford, B. (2004). Parsing expression grammars: A recognition-based syntactic foundation. In Proceedings
of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’04,
pages 111–122, New York, NY, USA. ACM.
Grimm, R. (2006). Better extensibility through modular syntax. In Proceedings of the 2006 ACM
SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’06, pages 38–51,
New York, NY, USA. ACM.
Hazel, P. (2015). Pcre - perl compatible regular expressions. http://www.pcre.org.
Hill, O. (2014). Language development with waxeye. http://waxeye.org/manual.html.
Ierusalimschy, R. (2009). A text pattern-matching tool based on parsing expression grammars. Softw.
Pract. Exper., 39(3):221–258.
Ierusalimschy, R., de Figueiredo, L. H., and Celes, W. (2007). The evolution of lua. In Proceedings of the
Third ACM SIGPLAN Conference on History of Programming Languages, HOPL III, pages 2–1–2–26,
New York, NY, USA. ACM.
Kostoulas, M. G., Matsa, M., Mendelsohn, N., Perkins, E., Heifets, A., and Mercaldi, M. (2006). Xml
screamer: An integrated approach to high performance xml parsing, validation and deserialization. In
Proceedings of the 15th International Conference on World Wide Web, WWW ’06, pages 93–102, New
York, NY, USA. ACM.
Kuramitsu, K. (2015a). Nez - declrative parsing expression grammar toolkit. http://peg-nez.github.io/.
Kuramitsu, K. (2015b). Packrat parsing with elastic sliding window. Journal of Infomration Processing,
23(4):505–512.
Kuramitsu, K. (2015c). Toward trans-parsing with nez. In Informal Proceedings of JSSST Workshop on
Programming and Programming Languages.
Majda, D. (2015). Peg.js - parser generator for javascript.
Medeiros, S. and Ierusalimschy, R. (2008). A parsing machine for pegs. In Proceedings of the 2008
Symposium on Dynamic Languages, DLS ’08, pages 2:1–2:12, New York, NY, USA. ACM.
Pang, R., Paxson, V., Sommer, R., and Peterson, L. (2006). Binpac: A yacc for writing application
protocol parsers. In Proceedings of the 6th ACM SIGCOMM Conference on Internet Measurement,
IMC ’06, pages 289–300, New York, NY, USA. ACM.
Piumarta,
I. (2015).
peg/leg —- recursive-descent parser generators for c.
http://piumarta.com/software/peg/.
14/15

Piumarta, I. and Riccardi, F. (1998). Optimizing direct threaded code by selective inlining. In Proceedings
of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, PLDI
’98, pages 291–300, New York, NY, USA. ACM.
Redziejowski, R. R. (2007). Parsing expression grammar as a primitive recursive-descent parser with
backtracking. Fundam. Inf., 79(3-4):513–524.
Schmidt, A., Waas, F., Kersten, M., Carey, M. J., Manolescu, I., and Busse, R. (2002). Xmark: A
benchmark for xml data management. In Proceedings of the 28th International Conference on Very
Large Data Bases, VLDB ’02, pages 974–985. VLDB Endowment.
Shida, S., Ide, M., and Kuramitsu, K. (2013). Downsizing konoha scripting langauge intended for
mindstorms nxt. IPSJ Transaction on Programming (in Japanese), 6(4):1–9.

15/15

