Comparison of parser generators

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Template:Short description Template:More citations needed

This is a list of notable lexer generators and parser generators for various language classes.

Regular languages

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 Template:D-A All Free, BSD
AnnoFlex DFA Java Template:D-A Java virtual machine Free, BSD
Astir DFA table driven, with branching C++ Template:D-P All Free, MIT
AustenX DFA Java Template:D-P All Free, BSD
C# Flex DFA C# Template:D-A .NET CLR Free, GNU GPL
C# Lex DFA C# Template:D-A .NET CLR ?
CookCC DFA Java Template:D-A Java virtual machine Free, Apache 2.0
DFA DFA compressed matrix C, C++ Template:D-P Windows, Visual Studio BSD
Dolphin DFA C++ Template:D-P All Template:Proprietary
Flex DFA table driven C, C++ Template:D-A All Free, BSD
gelex DFA Eiffel Template:D-A Eiffel Free, MIT
golex DFA Go Template:D-A Go Free, BSD-style
gplex DFA C# Template:D-A .NET CLR Free, BSD-like
JFlex DFA Java Template:D-A Java virtual machine Free, BSD
JLex DFA Java Template:D-A Java virtual machine Free, BSD-like
lex DFA C Template:D-A POSIX Partial, proprietary, CDDL
lexertl DFA C++ ? All Free, GNU LGPL
Quex DFA direct code C, C++ Template:D-A All Free, GNU LGPL
Ragel DFA Go, C, C++, Java, assembly Template:D-A All Free, GNU GPL, MIT[1][2]
RE/flex DFA direct code, DFA table driven, and NFA regex libraries C++ Template:D-A All Free, BSD
re2c DFA direct code C, C++, Go, Rust Template:D-A All Free, public domain

