Open main menu

Comparison of parser generators

  (Redirected from List of parser generators)

Regular languagesEdit

Regular languages are a category of languages (sometimes termed Chomsky Type 3) which can be matched by a state machine (more specifically, by a deterministic finite automaton or a nondeterministic finite automaton) constructed from a regular expression. In particular, a regular language can match constructs like "A follows B", "Either A or B", "A, followed by zero or more instances of B", but cannot match constructs which require consistency between non-adjacent elements, such as "some instances of A followed by the same number of instances of B", and also cannot express the concept of recursive "nesting" ("every A is eventually followed by a matching B"). A classic example of a problem which a regular grammar cannot handle is the question of whether a given string contains correctly-nested parentheses. (This is typically handled by a Chomsky Type 2 grammar, also termed a context-free grammar.)

Name Lexer algorithm Output languages Grammar, code Development platform License
Alex DFA Haskell Mixed All Free, BSD
AnnoFlex DFA Java Mixed Java virtual machine Free, BSD
AustenX DFA Java Separate All Free, BSD
Booze-tools DFA state machine is runtime-generated or saved as JSON Mixed Python Free, public domain
C# Flex DFA C# Mixed .NET CLR Free, GNU GPL
C# Lex DFA C# Mixed .NET CLR ?
CookCC DFA Java Mixed Java virtual machine Free, Apache 2.0
DFAlex DFA no code generation required Java Java Free, Apache 2.0
Dolphin DFA C++ Separate All Proprietary
Flex DFA table driven C, C++ Mixed All Free, BSD
gelex DFA Eiffel Mixed Eiffel Free, MIT
golex DFA Go Mixed Go Free, BSD-style
gplex DFA C# Mixed .NET CLR Free, BSD-like
JFlex DFA Java Mixed Java virtual machine Free, BSD
JLex DFA Java Mixed Java virtual machine Free, BSD-like
lex DFA C Mixed POSIX Partial, proprietary, CDDL
lexertl DFA C++ ? All Free, GNU LGPL
LRSTAR DFA C++ Separate Windows Free, BSD
Quex DFA direct code C, C++ Mixed All Free, GNU LGPL
Ragel DFA C, C++, assembly Mixed All Free, GNU GPL, MIT[1][1]
RE/flex DFA direct code, DFA table driven, and NFA regex libraries C++ Mixed All Free, BSD
re2c DFA direct code C Mixed All Free, public domain

Deterministic context-free languagesEdit

Context-free languages are a category of languages (sometimes termed Chomsky Type 2) which can be matched by a sequence of replacement rules, each of which essentially maps each non-terminal element to a sequence of terminal elements and/or other nonterminal elements. Grammars of this type can match anything that can be matched by a regular grammar, and furthermore, can handle the concept of recursive "nesting" ("every A is eventually followed by a matching B"), such as the question of whether a given string contains correctly-nested parentheses. The rules of Context-free grammars are purely local, however, and therefore cannot handle questions that require non-local analysis such as "Does a declaration exist for every variable that is used in a function?". To do so technically would require a more sophisticated grammar, like a Chomsky Type 1 grammar, also termed a context-sensitive grammar. However, parser generators for context-free grammars often support the ability for user-written code to introduce limited amounts of context-sensitivity. (For example, upon encountering a variable declaration, user-written code could save the name and type of the variable into an external data structure, so that these could be checked against later variable references detected by the parser.)

The deterministic context-free languages are a proper subset of the context-free languages which can be efficiently parsed by deterministic pushdown automata.

