Journal of Robotics, Networking and Artificial Life
Vol. 6(2); September (2019), pp. 123–127
DOI: https://doi.org/10.2991/jrnal.k.190828.011; ISSN 2405-9021; eISSN 2352-6386
https://www.atlantis-press.com/journals/jrnal

Research Article

Implementation of Tamias to Check Production Rules
for Parsing Expression Grammar
Tetsuro Katayama1,*, Toshihiro Miyaji1, Yoshihiro Kita2, Hisaaki Yamaba1, Kentaro Aburada1, Naonobu Okazaki1
Department of Computer Science and Systems Engineering, Faculty of Engineering, University of Miyazaki, 1-1 Gakuen-kibanadai-nishi,Miyazaki 889-2192, Japan2School of Computer Science, Tokyo University of Technology, 1404-1 Katakuramachi, Hachioji City, Tokyo 192-0982, Japan1

ARTICLE INFO
Article History
Received 15 October 2018
Accepted 22 November 2018
Keywords
Syntax analysis
parserparsing expression grammar
packrat parsing

ABSTRACT
Parsing Expression Grammar (PEG) proposed by Ford has the higher expressive ability than traditional Backus–Naur form, but
it also has problems such as prefix capture. “Prefix capture” is a problem of hiding the language to be accepted according to theorder of choice. To support checking syntax files including such mistakes, this paper proposes Tamias: a production rules checker
to support checking the PEG syntax files. Tamias has PEG interpreter which can check production rules of PEG. It can verify thebehavior of production rules and measure the reach rate of choices.

© 2019 The Authors. Published by Atlantis Press SARL.
This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

1. INTRODUCTION
Backus–Naur Form (BNF) can express type-2 grammar (CFG:Context-Free Grammar) in the Chomsky hierarchy. Although
BNF is traditionally used in the syntax definition of programming
languages, it is possible to describe ambiguous grammar (e.g. dangling-else problem). The ambiguous grammar is not allowed programming languages because the compiler would interpret multiplelanguages. Unfortunately, it has been proved that there is no algorithm to judge that the CFG contains ambiguous grammar [1,2].
On the other hand, Parsing Expression Grammar (PEG) introducedby Ford [3] is not ambiguous grammar because it has ordered choiceproperty. However, the ordered choice causes “prefix capture” [4].
“Prefix capture” is a problem of hiding the language to be accepted
according to the order of choice. Checking syntax files that containsuch mistakes usually confirms the behavior of the parser generated by the parser generator. However, in confirming the behaviorof the parser, it is possible to check only the top level non-terminal
symbols, and it is necessary to rebuild the parser for each change inthe syntax files. To support checking the syntax files, this paper proposes Tamias to check the production rules in the PEG syntax files.

2. PARSING EXPRESSION GRAMMAR
AND ITS PARSING TECHNIQUE
Parsing expression grammar is a formal grammar, introduced
by Ford [3]. PEG is deterministic. Therefore, it is suitable for thesyntax definition of the programming languages, and it was found
Corresponding author. Email: kat@cs.miyazaki-u.ac.jp*

that not only the CFG but also a part of the context-sensitive
grammar can be expressed.

2.1. Definition of PEG
A PEG G is defined by the four-tuples:
G = (VN , Σ , R, eS )where
1. VN is a finite set of non-terminal symbols.
2. Σ is a finite set of terminals (Σ ∩ VN = f).
3. R is a finite set of production rules.
4. es is a parsing expression called the start expression.
The production rule is described in the form of “A = e” or “A ← e”
(where A ∈VN, e is a parsing expression). A parsing expression isan instruction for an input string given by users and is described bya non-terminal or a terminal symbol. A parsing expression can useoperators. When the input string s is applied to the parsing expressione, e matches the substring of s and indicates “success” or “failure”. s hasa pointer p representing the reading position. If e indicates success, econsumes the prefix of s (i.e. advances p by the length of the substring).
Also, if e indicates failure, let s applies the next parsing expression.

2.2. Packrat Parsing TechniquePackrat parsing is one of the parsing techniques that can parse
PEG [5]. It is a top-down parsing technique proposed by Ford

T. Katayama et al. / Journal of Robotics, Networking and Artificial Life 6(2) 123–127

124in 2002. Ford solved the problem that the parsing time of PEG
including a backtracking increases exponentially with linear timeby memoization of the parsing result.

2.3. Prefix Capture“Prefix capture” is a problem of hiding the language to be accepted
according to the order of choice. For example, the grammar “A =(‘+’/‘++’)[a–z]” does not accept the language “++i”. The reason isthat parsing “[a–z]” fails after parsing “+” of the language “++i”.
To solve this problem, the order ‘+’ and ‘++’ is reversed. Thus, it isdifficult to understand prefix capture immediately.