Deterministic context-free languages

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 Adaptive LL(*)[3] EBNF C#, Java, Python, JavaScript, C++, Swift, Go, PHP Template:D-P generated Java virtual machine Yes Free, BSD
ANTLR3 LL(*) EBNF ActionScript, Ada95, C, C++, C#, Java, JavaScript, Objective-C, Perl, Python, Ruby Template:D-A generated Java virtual machine Yes Free, BSD
APGScript error: No such module "Unsubst". Recursive descent, backtracking ABNF Python, JavaScript, C, Java Template:D-P none All No Free, BSD
Beaver[4][5] LALR(1) EBNF Java Template:D-A external Java virtual machine No Free, BSD
Bison LALR(1), LR(1), IELR(1), GLR Yacc C, C++, D, Java Template:D-A external All No Free, GNU GPL with exception
BtYacc Backtracking Bottom-up ? C++ Template:D-A external All No Free, public domain
byacc LALR(1) Yacc C Template:D-A external All No Free, public domain
CL-Yacc[6][7] LALR(1) Lisp Common Lisp Template:D-A external All No Free, MIT
Coco/R LL(1) + semantic predicates EBNF C, C++, C#, F#, Java, Ada, Object Pascal, Delphi, Modula-2, Oberon, Ruby, Swift, Unicon, Visual Basic .NET Template:D-A generated Java virtual machine, .NET framework, Windows, POSIX (depends on output language) No Free, GNU GPL
CppCC[8][9] LL(k) ? C++ Template:D-A generated POSIX No Free, GNU GPL
CUP[10][11] LALR(1) ? Java Template:D-A external Java virtual machine No Free, BSD-like
Eli[12][13] LALR(1) ? C Template:D-A generated POSIX No Free, GNU GPL, GNU LGPL
Essence[14] LR(?) ? Scheme 48 Template:D-A external All No Free, BSD
eyapp[15] LALR(1) ? Perl Template:D-A external or generated All No Free, Artistic
GOLD[16] LALR(1) BNF x86 assembly language, ANSI C, C#, D, Java, Pascal, Object Pascal, Python, Visual Basic 6, Visual Basic .NET, Visual C++ Template:D-P generated Windows Yes Free, zlib modified
Hime Parser Generator[17] LALR(1), GLR BNF dialect C#, Java, Rust Template:D-P generated .NET framework, Java virtual machine No Free, GNU LGPL
Hyacc[18] LR(1), LALR(1), LR(0) Yacc C Template:D-A external All No Free, GNU GPL
JavaCC[19][20] LL(k) EBNF Java, C++, JavaScript (via GWT compiler)[21] Template:D-A generated Java virtual machine Yes Free, BSD
JFLAP LL(1), LALR(1) ? Java ? ? Java virtual machine Yes ?
JetPAG LL(k) ? C++ Template:D-A generated All No Free, GNU GPL
JS/CC LALR(1) EBNF JavaScript, JScript, ECMAScript Template:D-A internal All Yes Free, BSD
KDevelop-PG-Qt LL(1), backtracking, shunting-yard ? C++ Template:D-A generated or external All, KDE No Free, GNU LGPL
Kelbt Backtracking LALR(1) ? C++ Template:D-A generated POSIX No Free, GNU GPL
kmyacc LALR(1) ? C, Java, Perl, JavaScript Template:D-A external All No Free, GNU GPL
Lapg LALR(1) ? C, C++, C#, Java, JavaScript Template:D-A generated Java virtual machine No Free, GNU GPL
Lark LALR(1), Earley (SPPF) EBNF Python, JavaScript Template:D-A generated All Yes Free, MIT
Lemon LALR(1) BNF dialect[22] C Template:D-A external All No Free, public domain
Lezer[23][24][25] LR(1), GLR EBNF dialect JavaScript Template:D-P generated Node.js, JavaScript No Free, MIT
Lime LALR(1) ? PHP Template:D-A external All No Free, GNU GPL
LISA LR(?), LL(?), LALR(?), SLR(?) ? Java Template:D-A generated Java virtual machine Yes Free, public domain
LLgen LL(1) ? C Template:D-A external POSIX No Free, BSD
LLnextgen LL(1) ? C Template:D-A external All No Free, GNU GPL
LLLPG LL(k) + syntactic and semantic predicates ANTLR-like C# Template:D-A generated (?) .NET framework, Mono Visual Studio Free, GNU LGPL
LPG Backtracking LALR(k) ? Java Template:D-A generated Java virtual machine No Free, EPL
LRSTAR[26] LALR(1), LALR(*) YACC, ANTLR, EBNF C++ Template:D-P generated Windows Visual Studio Free, BSD
Menhir LR(1) ? OCaml Template:D-A generated All No Free, QPL
ML-Yacc LALR(1) ? ML Template:D-A external All No ?
Monkey LR(1) ? Java Template:D-P generated Java virtual machine No Free, GNU GPL
Msta LALR(k), LR(k) YACC, EBNF C, C++ Template:D-A external or generated POSIX, Cygwin No Free, GNU GPL
MTP (More Than Parsing) LL(1) ? Java Template:D-P generated Java virtual machine No Free, GNU GPL
MyParser LL(*) Markdown C++11 Template:D-P internal Any with standard C++11 compiler No Free, MIT
NLT GLR C#/BNF-like C# Template:D-A mixed .NET framework No Free, MIT
ocamlyacc LALR(1) ? OCaml Template:D-A external All No Free, QPL
olex LL(1) ? C++ Template:D-A generated All No Free, GNU GPL
Parsec LL, backtracking Haskell Haskell Template:D-A none All No Free, BSD
yapp[15] LALR(1) ? Perl Template:D-A external All No Free, GNU GPL
Parser Objects LL(k) ? Java Template:D-A ? Java virtual machine No Free, zlib
PCCTS LL ? C, C++ ? ? All No ?
PLY LALR(1) BNF Python Template:D-A generated All No Free, MIT
PlyPlus LALR(1) EBNF Python Template:D-P generated All No Free, MIT
PRECC LL(k) ? C Template:D-P generated DOS, POSIX No Free, GNU GPL
QLALR LALR(1) ? C++ Template:D-A external All No Free, GNU GPL
racc[27] LALR(1) BNF-like, yacc-like[28] Ruby Template:D-A ? Template:D-A No LGPL
REX[29] LL(1) sLL(k) LR(k) LALR(k) GLR PEG DFA Context-dependent lexing EBNF C++, C#, Java, JavaScript, Go, Haxe, Python, Scala, Typescript, XQuery, XSLT Template:D-P generated All No Free, Apache License 2.0
SableCC LALR(1) ? C, C++, C#, Java, OCaml, Python Template:D-P generated Java virtual machine No Free, GNU LGPL
SLK[30] LL(k) LR(k) LALR(k) EBNF C, C++, C#, Java, JavaScript Template:D-P external All No SLK[31]
SLY[32] LALR(1) BNF Python Template:D-A generated All No Free, BSD
SP (Simple Parser) Recursive descent Python Python Template:D-P generated All No Free, GNU LGPL
Spirit Recursive descent ? C++ Template:D-A internal All No Free, Boost
Styx LALR(1) ? C, C++ Template:D-P generated All No Free, GNU LGPL
Sweet Parser LALR(1) ? C++ Template:D-P generated Windows No Free, zlib
Tap LL(1) ? C++ Template:D-A generated All No Free, GNU GPL
TextTransformer LL(k) ? C++ Template:D-A generated Windows Yes Template:Proprietary
TinyPG LL(1) ? C#, Visual Basic ? ? Windows Yes Partial, CPOL 1.0
Toy Parser Generator Recursive descent ? Python Template:D-A generated All No Free, GNU LGPL
TP Yacc LALR(1) ? Turbo Pascal Template:D-A external All Yes Free, GNU GPL
Tree-Sitter[33] LR(1), GLR JavaScript DSL, JSON C, bindings (Rust, WebAssembly, JavaScript, Python, many other) Template:D-P generated + external All Template:D-A Free, MIT
Tunnel Grammar Studio Tunnel Parsing ABNF C++ Template:D-P generated Windows Yes Template:Proprietary
UltraGram LALR(1), LR(1), GLR BNF C++, Java, C#, Visual Basic .NET Template:D-P external Windows Yes Free, public domain
UniCC LALR(1) EBNF C, C++, Python, JavaScript, JSON, XML Template:D-A generated POSIX No Free, BSD
UrchinCC LL(1) ? Java ? generated Java virtual machine No ?
Yacc AT&T/Sun LALR(1) Yacc C Template:D-A external POSIX No Free, CPL & CDDL
Yacc++ LR(1), LALR(1) Yacc C++, C# Template:D-A generated or external All No Template:Proprietary
Yapps LL(1) ? Python Template:D-A generated All No Free, MIT
yecc LALR(1) ? Erlang Template:D-P generated All No Free, Apache 2.0
Visual BNF LR(1), LALR(1) ? C# Template:D-P generated .NET framework Yes Template:Proprietary
YooParse LR(1), LALR(1) ? C++ Template:D-A external All No Free, MIT
Parse[34] LR(1) BNF in C++ types ? ? none C++11 standard compiler No Free, MIT
GGLL LL(1) Graph Java Template:D-A 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 grammars

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

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

