Context-free grammar

A context-free grammar is a set of production rules, each replacing one nonterminal with a sequence of terminals and nonterminals. It generates a language by repeated rule application.

Production rule: A formal instruction that replaces a symbol or sequence of symbols during a derivation. Each context-free production replaces exactly one nonterminal with its right-hand sequence.
Formal grammar: A finite set of symbols and production rules that specifies how strings in a language can be formed. Context-free grammars are one precisely defined kind of formal grammar.
Compiler: A program that translates source code into another representation, often machine code. Compilers commonly use context-free grammars to describe and parse programming-language syntax.
Noam Chomsky: An American linguist whose work shaped modern theories of generative grammar and formal language. Chomsky introduced the formal hierarchy that classifies context-free grammars.
Derivation (formal language theory): A sequence of production-rule applications that transforms a start symbol into a string. Derivations show how repeated context-free productions generate a sentence.
Formal language: A set of finite strings over an alphabet, defined by explicit mathematical rules. A grammar's central purpose is to define a formal language.
Parsing: The process of determining the grammatical structure of an input string. Parsing applies grammar rules to identify the structure of source code or other input.
Formal language theory: The mathematical study of languages defined by formal rules and the machines that recognize them. Context-free grammars became a foundational object in this broader theory.
Parse tree: A tree showing how a string is generated by a grammar's production rules. Its branches record the nested structure imposed by context-free productions.
Terminal symbol: A symbol that appears in the final strings generated by a grammar and is not expanded further. Terminal symbols make up the strings that a context-free grammar generates.

Linked from 13 pages