3. TAMIAS
Tamias is a production rules checker to support checking the syntax
files for PEG. Tamias has three areas: a text editor area, a list of
non-terminal symbols, and a production rules check area. Tamiasparses the production rules entered in the text editor area and converts them into an Abstract Syntax Tree (AST) as shown in Figure 1.
Tamias has PEG interpreter which can check all choices and any
non-terminal symbols in production rules according to PEG. Also,
Tamias can parse without building a parser. A checking method
using a PEG interpreter can be selected from the production rules
check area. There are two methods of checking the production rules,“production rules verification” and “reach rate measurement”. Bothmethods require one testable symbol and one input string. A testable symbol refers to a non-terminal symbol from which a terminal
symbol can be derived. Tamias recursively searches and extracts
testable symbols from the grammar described in the text editor area.

3.2. Reach Rate Measurement
Reach rate measurement calculates the rate of success of parsing in
the ordered choice of the selected production rule. The reach rate isobtained by assigning two or more check results in one production
rule to the following calculating formula (1):Reach rate [%] =Parsing success choices
All choices

× 100 (1)3.3. PEG Interpreter
Parsing expression grammar interpreter is an interpreter that executes parsing for PEG described in text editor in Tamias. PEG
interpreter requires a testable symbol and an input string. PEG
interpreter shows the output of the parsing expression after parsing.
By selecting testable symbols, PEG interpreter can check not only
top level non-terminal symbols.

4. IMPLEMENTATION OF PEG INTERPRETER
4.1. Data used in the PEG Interpreter•• Production rules:
Production rules are rules obtained from non-terminal symbols that can be derived from testable symbols. One production rule is expressed as a pair of a non-terminal symbol and aparsing expression. The parsing expression is further, as shownin Figure 1, divided into ordered choice and sequence for easy
execution with a PEG interpreter.
•• Input string:

3.1. Production Rules Verification
Production rules verification can confirm whether the input stringis accepted by the production rule. In one verification, production
rules verification requires an expected output in addition to one
testable symbol and one input string. The users can select whether
the specified input string is accepted or rejected. Tamias displays
the comparison result between the expected output and the output
of PEG interpreter. If the expected output and the actual output areequal, “Passed” is displayed. Otherwise, “Failed” is displayed.

Input string has a string and a pointer that expresses a readingposition.
•• Lookup table:
Lookup table stores the reading position of the input string.
The row of the lookup table corresponds to the parsing processing, and the column corresponds to the reading position of theinput string.

4.2. PEG Interpreter Algorithm
We have developed a PEG interpreter based on Packrat parsing technique described in Subsection 2.2 to parse the grammar
written in the text editor area. As a result, production rules can bequickly verified.
The algorithm of the PEG interpreter is shown in Figure 2. It recursively is executed until parsing of the terminal symbol.

5. EXPERIMENT AND DISCUSSION

Figure 1 | AST for production rule “A = B + / & C D / E*”.

We confirm that PEG interpreter can parse correctly by using
grammar representing addition and multiplication and grammar
including prefix capture.

T. Katayama et al. / Journal of Robotics, Networking and Artificial Life 6(2) 123–127

125

Figure 3 | Result of executing production rules verification.

Figure 2 | PEG interpreter algorithm.

5.1. Production Rules Verification
We confirm the production rules verification method by using
grammar representing the addition and multiplication below:
Sum = Product ‘+’ Product/ProductProduct = Value ‘*’ Value/Value
Value = [0–9]

We write the grammar in the text editor area of Tamias and checkthe two languages “1 + 2 * 3” and “*2” in the production rules checkarea. Next, we selected “accept” as the expected output in both languages. The experimental results are shown in Figure 3.
As shown in Figure 3, the check result of the language “1 + 2 * 3”according to the grammar was “Passed”. On the other hand, thecheck result of the language “*2” not conforming to the grammar
was “Failed”. Therefore, the production rules verification can checkthe grammar correctly.

5.2. Reach Rate Measurement
We confirm the reach rate measurement method by using grammar“A = (‘+’/‘++’)[a–z]” including prefix capture. However, sinceTamias does not currently support input of parsing subexpression, we write the following grammar into the text editor areaof Tamias.
A = Op Id
Op = ‘+’/‘++’
Id = [a–z]Figure 4 | Two results of executing reach rate measurement.

Next, we measure the reach rate of “A” using two languages “+i” and“++i”. Finally, we reverse the choices of “Op” and measure the reachrate of “A” using the same languages. The experimental results areshown in Figure 4.

T. Katayama et al. / Journal of Robotics, Networking and Artificial Life 6(2) 123–127

126

As shown in the upper part of Figure 4, the reach rate is not 100%in the grammar including prefix capture. In contrast, as shown in
the lower part of Figure 4, the reach rate is 100% in the grammar
excluding prefix capture. Therefore, from the formula of reach rate
[formula (1)]:Parsing success choices = All choices

The experiment with a grammar representing addition and multiplication showed that Tamias can compare the expected output
by users with actual output by PEG interpreter without building aparser. The experiment with a grammar including prefix capture
showed that Tamias can prove that prefix capture has not occurred
for any input strings by measuring reach rate.

it can be proved that prefix capture has not occurred for all input
strings.

Therefore, Tamias can support checking PEG syntax files. A future
work is to improve Tamias to support parsing subexpression
described by parentheses.

