PetitParser Compiler

Logo


Petit Compiler accepts PetitParser as input and produces a Smalltalk class with an equivalent top-down parser. Combinators of PetitParser are analyzed and the fastest parsing strategy is choosen for each of them. The compiled parser is significantly faster.



Performance

Smalltalk

We compare four different Smalltalk parsers. All of them create an identical AST:

  • PetitParser is an implementation of a Smalltalk parser in PetitParser.
  • Compiled PetitParser is a compiled version of the above parser.
  • SmaCC is a parser compiled by SmaCC (see more) from a LALR grammar.
  • Hand-Written is a hand-written parser used by Pharo to compile its code.

Smalltalk-speedup
Speedup compared to PetitParser.
Smalltalk-tpc
Average time per character for each of the parsers.

Other Benchmarks

In general, we measure performance speedup ranging form factor two to ten. In the figure bellow, there is a speedup for the following grammars:

  • Identifier parses list of identifiers
  • Arithmetics parses an aritmetic expressions (with priorities of operators)
  • Smalltalk is PetitParser implementation of Smalltalk grammar.
  • Java is PetitParser implementation of Java grammar.
  • Python is an island gramar that extracts structure of Python programs while utilizing indentation.

Speedup

Installation

Gofer new smalltalkhubUser: 'JanKurs' project: 'PetitParser';
    configurationOf: #PetitCompiler; load.
(Smalltalk at: #ConfigurationOfPetitCompiler) perform: #'loadStable'.

Using PetitCompiler

| petitParser compiledParser |
petitParser := PPSmalltlakParser new.
"compilation might be costly do it only when you change your parser"
compiledParser := parser compile.
compiledParser parse: 'foo ^ 1'.

Visit Smalltalkhub for more information.

Limitations

  • All your code should be functional, i.e. no state should be stored in additional instance variables of PPCompositeParser.
  • If there are other problems, it is probably a bug in implementation. In that case, please contact Jan (this Jan).

Supported Smalltalks

PetitCompiler supports Pharo 5 and Smalltalk/X.

Do not hesitate to contact us, if you want to port into your own Smallatlk.

Publications

2016

  1. Jan Kurš, Jan Vraný, Mohammad Ghafari, Mircea Lungu, and Oscar Nierstrasz. Optimizing Parser Combinators. In Proceedings of International Workshop on Smalltalk Technologies (IWST 2016), p. 1:1—1:13, 2016. DOI PDF 

Last changed by kurs on 29 August 2016