Name Parsing algorithm Input grammar notation Output languages Grammar, code Lexer Development platform IDE License
ANTLR4 ALL(*)[2] EBNF C#, Java, Python, JavaScript, C++, Swift, Go, PHP Mixed generated Java virtual machine Yes Free, BSD
ANTLR3 LL(*) EBNF ActionScript, Ada95, C, C++, C#, Java, JavaScript, Objective-C, Perl, Python, Ruby Mixed generated Java virtual machine Yes Free, BSD
APG Recursive descent, backtracking ABNF C, C++, JavaScript, Java Separate none All No Free, GNU GPL
AXE Recursive descent AXE/C++ C++17, C++11 Mixed none Any with C++17 or C++11 standard compiler No Free, Boost
Beaver LALR(1) EBNF Java Mixed external Java virtual machine No Free, BSD
Belr Recursive descent ABNF C++17, C++11 Separate included POSIX No Partial, GNU GPL, proprietary
Bison LALR(1), LR(1), IELR(1), GLR Yacc C, C++, Java Mixed external All No Free, GNU GPL with exception
Bison++[note 1] LALR(1) ? C++ Mixed external POSIX No Free, GNU GPL
Bisonc++ LALR(1) ? C++ Mixed external POSIX No Free, GNU GPL
Booze-tools LALR(1) or LR(1) canonical or minimal BNF with macros in place of EBNF State machine can be runtime-generated or saved as JSON Mixed, separable included Python No Free, public domain
BtYacc Backtracking Bottom-up ? C++ Mixed external All No Free, public domain
byacc LALR(1) Yacc C Mixed external All No Free, public domain
BYACC/J LALR(1) Yacc C, Java Mixed external All No Free, public domain
CL-Yacc LALR(1) Lisp Common Lisp Mixed external All No Free, MIT
Coco/R LL(1) EBNF C, C++, C#, F#, Java, Ada, Object Pascal, Delphi, Modula-2, Oberon, Ruby, Swift, Unicon, Visual Basic .NET Mixed generated Java virtual machine, .NET Framework, Windows, POSIX (depends on output language) No Free, GNU GPL
CookCC LALR(1) Java annotations Java Mixed generated Java virtual machine No Free, Apache 2.0
CppCC LL(k) ? C++ Mixed generated POSIX No Free, GNU GPL
CSP LR(1) ? C++ Separate generated POSIX No Free, Apache 2.0
CUP LALR(1) ? Java Mixed external Java virtual machine No Free, BSD-like
Dragon LR(1), LALR(1) ? C++, Java Separate generated All No Free, GNU GPL
eli LALR(1) ? C Mixed generated POSIX No Free, GNU GPL, GNU LGPL
Tunnel Grammar Studio Recursive descent, backtracking ABNF C++ Separate generated Windows Yes Proprietary
Essence LR(?) ? Scheme 48 Mixed external All No Free, BSD
Eto.Parse LL(k) BNF, EBNF or C# N/A (state machine is runtime generated) Separate internal .NET Framework No Free, MIT
eyapp LALR(1) ? Perl Mixed external or generated All No Free, Artistic
Frown LALR(k) ? Haskell 98 Mixed external All No Free, GNU GPL
geyacc LALR(1) ? Eiffel Mixed external All No Free, MIT
GOLD LALR(1) BNF x86 assembly language, ANSI C, C#, D, Java, Pascal, Object Pascal, Python, Visual Basic 6, Visual Basic .NET, Visual C++ Separate generated Windows Yes Free, zlib modified
GPPG LALR(1) Yacc C# Separate external Windows Yes Free, BSD
Grammatica LL(k) BNF dialect C#, Java Separate generated Java virtual machine No Free, BSD
HiLexed LL(*) EBNF or Java Java Separate internal Java virtual machine No Free, GNU LGPL
Hime Parser Generator LALR(1), GLR BNF dialect C#, Java, Rust Separate generated .NET Framework, Java virtual machine No Free, GNU LGPL
Hyacc LR(1), LALR(1), LR(0) Yacc C Mixed external All No Free, GNU GPL
Irony LALR(1) C# N/A (state machine is runtime generated) Separate internal .NET Framework Yes Free, MIT
iyacc LALR(1) Yacc Icon Mixed external All No Free, GNU LGPL
jacc LALR(1) ? Java Mixed external Java virtual machine No Free, BSD
JavaCC LL(k) EBNF Java, C++, JavaScript (via GWT compiler)[3] Mixed generated Java virtual machine Yes Free, BSD
jay LALR(1) Yacc C#, Java Mixed none Java virtual machine No Free, BSD
JFLAP LL(1), LALR(1) ? Java ? ? Java virtual machine Yes ?
JetPAG LL(k) ? C++ Mixed generated All No Free, GNU GPL
JS/CC LALR(1) EBNF JavaScript, JScript, ECMAScript Mixed internal All Yes Free, BSD
KDevelop-PG-Qt LL(1), backtracking, shunting-yard ? C++ Mixed generated or external All, KDE No Free, GNU LGPL
Kelbt Backtracking LALR(1) ? C++ Mixed generated POSIX No Free, GNU GPL
kmyacc LALR(1) ? C, Java, Perl, JavaScript Mixed external All No Free, GNU GPL
Lapg LALR(1) ? C, C++, C#, Java, JavaScript Mixed generated Java virtual machine No Free, GNU GPL
Lark LALR(1), Earley, CYK EBNF Python (no generation, library) Separate none All No Free, MIT
Lemon LALR(1) ? C Mixed external All No Free, public domain
LEPL Recursive descent Python Python (no generation, library) Separate none All No Free, MPL, GNU LGPL
Lime LALR(1) ? PHP Mixed external All No Free, GNU GPL
LISA LR(?), LL(?), LALR(?), SLR(?) ? Java Mixed generated Java virtual machine Yes Free, public domain
LLgen LL(1) ? C Mixed external POSIX No Free, BSD
LLnextgen LL(1) ? C Mixed external All No Free, GNU GPL
LLLPG LL(k) + syntactic and semantic predicates ANTLR-like C# Mixed generated (?) .NET Framework, Mono Visual Studio Free, GNU LGPL
LPG Backtracking LALR(k) ? Java Mixed generated Java virtual machine No Free, EPL
LRSTAR LALR(1), LR(1), LR(*) EBNF, Yacc-like C++ Separate generated Windows Visual Studio Free, BSD
Menhir LR(1) ? OCaml Mixed generated All No Free, QPL
ML-Yacc LALR(1) ? ML Mixed external All No ?
Monkey LR(1) ? Java Separate generated Java virtual machine No Free, GNU GPL
Msta LALR(k), LR(k) YACC, EBNF C, C++ Mixed external or generated POSIX, Cygwin No Free, GNU GPL
MTP (More Than Parsing) LL(1) ? Java Separate generated Java virtual machine No Free, GNU GPL
MyParser LL(*) Markdown C++11 Separate internal Any with standard C++11 compiler No Free, MIT
NLT GLR C#/BNF-like C# Mixed mixed .NET Framework No Free, MIT
ocamlyacc LALR(1) ? OCaml Mixed external All No Free, QPL
olex LL(1) ? C++ Mixed generated All No Free, GNU GPL
parglare Scannerless LALR(1)/SLR(1)/GLR BNF-like, Python N/A (state machine is runtime generated) Mixed none All No Free, MIT
Parsec LL, backtracking Haskell Haskell Mixed none All No Free, BSD
Parse::Yapp LALR(1) ? Perl Mixed external All No Free, GNU GPL
Parser Objects LL(k) ? Java Mixed ? Java virtual machine No Free, zlib
PCCTS LL ? C, C++ ? ? All No ?
PLY LALR(1) BNF Python Mixed generated All No Free, MIT
PlyPlus LALR(1) EBNF Python Separate generated All No Free, MIT
PRECC LL(k) ? C Separate generated DOS, POSIX No Free, GNU GPL
QLALR LALR(1) ? C++ Mixed external All No Free, GNU GPL
RPATK Recursive descent, backtracking BNF C (no generation, library) Separate none All No Free, GNU GPL
SableCC LALR(1) ? C, C++, C#, Java, OCaml, Python Separate generated All No Free, GNU LGPL
SLK LL(k) LR(k) LALR(k) EBNF C, C++, C#, Java, JavaScript Separate external All No SLK[4]
SP (Simple Parser) Recursive descent Python Python Separate generated All No Free, GNU LGPL
Spirit Recursive descent ? C++ Mixed internal All No Free, Boost
Sprache LL, backtracking C# interpreted Mixed internal .NET Framework No Free, MIT
Styx LALR(1) ? C, C++ Separate generated All No Free, GNU LGPL
Sweet Parser LALR(1) ? C++ Separate generated Windows No Free, zlib
Tap LL(1) ? C++ Mixed generated All No Free, GNU GPL
TextTransformer LL(k) ? C++ Mixed generated Windows Yes Proprietary
TinyPG LL(1) ? C#, Visual Basic ? ? Windows Yes Partial, CPOL 1.0
Toy Parser Generator Recursive descent ? Python Mixed generated All No Free, GNU LGPL
TP Yacc LALR(1) ? Turbo Pascal Mixed external All Yes Free, GNU GPL
UltraGram LALR(1), LR(1), GLR BNF C++, Java, C#, Visual Basic .NET Separate external Windows Yes Free, public domain
UniCC LALR(1) EBNF C, C++, Python, JavaScript, JSON, XML Mixed generated POSIX No Free, BSD
UrchinCC LL(1) ? Java ? generated Java virtual machine No ?
Whale LR(?), some conjunctive stuff, see Whale Calf ? C++ Mixed external All No Proprietary
wisent LALR(1) ? C++, Java Mixed external All No Free, GNU GPL
Yacc AT&T/Sun LALR(1) Yacc C Mixed external POSIX No Free, CPL & CDDL
Yacc++ LR(1), LALR(1) Yacc C++, C# Mixed generated or external All No Proprietary
Yapps LL(1) ? Python Mixed generated All No Free, MIT
yecc LALR(1) ? Erlang Separate generated All No Free, Apache 2.0
Visual BNF LR(1), LALR(1) ? C# Separate generated .NET Framework Yes Proprietary
YooParse LR(1), LALR(1) ? C++ Mixed external All No Free, MIT
Parse LR(1) BNF in C++ types ? ? none C++11 standard compiler No Free, MIT
GGLL LL(1) Graph Java Mixed generated Windows Yes Free, MIT
Product Parsing algorithm Input grammar notation Output languages Grammar, code Lexer Development platform IDE License

