A CONTEXT-FREE GRAMMAR IS A 4-TUPLE G = (V, T, P, S) V a finite set of VARIABLES (non-terminals), written in capitals T a finite set of TERMINALS — the alphabet of the language itself, disjoint from V P a finite set of PRODUCTIONS, each of the form A → α where A ∈ V and α ∈ (V ∪ T)* S the START SYMBOL, S ∈ V ── WHY "CONTEXT FREE" ────────────────────────────────────── THE LEFT-HAND SIDE OF EVERY PRODUCTION IS A SINGLE VARIABLE. That is the entire content of the name. A variable A may be replaced by α WHEREVER IT APPEARS, irrespective of what surrounds it — the surrounding CONTEXT is irrelevant, hence "context free". Contrast a CONTEXT-SENSITIVE production such as aAb → aαb which permits the replacement only when A sits between an a and a b. That restriction is what the next level of the Chomsky hierarchy adds. ── DERIVATION ────────────────────────────────────────────── Writing α ⇒ β means β is obtained from α by applying ONE production; α ⇒* β means zero or more steps. THE LANGUAGE GENERATED IS L(G) = { w ∈ T* : S ⇒* w } — the set of TERMINAL strings derivable from the start symbol. A string still containing variables is a SENTENTIAL FORM, not a sentence. LEFTMOST DERIVATION — always expand the LEFTMOST variable. RIGHTMOST DERIVATION — always expand the RIGHTMOST variable. BOTH EXIST FOR EVERY DERIVABLE STRING, and both correspond to the SAME parse tree. The distinction matters for parsing algorithms: top-down parsers (LL) construct leftmost derivations, bottom-up parsers (LR) construct rightmost derivations in reverse. ── WORKED EXAMPLE 1: BALANCED PARENTHESES ────────────────── S → ( S ) | S S | ε A leftmost derivation of ( ( ) ) ( ): S ⇒ S S ⇒ ( S ) S using S → (S) on the first S ⇒ ( ( S ) ) S again ⇒ ( ( ) ) S S → ε ⇒ ( ( ) ) ( S ) ⇒ ( ( ) ) ( ) THIS LANGUAGE IS NOT REGULAR — the pumping lemma of the last topic proves it — YET THE GRAMMAR IS THREE SHORT RULES. THAT GAP IS THE ENTIRE MOTIVATION FOR THE CHAPTER: recursion in the grammar supplies the unbounded memory that a finite automaton lacks, because the derivation can nest to any depth. ── WORKED EXAMPLE 2: aⁿbⁿ ────────────────────────────────── S → a S b | ε S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb EACH STEP ADDS ONE a AND ONE b SIMULTANEOUSLY, which is exactly how the grammar enforces the equality of counts that no finite automaton could maintain. ── WORKED EXAMPLE 3: ARITHMETIC EXPRESSIONS ──────────────── E → E + T | T T → T * F | F F → ( E ) | id THIS IS THE MOST IMPORTANT GRAMMAR IN THE TOPIC, and the layering is deliberate. THREE LEVELS OF VARIABLE ENCODE THREE LEVELS OF PRECEDENCE: · E (expression) handles +, the loosest-binding operator · T (term) handles *, which binds tighter · F (factor) handles parentheses and atoms, binding tightest Because * can only be introduced BELOW +, a multiplication can never span an addition, so id + id * id must parse as id + (id * id). AND THE RECURSION IS LEFT-RECURSIVE (E → E + T rather than E → T + E), WHICH MAKES + LEFT-ASSOCIATIVE: a − b − c groups as (a − b) − c, which is what arithmetic requires. PRECEDENCE AND ASSOCIATIVITY ARE THEREFORE PROPERTIES OF THE GRAMMAR'S SHAPE, not extra annotations — a fact that is examined often. ── DESIGNING A GRAMMAR ───────────────────────────────────── THE STANDARD PATTERNS: MATCHING PAIRS S → a S b | ε NESTING S → ( S ) | ε REPETITION S → a S | ε (right-recursive) S → S a | ε (left-recursive) UNION S → S₁ | S₂ PALINDROMES S → a S a | b S b | a | b | ε EQUAL COUNTS (in any order) S → a S b S | b S a S | ε THE METHOD: identify the RECURSIVE STRUCTURE of the language — what does a string look like in terms of smaller strings of the same language? — and write that directly as a production.