General context-free, conjunctive, or Boolean languages

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 Template:D-A external All No Free, GNU GPL
APaGeD GLR, LALR(1), LL(k) ? D Template:D-A generated All No Free, Artistic
Bison LALR(1), LR(1), IELR(1), GLR Yacc C, C++, D,[39] Java, XML Template:D-A, except XML external All No Free, GNU GPL
DMS Software Reengineering Toolkit GLR ? Parlanse Template:D-A generated Windows No Template:Proprietary
DParser Scannerless GLR ? C Template:D-A scannerless POSIX No Free, BSD
Dypgen Runtime-extensible GLR ? OCaml Template:D-A generated All No Free, CeCILL-B
E3 Earley ? OCaml Template:D-A external, or scannerless All No ?
Elkhound GLR ? C++, OCaml Template:D-A external All No Free, BSD
GDK LALR(1), GLR ? C, Lex, Haskell, HTML, Java, Object Pascal, Yacc Template:D-A generated POSIX No Free, MIT
Happy LALR, GLR ? Haskell Template:D-A external All No Free, BSD
Hime Parser Generator GLR ? C#, Java, Rust Template:D-P generated .NET framework, Java virtual machine No Free, GNU LGPL
IronText Library LALR(1), GLR C# C# Template:D-A generated or external .NET framework No Free, Apache 2.0
Jison LALR(1), LR(0), SLR(1) Yacc JavaScript, C#, PHP Template:D-A generated All No Free, MIT
Syntax LALR(1), LR(0), SLR(1) CLR(1) LL(1) JSON/Yacc JavaScript, Python, PHP, Ruby, C++, C#, Rust, Java Template:D-A generated All No Free, MIT
Laja Scannerless, two phase Laja Java Template:D-P scannerless All No Free, GNU GPL
ModelCC Earley Annotated class model Java Generated generated All No Free, BSD
P3 Earley–combinators BNF-like OCaml Template:D-A external, or scannerless All No ?
P4 Earley–combinators, infinitary CFGs BNF-like OCaml Template:D-A external, or scannerless All No ?
Scannerless Boolean Parser Scannerless GLR (Boolean grammars) ? Haskell, Java Template:D-P scannerless Java virtual machine No Free, BSD
SDF/SGLR Scannerless GLR SDF C, Java Template:D-P scannerless All Yes Free, BSD
SmaCC GLR(1), LALR(1), LR(1) ? Smalltalk Template:D-A internal All Yes Free, MIT
SPARK Earley ? Python Template:D-A 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 Template:D-P generated Windows Yes Template:Proprietary
Wormhole Pruning, LR, GLR, Scannerless GLR ? C, Python Template:D-A scannerless Windows No Free, MIT
Whale Calf General tabular, SLL(k), Linear normal form (conjunctive grammars), LR, Binary normal form (Boolean grammars) ? C++ Template:D-P external All No Template:Proprietary
yaep Earley Yacc-like C Template:D-A external All No Free, GNU LGPL

