Comparison of parser generators: Difference between revisions
StereoFolic (talk | contribs) I couldn't find any evidence that REx is notable enough for inclusion in this list. Note that many other entries currently on this page also don't meet this bar and should be deleted. Their present inclusion is a defect of this page, not a reason to include more. |
|||
(75 intermediate revisions by 41 users not shown) | |||
Line 1: | Line 1: | ||
{{short description|None}} |
{{short description|None}} |
||
{{More citations needed|date=July 2023}} |
|||
{{confusing|date=March 2014}}<!--See 'Talk:Comparison_of_parser_generators#"Confusing"'--> |
|||
This is a list of notable [[lexer generator]]s and [[parser generator]]s for various language classes. |
This is a list of notable [[lexer generator]]s and [[parser generator]]s for various language classes. |
||
== Regular languages == |
== Regular languages == |
||
[[Regular language]]s are a category of languages (sometimes termed [[Chomsky hierarchy|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 |
[[Regular language]]s are a category of languages (sometimes termed [[Chomsky hierarchy|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]].) |
||
{| class="wikitable sortable" style="text-align: center; font-size: 85%; width: auto;" |
{| class="wikitable sortable" style="text-align: center; font-size: 85%; width: auto;" |
||
Line 11: | Line 11: | ||
! Name !!Lexer algorithm !! [[Programming language|Output languages]] !! Grammar, code !! Development platform !! [[Software license|License]] |
! Name !!Lexer algorithm !! [[Programming language|Output languages]] !! Grammar, code !! Development platform !! [[Software license|License]] |
||
|- |
|- |
||
| Alex || [[Deterministic finite automaton|DFA]] || [[ |
| Alex || [[Deterministic finite automaton|DFA]] || [[Haskell]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| AnnoFlex || [[Deterministic finite automaton|DFA]] || [[Java (programming language)|Java]] || {{D-A|Mixed}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[BSD licenses|BSD]] |
| AnnoFlex || [[Deterministic finite automaton|DFA]] || [[Java (programming language)|Java]] || {{D-A|Mixed}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[BSD licenses|BSD]] |
||
Line 22: | Line 22: | ||
|- |
|- |
||
| C# Lex || [[Deterministic finite automaton|DFA]] || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || {{Some|[[Common Language Runtime|.NET CLR]]}} || ? |
| C# Lex || [[Deterministic finite automaton|DFA]] || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || {{Some|[[Common Language Runtime|.NET CLR]]}} || ? |
||
⚫ | |||
⚫ | |||
|- |
|- |
||
| CookCC || [[Deterministic finite automaton|DFA]] || [[Java (programming language)|Java]] || {{D-A|Mixed}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[Apache License|Apache]] 2.0 |
| CookCC || [[Deterministic finite automaton|DFA]] || [[Java (programming language)|Java]] || {{D-A|Mixed}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[Apache License|Apache]] 2.0 |
||
Line 49: | Line 47: | ||
| Quex || [[Deterministic finite automaton|DFA]] direct code || [[C (programming language)|C]], [[C++]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
| Quex || [[Deterministic finite automaton|DFA]] direct code || [[C (programming language)|C]], [[C++]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
||
|- |
|- |
||
| [[Ragel]] || [[Deterministic finite automaton|DFA]] || [[Go (programming language)|Go]], [[C (programming language)|C]], [[C++]], [[Assembly language|assembly]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[GNU General Public License|GNU GPL]], [[MIT License|MIT]]<ref>{{Cite web|url=http://www.colm.net/open-source/ragel/|title = Ragel State Machine Compiler}}</ref><ref>http://www.colm.net/open-source/ragel/ {{verify source |date=November 2020 |reason=This ref was deleted Special:Diff/987467678 by a bug in VisualEditor and later restored by a bot from the original cite located at Special:Permalink/987467450 cite #1 - verify the cite is accurate and delete this template. [[User:GreenC bot/Job 18]]}}</ref> |
| [[Ragel]] || [[Deterministic finite automaton|DFA]] || [[Go (programming language)|Go]], [[C (programming language)|C]], [[C++]], [[Java (programming language)|Java]], [[Assembly language|assembly]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[GNU General Public License|GNU GPL]], [[MIT License|MIT]]<ref>{{Cite web|url=http://www.colm.net/open-source/ragel/|title = Ragel State Machine Compiler}}</ref><ref>http://www.colm.net/open-source/ragel/ {{verify source |date=November 2020 |reason=This ref was deleted Special:Diff/987467678 by a bug in VisualEditor and later restored by a bot from the original cite located at Special:Permalink/987467450 cite #1 - verify the cite is accurate and delete this template. [[User:GreenC bot/Job 18]]}}</ref> |
||
|- |
|- |
||
| [[RE/flex]] || [[Deterministic finite automaton|DFA]] direct code, DFA table driven, and [[Nondeterministic finite automaton|NFA]] regex libraries || [[C++]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
| [[RE/flex]] || [[Deterministic finite automaton|DFA]] direct code, DFA table driven, and [[Nondeterministic finite automaton|NFA]] regex libraries || [[C++]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| [[re2c]] || [[Deterministic finite automaton|DFA]] direct code || [[C (programming language)|C]], [[Go (programming language)|Go]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[public domain]] |
| [[re2c]] || [[Deterministic finite automaton|DFA]] direct code || [[C (programming language)|C]], [[C++]], [[Go (programming language)|Go]], [[Rust (programming language)|Rust]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[public domain]] |
||
|} |
|} |
||
== Deterministic context-free languages == |
== Deterministic context-free languages == |
||
[[Context-free language]]s are a category of languages (sometimes termed [[Chomsky hierarchy|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 |
[[Context-free language]]s are a category of languages (sometimes termed [[Chomsky hierarchy|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.) |
||
⚫ | |||
⚫ | |||
{| class="wikitable sortable" style="text-align: center; font-size: 85%; width: auto;" |
{| class="wikitable sortable" style="text-align: center; font-size: 85%; width: auto;" |
||
|- |
|- |
||
! Name !! [[Parsing]] algorithm !! Input grammar notation !! [[Programming language|Output languages]] !! Grammar, code !! [[Lexical analyzer|Lexer]] !! Development platform !! [[Integrated development environment|IDE]] !! [[Software license|License]] |
! Name !! [[Parsing]] algorithm !! Input grammar notation !! [[Programming language|Output languages]] !! Grammar, code !! [[Lexical analyzer|Lexer]] !! Development platform !! [[Integrated development environment|IDE]] !! [[Software license|License]] |
||
⚫ | |||
| AGL || [[GLR parser|GLR]] || [[Extended Backus–Naur form|EBNF]] || [[Java (programming language)|Java]], [[JavaScript]], (other Kotlin targets) || {{D-P|Separate}} || none || Any Kotlin target platform || {{No}} || {{Free}}, [[Apache License|Apache]] 2.0 |
|||
|- |
|- |
||
| [[ANTLR]]4 || Adaptive LL(*)<ref>{{Cite web |url=http://www.antlr.org/papers/allstar-techreport.pdf |title=Adaptive LL(*) Parsing: The Power of Dynamic Analysis |access-date=2016-04-03 |publisher=Terence Parr}}</ref> || [[Extended Backus–Naur form|EBNF]] || [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[Python (programming language)|Python]], [[JavaScript]], [[C++]], [[Swift (programming language)|Swift]], [[Go (programming language)|Go]], [[PHP]] || {{D-P|Separate}} || generated || {{Some|[[Java virtual machine]]}} || {{Yes}} || {{Free}}, [[BSD licenses|BSD]] |
| [[ANTLR]]4 || Adaptive LL(*)<ref>{{Cite web |url=http://www.antlr.org/papers/allstar-techreport.pdf |title=Adaptive LL(*) Parsing: The Power of Dynamic Analysis |access-date=2016-04-03 |publisher=Terence Parr}}</ref> || [[Extended Backus–Naur form|EBNF]] || [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[Python (programming language)|Python]], [[JavaScript]], [[C++]], [[Swift (programming language)|Swift]], [[Go (programming language)|Go]], [[PHP]] || {{D-P|Separate}} || generated || {{Some|[[Java virtual machine]]}} || {{Yes}} || {{Free}}, [[BSD licenses|BSD]] |
||
Line 71: | Line 66: | ||
| [[ANTLR]]3 || [[LL parser|LL]](*) || [[Extended Backus–Naur form|EBNF]] || [[ActionScript]], [[Ada (programming language)|Ada95]], [[C (programming language)|C]], [[C++]], [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[JavaScript]], [[Objective-C]], [[Perl]], [[Python (programming language)|Python]], [[Ruby (programming language)|Ruby]] || {{D-A|Mixed}} || generated || {{Some|[[Java virtual machine]]}} || {{Yes}} || {{Free}}, [[BSD licenses|BSD]] |
| [[ANTLR]]3 || [[LL parser|LL]](*) || [[Extended Backus–Naur form|EBNF]] || [[ActionScript]], [[Ada (programming language)|Ada95]], [[C (programming language)|C]], [[C++]], [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[JavaScript]], [[Objective-C]], [[Perl]], [[Python (programming language)|Python]], [[Ruby (programming language)|Ruby]] || {{D-A|Mixed}} || generated || {{Some|[[Java virtual machine]]}} || {{Yes}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| APG || [[Recursive descent]], [[backtracking]] || [[ABNF]] || [[ |
| APG<ref>{{Cite web |title=Survey on Various Syntax Analyzer Tools |url=https://www.ijraset.com/research-paper/various-syntax-analyzer-tools |access-date=2023-09-16 |website=www.ijraset.com |language=en}}</ref>|| [[Recursive descent]], [[backtracking]] || [[ABNF]] || [[Python (programming language)|Python]], [[JavaScript]], [[C (programming language)|C]], [[Java (programming language)|Java]] || {{D-P|Separate}} || none || {{Yes|All}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
||
⚫ | |||
| Astir || [[LL parser|LL]](k), [[LL parser|LL]](finite), [[LL parser|LL]](*) || Astir hierarchical grammar || [[C++]] || {{D-P|Only grammar (actioned)}} || generated || {{Yes|All}} || {{Yes|[[Visual Studio Code]]}} || {{Free}}, [[MIT License|MIT]] |
|||
|- |
|- |
||
| Beaver<ref>{{Cite journal |last1=Boyland |first1=John |last2=Spiewak |first2=Daniel |date=2010-09-17 |title=Tool Paper: ScalaBison Recursive Ascent-Descent Parser Generator |journal=Electronic Notes in Theoretical Computer Science |series=Proceedings of the Ninth Workshop on Language Descriptions Tools and Applications (LDTA 2009) |volume=253 |issue=7 |pages=65–74 |doi=10.1016/j.entcs.2010.08.032 |issn=1571-0661|doi-access=free }}</ref><ref>{{Cite web |title=Beaver - a LALR Parser Generator |url=https://beaver.sourceforge.net/ |access-date=2023-09-16 |website=beaver.sourceforge.net}}</ref>|| [[LALR parser|LALR]](1) || [[Extended Backus–Naur form|EBNF]]|| [[Java (programming language)|Java]]|| {{D-A|Mixed}} || external || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
|||
| AXE || [[Recursive descent]] || AXE/C++ || [[C++17]], [[C++11]] || {{D-A|Mixed}} || none || {{Some|Any with [[C++17]] or [[C++11]] standard compiler}} || {{No}} || {{Free}}, [[Boost Software License|Boost]] |
|||
|- |
|||
| Beaver || [[LALR parser|LALR]](1) || [[Extended Backus–Naur form|EBNF]] || [[Java (programming language)|Java]] || {{D-A|Mixed}} || external || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
|||
|- |
|||
| Belr || [[Recursive descent]] || [[ABNF]] || [[C++17]], [[C++11]] || {{D-P|Separate}} || included || {{Some|[[POSIX]]}} || {{No}} || {{Partial}}, [[GNU General Public License|GNU GPL]], [[Proprietary software|proprietary]] |
|||
|- |
|- |
||
| [[GNU Bison|Bison]] || [[LALR parser|LALR]](1), [[Canonical LR parser|LR]](1), [[IELR parser|IELR]](1), [[GLR parser|GLR]] || [[Yacc]] || [[C (programming language)|C]], [[C++]], [[Java (programming language)|Java]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] with exception |
| [[GNU Bison|Bison]] || [[LALR parser|LALR]](1), [[Canonical LR parser|LR]](1), [[IELR parser|IELR]](1), [[GLR parser|GLR]] || [[Yacc]] || [[C (programming language)|C]], [[C++]], [[Java (programming language)|Java]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] with exception |
||
|- |
|||
| Bison++<ref group="note">Bison 1.19 fork</ref> || [[LALR parser|LALR]](1) || ? || [[C++]] || {{D-A|Mixed}} || external || {{Some|[[POSIX]]}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
|||
|- |
|||
| Bisonc++ || [[LALR parser|LALR]](1) || ? || [[C++]] || {{D-A|Mixed}} || external || {{Some|[[POSIX]]}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
|||
|- |
|- |
||
| [[BtYacc]] || [[Backtracking]] [[Bottom-up parsing|Bottom-up]] || ? || [[C++]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[public domain]] |
| [[BtYacc]] || [[Backtracking]] [[Bottom-up parsing|Bottom-up]] || ? || [[C++]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[public domain]] |
||
Line 91: | Line 76: | ||
| [[Berkeley Yacc|byacc]] || [[LALR parser|LALR]](1) || [[Yacc]] || [[C (programming language)|C]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[public domain]] |
| [[Berkeley Yacc|byacc]] || [[LALR parser|LALR]](1) || [[Yacc]] || [[C (programming language)|C]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[public domain]] |
||
|- |
|- |
||
| CL-Yacc<ref>{{Cite journal |last1=Newton |first1=Jim E. |last2=Demaille |first2=Akim |last3=Verna |first3=Didier |date=2016-05-09 |title=Type-Checking of Heterogeneous Sequences in Common Lisp |url=https://www.lrde.epita.fr/dload/papers/newton.16.rte.report.pdf |journal=Proceedings of the 9th European Lisp Symposium on European Lisp Symposium |series=ELS2016 |location=Kraków, Poland |publisher=European Lisp Scientific Activities Association |pages=13–20 |isbn=978-2-9557474-0-7}}</ref><ref>{{Cite web |title=CL-Yacc — a LALR(1) parser generator for Common Lisp |url=https://www.irif.fr/~jch/software/cl-yacc/ |access-date=2023-09-16 |website=www.irif.fr}}</ref>|| [[LALR parser|LALR]](1) || [[Lisp (programming language)|Lisp]]|| [[Common Lisp]]|| {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
|||
⚫ | |||
|- |
|- |
||
⚫ | | [[Coco/R]] || [[LL parser|LL]](1) + semantic predicates || [[Extended Backus–Naur form|EBNF]] || [[C (programming language)|C]], [[C++]], [[C Sharp (programming language)|C#]], [[F Sharp (programming language)|F#]], [[Java (programming language)|Java]], [[Ada (programming language)|Ada]], [[Object Pascal]], [[Delphi (software)|Delphi]], [[Modula-2]], [[Oberon (programming language)|Oberon]], [[Ruby (programming language)|Ruby]], [[Swift (programming language)|Swift]], [[Unicon (programming language)|Unicon]], [[Visual Basic .NET]] || {{D-A|Mixed}} || generated || {{Some|[[Java virtual machine]], [[.NET]] framework, [[Microsoft Windows|Windows]], [[POSIX]] (depends on output language)}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
| Carburetta || [[LALR parser|LALR]](1) || BNF Dialect || [[C (programming language)|C]], [[C++]] || {{D-A|Mixed}} || external or generated || {{Yes|All}} || {{No}} || {{Free}}, [[Apache License|Apache]] 2.0 |
|||
|- |
|- |
||
| CppCC<ref>{{Cite journal |last1=Hosseinpour |first1=Sahereh |last2=Alavi Milani |first2=Mir Mohammad Reza |last3=Pehlivan |first3=Hüseyin |date=July 2018 |title=A Step-by-Step Solution Methodology for Mathematical Expressions |journal=Symmetry |language=en |volume=10 |issue=7 |pages=285 |doi=10.3390/sym10070285 |bibcode=2018Symm...10..285H |issn=2073-8994 |doi-access=free }}</ref><ref>{{Cite web |title=CppCC's Home Page |url=https://cppcc.sourceforge.net/ |access-date=2023-09-16 |website=cppcc.sourceforge.net}}</ref>|| [[LL parser|LL]](k) || ? || [[C++]]|| {{D-A|Mixed}} || generated || {{Some|[[POSIX]]}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
|||
| CL-Yacc || [[LALR parser|LALR]](1) || [[Lisp (programming language)|Lisp]] || [[Common Lisp]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
|||
|- |
|- |
||
| CUP<ref>{{Cite web |title=Java Cup |url=https://pages.cs.wisc.edu/~fischer/cs536.s06/course.hold/html/NOTES/4a.JAVA-CUP.html |access-date=2023-09-16 |website=pages.cs.wisc.edu}}</ref><ref>{{Cite web |title=CUP |url=http://www2.cs.tum.edu/projects/cup/docs.php |access-date=2023-09-16 |website=www2.cs.tum.edu}}</ref>|| [[LALR parser|LALR]](1) || ? || [[Java (programming language)|Java]]|| {{D-A|Mixed}} || external || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[BSD licenses|BSD]]-like |
|||
⚫ | | [[Coco/R]] || [[LL parser|LL]](1) || [[Extended Backus–Naur form|EBNF]] || [[C (programming language)|C]], [[C++]], [[C Sharp (programming language)|C#]], [[F Sharp (programming language)|F#]], [[Java (programming language)|Java]], [[Ada (programming language)|Ada]], [[Object Pascal]], [[Delphi ( |
||
|- |
|||
| CookCC || [[Canonical LR parser|LALR]](1) || Java annotations || [[Java (programming language)|Java]] || {{D-A|Mixed}} || generated || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[Apache License|Apache]] 2.0 |
|||
|- |
|||
| CppCC || [[LL parser|LL]](k) || ? || [[C++]] || {{D-A|Mixed}} || generated || {{Some|[[POSIX]]}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
|||
|- |
|||
| CSP || [[Canonical LR parser|LR]](1) || ? || [[C++]] || {{D-P|Separate}} || generated || {{Some|[[POSIX]]}} || {{No}} || {{Free}}, [[Apache License|Apache]] 2.0 |
|||
|- |
|||
| CUP || [[LALR parser|LALR]](1) || ? || [[Java (programming language)|Java]] || {{D-A|Mixed}} || external || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[BSD licenses|BSD]]-like |
|||
|- |
|||
| Dragon || [[Canonical LR parser|LR]](1), [[LALR parser|LALR]](1) || ? || [[C++]], [[Java (programming language)|Java]] || {{D-P|Separate}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
|||
|- |
|- |
||
<!-- Other programming languages may be supported. See http://eli-project.sourceforge.net/ --> |
<!-- Other programming languages may be supported. See http://eli-project.sourceforge.net/ --> |
||
| |
| Eli<ref>{{Cite journal |last1=Thiemann |first1=Peter |last2=Neubauer |first2=Matthias |date=2004-12-31 |title=Parameterized LR Parsing |journal=Electronic Notes in Theoretical Computer Science |series=Proceedings of the Fourth Workshop on Language Descriptions, Tools, and Applications (LDTA 2004) |volume=110 |pages=115–132 |doi=10.1016/j.entcs.2004.06.007 |issn=1571-0661|doi-access=free }}</ref><ref>{{Cite journal |last1=Gray |first1=Robert W. |last2=Levi |first2=Steven P. |last3=Heuring |first3=Vincent P. |last4=Sloane |first4=Anthony M. |last5=Waite |first5=William M. |title=Eli: a complete, flexible compiler construction system |journal=Communications of the ACM |date=1992 |language=en |volume=35 |issue=2 |pages=121–130 |doi=10.1145/129630.129637 |s2cid=5121773 |issn=0001-0782|doi-access=free }}</ref> || [[LALR parser|LALR]](1) || ? || [[C (programming language)|C]] || {{D-A|Mixed}} || generated || {{Some|[[POSIX]]}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]], [[GNU Lesser General Public License|GNU LGPL]] |
||
|- |
|- |
||
| Essence || [[LR parser|LR]](?) || ? || [[Scheme 48]] |
| Essence<ref>{{Cite journal |last1=Owens |first1=Scott |last2=Flatt |first2=M. |last3=Shivers |first3=O. |last4=McMullan |first4=Benjamin |date=2004-10-01 |title=Lexer and Parser Generators in Scheme |url=https://www.khoury.northeastern.edu/home/shivers/papers/scmparse.pdf |journal=Scheme 2004: Proceedings of the Fifth Workshop on Scheme and Functional Programming}}</ref>|| [[LR parser|LR]](?) || ? || [[Scheme 48]]|| {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| eyapp || [[Canonical LR parser|LALR]](1) || ? || [[Perl]] |
| eyapp<ref name=":0">{{Cite journal |last1=Areias |first1=Hugo |last2=Simões |first2=Alberto |last3=Henriques |first3=P. |last4=Cruz |first4=Daniela Carneiro da |date=2010-09-01 |title=Parser generation in Perl : an overview and available tools |url=https://core.ac.uk/download/pdf/55615107.pdf |journal=}}</ref>|| [[Canonical LR parser|LALR]](1) || ? || [[Perl]]|| {{D-A|Mixed}} || external or generated || {{Yes|All}} || {{No}} || {{Free}}, [[Artistic License|Artistic]] |
||
|- |
|- |
||
⚫ | | [[GOLD (parser)|GOLD]]<ref>{{Cite web |last=Volkman |first=Victor |date=2007-07-19 |title=Let Your Parser Go for the GOLD |url=https://www.developer.com/java/let-your-parser-go-for-the-gold/ |access-date=2023-11-04 |website=Developer.com |language=en-US}}</ref>|| [[LALR parser|LALR]](1) || BNF || [[x86 assembly language]], [[ANSI C]], [[C Sharp (programming language)|C#]], [[D (programming language)|D]], [[Java (programming language)|Java]], [[Pascal (programming language)|Pascal]], [[Object Pascal]], [[Python (programming language)|Python]], [[Visual Basic]] 6, [[Visual Basic .NET]], [[Visual C++]]|| {{D-P|Separate}} || generated || {{Some|[[Microsoft Windows|Windows]]}} || {{Yes}} || {{Free}}, [[zlib License|zlib]] modified |
||
| Frown || [[LALR parser|LALR]](k) || ? || [[Haskell (programming language)|Haskell 98]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
|||
|- |
|- |
||
⚫ | | Hime Parser Generator<ref>{{Cite web |title=Parsing in C#: All the Tools and Libraries You Can Use (Part 2) - DZone |url=https://dzone.com/articles/parsing-in-c-all-the-tools-and-libraries-you-can-u-1 |access-date=2023-11-04 |website=dzone.com |language=en}}</ref>|| [[LALR parser|LALR]](1), [[GLR parser|GLR]]|| BNF dialect || [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[Rust (programming language)|Rust]]|| {{D-P|Separate}} || generated || {{Some|[[.NET]] framework, [[Java virtual machine]]}} || {{No}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
||
<!-- More parsing algorithms and output formats supported. See http://gdk.sourceforge.net/gdkref.pdf --> |
|||
| geyacc || [[LALR parser|LALR]](1) || ? || [[Eiffel (programming language)|Eiffel]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
|||
|- |
|- |
||
| Hyacc<ref>{{Cite journal |last1=Ortin |first1=Francisco |last2=Quiroga |first2=Jose |last3=Rodriguez-Prieto |first3=Oscar |last4=Garcia |first4=Miguel |date=2022-03-03 |title=An empirical evaluation of Lex/Yacc and ANTLR parser generation tools |journal=PLOS ONE |language=en |volume=17 |issue=3 |pages=e0264326 |doi=10.1371/journal.pone.0264326 |issn=1932-6203 |pmc=8893623 |pmid=35239695 |bibcode=2022PLoSO..1764326O |doi-access=free }}</ref>|| [[Canonical LR parser|LR(1), LALR(1), LR]](0) || [[Yacc]]|| [[C (programming language)|C]]|| {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
|||
⚫ | | [[GOLD (parser)|GOLD]] || [[LALR parser|LALR]](1) || BNF || [[x86 assembly language]], [[ANSI C]], [[C Sharp (programming language)|C#]], [[D (programming language)|D]], [[Java (programming language)|Java]], [[Pascal (programming language)|Pascal]], [[Object Pascal]], [[Python (programming language)|Python]], [[Visual Basic]] 6, [[Visual Basic .NET]], [[Visual C++]] |
||
|- |
|- |
||
⚫ | | [[JavaCC]]<ref>{{Cite web |last=Enseling |first=Oliver |date=2000-12-29 |title=Build your own languages with JavaCC |url=https://www.infoworld.com/article/2076269/build-your-own-languages-with-javacc.html |access-date=2023-11-04 |website=InfoWorld |language=en}}</ref><ref>{{Cite web |title=JavaCC |url=https://javacc.github.io/javacc/ |access-date=2023-11-04 |website=JavaCC |language=en-US}}</ref>|| [[LL parser|LL]](k) || [[Extended Backus–Naur form|EBNF]]|| [[Java (programming language)|Java]], [[C++]], [[JavaScript]] (via [[Google Web Toolkit|GWT]] compiler)<ref>{{Cite web |url=http://consoliii.blogspot.co.uk/2014/04/creating-gwt-compatible-parser-using.html |title=Building parsers for the web with JavaCC & GWT (Part one) |date=14 April 2014 |access-date=2014-05-04 |publisher=Chris Ainsley}}</ref>|| {{D-A|Mixed}} || generated || {{Some|[[Java virtual machine]]}} || {{Yes}} || {{Free}}, [[BSD licenses|BSD]] |
||
| GPPG || [[LALR parser|LALR]](1) || [[Yacc]] || [[C Sharp (programming language)|C#]] || {{D-P|Separate}} || external || {{Some|[[Microsoft Windows|Windows]]}} || {{Yes}} || {{Free}}, [[BSD licenses|BSD]] |
|||
|- |
|||
| [[Grammatica]] || [[LL parser|LL]](k) || BNF dialect || [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]] || {{D-P|Separate}} || generated || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
|||
|- |
|||
| HiLexed || [[LL parser|LL]](*) || EBNF or Java || [[Java (programming language)|Java]] || {{D-P|Separate}} || internal || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
|||
|- |
|||
⚫ | | Hime Parser Generator || [[LALR parser|LALR]](1), [[GLR parser|GLR]] |
||
|- |
|||
| Hyacc || [[Canonical LR parser|LR(1), LALR(1), LR]](0) || [[Yacc]] || [[C (programming language)|C]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
|||
|- |
|||
| iyacc || [[LALR parser|LALR]](1) || [[Yacc]] || [[Icon (programming language)|Icon]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
|||
|- |
|||
| jacc || [[LALR parser|LALR]](1) || ? || [[Java (programming language)|Java]] || {{D-A|Mixed}} || external || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
|||
|- |
|||
⚫ | | [[JavaCC]] || [[LL parser|LL]](k) || [[Extended Backus–Naur form|EBNF]] |
||
|- |
|||
| jay || [[LALR parser|LALR]](1) || [[Yacc]] || [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]] || {{D-A|Mixed}} || none || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
|||
|- |
|- |
||
| [[JFLAP]] || [[LL parser|LL]](1), [[LALR parser|LALR]](1) || ? || [[Java (programming language)|Java]] || ? || ? || {{Some|[[Java virtual machine]]}} || {{Yes}} || ? |
| [[JFLAP]] || [[LL parser|LL]](1), [[LALR parser|LALR]](1) || ? || [[Java (programming language)|Java]] || ? || ? || {{Some|[[Java virtual machine]]}} || {{Yes}} || ? |
||
Line 155: | Line 113: | ||
| Lapg || [[LALR parser|LALR]](1) || ? || [[C (programming language)|C]], [[C++]], [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[JavaScript]] || {{D-A|Mixed}} || generated || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| Lapg || [[LALR parser|LALR]](1) || ? || [[C (programming language)|C]], [[C++]], [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[JavaScript]] || {{D-A|Mixed}} || generated || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| |
| Lark || [[LALR parser|LALR]](1), [[Earley parser|Earley (SPPF)]] || [[Extended Backus–Naur form|EBNF]] || [[Python (programming language)|Python]], [[JavaScript]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{Yes}} || {{Free}}, [[MIT license|MIT]] |
||
⚫ | |||
⚫ | | [[Lemon (parser generator)|Lemon]] || [[LALR parser|LALR]](1) ||BNF dialect<ref>{{Cite web |title=The Lemon Parser Generator |url=https://sqlite.org/src/doc/trunk/doc/lemon.html#syntax |access-date=2023-11-30 |website=sqlite.org}}</ref>|| [[C (programming language)|C]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[public domain]] |
||
⚫ | |||
| Lezer<ref>{{Cite web |url=https://lezer.codemirror.net/ |title=The Lezer Parser System}}</ref><ref>{{Cite news |title=Building a ShopifyQL Code Editor |language=en |work=Shopify |url=https://shopify.engineering/building-a-shopifyql-code-editor |access-date=2023-12-06}}</ref><ref>{{Cite web |date=2022-03-11 |title=Sponsoring the Lezer parser system {{!}} Tines |url=https://www.tines.com/blog/sponsoring-the-lezer-parser-system/ |access-date=2023-12-06 |website=www.tines.com}}</ref>|| [[LR parser|LR]](1), [[GLR parser|GLR]] || EBNF dialect || [[JavaScript]] || {{D-P|Separate}} || generated || [[Node.js]], [[JavaScript]] || {{No}} || {{Free}}, [[MIT License|MIT]] |
|||
|- |
|- |
||
| Lime || [[LALR parser|LALR]](1) || ? || [[PHP]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| Lime || [[LALR parser|LALR]](1) || ? || [[PHP]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
Line 165: | Line 127: | ||
| LLnextgen || [[LL parser|LL]](1) || ? || [[C (programming language)|C]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| LLnextgen || [[LL parser|LL]](1) || ? || [[C (programming language)|C]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| LLLPG || [[LL parser|LL]](k) + [[Syntactic predicate|syntactic]] and semantic predicates || ANTLR-like || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || generated (?) || {{Some|[[.NET |
| LLLPG || [[LL parser|LL]](k) + [[Syntactic predicate|syntactic]] and semantic predicates || ANTLR-like || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || generated (?) || {{Some|[[.NET]] framework, [[Mono (software)|Mono]]}} || {{Yes|[[Microsoft Visual Studio|Visual Studio]]}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
||
|- |
|- |
||
| LPG || [[Backtracking]] [[LALR parser|LALR]](k) || ? || [[Java (programming language)|Java]] || {{D-A|Mixed}} || generated || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[Eclipse Public License|EPL]] |
| LPG || [[Backtracking]] [[LALR parser|LALR]](k) || ? || [[Java (programming language)|Java]] || {{D-A|Mixed}} || generated || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[Eclipse Public License|EPL]] |
||
|- |
|- |
||
| LRSTAR || [[LALR parser|LALR]](1), [[LALR parser|LALR]](*) || YACC, ANTLR, EBNF || [[C++]] || |
| LRSTAR<ref>{{Cite web |url=http://lrstar.cc/ |title=An LR(*) parser generator for C++}}</ref> || [[LALR parser|LALR]](1), [[LALR parser|LALR]](*) || YACC, ANTLR, EBNF || [[C++]] || {{D-P|Separate}} || generated || {{Some|[[Microsoft Windows|Windows]]}} || {{Yes|[[Microsoft Visual Studio|Visual Studio]]}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| Menhir || [[Canonical LR parser|LR]](1) || ? || [[OCaml]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[Q Public License|QPL]] |
| Menhir || [[Canonical LR parser|LR]](1) || ? || [[OCaml]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[Q Public License|QPL]] |
||
Line 183: | Line 145: | ||
| MyParser || [[LL parser|LL]](*) || [[Markdown]] || [[C++11]] || {{D-P|Separate}} || internal || {{Some|Any with standard C++11 compiler}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
| MyParser || [[LL parser|LL]](*) || [[Markdown]] || [[C++11]] || {{D-P|Separate}} || internal || {{Some|Any with standard C++11 compiler}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| NLT || [[GLR parser|GLR]] || [[C Sharp (programming language)|C#]]/[[Backus–Naur form|BNF]]-like || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || mixed || {{Some|[[.NET |
| NLT || [[GLR parser|GLR]] || [[C Sharp (programming language)|C#]]/[[Backus–Naur form|BNF]]-like || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || mixed || {{Some|[[.NET]] framework}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| ocamlyacc || [[LALR parser|LALR]](1) || ? || [[OCaml]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[Q Public License|QPL]] |
| ocamlyacc || [[LALR parser|LALR]](1) || ? || [[OCaml]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[Q Public License|QPL]] |
||
Line 189: | Line 151: | ||
| olex || [[LL parser|LL]](1) || ? || [[C++]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| olex || [[LL parser|LL]](1) || ? || [[C++]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| [[Parsec (parser)|Parsec]]|| [[LL parser|LL]], [[backtracking]] || [[ |
| [[Parsec (parser)|Parsec]]|| [[LL parser|LL]], [[backtracking]] || [[Haskell]] || [[Haskell]] || {{D-A|Mixed}} || none || {{Yes|All}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| |
| yapp<ref name=":0" />|| [[LALR parser|LALR]](1) || ? || [[Perl]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| Parser Objects || [[LL parser|LL]](k) || ? || [[Java (programming language)|Java]] || {{D-A|Mixed}} || ? || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[zlib License|zlib]] |
| Parser Objects || [[LL parser|LL]](k) || ? || [[Java (programming language)|Java]] || {{D-A|Mixed}} || ? || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[zlib License|zlib]] |
||
Line 202: | Line 164: | ||
|- |
|- |
||
| PRECC || [[LL parser|LL]](k) || ? || [[C (programming language)|C]] || {{D-P|Separate}} || generated || {{Some|[[DOS]], [[POSIX]]}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| PRECC || [[LL parser|LL]](k) || ? || [[C (programming language)|C]] || {{D-P|Separate}} || generated || {{Some|[[DOS]], [[POSIX]]}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
⚫ | |||
⚫ | |||
|- |
|- |
||
|racc<ref>{{Cite web|title=Racc|url=https://i.loveruby.net/en/projects/racc/|access-date=2021-11-26|website=i.loveruby.net}}</ref> |
|racc<ref>{{Cite web|title=Racc|url=https://i.loveruby.net/en/projects/racc/|access-date=2021-11-26|website=i.loveruby.net}}</ref> |
||
Line 212: | Line 176: | ||
|{{No}} |
|{{No}} |
||
|{{Free|[[LGPL]]}} |
|{{Free|[[LGPL]]}} |
||
|- |
|||
| QLALR || [[LALR parser|LALR]](1) || ? || [[C++]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
|||
|- |
|- |
||
| [[SableCC]] || [[LALR parser|LALR]](1) || ? || [[C (programming language)|C]], [[C++]], [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[OCaml]], [[Python (programming language)|Python]] || {{D-P|Separate}} || generated || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
| [[SableCC]] || [[LALR parser|LALR]](1) || ? || [[C (programming language)|C]], [[C++]], [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[OCaml]], [[Python (programming language)|Python]] || {{D-P|Separate}} || generated || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
||
|- |
|- |
||
| SLK<ref>{{Cite web |url=http://www.slkpg. |
| SLK<ref>{{Cite web |url=http://www.slkpg.tech/ |title=The SLK Parser Generator supports C, C++, Java, JavaScript, and C#, optional backtracking, free}}</ref> || [[LL parser|LL]](k) [[LR parser|LR]](k) [[LALR]](k) || [[Extended Backus–Naur form|EBNF]] || [[C (programming language)|C]], [[C++]], [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[JavaScript]] || {{D-P|Separate}} || external || {{Yes|All}} || {{No}} || SLK<ref>http://www.slkpg.tech/license.txt {{Bare URL plain text|date=March 2022}}</ref> |
||
|- |
|- |
||
| SLY<ref>{{Cite web |url=https://sly.readthedocs.io/en/latest/sly.html |title=SLY (Sly Lex Yacc)}}</ref> || [[LALR parser|LALR]](1) || BNF || [[Python (programming language)|Python]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
| SLY<ref>{{Cite web |url=https://sly.readthedocs.io/en/latest/sly.html |title=SLY (Sly Lex Yacc)}}</ref> || [[LALR parser|LALR]](1) || BNF || [[Python (programming language)|Python]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
||
Line 239: | Line 201: | ||
| TP Yacc || [[LALR parser|LALR]](1) || ? || [[Turbo Pascal]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{Yes}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| TP Yacc || [[LALR parser|LALR]](1) || ? || [[Turbo Pascal]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{Yes}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| Tree-Sitter<ref>{{Cite web |url=https://tree-sitter.github.io/ |title=Tree-Sitter - An incremental parsing system for programming tools}}</ref> || [[LR parser|LR]](1), [[GLR parser|GLR]] || [[JavaScript]] [[Domain-specific language|DSL]], [[JSON]] || [[C (programming language)|C]], bindings ([[Rust (programming language)|Rust]], [[WebAssembly]], [[JavaScript]], [[Python (programming language)|Python]], many other) || {{D-P|Separate}} || generated + external || {{Yes|All}} || {{D-A|[[Vim (text editor)#Neovim|Neovim]], [[ |
| [[Tree-sitter (parser generator)|Tree-Sitter]]<ref>{{Cite web |url=https://tree-sitter.github.io/ |title=Tree-Sitter - An incremental parsing system for programming tools}}</ref> || [[LR parser|LR]](1), [[GLR parser|GLR]] || [[JavaScript]] [[Domain-specific language|DSL]], [[JSON]] || [[C (programming language)|C]], bindings ([[Rust (programming language)|Rust]], [[WebAssembly]], [[JavaScript]], [[Python (programming language)|Python]], many other) || {{D-P|Separate}} || generated + external || {{Yes|All}} || {{D-A|[[Vim (text editor)#Neovim|Neovim]], [[Helix]], [[GNU Emacs]], [[Lapce]], [[Zed (text editor)|Zed]]}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| Tunnel Grammar Studio || [[ |
| Tunnel Grammar Studio || [[Tunnel Parsing]] || [[Augmented Backus–Naur form|ABNF]] || [[C++]] || {{D-P|Separate}} || generated || {{Some|[[Microsoft Windows|Windows]]}} || {{Yes}} || {{Proprietary}} |
||
|- |
|- |
||
| UltraGram || [[LALR parser|LALR]](1), [[LR parser|LR]](1), [[GLR parser|GLR]] || [[Backus–Naur form|BNF]] || C++, Java, C#, Visual Basic .NET || {{D-P|Separate}} || external || {{Some|[[Microsoft Windows|Windows]]}} || {{Yes}} || {{Free}}, [[public domain]] |
| UltraGram || [[LALR parser|LALR]](1), [[LR parser|LR]](1), [[GLR parser|GLR]] || [[Backus–Naur form|BNF]] || C++, Java, C#, Visual Basic .NET || {{D-P|Separate}} || external || {{Some|[[Microsoft Windows|Windows]]}} || {{Yes}} || {{Free}}, [[public domain]] |
||
Line 248: | Line 210: | ||
|- |
|- |
||
| [[UrchinCC]] || [[LL parser|LL]](1) || ? || Java || ? || generated || {{Some|[[Java virtual machine]]}} || {{No}} || ? |
| [[UrchinCC]] || [[LL parser|LL]](1) || ? || Java || ? || generated || {{Some|[[Java virtual machine]]}} || {{No}} || ? |
||
|- |
|||
| Whale || [[LR parser|LR]](?), some conjunctive stuff, see Whale Calf || ? || [[C++]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Proprietary}} |
|||
|- |
|||
| wisent || [[LALR parser|LALR]](1) || ? || [[C++]], [[Java (programming language)|Java]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
|||
|- |
|- |
||
<!-- Other programming languages may be supported. --> |
<!-- Other programming languages may be supported. --> |
||
Line 262: | Line 220: | ||
| yecc || [[LALR parser|LALR]](1) || ? || [[Erlang (programming language)|Erlang]] || {{D-P|Separate}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[Apache License|Apache]] 2.0 |
| yecc || [[LALR parser|LALR]](1) || ? || [[Erlang (programming language)|Erlang]] || {{D-P|Separate}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[Apache License|Apache]] 2.0 |
||
|- |
|- |
||
| [[Visual BNF]] || [[Canonical LR parser|LR]](1), [[LALR parser|LALR]](1) || ? || [[C Sharp (programming language)|C#]] || {{D-P|Separate}} || generated || {{Some|[[.NET |
| [[Visual BNF]] || [[Canonical LR parser|LR]](1), [[LALR parser|LALR]](1) || ? || [[C Sharp (programming language)|C#]] || {{D-P|Separate}} || generated || {{Some|[[.NET]] framework}} || {{Yes}} || {{Proprietary}} |
||
|- |
|- |
||
| YooParse || [[Canonical LR parser|LR]](1), [[LALR parser|LALR]](1) || ? || [[C++]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
| YooParse || [[Canonical LR parser|LR]](1), [[LALR parser|LALR]](1) || ? || [[C++]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
||
Line 273: | Line 231: | ||
|} |
|} |
||
==Parsing expression grammars, deterministic |
==Parsing expression grammars, deterministic Boolean grammars== |
||
This table compares parser generators with [[parsing expression grammar]]s, deterministic [[ |
This table compares parser generators with [[parsing expression grammar]]s, deterministic [[Boolean grammar]]s. |
||
{| class="wikitable sortable" style="text-align: center; font-size: 85%; width: auto;" |
{| class="wikitable sortable" style="text-align: center; font-size: 85%; width: auto;" |
||
Line 281: | Line 239: | ||
! Name !! [[Parsing]] algorithm !! [[Programming language|Output languages]] !! Grammar, code !! Development platform !! [[Software license|License]] |
! Name !! [[Parsing]] algorithm !! [[Programming language|Output languages]] !! Grammar, code !! Development platform !! [[Software license|License]] |
||
|- |
|- |
||
| AustenX || Packrat (modified) || [[Java (programming language)|Java]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
| AustenX || [[Packrat parser|Packrat]] (modified) || [[Java (programming language)|Java]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| Aurochs || Packrat || [[C (programming language)|C]], [[OCaml]], [[Java (programming language)|Java]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| Aurochs || [[Packrat parser|Packrat]] || [[C (programming language)|C]], [[OCaml]], [[Java (programming language)|Java]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| BNFlite || Recursive descent || [[C++]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| BNFlite || Recursive descent || [[C++]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| Canopy || Packrat || [[Java (programming language)|Java]], [[JavaScript]], [[Python (programming language)|Python]], [[Ruby (programming language)|Ruby]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| Canopy || [[Packrat parser|Packrat]] || [[Java (programming language)|Java]], [[JavaScript]], [[Python (programming language)|Python]], [[Ruby (programming language)|Ruby]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| CL-peg || Packrat || [[Common Lisp]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| CL-peg || [[Packrat parser|Packrat]] || [[Common Lisp]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| Drat! || Packrat || [[D (programming language)|D]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| Drat! || [[Packrat parser|Packrat]] || [[D (programming language)|D]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| Frisby || Packrat || [[ |
| Frisby || [[Packrat parser|Packrat]] || [[Haskell]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| [[tcllib|grammar::peg]] || Packrat || [[Tcl]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
| [[tcllib|grammar::peg]] || [[Packrat parser|Packrat]] || [[Tcl]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| Grako || Packrat + Cut + Left Recursion || [[Python (programming language)|Python]], [[C++]] (beta) || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
| Grako || [[Packrat parser|Packrat]] + Cut + Left Recursion || [[Python (programming language)|Python]], [[C++]] (beta) || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| IronMeta || Packrat || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || {{Some|[[Microsoft Windows|Windows]]}} || {{Free}}, [[BSD licenses|BSD]] |
| IronMeta || [[Packrat parser|Packrat]] || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || {{Some|[[Microsoft Windows|Windows]]}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| Laja || 2-phase scannerless top-down [[backtracking]] + runtime support || [[Java (programming language)|Java]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| Laja || 2-phase scannerless top-down [[backtracking]] + runtime support || [[Java (programming language)|Java]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| lars::Parser || Packrat (supporting left-recursion and grammar ambiguity) || [[C++]] || Identical || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
| lars::Parser || [[Packrat parser|Packrat]] (supporting left-recursion and grammar ambiguity) || [[C++]] || Identical || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| LPeg || Parsing machine || [[Lua (programming language)|Lua]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| LPeg || Parsing machine || [[Lua (programming language)|Lua]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
Line 309: | Line 267: | ||
| lug || Parsing machine || [[C++17]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| lug || Parsing machine || [[C++17]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| Mouse || Recursive descent || [[Java (programming language)|Java]] || {{D-P|Separate}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[Apache License|Apache]] 2.0 |
| Mouse || Recursive descent (modified, limited memoization and left-recursion) || [[Java (programming language)|Java]] || {{D-P|Separate}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[Apache License|Apache]] 2.0 |
||
|- |
|- |
||
| Narwhal || Packrat || [[C (programming language)|C]] || {{D-A|Mixed}} || {{Some|[[POSIX]], [[Microsoft Windows|Windows]]}} || {{Free}}, [[BSD licenses|BSD]] |
| Narwhal || [[Packrat parser|Packrat]] || [[C (programming language)|C]] || {{D-A|Mixed}} || {{Some|[[POSIX]], [[Microsoft Windows|Windows]]}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| Nearley || [[Earley parser|Earley]] || [[JavaScript]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| Nearley || [[Earley parser|Earley]] || [[JavaScript]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
Line 317: | Line 275: | ||
| Nemerle.Peg || Recursive descent + Pratt || [[Nemerle]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
| Nemerle.Peg || Recursive descent + Pratt || [[Nemerle]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| neotoma || Packrat || [[Erlang (programming language)|Erlang]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| neotoma || [[Packrat parser|Packrat]] || [[Erlang (programming language)|Erlang]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| NPEG || Recursive descent || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| NPEG || Recursive descent || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| [[OMeta]] || Packrat (modified, partial memoization) || [[JavaScript]], [[Squeak]], [[Python (programming language)|Python]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| [[OMeta]] || [[Packrat parser|Packrat]] (modified, partial memoization) || [[JavaScript]], [[Squeak]], [[Python (programming language)|Python]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| |
| PackCC || [[Packrat parser|Packrat]] (modified, left-recursion support) || [[C (programming language)|C]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| Packrat || Packrat || [[Scheme (programming language)|Scheme]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| [[Packrat parser|Packrat]] || [[Packrat parser|Packrat]] || [[Scheme (programming language)|Scheme]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| [[Pappy]] || Packrat || [[ |
| [[Pappy]] || [[Packrat parser|Packrat]] || [[Haskell]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| [[Parboiled (Java)|parboiled]] || Recursive descent || [[Java (programming language)|Java]], [[Scala (programming language)|Scala]] || {{D-A|Mixed}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[Apache License|Apache]] 2.0 |
| [[Parboiled (Java)|parboiled]] || Recursive descent || [[Java (programming language)|Java]], [[Scala (programming language)|Scala]] || {{D-A|Mixed}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[Apache License|Apache]] 2.0 |
||
Line 335: | Line 293: | ||
| parsepp || Recursive descent || [[C++]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[public domain]] |
| parsepp || Recursive descent || [[C++]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[public domain]] |
||
|- |
|- |
||
| Parsnip || Packrat || [[C++]] || {{D-A|Mixed}} || {{Some|[[Microsoft Windows|Windows]]}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| Parsnip || [[Packrat parser|Packrat]] || [[C++]] || {{D-A|Mixed}} || {{Some|[[Microsoft Windows|Windows]]}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| Patterns || Parsing machine || [[Swift (programming language)|Swift]] || Identical || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| Patterns || Parsing machine || [[Swift (programming language)|Swift]] || Identical || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
Line 341: | Line 299: | ||
| peg || Recursive descent || [[C (programming language)|C]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| peg || Recursive descent || [[C (programming language)|C]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| PEG.js || Packrat (partial memoization) || [[JavaScript]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| PEG.js || [[Packrat parser|Packrat]] (partial memoization) || [[JavaScript]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| Peggy<ref>Maintained fork of PEG.js</ref> || Packrat (partial memoization) || [[JavaScript]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| Peggy<ref>Maintained fork of PEG.js</ref> || [[Packrat parser|Packrat]] (partial memoization) || [[JavaScript]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| Pegasus || Recursive descent, Packrat (selectively) || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || {{Some|[[Microsoft Windows|Windows]]}} || {{Free}}, [[MIT License|MIT]] |
| Pegasus || Recursive descent, [[Packrat parser|Packrat]] (selectively) || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || {{Some|[[Microsoft Windows|Windows]]}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| pegc || Recursive descent || [[C (programming language)|C]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[public domain]] |
| pegc || Recursive descent || [[C (programming language)|C]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[public domain]] |
||
|- |
|- |
||
| pest || Recursive descent || [[Rust (programming language)|Rust]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[ |
| pest || Recursive descent || [[Rust (programming language)|Rust]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]], [[Apache License|Apache]] 2.0 |
||
|- |
|- |
||
| PetitParser || Packrat || [[Smalltalk]], [[Java (programming language)|Java]], [[Dart (programming language)|Dart]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| PetitParser || [[Packrat parser|Packrat]] || [[Smalltalk]], [[Java (programming language)|Java]], [[Dart (programming language)|Dart]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| PEGTL || Recursive descent || [[C++11]], [[C++17]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[Boost Software License|Boost]] |
| PEGTL<ref>{{Citation |title=taocpp/PEGTL |date=2024-03-14 |url=https://github.com/taocpp/PEGTL |access-date=2024-03-16 |publisher=The Art of C++}}</ref>|| Recursive descent || [[C++11]], [[C++17]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[Boost Software License|Boost]] |
||
|- |
|- |
||
| [[Parser Grammar Engine]] (PGE) || Hybrid recursive descent / operator precedence<ref>{{cite web |url=https://parrot.github.com/html/docs/book/pct/ch04_pge.pod.html |title=Parrot: Grammar Engine |year=2011 |publisher=The Parrot Foundation |quote=PGE rules provide the full power of recursive descent parsing and operator precedence parsing.}}</ref> || [[Parrot virtual machine|Parrot bytecode]] || {{D-A|Mixed}} || {{Some|[[Parrot virtual machine]]}} || {{Free}}, [[Artistic License|Artistic]] 2.0 |
| [[Parser Grammar Engine]] (PGE) || Hybrid recursive descent / operator precedence<ref>{{cite web |url=https://parrot.github.com/html/docs/book/pct/ch04_pge.pod.html |title=Parrot: Grammar Engine |year=2011 |publisher=The Parrot Foundation |quote=PGE rules provide the full power of recursive descent parsing and operator precedence parsing.}}</ref> || [[Parrot virtual machine|Parrot bytecode]] || {{D-A|Mixed}} || {{Some|[[Parrot virtual machine]]}} || {{Free}}, [[Artistic License|Artistic]] 2.0 |
||
|- |
|- |
||
| [[PyPy]] rlib || Packrat || [[Python (programming language)|Python]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
| [[PyPy]] rlib || [[Packrat parser|Packrat]] || [[Python (programming language)|Python]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| Rats! || Packrat || [[Java (programming language)|Java]] || {{D-A|Mixed}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
| Rats! || [[Packrat parser|Packrat]] || [[Java (programming language)|Java]] || {{D-A|Mixed}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
||
|- |
|||
| [https://github.com/zhong-j-yu/rekex Rekex] || Recursive descent || [[Java (programming language)|Java]] || {{D-A|Mixed}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[Apache License|Apache]] 2.0 |
|||
|- |
|- |
||
| Spirit2 || Recursive descent || [[C++]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[Boost Software License|Boost]] |
| Spirit2 || Recursive descent || [[C++]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[Boost Software License|Boost]] |
||
Line 374: | Line 330: | ||
|} |
|} |
||
== General context-free, conjunctive, or |
== General context-free, conjunctive, or Boolean languages == |
||
This table compares parser generator languages with a general [[context-free grammar]], a [[conjunctive grammar]], or a [[ |
This table compares parser generator languages with a general [[context-free grammar]], a [[conjunctive grammar]], or a [[Boolean grammar]]. |
||
{| class="wikitable sortable" style="text-align: center; font-size: 85%; width: auto;" |
{| class="wikitable sortable" style="text-align: center; font-size: 85%; width: auto;" |
||
Line 386: | Line 342: | ||
| APaGeD || [[GLR parser|GLR]], [[LALR parser|LALR]](1), [[LL parser|LL]](k) || ? || [[D (programming language)|D]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[Artistic License|Artistic]] |
| APaGeD || [[GLR parser|GLR]], [[LALR parser|LALR]](1), [[LL parser|LL]](k) || ? || [[D (programming language)|D]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[Artistic License|Artistic]] |
||
|- |
|- |
||
| [[GNU Bison|Bison]] || [[LALR parser|LALR]](1), [[Canonical LR parser|LR]](1), [[IELR parser|IELR]](1), [[GLR parser|GLR]] || [[Yacc]] || [[C (programming language)|C]], [[C++]], [[Java (programming language)|Java]], [[XML]] || {{D-A|Mixed}}, except XML || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
| [[GNU Bison|Bison]] || [[LALR parser|LALR]](1), [[Canonical LR parser|LR]](1), [[IELR parser|IELR]](1), [[GLR parser|GLR]] || [[Yacc]] || [[C (programming language)|C]], [[C++]], [[D (programming language)|D]],<ref>{{cite web |title=Decl Summary (Bison 3.8.1) |url=https://www.gnu.org/software/bison/manual/html_node/Decl-Summary.html |website=www.gnu.org}}</ref> [[Java (programming language)|Java]], [[XML]] || {{D-A|Mixed}}, except XML || external || {{Yes|All}} || {{No}} || {{Free}}, [[GNU General Public License|GNU GPL]] |
||
|- |
|- |
||
| [[DMS Software Reengineering Toolkit]] || [[GLR parser|GLR]] || ? || [[Parlanse]] || {{D-A|Mixed}} || generated || {{Some|[[Microsoft Windows|Windows]]}} || {{No}} || {{Proprietary}} |
| [[DMS Software Reengineering Toolkit]] || [[GLR parser|GLR]] || ? || [[Parlanse]] || {{D-A|Mixed}} || generated || {{Some|[[Microsoft Windows|Windows]]}} || {{No}} || {{Proprietary}} |
||
Line 398: | Line 354: | ||
| Elkhound || [[GLR parser|GLR]] || ? || [[C++]], [[OCaml]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
| Elkhound || [[GLR parser|GLR]] || ? || [[C++]], [[OCaml]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| GDK || [[LALR parser|LALR]](1), [[GLR parser|GLR]] || ? || [[C (programming language)|C]], [[lex (software)|Lex]], [[ |
| GDK || [[LALR parser|LALR]](1), [[GLR parser|GLR]] || ? || [[C (programming language)|C]], [[lex (software)|Lex]], [[Haskell]], [[HTML]], [[Java (programming language)|Java]], [[Object Pascal]], [[Yacc]] || {{D-A|Mixed}} || generated || {{Some|[[POSIX]]}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
||
|- |
|- |
||
| Happy || [[LALR parser|LALR]], [[GLR parser|GLR]] || ? || [[ |
| Happy || [[LALR parser|LALR]], [[GLR parser|GLR]] || ? || [[Haskell]] || {{D-A|Mixed}} || external || {{Yes|All}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| Hime Parser Generator || [[GLR parser|GLR]] || ? || [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[Rust (programming language)|Rust]] || {{D-P|Separate}} || generated || {{Some|[[.NET |
| Hime Parser Generator || [[GLR parser|GLR]] || ? || [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]], [[Rust (programming language)|Rust]] || {{D-P|Separate}} || generated || {{Some|[[.NET]] framework, [[Java virtual machine]]}} || {{No}} || {{Free}}, [[GNU Lesser General Public License|GNU LGPL]] |
||
|- |
|- |
||
| IronText Library || [[LALR parser|LALR]](1), [[GLR parser|GLR]] || [[C Sharp (programming language)|C#]] || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || generated or external || {{Some|[[.NET |
| IronText Library || [[LALR parser|LALR]](1), [[GLR parser|GLR]] || [[C Sharp (programming language)|C#]] || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || generated or external || {{Some|[[.NET]] framework}} || {{No}} || {{Free}}, [[Apache License|Apache]] 2.0 |
||
|- |
|- |
||
| Jison || [[LALR parser|LALR]](1), [[LR parser|LR]](0), [[SLR parser|SLR]](1) || [[Yacc]] || [[JavaScript]], [[C Sharp (programming language)|C#]], [[PHP]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
| Jison || [[LALR parser|LALR]](1), [[LR parser|LR]](0), [[SLR parser|SLR]](1) || [[Yacc]] || [[JavaScript]], [[C Sharp (programming language)|C#]], [[PHP]] || {{D-A|Mixed}} || generated || {{Yes|All}} || {{No}} || {{Free}}, [[MIT License|MIT]] |
||
Line 418: | Line 374: | ||
| P4 || Earley–combinators, infinitary CFGs || BNF-like || [[OCaml]] || {{D-A|Mixed}} || external, or scannerless || {{Yes|All}} || {{No}} || ? |
| P4 || Earley–combinators, infinitary CFGs || BNF-like || [[OCaml]] || {{D-A|Mixed}} || external, or scannerless || {{Yes|All}} || {{No}} || ? |
||
|- |
|- |
||
| [[Scannerless Boolean Parser]] || [[Scannerless parsing|Scannerless GLR]] ([[Boolean grammar]]s) || ? || [[ |
| [[Scannerless Boolean Parser]] || [[Scannerless parsing|Scannerless GLR]] ([[Boolean grammar]]s) || ? || [[Haskell]], [[Java (programming language)|Java]] || {{D-P|Separate}} || [[Scannerless parsing|scannerless]] || {{Some|[[Java virtual machine]]}} || {{No}} || {{Free}}, [[BSD licenses|BSD]] |
||
|- |
|- |
||
| [[Syntax Definition Formalism|SDF]]/SGLR || [[Scannerless parsing|Scannerless GLR]] || [[Syntax Definition Formalism|SDF]] || [[C (programming language)|C]], [[Java (programming language)|Java]] || {{D-P|Separate}} || [[Scannerless parsing|scannerless]] || {{Yes|All}} || {{Yes}} || {{Free}}, [[BSD licenses|BSD]] |
| [[Syntax Definition Formalism|SDF]]/SGLR || [[Scannerless parsing|Scannerless GLR]] || [[Syntax Definition Formalism|SDF]] || [[C (programming language)|C]], [[Java (programming language)|Java]] || {{D-P|Separate}} || [[Scannerless parsing|scannerless]] || {{Yes|All}} || {{Yes}} || {{Free}}, [[BSD licenses|BSD]] |
||
Line 443: | Line 399: | ||
{| class="wikitable sortable" |
{| class="wikitable sortable" |
||
! Name !! Parsing algorithm !! Input grammar notation !! Boolean grammar abilities !! Development platform !! [[Software license|License]] |
! Name !! Parsing algorithm !! Input grammar notation !! Boolean grammar abilities !! Development platform !! [[Software license|License]] |
||
|- |
|||
| LuZc<ref>{{Cite web |url=http://qyxz.netau.net/ |title=LuZ: A context sensitive parser |date=2016-10-17 |archive-url=https://web.archive.org/web/20161017051112/http://qyxz.netau.net/ |archive-date=2016-10-17 |access-date=2018-10-17}}</ref><ref>{{Cite web |url=http://luzc.zohosites.com/ |title=LuZc – A conjunctive context-sensitive parser |website=luzc.zohosites.com |access-date=2018-10-17}}</ref> || delta chain || modular || Conjunctive, not complimentary || {{Some|[[POSIX]]}} || {{Proprietary}} |
|||
|- |
|- |
||
| [http://sourceforge.net/p/bnf2xml/ bnf2xml] || [[Recursive descent]] (is a text filter output is xml) || simple [[Backus–Naur form|BNF]]{{clarify|Only context-free grammars can be denoted in BNF.|date=January 2018}} grammar (input matching), output is xml || ? || Beta, and not a full EBNF parser || {{Free}}, [[GNU General Public License|GNU GPL]] |
| [http://sourceforge.net/p/bnf2xml/ bnf2xml] || [[Recursive descent]] (is a text filter output is xml) || simple [[Backus–Naur form|BNF]]{{clarify|Only context-free grammars can be denoted in BNF.|date=January 2018}} grammar (input matching), output is xml || ? || Beta, and not a full EBNF parser || {{Free}}, [[GNU General Public License|GNU GPL]] |
Latest revision as of 17:27, 30 November 2024
This article needs additional citations for verification. (July 2023) |
This is a list of notable lexer generators and parser generators for various language classes.
Regular languages
[edit]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 |
Astir | DFA table driven, with branching | C++ | Only grammar (actioned) | All | Free, MIT |
AustenX | DFA | Java | Separate | All | Free, BSD |
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 |
DFA | DFA compressed matrix | C, C++ | Separate | Windows, Visual Studio | BSD |
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 |
Quex | DFA direct code | C, C++ | Mixed | All | Free, GNU LGPL |
Ragel | DFA | Go, C, C++, Java, assembly | Mixed | All | Free, GNU GPL, MIT[1][2] |
RE/flex | DFA direct code, DFA table driven, and NFA regex libraries | C++ | Mixed | All | Free, BSD |
re2c | DFA direct code | C, C++, Go, Rust | Mixed | All | Free, public domain |
Deterministic context-free languages
[edit]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 | Separate | 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[4] | Recursive descent, backtracking | ABNF | Python, JavaScript, C, Java | Separate | none | All | No | Free, BSD |
Beaver[5][6] | LALR(1) | EBNF | Java | Mixed | external | Java virtual machine | No | Free, BSD |
Bison | LALR(1), LR(1), IELR(1), GLR | Yacc | C, C++, Java | Mixed | external | All | No | Free, GNU GPL with exception |
BtYacc | Backtracking Bottom-up | ? | C++ | Mixed | external | All | No | Free, public domain |
byacc | LALR(1) | Yacc | C | Mixed | external | All | No | Free, public domain |
CL-Yacc[7][8] | LALR(1) | Lisp | Common Lisp | Mixed | 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 | Mixed | generated | Java virtual machine, .NET framework, Windows, POSIX (depends on output language) | No | Free, GNU GPL |
CppCC[9][10] | LL(k) | ? | C++ | Mixed | generated | POSIX | No | Free, GNU GPL |
CUP[11][12] | LALR(1) | ? | Java | Mixed | external | Java virtual machine | No | Free, BSD-like |
Eli[13][14] | LALR(1) | ? | C | Mixed | generated | POSIX | No | Free, GNU GPL, GNU LGPL |
Essence[15] | LR(?) | ? | Scheme 48 | Mixed | external | All | No | Free, BSD |
eyapp[16] | LALR(1) | ? | Perl | Mixed | external or generated | All | No | Free, Artistic |
GOLD[17] | 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 |
Hime Parser Generator[18] | LALR(1), GLR | BNF dialect | C#, Java, Rust | Separate | generated | .NET framework, Java virtual machine | No | Free, GNU LGPL |
Hyacc[19] | LR(1), LALR(1), LR(0) | Yacc | C | Mixed | external | All | No | Free, GNU GPL |
JavaCC[20][21] | LL(k) | EBNF | Java, C++, JavaScript (via GWT compiler)[22] | Mixed | generated | Java virtual machine | Yes | 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 (SPPF) | EBNF | Python, JavaScript | Mixed | generated | All | Yes | Free, MIT |
Lemon | LALR(1) | BNF dialect[23] | C | Mixed | external | All | No | Free, public domain |
Lezer[24][25][26] | LR(1), GLR | EBNF dialect | JavaScript | Separate | generated | Node.js, JavaScript | No | Free, MIT |
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[27] | LALR(1), LALR(*) | YACC, ANTLR, EBNF | 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 |
Parsec | LL, backtracking | Haskell | Haskell | Mixed | none | All | No | Free, BSD |
yapp[16] | 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 |
racc[28] | LALR(1) | BNF-like, yacc-like[29] | Ruby | Mixed | ? | Windows, Linux, macOS, FreeBSD, NetBSD | No | LGPL |
SableCC | LALR(1) | ? | C, C++, C#, Java, OCaml, Python | Separate | generated | Java virtual machine | No | Free, GNU LGPL |
SLK[30] | LL(k) LR(k) LALR(k) | EBNF | C, C++, C#, Java, JavaScript | Separate | external | All | No | SLK[31] |
SLY[32] | LALR(1) | BNF | Python | Mixed | generated | All | No | Free, MIT |
SP (Simple Parser) | Recursive descent | Python | Python | Separate | generated | All | No | Free, GNU LGPL |
Spirit | Recursive descent | ? | C++ | Mixed | internal | All | No | Free, Boost |
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 |
Tree-Sitter[33] | LR(1), GLR | JavaScript DSL, JSON | C, bindings (Rust, WebAssembly, JavaScript, Python, many other) | Separate | generated + external | All | Neovim, Helix, GNU Emacs, Lapce, Zed | Free, MIT |
Tunnel Grammar Studio | Tunnel Parsing | ABNF | C++ | Separate | generated | Windows | Yes | Proprietary |
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 | ? |
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[34] | 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 grammars
[edit]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 | 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 |
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 (modified, limited memoization and left-recursion) | 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, left-recursion support) | 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 |
Patterns | Parsing machine | Swift | Identical | All | Free, MIT |
peg | Recursive descent | C | Mixed | All | Free, MIT |
PEG.js | Packrat (partial memoization) | JavaScript | Mixed | All | Free, MIT |
Peggy[35] | Packrat (partial memoization) | JavaScript | Mixed | All | Free, MIT |
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, MIT, Apache 2.0 |
PetitParser | Packrat | Smalltalk, Java, Dart | Mixed | All | Free, MIT |
PEGTL[36] | Recursive descent | C++11, C++17 | Mixed | All | Free, Boost |
Parser Grammar Engine (PGE) | Hybrid recursive descent / operator precedence[37] | Parrot bytecode | Mixed | Parrot virtual machine | Free, Artistic 2.0 |
PyPy rlib | Packrat | Python | Mixed | All | Free, MIT |
Rats! | Packrat | Java | Mixed | Java virtual machine | Free, GNU LGPL |
Spirit2 | Recursive descent | C++ | Mixed | All | Free, Boost |
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 languages
[edit]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++, D,[38] 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 |
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++, 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 |
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 |
Context-sensitive grammars
[edit]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 BNF[clarification needed] grammar (input matching), output is xml | ? | Beta, and not a full EBNF parser | Free, GNU GPL |
See also
[edit]Notes
[edit]
References
[edit]- ^ "Ragel State Machine Compiler".
- ^ http://www.colm.net/open-source/ragel/ [verification needed]
- ^ "Adaptive LL(*) Parsing: The Power of Dynamic Analysis" (PDF). Terence Parr. Retrieved 2016-04-03.
- ^ "Survey on Various Syntax Analyzer Tools". www.ijraset.com. Retrieved 2023-09-16.
- ^ Boyland, John; Spiewak, Daniel (2010-09-17). "Tool Paper: ScalaBison Recursive Ascent-Descent Parser Generator". Electronic Notes in Theoretical Computer Science. Proceedings of the Ninth Workshop on Language Descriptions Tools and Applications (LDTA 2009). 253 (7): 65–74. doi:10.1016/j.entcs.2010.08.032. ISSN 1571-0661.
- ^ "Beaver - a LALR Parser Generator". beaver.sourceforge.net. Retrieved 2023-09-16.
- ^ Newton, Jim E.; Demaille, Akim; Verna, Didier (2016-05-09). "Type-Checking of Heterogeneous Sequences in Common Lisp" (PDF). Proceedings of the 9th European Lisp Symposium on European Lisp Symposium. ELS2016. Kraków, Poland: European Lisp Scientific Activities Association: 13–20. ISBN 978-2-9557474-0-7.
- ^ "CL-Yacc — a LALR(1) parser generator for Common Lisp". www.irif.fr. Retrieved 2023-09-16.
- ^ Hosseinpour, Sahereh; Alavi Milani, Mir Mohammad Reza; Pehlivan, Hüseyin (July 2018). "A Step-by-Step Solution Methodology for Mathematical Expressions". Symmetry. 10 (7): 285. Bibcode:2018Symm...10..285H. doi:10.3390/sym10070285. ISSN 2073-8994.
- ^ "CppCC's Home Page". cppcc.sourceforge.net. Retrieved 2023-09-16.
- ^ "Java Cup". pages.cs.wisc.edu. Retrieved 2023-09-16.
- ^ "CUP". www2.cs.tum.edu. Retrieved 2023-09-16.
- ^ Thiemann, Peter; Neubauer, Matthias (2004-12-31). "Parameterized LR Parsing". Electronic Notes in Theoretical Computer Science. Proceedings of the Fourth Workshop on Language Descriptions, Tools, and Applications (LDTA 2004). 110: 115–132. doi:10.1016/j.entcs.2004.06.007. ISSN 1571-0661.
- ^ Gray, Robert W.; Levi, Steven P.; Heuring, Vincent P.; Sloane, Anthony M.; Waite, William M. (1992). "Eli: a complete, flexible compiler construction system". Communications of the ACM. 35 (2): 121–130. doi:10.1145/129630.129637. ISSN 0001-0782. S2CID 5121773.
- ^ Owens, Scott; Flatt, M.; Shivers, O.; McMullan, Benjamin (2004-10-01). "Lexer and Parser Generators in Scheme" (PDF). Scheme 2004: Proceedings of the Fifth Workshop on Scheme and Functional Programming.
- ^ a b Areias, Hugo; Simões, Alberto; Henriques, P.; Cruz, Daniela Carneiro da (2010-09-01). "Parser generation in Perl : an overview and available tools" (PDF).
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ Volkman, Victor (2007-07-19). "Let Your Parser Go for the GOLD". Developer.com. Retrieved 2023-11-04.
- ^ "Parsing in C#: All the Tools and Libraries You Can Use (Part 2) - DZone". dzone.com. Retrieved 2023-11-04.
- ^ Ortin, Francisco; Quiroga, Jose; Rodriguez-Prieto, Oscar; Garcia, Miguel (2022-03-03). "An empirical evaluation of Lex/Yacc and ANTLR parser generation tools". PLOS ONE. 17 (3): e0264326. Bibcode:2022PLoSO..1764326O. doi:10.1371/journal.pone.0264326. ISSN 1932-6203. PMC 8893623. PMID 35239695.
- ^ Enseling, Oliver (2000-12-29). "Build your own languages with JavaCC". InfoWorld. Retrieved 2023-11-04.
- ^ "JavaCC". JavaCC. Retrieved 2023-11-04.
- ^ "Building parsers for the web with JavaCC & GWT (Part one)". Chris Ainsley. 14 April 2014. Retrieved 2014-05-04.
- ^ "The Lemon Parser Generator". sqlite.org. Retrieved 2023-11-30.
- ^ "The Lezer Parser System".
- ^ "Building a ShopifyQL Code Editor". Shopify. Retrieved 2023-12-06.
- ^ "Sponsoring the Lezer parser system | Tines". www.tines.com. 2022-03-11. Retrieved 2023-12-06.
- ^ "An LR(*) parser generator for C++".
- ^ "Racc". i.loveruby.net. Retrieved 2021-11-26.
- ^ "Racc Grammar File Reference". i.loveruby.net. Retrieved 2021-11-26.
- ^ "The SLK Parser Generator supports C, C++, Java, JavaScript, and C#, optional backtracking, free".
- ^ http://www.slkpg.tech/license.txt [bare URL plain text file]
- ^ "SLY (Sly Lex Yacc)".
- ^ "Tree-Sitter - An incremental parsing system for programming tools".
- ^ "Parse - Compile time (LR) type safe parser generator for C++". GitHub. 30 December 2021.
- ^ Maintained fork of PEG.js
- ^ taocpp/PEGTL, The Art of C++, 2024-03-14, retrieved 2024-03-16
- ^ "Parrot: Grammar Engine". The Parrot Foundation. 2011.
PGE rules provide the full power of recursive descent parsing and operator precedence parsing.
- ^ "Decl Summary (Bison 3.8.1)". www.gnu.org.