• Source: Comparison of parser generators

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




Regular languages


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




Deterministic context-free languages


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




Parsing expression grammars, deterministic Boolean grammars


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




General context-free, conjunctive, or Boolean languages


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




Context-sensitive grammars


This table compares parser generators with context-sensitive grammars.




See also


Compiler-compiler
List of program transformation systems
Comparison of regular expression engines




Notes






References






External links


The Catalog of Compiler Construction Tools
Open Source Parser Generators in Java

Kata Kunci Pencarian:

• Comparison of parser generators
• LALR parser
• Tree-sitter (parser generator)
• Lex (software)
• Comparison of documentation generators
• Flex (lexical analyser generator)
• Parsing expression grammar
• LALR parser generator
• LL parser
• Ragel