Context-sensitive grammars

This table compares parser generators with context-sensitive grammars.

Name Parsing algorithm Input grammar notation Boolean grammar abilities Development platform License
bnf2xml Recursive descent (is a text filter output is xml) simple BNFTemplate:Clarify grammar (input matching), output is xml ? Beta, and not a full EBNF parser Free, GNU GPL

See also

Notes


References

Template:Reflist

External links

Template:Parsers

  1. ↑ Script error: No such module "citation/CS1".
  2. ↑ http://www.colm.net/open-source/ragel/ Script error: No such module "Unsubst".
  3. ↑ Script error: No such module "citation/CS1".
  4. ↑ Script error: No such module "Citation/CS1".
  5. ↑ Script error: No such module "citation/CS1".
  6. ↑ Script error: No such module "Citation/CS1".
  7. ↑ Script error: No such module "citation/CS1".
  8. ↑ Script error: No such module "Citation/CS1".
  9. ↑ Script error: No such module "citation/CS1".
  10. ↑ Script error: No such module "citation/CS1".
  11. ↑ Script error: No such module "citation/CS1".
  12. ↑ Script error: No such module "Citation/CS1".
  13. ↑ Script error: No such module "Citation/CS1".
  14. ↑ Script error: No such module "Citation/CS1".
  15. ↑ a b Script error: No such module "Citation/CS1".
  16. ↑ Script error: No such module "citation/CS1".
  17. ↑ Script error: No such module "citation/CS1".
  18. ↑ Script error: No such module "Citation/CS1".
  19. ↑ Script error: No such module "citation/CS1".
  20. ↑ Script error: No such module "citation/CS1".
  21. ↑ Script error: No such module "citation/CS1".
  22. ↑ Script error: No such module "citation/CS1".
  23. ↑ Script error: No such module "citation/CS1".
  24. ↑ Script error: No such module "citation/CS1".
  25. ↑ Script error: No such module "citation/CS1".
  26. ↑ Script error: No such module "citation/CS1".
  27. ↑ Script error: No such module "citation/CS1".
  28. ↑ Script error: No such module "citation/CS1".
  29. ↑ Script error: No such module "citation/CS1".
  30. ↑ Script error: No such module "citation/CS1".
  31. ↑ http://www.slkpg.com/license.txt Template:Bare URL plain text
  32. ↑ Script error: No such module "citation/CS1".
  33. ↑ Script error: No such module "citation/CS1".
  34. ↑ Script error: No such module "citation/CS1".
  35. ↑ Script error: No such module "citation/CS1".
  36. ↑ Maintained fork of PEG.js
  37. ↑ Script error: No such module "citation/CS1".
  38. ↑ Script error: No such module "citation/CS1".
  39. ↑ Script error: No such module "citation/CS1".
Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=Comparison_of_parser_generators&oldid=2470477"