Top Qs
Timeline
Chat
Perspective
Comparison of parser generators
From Wikipedia, the free encyclopedia
Remove ads
This is a list of notable lexer generators and parser generators for various language classes.
 | This article needs additional citations for verification. (July 2023) |
Regular languages
Summarize
Perspective
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.)
Remove ads
Deterministic context-free languages
Summarize
Perspective
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.
Remove ads
Parsing expression grammars, deterministic Boolean grammars
Summarize
Perspective
This table compares parser generators with parsing expression grammars, deterministic Boolean grammars.
Remove ads
General context-free, conjunctive, or Boolean languages
Summarize
Perspective
This table compares parser generator languages with a general context-free grammar, a conjunctive grammar, or a Boolean grammar.
Remove ads
Context-sensitive grammars
This table compares parser generators with context-sensitive grammars.
Remove ads
See also
Notes
References
External links
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads