Parsing: Difference between revisions
| Line 17: | Line 17: | ||
==Context-Free Grammar== | ==Context-Free Grammar== | ||
A context-free grammar is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol. A popular notation for context-free grammar is Backus-Naur (BNF). | A context-free grammar is a grammar in which the left-hand side of each production rule consists of only a '''single''' nonterminal symbol. A popular notation for context-free grammar is Backus-Naur (BNF). | ||
Deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They can be derived from deterministic pushdown automata, and they generate deterministic context-free languages. DCFGs are unambiguous and are of practical interest as they can be parsed in linear time. Parsers can be automatically generated from the grammar by a [[#Parser_Generator|parser generator]]. Restricted forms of DCFGs can be parsed by simpler parsers. These grammar classes are referred by the type of parser that parses them: LALR, SLR and LL. | Deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They can be derived from deterministic pushdown automata, and they generate deterministic context-free languages. DCFGs are unambiguous and are of practical interest as they can be parsed in linear time. Parsers can be automatically generated from the grammar by a [[#Parser_Generator|parser generator]]. Restricted forms of DCFGs can be parsed by simpler parsers. These grammar classes are referred by the type of parser that parses them: LALR, SLR and LL. | ||
Revision as of 20:05, 13 June 2018
External
Internal
Overview
Formal Grammar
A set of production rules that describe all possible strings in a given formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language syntax. The grammar does not describe the meaning of strings, or what can be done with them in whatever context, only their form.
Context-Free Grammar
A context-free grammar is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol. A popular notation for context-free grammar is Backus-Naur (BNF).
Deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They can be derived from deterministic pushdown automata, and they generate deterministic context-free languages. DCFGs are unambiguous and are of practical interest as they can be parsed in linear time. Parsers can be automatically generated from the grammar by a parser generator. Restricted forms of DCFGs can be parsed by simpler parsers. These grammar classes are referred by the type of parser that parses them: LALR, SLR and LL.
Backus-Naur Form BNF
Backus-Naur form is notation technique for context-free grammars that is used to describe the syntax of languages used in computing.
A BNF specification is a set of derivation rules, written as:
<symbol> ::= expression
where <symbol> is a nonterminal, and expression consists of one or more sequence of symbols. The expression may contain vertical bars '|' indicating a choice. Symbols that. never appear on the left side are terminals. The ::= means that the symbol on the left must be replaced with the expression on the right.
Extended Backus-Naur form EBNF
EBNF Variant that Used to Define the XML Grammar
Parse Tree
Difference between parse tree and syntax tree.
Syntax Tree
Parser
Top-Down Parser
A top-down parser is a parser that employs a strategy where it first looks at the highest level of the parse tree and works down the parser tree by suing the rewriting rules of the formal grammar.
Parser Generator
ANTLR