Parsing expression grammars, deterministic boolean grammarsEdit

This table compares parser generators with parsing expression grammars, deterministic boolean grammars.

Name Parsing algorithm Output languages Grammar, code Development platform License
Arpeggio PEG parser interpreter, Packrat Python (no generation, interpreted) Mixed All Free, MIT
AustenX Packrat (modified) Java Separate All Free, BSD
Aurochs Packrat C, OCaml, Java Mixed All Free, GNU GPL
BNFlite Recursive descent C++ Mixed All Free, MIT
Canopy Packrat Java, JavaScript, Python, Ruby Separate All Free, GNU GPL
CL-peg Packrat Common Lisp Mixed All Free, MIT
Drat! Packrat D Mixed All Free, GNU GPL
Frisby Packrat Haskell Mixed All Free, BSD
grammar::peg Packrat Tcl Mixed All Free, BSD
Grako Packrat + Cut + Left Recursion Python, C++ (beta) Separate All Free, BSD
IronMeta Packrat C# Mixed Windows Free, BSD
Katahdin Packrat (modified), mutating interpreter C# Mixed All Free, public domain
Laja 2-phase scannerless top-down backtracking + runtime support Java Separate All Free, GNU GPL
lars::Parser Packrat (supporting left-recursion and grammar ambiguity) C++ Identical All Free, BSD
LPeg Parsing machine Lua Mixed All Free, MIT
lug Parsing machine C++17 Mixed All Free, MIT
Mouse Recursive descent Java Separate Java virtual machine Free, Apache 2.0
Narwhal Packrat C Mixed POSIX, Windows Free, BSD
Nearley Earley JavaScript Mixed All Free, MIT
Nemerle.Peg Recursive descent + Pratt Nemerle Separate All Free, BSD
neotoma Packrat Erlang Separate All Free, MIT
NPEG Recursive descent C# Mixed All Free, MIT
OMeta Packrat (modified, partial memoization) JavaScript, Squeak, Python Mixed All Free, MIT
PackCC Packrat (modified) C Mixed All Free, MIT
Packrat Packrat Scheme Mixed All Free, MIT
Pappy Packrat Haskell Mixed All Free, BSD
parboiled Recursive descent Java, Scala Mixed Java virtual machine Free, Apache 2.0
Lambda PEG Recursive descent Java Mixed Java virtual machine Free, Apache 2.0
parsepp Recursive descent C++ Mixed All Free, public domain
Parsnip Packrat C++ Mixed Windows Free, GNU GPL
peg Recursive descent C Mixed All Free, MIT
PEG.js Packrat (partial memoization) JavaScript Mixed All Free, MIT
peg-parser PEG parser interpreter Dylan Separate All ?
Pegasus Recursive descent, Packrat (selectively) C# Mixed Windows Free, MIT
pegc Recursive descent C Mixed All Free, public domain
pest Recursive descent Rust Separate All Free, MPL
PetitParser Packrat Smalltalk, Java, Dart Mixed All Free, MIT
PEGTL Recursive descent C++11 Mixed All Free, MIT
Parser Grammar Engine (PGE) Hybrid recursive descent / operator precedence[5] Parrot bytecode Mixed Parrot virtual machine Free, Artistic 2.0
PyPy rlib Packrat Python Mixed All Free, MIT
pyPEG PEG parser interpreter, Packrat Python Mixed All Free, GNU GPL
Rats! Packrat Java Mixed Java virtual machine Free, GNU LGPL
Spirit2 Recursive descent C++ Mixed All Free, Boost
textX PEG parser interpreter, Packrat Python (no generation, interpreted) Separate All Free, MIT
Treetop Recursive descent Ruby Mixed All Free, MIT
Yard Recursive descent C++ Mixed All Free, MIT or public domain
Waxeye Parsing machine C, Java, JavaScript, Python, Racket, Ruby Separate All Free, MIT
PHP PEG PEG Parser? PHP Mixed All Free, BSD

