Context-Free Grammar — Fixing Ambiguous Parser Failures

Every time you hit compile and your IDE catches a missing semicolon before running a single line, a CFG is quietly doing that job. Compilers for C, Java, Python, SQL — every one of them is built on top of a formal grammar that precisely defines what 'valid code' looks like. CFGs aren't an academic curiosity; they're the load-bearing wall of language design.

Before CFGs existed, language recognizers were brittle, hand-coded state machines that couldn't handle nested structures like balanced parentheses or recursive function calls. Regular expressions — powerful as they are — can't count. They can't verify that every opening brace has a matching closing brace. CFGs solve exactly this problem by introducing recursive production rules that can describe arbitrarily deep nesting with a handful of compact rules.

By the end of this article you'll be able to write your own CFG for a mini expression language, trace through a derivation by hand, build a recursive-descent parser from those production rules in Java, spot ambiguity before it bites you in production, and answer the CFG questions that senior compiler-track interviewers love to ask.

What is Context-Free Grammar?

A CFG is a set of rules that describe how to form strings in a language. Each rule has a single non-terminal on the left and a sequence of terminals and non-terminals on the right. The key insight is recursion — a rule can refer to itself, allowing you to describe nested structures like parentheses or nested if-statements.

Let's look at a concrete example. The language of balanced parentheses can be described with just two rules: S → ( S ) S → ( ) That's it. With these two rules you can generate any string of properly balanced parentheses, no matter how deep. Try doing that with a regular expression — you can't. That's why every programming language uses a CFG: because real code has nested structures (blocks, expressions, function calls) that require counting and matching.

In production, the grammar is the contract between the developer and the compiler. If the grammar is ambiguous or incomplete, the parser will reject valid code or accept invalid code. That's why language specifications are written as formal grammars — it's the only way to be unambiguous about what is and isn't allowed.

The name 'context-free' means the rule for expanding a non-terminal doesn't depend on where it appears — no surrounding context needed. That's what makes CFGs both powerful (they can describe recursion) and tractable (efficient parsers exist). The trade-off: context-sensitive features like variable declarations must be handled in later compiler phases.

package io.thecodeforge.cfg;

// A simple CFG representation in Java
public class CoreExample {
    public static void main(String[] args) {
        String language = "Context-Free Grammar";
        System.out.println("Learning: " + language);
        System.out.println("Balanced parens example: S -> ( S ) | ( )");
    }
}

Formal Definition of a CFG

Each production rule describes how a non-terminal can be replaced by a string of terminals and non-terminals. The term 'context-free' means the rule applies regardless of the surrounding symbols — no context is needed. This is what allows nesting and recursion, but also introduces ambiguity when multiple rules can expand the same non-terminal in conflicting ways.

Let's dissect that with a real example. For a simple arithmetic grammar: V = {Exp, Term, Factor} Σ = {+, , (, ), num} R = { Exp → Exp + Term | Term, Term → Term Factor | Factor, Factor → ( Exp ) | num } S = Exp

Notice how Exp can rewrite to itself plus a Term — that's left recursion, which is fine for bottom-up parsers, but top-down parsers require elimination. Also notice the precedence hierarchy: multiplication is one level below addition, so it binds tighter.

In a production grammar, you'll often have dozens or hundreds of non-terminals. A real language like Java has around 80 non-terminals and hundreds of productions. Managing that by hand is error-prone — that's why parser generators like ANTLR and Bison exist. The trade-off is learnability: parser generators hide the complexity but you must understand conflicts and precedence to debug them.

package io.thecodeforge.cfg;

import java.util.*;

public record GrammarDefinition(
    Set<String> nonTerminals,
    Set<String> terminals,
    Map<String, List<List<String>>> productions,
    String startSymbol
) {
    public GrammarDefinition {
        nonTerminals = Set.copyOf(nonTerminals);
        terminals = Set.copyOf(terminals);
        productions = Map.copyOf(productions);
    }

    public boolean isNonTerminal(String symbol) {
        return nonTerminals.contains(symbol);
    }

    public boolean isTerminal(String symbol) {
        return terminals.contains(symbol);
    }

    public List<List<String>> getProductionsFor(String nonTerminal) {
        return productions.getOrDefault(nonTerminal, List.of());
    }

    public static GrammarDefinition balancedParensGrammar() {
        Set<String> nonTerminals = Set.of("S");
        Set<String> terminals = Set.of("(", ")");
        Map<String, List<List<String>>> productions = new HashMap<>();
        productions.put("S", List.of(
            List.of("(", "S", ")"),
            List.of("(", ")")
        ));
        return new GrammarDefinition(nonTerminals, terminals, productions, "S");
    }
}

