Context-Free Grammar
In a context-free grammar, the left-hand side of each production is a single nonterminal; it can describe recursive structures and forms the basis of most programming-language syntax.
Purpose
Describe the syntactic structure of programming languages and drive parser design.
Mechanism
Rules of the form A→α, where A is a nonterminal and α is a string of terminals/nonterminals. Can describe nesting (e.g., balanced parentheses, expressions) but not context dependencies (e.g., declare-before-use of variables). A Chomsky type-2 grammar.
Use cases
- Language design
- Parsers
- Syntax analysis