General context-free, conjunctive, or boolean languagesEdit

This table compares parser generator languages with a general context-free grammar, a conjunctive grammar, or a boolean grammar.

Name Parsing algorithm Input grammar notation Output languages Grammar, code Lexer Development platform IDE License
ACCENT Earley Yacc variant C Mixed external All No Free, GNU GPL
APaGeD GLR, LALR(1), LL(k) ? D Mixed generated All No Free, Artistic
Bison LALR(1), LR(1), IELR(1), GLR Yacc C, C++, Java, XML Mixed, except XML external All No Free, GNU GPL
DMS Software Reengineering Toolkit GLR ? Parlanse Mixed generated Windows No Proprietary
DParser Scannerless GLR ? C Mixed scannerless POSIX No Free, BSD
Dypgen Runtime-extensible GLR ? OCaml Mixed generated All No Free, CeCILL-B
E3 Earley ? OCaml Mixed external, or scannerless All No ?
Elkhound GLR ? C++, OCaml Mixed external All No Free, BSD
eu.h8me.Parsing GLR ? N/A (state machine is runtime generated) Separate external .NET Framework No Free, BSD
GDK LALR(1), GLR ? C, Lex, Haskell, HTML, Java, Object Pascal, Yacc Mixed generated POSIX No Free, MIT
Happy LALR, GLR ? Haskell Mixed external All No Free, BSD
Hime Parser Generator GLR ? C#, Java, Rust Separate generated .NET Framework, Java virtual machine No Free, GNU LGPL
IronText Library LALR(1), GLR C# C# Mixed generated or external .NET Framework No Free, Apache 2.0
Jison LALR(1), LR(0), SLR(1) Yacc JavaScript, C#, PHP Mixed generated All No Free, MIT
Syntax LALR(1), LR(0), SLR(1) CLR(1) LL(1) JSON/Yacc JavaScript, Python, PHP, Ruby, C#, Rust, Java Mixed generated All No Free, MIT
Laja Scannerless, two phase Laja Java Separate scannerless All No Free, GNU GPL
ModelCC Earley Annotated class model Java Generated generated All No Free, BSD
parglare Scannerless LR/GLR BNF-like Python interpreted, automata run-time generated Mixed scannerless All No Free, MIT
P1 Combinators BNF-like OCaml Mixed external, or scannerless All No ?
P3 Earley–combinators BNF-like OCaml Mixed external, or scannerless All No ?
P4 Earley–combinators, infinitary CFGs BNF-like OCaml Mixed external, or scannerless All No ?
Scannerless Boolean Parser Scannerless GLR (Boolean grammars) ? Haskell, Java Separate scannerless Java virtual machine No Free, BSD
SDF/SGLR Scannerless GLR SDF C, Java Separate scannerless All Yes Free, BSD
SmaCC GLR(1), LALR(1), LR(1) ? Smalltalk Mixed internal All Yes Free, MIT
SPARK Earley ? Python Mixed external All No Free, MIT
Tom GLR ? C Generated none All No Free, "No licensing or copyright restrictions"
UltraGram LALR, LR, GLR ? C++, C#, Java, Visual Basic .NET Separate generated Windows Yes Proprietary
Wormhole Pruning, LR, GLR, Scannerless GLR ? C, Python Mixed scannerless Windows No Free, MIT
Whale Calf General tabular, SLL(k), Linear normal form (conjunctive grammars), LR, Binary normal form (Boolean grammars) ? C++ Separate external All No Proprietary
yaep Earley Yacc-like C Mixed external All No Free, GNU LGPL
Zecc Recursive pattern matching Zecc/Zacc Linkable library Mixed Scannerless macOS Yes Proprietary