Derivations and Parse Trees

A derivation is a sequence of production rule applications that starts with the start symbol and ends with a string of only terminals. Each step replaces one non-terminal with the right-hand side of a matching production. The resulting structure can be visualised as a parse tree, where the root is the start symbol, internal nodes are non-terminals, leaves are terminals, and children of a node correspond to the symbols in the production used.

Leftmost derivation always replaces the leftmost non-terminal; rightmost derivation always replaces the rightmost. Both produce the same parse tree for an unambiguous grammar. Parse trees are the foundation of syntax-directed translation: compilers attach semantic actions to tree nodes.

Here's a concrete derivation for the string "2 + 3" using our arithmetic grammar: Exp → Exp + Term (leftmost) → Term + Term → Factor + Term → 2 + Term → 2 + Factor → 2 + 3

The parse tree would have Exp at root, with children Exp, +, Term. And so on. In production, you don't usually build the full parse tree — you build an Abstract Syntax Tree (AST) that prunes away unnecessary nodes like single-child productions. That's a memory savings of 40-60% on typical code.

When you debug a parser, tracing the derivation is often the fastest way to find why certain inputs fail. Tools like ANTLR's -trace option output the derivation steps, which is invaluable.

package io.thecodeforge.cfg;

import java.util.*;

public class ParseTree {
    private final String symbol;
    private final List<ParseTree> children;

    public ParseTree(String symbol, List<ParseTree> children) {
        this.symbol = symbol;
        this.children = children;
    }

    public static ParseTree fromDerivation(String start, Map<String, List<List<String>>> prods) {
        // Simplified: builds tree from leftmost derivation steps
        // In practice, the parser outputs this structure
        return new ParseTree(start, List.of());
    }

    public void print(String indent) {
        System.out.println(indent + symbol);
        for (ParseTree child : children) {
            child.print(indent + "  ");
        }
    }

    // Add method to compute AST by removing single-child nodes
    public ParseTree toAST() {
        if (children.size() == 1 && children.get(0).children.size() > 0) {
            return children.get(0).toAST();
        }
        List<ParseTree> astChildren = new ArrayList<>();
        for (ParseTree child : children) {
            astChildren.add(child.toAST());
        }
        return new ParseTree(symbol, astChildren);
    }
}

Ambiguity in CFGs and How to Resolve It

A grammar is ambiguous if some string in its language has more than one distinct parse tree (or equivalently, more than one leftmost derivation). Ambiguity is a serious problem in compilers because it means the same source code can have multiple meanings — the compiler cannot choose which one is intended. Classic examples include the 'dangling else' problem in C-like languages and operator precedence for arithmetic expressions.

Resolving ambiguity: Restructure the grammar to enforce precedence and associativity. For example, instead of a single non-terminal for expressions, break it into multiple levels (Expr, Term, Factor). Use left recursion for left-associative operators. Parser generators like ANTLR also allow disambiguating predicates or semantic actions, but the cleanest solution is a non-ambiguous grammar.

Here's the classic ambiguous arithmetic grammar: E → E + E | E E | n For input "1 + 2 3", you get two parse trees: one treating it as (1+2)3, the other as 1+(23). That's a bug for any calculator. The fix is to introduce precedence levels as shown earlier.

In production, ambiguity can lead to security vulnerabilities. If an attacker can craft input that parses differently than intended, they might bypass validation. That's why SQL injection often exploits ambiguous grammar in SQL dialects.

package io.thecodeforge.cfg;

public class AmbiguityExample {
    // Ambiguous grammar: E → E + E | E * E | n
    // String "1 + 2 * 3" has two parse trees:
    // Tree1: (1 + 2) * 3
    // Tree2: 1 + (2 * 3)
    
    // Unambiguous version with precedence:
    // E → E + T | T
    // T → T * F | F
    // F → n | ( E )
    
    public static void main(String[] args) {
        System.out.println("Ambiguous: E → E+E | E*E | n");
        System.out.println("String '1+2*3' yields two parse trees.");
        System.out.println("Use precedence levels to disambiguate.");
    }
}

Writing a CFG for a Mini Expression Language

Let's design a small expression language that supports addition, multiplication, parentheses, and integer literals. We'll follow the standard precedence hierarchy (multiplication binds tighter than addition) and left associativity for both operators.

Grammar (unambiguous): Exp → Exp + Term | Term Term → Term * Factor | Factor Factor → ( Exp ) | num

