← CSC 414 Compiler Construction
Syntax Analysis and Context-Free Grammars
Notes
Introduction to Parsing
Syntax analysis, or parsing, constitutes the second foundational phase of compilation. While the lexical analyzer validates the vocabulary of a program, the parser enforces its grammatical structure according to a specified Context-Free Grammar (CFG). The syntax analyzer takes the stream of tokens provided by the scanner and checks whether the sequence satisfies language rules. In doing so, it generates a hierarchical structural representation, traditionally an Abstract Syntax Tree (AST) or a concrete parse tree, while effectively flagging syntax errors with precise context.
Context-Free Grammars and Derivations
A context-free grammar is defined as a 4-tuple comprising non-terminal symbols, terminal symbols (tokens), a designated start symbol, and a set of production rules. Productions demonstrate how non-terminal symbols expand into strings of terminals and non-terminals. Derivations proceed either leftmost, where the leftmost non-terminal is continually expanded, or rightmost. Top-down parsers, including Recursive Descent and LL(1) parsers, attempt to construct parse trees from the root down to the leaves, using leftmost derivations. Conversely, bottom-up parsers, such as LR(0), SLR(1), and LALR(1) engines, employ shift-reduce mechanisms to condense leaves into the start symbol using reversed rightmost derivations.
Handling Ambiguity and Parse Trees
A grammar is formally ambiguous if it permits two or more distinct parse trees for the same input string. Ambiguity is detrimental to compilation because it introduces unpredictable semantic behavior, particularly in mathematical evaluations and nested conditional statements such as the dangling-else problem. Compiler designers eradicate ambiguity by introducing explicit operator precedence and associativity rules through stratified grammatical tiers.
Practical example
Consider creating a compiler front-end for a student registration domain-specific language used at a Kenyan university such as the University of Nairobi. The command string is: REGISTER CS414 FOR 2024 SEMESTER 1.
We specify the grammar productions:
S -> REGISTER UnitRef FOR SessionRef
UnitRef -> IDENTIFIER
SessionRef -> YEAR SEMESTER DIGIT
When the scanner outputs tokens: TOKEN_REGISTER, TOKEN_IDENT(CS414), TOKEN_FOR, TOKEN_YEAR(2024), TOKEN_SEMESTER, TOKEN_DIGIT(1), the predictive LL(1) parser evaluates the lookahead symbol. It begins with start symbol S, looks at TOKEN_REGISTER, and applies the production rule. It expands UnitRef by matching CS414, matches terminal TOKEN_FOR, and then expands SessionRef to match 2024, SEMESTER, and 1. If a student mistakenly writes REGISTER CS414 2024 SEMESTER 1, omitting FOR, the parser detects that lookahead TOKEN_YEAR does not match the expected terminal FOR, halts generation, and outputs a syntax error indicating a missing preposition.
Quiz
1. Which parsing approach starts at the leaves and repeatedly applies reductions toward the root start symbol?
2. What formal issue occurs when a context-free grammar allows multiple parse trees for a single token string?
3. In a context-free grammar definition, what role do terminal symbols play?
Sign in to submit and securely grade your quiz.