Implementation of C Library for Constructing Packrat Parser with Statically Allocated Memory Implementation of C Library for Constructing Packrat Parser with Statically Allocated Memory

Access this Article

Search this Article

Author(s)

    • Sugimoto Yuta
    • Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba
    • Maeda Atusi
    • Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba

Abstract

<p>Packrat parsing is a recursive descent parsing method with backtracking and memoization. Parsers based on this method require no separate lexical analyzers, and backtracking enables those parsers to handle a wide range of complex syntactic constructs. Memoization is used to prevent exponential growth of running time, resulting in linear time complexity at th cost of linear space consumption. In this study, we propose CPEG - a library that can be used to write parsers using Packrat parsing in C language. This library enables programmers to describe syntactic rules in an internal domain-specific language (DSL) which, unlike parser combinators, does not require runtime data structures to represent syntax. Syntax rules are just expressed by plain C macros. The runtime routine does not dynamically allocate memory regions for memoization. Instead, statically allocated arrays are used as memoization cache tables. Therefore, programmers can implement practical parsers with CPEG, which does not depend on any specific memory management features, requiring fixed-sized memory (except for input string). To enhance usability, a translator to CPEG from an external DSL is provided, as well as a tuning mechanism to control memoization parameters. Parsing time compared to other systems when parsing JavaScript Object Notation and Java source files are given. The experimental results indicate that the performance of CPEG is competitive with other libraries.</p>

Journal

  • Journal of Information Processing

    Journal of Information Processing 26(0), 335-344, 2018

    Information Processing Society of Japan

Codes

  • NII Article ID (NAID)
    130006507554
  • NII NACSIS-CAT ID (NCID)
    AA00700121
  • Text Lang
    ENG
  • Article Type
    journal article
  • Data Source
    IR  J-STAGE 
Page Top