This grammar ensures that '+' sees '*' as a subexpression on the right, so multiplication happens first. The left recursion ensures left associativity: '1 + 2 + 3' parses as ((1+2)+3). We'll also handle whitespace and negative numbers by making 'num' a terminal that includes optional minus sign (or separate unary minus later).

Extending this grammar is straightforward: add a new non-terminal for each new precedence level. For example, to add exponentiation (right-associative), you'd insert: Factor → Factor ^ Unary | Unary Unary → ( Exp ) | num

This pattern scales to any language. In real parsers like GCC, there are around 15 precedence levels for C expressions. Each level is a non-terminal.

One nuance: left-recursive rules are fine for bottom-up parsers (Bison) but cause infinite recursion in top-down parsers. For recursive descent, you'll transform left recursion into iteration (while loop) as shown in the next section.

package io.thecodeforge.cfg;

import java.util.*;

public class ExpressionGrammar {
    public static Map<String, List<List<String>>> buildProductions() {
        Map<String, List<List<String>>> prods = new LinkedHashMap<>();
        prods.put("Exp", List.of(
            List.of("Exp", "+", "Term"),
            List.of("Term")
        ));
        prods.put("Term", List.of(
            List.of("Term", "*", "Factor"),
            List.of("Factor")
        ));
        prods.put("Factor", List.of(
            List.of("(", "Exp", ")"),
            List.of("num")
        ));
        return prods;
    }

    public static void main(String[] args) {
        var prods = buildProductions();
        System.out.println("Production rules:");
        prods.forEach((k, v) -> {
            for (List<String> rhs : v) {
                System.out.println(k + " → " + String.join(" ", rhs));
            }
        });
    }
}

Building a Recursive Descent Parser in Java

A recursive descent parser is a top-down parser that directly mirrors the grammar's production rules. Each non-terminal becomes a method. For each production of that non-terminal, the method tries to match the input tokens sequentially. If one production fails, it backtracks (or uses lookahead to choose deterministically). For our expression grammar, we'll implement a simple version that uses a lookahead token (LL(1) with a single token peek) to decide between alternatives.

The parser consumes tokens from a lexer. Our methods: parseExp(), parseTerm(), parseFactor(). Each returns an AST node or performs actions. We'll keep it simple: evaluate the expression on the fly (calculator style). The code below demonstrates the structure.

Key observation: the left recursion in the grammar becomes a while loop in the parser. That's a standard pattern — instead of recursive calls, use iteration for left associative operators. This avoids stack overflows. The same pattern works for addition, multiplication, and other left-assoc operators.

In production, you'd probably use a parser generator. But knowing how to build a recursive descent parser by hand is invaluable when you're using a tool like ANTLR and need to understand what it generates.

package io.thecodeforge.parser;

import java.util.*;

public class RecursiveDescentParser {
    private final List<String> tokens;
    private int pos = 0;

    public RecursiveDescentParser(List<String> tokens) {
        this.tokens = tokens;
    }

    // Exp → Exp + Term | Term
    public int parseExp() {
        int val = parseTerm();
        while (match("+")) {
            int right = parseTerm();
            val += right;
        }
        return val;
    }

    // Term → Term * Factor | Factor
    public int parseTerm() {
        int val = parseFactor();
        while (match("*")) {
            int right = parseFactor();
            val *= right;
        }
        return val;
    }

    // Factor → ( Exp ) | num
    public int parseFactor() {
        if (match("(")) {
            int val = parseExp();
            expect(")");
            return val;
        }
        // Assume token is a number
        String token = consume();
        return Integer.parseInt(token);
    }

    private boolean match(String expected) {
        if (pos < tokens.size() && tokens.get(pos).equals(expected)) {
            pos++;
            return true;
        }
        return false;
    }

    private String consume() {
        if (pos >= tokens.size()) throw new RuntimeException("Unexpected end of input");
        return tokens.get(pos++);
    }

    private void expect(String expected) {
        String actual = consume();
        if (!actual.equals(expected))
            throw new RuntimeException("Expected '" + expected + "' but got '" + actual + "'");
    }

    public static void main(String[] args) {
        // Input: "2 + 3 * 4" -> tokens: ["2", "+", "3", "*", "4"]
        List<String> tokens = Arrays.asList("2", "+", "3", "*", "4");
        RecursiveDescentParser parser = new RecursiveDescentParser(tokens);
        int result = parser.parseExp();
        System.out.println("Result: " + result);  // Should be 14 (not 20)
    }
}