Formal grammar

A formal grammar specifies how strings can be constructed. Terminals belong to the completed strings; nonterminals stand for structures that may still be expanded. A start symbol identifies the initial point, and productions specify permitted replacements. The language generated by a grammar consists of all terminal strings obtainable from its start symbol.

In a context-free grammar, a production has a single nonterminal on its left and a string of terminals and nonterminals on its right. Replacement does not depend on neighboring symbols. Context-free grammars are an important kind of formal grammar, not a definition of every possible grammar.

References: [1]

Take S as the start symbol, a and b as terminals, and the rules S → aSb and S → ε, where ε denotes the empty string. Two uses of the first rule followed by the second yield S ⇒ aSb ⇒ aaSbb ⇒ aabb. Each recursive step adds one a at the front and one b at the back.

The resulting language contains exactly a block of a symbols followed by an equally long block of b symbols, including the empty string. A production is a rule; a derivation is a sequence of applications; a generated string is one result. Finite recursive rules can describe infinitely many results without making any particular finite derivation produce an infinite string. For example, ab and aaabbb are generated, whereas aab is not. This can be checked by counting how each permitted replacement changes the two blocks.

References: [1]

A derivation can be represented as a tree, while parsing works from an input toward its grammatical structure. A concrete syntax tree retains grammatical details; an abstract syntax tree selects constructs useful to later processing. In LLVM's teaching compiler, parentheses establish grouping but do not need separate AST nodes.

Suppose a grammar permits a name followed by a plus sign and a number. The input x + 2 can then have a clear tree without establishing what x refers to, whether addition is permitted for its value, or what the result will be. Name resolution, type rules and evaluation supply information beyond that structure.

A string can also have two distinct parse trees in a given grammar: grammatical ambiguity. E → E + E | E × E | n, where n denotes a numeric-literal token, allows 2 + 3 × 5 to group as either 2 + (3 × 5) or (2 + 3) × 5. In this example, separate expression, term and factor nonterminals can preserve the string language while enforcing multiplication precedence. A parser selecting one tree does not establish that the original grammar was unambiguous.

References: [3] [2] [5]

Language specifications often use BNF or EBNF-style notation: named rules, quoted literal symbols, alternatives, repetition and optional parts. The notation must be read according to the document's definitions. Similar-looking rules need not have identical formal interpretations.

In particular, alternatives in a context-free grammar differ from ordered choice in a parsing expression grammar, or PEG. PEG tries alternatives in sequence and does not try a later alternative after an earlier one succeeds, so changing their order can change recognition. Python's PEP 617 discusses this distinction alongside parser and AST construction. A grammar description and the algorithm that processes it are related, but should not be treated as interchangeable.

References: [2] [4]