6. RELATED RESEARCH

CONFLICTS OF INTEREST

Honda et al. [6] proposed a PEG debugger to support developmentof PEG. The PEG debugger has functions such as setting breakpoints, executing steps, displaying stack trace, and so on. The PEG
debugger can check the behavior for one input and the occurrenceof prefix capture. However, the PEG debugger cannot prove thatprefix capture has not occurred for any input string.

The authors declare they have no conflicts of interest.

Mori et al. [7] proposed a parser generator that can composite parsers and implemented its prototype. In the traditional method, whenpart of the syntax in PEG was changed, it was necessary to rebuild
the corresponding parser. The proposed method can generate aparser that can deal with the problem of the traditional method.
Tamias solves the problem of rebuilding the parser by implementing a PEG interpreter.

7. CONCLUSION
In this paper, we have proposed Tamias: a production rules checker
to support checking the syntax files for PEG. Tamias has PEG interpreter which can check all choices and any non-terminal symbols
in production rules according to PEG. Tamias can check the production rules and can measure reach rate of choices by using PEG
interpreter. In the production rules verification, Tamias compares
the expected output with the output of the PEG interpreter and displays the result. In the reach rate measurement, Tamias can checkthat the grammar does not contain prefix capture.

REFERENCES
[1]
[2]
[3]

[4]
[5]

[6]
[7]

D.G. Cantor, On the ambiguity problem of Backus systems, J. Assoc.
Comput. Mach. 9 (1962), 477–479.
R.W. Floyd, On ambiguity in phrase structure languages,Commun. ACM 5 (1962), 526–534.
B. Ford, Parsing expression grammars: a recognition-based­syntactic foundation, 31st ACM SIGPLAN-SIGACT symposiumon Principles of programming languages, ACM, Venice, Italy, 39(2004), 111–122.
R.R. Redziejowski, Parsing expression grammar as a primitive
recursive-descent parser with backtracking, Fundam. Inform.
79 (2007), 513–524.
B. Ford, Packrat parsing: simple, powerful, lazy, linear time, functional pearl, Seventh ACM SIGPLAN International Conference
on Functional Programming, ACM, Pittsburgh, PA, USA, 37(2002), 36–47.
S. Honda, K. Kuramitsu, Implementing and evaluating a debugger for supporting development of PEGs. Japan Soc. Softw. Sci.
Technol. 32 (2015), 1–6 (in Japanese).
K. Mori, K. Wakita, Composition of parsers for incremental
Parsing Expression Grammars. Japan Soc. Softw. Sci. Technol.
30 (2013), 641–650 (in Japanese).

Authors Introduction
Tetsuro Katayama
He received the PhD degree inEngineering from Kyushu University,Fukuoka, Japan in 1996. From 1996
to 2000 he has been a Research
Associate at the Graduate School ofInformation Science, Nara Instituteof Science and Technology, Japan.
Since 2000, he has been an Associate
Professor at Faculty of Engineering,Miyazaki University, Japan. He
is currently a Professor with theFaculty of Engineering, University ofMiyazaki, Japan. His research interests include software testingand quality. He is a member of the IPSJ, IEICE, and JSSST.

Toshihiro Miyaji
He received the Bachelor’s degree
in Engineering (Computer Scienceand Systems Engineering) from
University of Miyazaki, Japan in 2018.
He is currently a Master’s student inGraduate School of Engineering at
the University of Miyazaki, Japan.
His research interests include parsing
and testing for formal languages.

T. Katayama et al. / Journal of Robotics, Networking and Artificial Life 6(2) 123–127

Yoshihir Kita

127

Kentaro Aburada
He received a PhD degree in Systems
Engineering from University ofMiyazaki, Japan, in 2011. He is currently an Assistant Professor with theComputer Science, Tokyo Universityof Technology, Japan. His researchinterests software testing and biometric authentication.

He received the B.S., M.S. andPhD degrees in Computer Scienceand System Engineering from theUniversity of Miyazaki, Japan, in2003, 2005 and 2009, respectively. Heis currently an Associate Professor
with the Faculty of Engineering,
University of Miyazaki, Japan. His
research interests include computer network and security. He is amember of IPSJ and IEICE.

Hisaaki Yamaba

Naonobu Okazaki

He received the B.S. and M.S. degrees
in Chemical Engineering from Tokyo
Institute of Technology, Japan, in1988 and 1990, respectively, and thePh.D. degree in Systems Engineeringfrom University of Miyazaki, Japan,in 2011. He is currently an AssistantProfessor with the Faculty ofEngineering, University of Miyazaki,
Japan. His research interests include
network security and user authentication. He is a member of SICE and SCEJ.

He received his B.S., M.S., andPhD degrees in Electrical andCommunication Engineering fromTohoku University, Japan, in 1986,1988 and 1992, respectively. He
joined the Information Technology
Research and Development Center,
Mitsubishi Electric Corporation in1991. He is currently a Professor
with the Faculty of Engineering,
University of Miyazaki since 2002.
His research interests include mobilenetwork and network security. He is a member of IPSJ, IEICEand IEEE.