── THE CHOMSKY HIERARCHY ─────────────────────────────────── Four grammar classes, defined by restrictions on productions, each strictly contained in the next: TYPE 3 — REGULAR A → aB or A → a (right-linear) MACHINE: finite automaton Only one variable, at the end. No nesting possible. TYPE 2 — CONTEXT FREE A → α (single variable on the left) MACHINE: PUSHDOWN AUTOMATON — a finite automaton with a STACK, which is exactly the unbounded memory needed for nesting. TYPE 1 — CONTEXT SENSITIVE αAβ → αγβ, with |γ| ≥ 1 (never shortening) MACHINE: linear bounded automaton TYPE 0 — UNRESTRICTED α → β, α containing at least one variable MACHINE: TURING MACHINE THE CONTAINMENTS ARE STRICT: REGULAR ⊊ CONTEXT FREE ⊊ CONTEXT SENSITIVE ⊊ RECURSIVELY ENUMERABLE with the pumping lemmas providing the separating witnesses: aⁿbⁿ separates regular from context free, and aⁿbⁿcⁿ separates context free from context sensitive. ── WHAT CONTEXT-FREE GRAMMARS CANNOT GENERATE ────────────── { aⁿbⁿcⁿ } — THREE counts cannot be matched; a stack can compare two things, not three { ww : w ∈ Σ* } — a string repeated; the stack pops in reverse, so it can produce w wᴿ (a palindrome) but not w w { aⁿ : n prime } { aⁱbʲcᵏ : i < j < k } THE CHARACTERISTIC LIMITATION IS WORTH STATING PRECISELY: A STACK IS LAST-IN-FIRST-OUT, SO IT CAN MATCH ONE PAIR OF NESTED COUNTS BUT CANNOT COMPARE THREE, AND CANNOT REPLAY A STRING IN THE ORDER IT WAS READ. That single sentence explains every entry in the list above. ── THE PRACTICAL LIMITATION IN PROGRAMMING LANGUAGES ─────── A real and instructive consequence: MOST PROGRAMMING LANGUAGES ARE NOT ACTUALLY CONTEXT FREE, even though their syntax is specified by a CFG. Rules such as · "a variable must be declared before use" · "the number of arguments must match the function's declaration" · "types on both sides of an assignment must agree" ARE NOT EXPRESSIBLE IN A CFG — the first is essentially the ww problem, requiring the identifier at the use site to match one seen arbitrarily far earlier. THE ENGINEERING RESPONSE IS THE STANDARD COMPILER ARCHITECTURE: LEXICAL ANALYSIS — regular expressions handle tokens SYNTAX ANALYSIS — a CFG handles nested structure SEMANTIC ANALYSIS — a SYMBOL TABLE handles declarations, types and scope EACH PHASE USES THE WEAKEST FORMALISM THAT SUFFICES, and the things the formalism cannot express are pushed to the next phase. THAT LAYERING IS A DIRECT PRACTICAL APPLICATION OF THE CHOMSKY HIERARCHY, and it is why the theory is taught to engineers rather than only to mathematicians. ── SIMPLIFICATION OF GRAMMARS ────────────────────────────── Before most algorithms are applied, a grammar is cleaned up: 1. REMOVE USELESS SYMBOLS NON-GENERATING — variables from which no terminal string can be derived UNREACHABLE — symbols not reachable from S ORDER MATTERS: remove non-generating symbols FIRST, then unreachable ones. Doing it the other way can leave useless symbols behind, and this is a classic exam trap. 2. ELIMINATE ε-PRODUCTIONS (A → ε), except that S → ε is retained if ε ∈ L(G) 3. ELIMINATE UNIT PRODUCTIONS (A → B, one variable to another) 4. The result can then be put into Chomsky or Greibach normal form, as covered later in this section.