Comparison of parser generators: Difference between revisions

Revision as of 21:50, 17 May 2025

Latest revision as of 18:23, 9 August 2025

(One intermediate revision by one other user not shown)

Line 57:

[[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.)

The [[deterministic context-free language]]s are a proper subset of the context-free languages which can be efficiently parsed by [[deterministic pushdown automata]].<!-- More parsing algorithms and output formats supported. See httphttps://gdk.sourceforge.net/gdkref.pdf -->

{| class="wikitable sortable" style="text-align: center; font-size: 85%; width: auto;"

|-

Line 84:

| 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

|-

<!-- Other programming languages may be supported. See httphttps://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]]

|-

Line 279:

| neotoma || [[Packrat parser|Packrat]] || [[Erlang (programming language)|Erlang]] || {{D-P|Separate}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]]

|-

| nez<ref>{{Citation |title=Nez: practical open grammar language |date=2015-11-26 |url=https://arxiv.org/abs/=1511.08307 |last1=Kuramitsu |first1=Kimio }}</ref> || Parsing machine || [[Java (programming language)|Java]], [[C (programming language)|C]] || {{D-P|Separate}} || {{Some|[[Java virtual machine]]}} || {{Free}}, [[BSD License|BSD]]

|-

| NPEG || Recursive descent || [[C Sharp (programming language)|C#]] || {{D-A|Mixed}} || {{Yes|All}} || {{Free}}, [[MIT License|MIT]]

Line 404:

! Name !! Parsing algorithm !! Input grammar notation !! Boolean grammar abilities !! Development platform !! [[Software license|License]]

|-

| [httphttps://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]]

|}