Context-sensitive grammarsEdit

This table compares parser generators with context-sensitive grammars.

Name Parsing algorithm Input grammar notation Boolean grammar abilities Development platform License
LuZc[6][7] delta chain modular Conjunctive, not complimentary POSIX Proprietary
bnf2xml Recursive descent (is a text filter output is xml) simple BNF[clarification needed] grammar (input matching), output is xml ? Beta, and not a full EBNF parser Free, GNU GPL

See alsoEdit

ReferencesEdit

  1. ^ http://www.colm.net/open-source/ragel/
  2. ^ "Adaptive LL(*) Parsing: The Power of Dynamic Analysis" (PDF). Terence Parr. Retrieved 2016-04-03.
  3. ^ "Building parsers for the web with JavaCC & GWT (Part one)". Chris Ainsley. Retrieved 2014-05-04.
  4. ^ http://www.slkpg2.com/license.txt
  5. ^ "Parrot: Grammar Engine". The Parrot Foundation. 2011. PGE rules provide the full power of recursive descent parsing and operator precedence parsing.
  6. ^ "LuZ: A context sensitive parser". 2016-10-17. Archived from the original on 2016-10-17. Retrieved 2018-10-17.
  7. ^ "LuZc – A conjunctive context-sensitive parser". luzc.zohosites.com. Retrieved 2018-10-17.

NotesEdit

  1. ^ Bison 1.19 fork

External linksEdit