Top-down parsing: FIRST, FOLLOW and LL(1) (Compiler Design)

Cheat sheets

CD-04Cheat sheet1 pageIn a paid pack

Ambiguity and Grammar Clean-up

Context-free grammar vocabulary for parsing: sentential forms, leftmost and rightmost derivations, parse trees and ambiguity, with script-counted parse trees for the classic ambiguous grammars. How precedence and associativity are built into a grammar with one non-terminal per level. Removal of immediate and indirect left recursion with the general algorithm and worked results, left factoring step by step, and why neither transformation removes ambiguity: the left-factored dangling-else grammar still has an LL(1) conflict.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Compiler Design cheat sheet pack.

CD-05Cheat sheet1 pageIn a paid pack

FIRST and FOLLOW

The two fixed-point procedures for FIRST and FOLLOW written as ordered steps, FIRST of a string of symbols, and the rules that trip students: ε lives only in FIRST, $ only in FOLLOW, and the copy rule runs from the head into the last non-terminal. Worked sets for the LL(1) expression grammar with the FOLLOW sets shown pass by pass, a chain of nullable symbols, an original grammar where nullable symbols expose later terminals, and the FOLLOW of a start symbol that also appears inside a body. All sets come from a script.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Compiler Design cheat sheet pack.

CD-06Cheat sheet1 pageIn a paid pack

LL(1) Tables and Predictive Parsing

The LL(1) condition for every pair of alternatives, the procedure that fills M[A, a], and the full table for the expression grammar. A complete predictive-parsing trace of id + id * id with stack, input and action, recursive descent as one procedure per non-terminal, panic-mode recovery with synchronising sets, signals that rule out LL(1) at a glance, a script-found conflict, and LL(1) facts that past questions test.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Compiler Design cheat sheet pack.