CSCD 420 Nov 19 2026
Overview
Chris Cain surveys compiler stages, showing how a simple program moves from tokens through context-free grammar parsing, semantic type checking, intermediate code, optimization, and machine code. He then compares exponential exhaustive parsing with CYK's cubic-time approach and introduces top-down LL parsing, focusing on the FIRST function and how it identifies possible leading terminals for grammar symbols.
Key takeaways
- A compiler checks different kinds of correctness in stages: parsing detects syntax errors, while type checking catches semantic mismatches such as passing a string to a method expecting a float.
- Implicit conversions, such as passing an int to a float parameter, are compiler-design choices rather than behavior guaranteed identically by every compiler.
- Intermediate code limits each operation to at most three memory addresses, making complex expressions easier to translate into assembly instructions.
- Code optimization can remove repeated calculations, such as reusing a + b across multiple assignments instead of generating duplicate intermediate operations.
- Exhaustive grammar parsing can be exponential, while CYK uses stored partial derivations to parse in cubic time; LL and LR methods aim to make parsing more efficient where grammar structure allows.
- FIRST sets summarize which terminals can begin strings derived from a grammar symbol; for the worked grammar, FIRST(S) is {a, b, c}.
Chapters
- An assignment is due that night; review sessions are planned for Monday and Tuesday, with an exam after Thanksgiving break.
- The class is continuing compiler topics, beginning with tokenization: a DFA maps input characters to tokens, which are then classified as keywords, variables, or constants.
- Chris Cain plans to contrast compilation and interpretation in a short video during the next class.
- The example language has a main method containing a sequence of assignment or print statements.
- The sample program assigns 4 to a and 8 to b, then prints a + b.
- A grammar can use non-terminals such as program, sequence, line, variable, and integer, while leaving expression undefined for the exercise.
- The grammar must include terminals for keywords and symbols, such as main, parentheses, and the assignment operator.
- The example grammar defines a program as main followed by a sequence of one or more lines.
- Each line is either an assignment, such as variable = integer, or a print statement containing an expression.
- A parse tree derives the sample program by expanding program, sequence, and line into the exact assignments and print expression.
- A program is syntactically valid if production rules can derive its token sequence from the start non-terminal; parsing errors arise when no production matches.
- Type checking follows syntax analysis and detects semantic problems, including argument types that do not match a method's parameters.
- Passing a string to a method expecting a float is treated as an error because the compiler cannot safely infer the intended conversion.
- Passing an int where a float is expected may be accepted through an implicit conversion, as in Java.
- Whether conversions are permitted is a compiler-design decision, so different compilers may handle the same language construct differently.
- Type checking works in both directions: context from outer scopes can indicate an expected type, while evaluating an expression reveals the type it produces.
- A mismatch, such as expecting a string when an expression evaluates to a float, can be detected before intermediate code generation.
- Intermediate code breaks complex expressions into simpler operations that reference at most three memory addresses.
- For example, sum = a + b + c becomes temp1 = a + b followed by sum = temp1 + c.
- The optimizer can eliminate repeated work, such as computing a + b twice for sum = a + b + c and sum2 = a + b + d.
- Compiler optimization can make inefficient-looking source code execute more efficiently by simplifying its intermediate representation.
- The final code-generation stage maps intermediate operations to a target instruction set, such as assembly.
- The operation temp1 = a + b can become register moves, an addition instruction, and a move of the result back to temp1.
- A symbol table records identifiers, including variable and function names, declared types, and scope-related information.
- Scanning adds recognized identifiers to the table; parsing can determine a variable's type from its grammatical context, such as an int declaration.
- Type checking consults the table to validate assignments, variable conversions, and function arguments.
- Syntax errors occur when tokens cannot match a grammar production; line numbers and IDE squiggles are driven by compiler diagnostics, often surfaced through the IDE.
- Brute-force parsing explores possible production rules and can scale exponentially when a grammar offers multiple choices.
- CYK reduces the search by storing partial derivations and checking which non-terminals can produce substrings, achieving cubic time.
- Cubic parsing is still costly for large inputs, so more efficient methods are useful for many programming-language grammars.
- Parsing approaches divide into top-down methods, including exhaustive search and LL, and bottom-up methods, including CYK and LR.
- A top-down derivation starts at the grammar's start non-terminal and repeatedly expands non-terminals until it produces the target string.
- A bottom-up parse starts from the input terminals and replaces matching right-hand sides with left-hand-side non-terminals until it reaches the start symbol.
- The example grammar derives the string a a b c b c through a leftmost derivation and reverses productions to illustrate bottom-up parsing.
- When several productions could apply, bottom-up parsing also needs a way to choose among alternatives; CYK handles that search systematically in cubic time.
- LL and LR parsing use FIRST and FOLLOW information to help resolve which production to apply without exhaustive search.
- FIRST of a grammar symbol is the set of terminals that can begin strings derived from that symbol; for a terminal such as a, FIRST(a) is {a}.
- For a non-terminal, FIRST sets are built iteratively by taking the union of possible first terminals across its productions.
- The pseudo-code initializes non-terminal FIRST sets as empty, includes lambda where applicable, and repeatedly adds terminals found through production right-hand sides.
- For the example grammar, the production S → aSB contributes a to FIRST(S) because its right-hand side begins with terminal a.
- The alternative production through non-terminal A contributes b and c after expanding A's possible leading symbols.
- The resulting set is FIRST(S) = {a, b, c}, corresponding to strings in the language that can begin with each of those terminals.
- Chris Cain closes by returning to FIRST sets in the next class, as a foundation for implementing LL parsing.
Transcript excerpt
0:00 20. >> All right, we are getting started. Reminder, we have an assignment due tonight. We're going to be reviewing Monday and Tuesday of next week and then we'll take an exam the day we get back from Thanksgiving break. So, that's why I got that study guide to you early so that you can do some pre-review studying. Make sure you have some questions. I do have some practice problems that we can go over in class, but that will probably only take about half of the cumulative time that I want to have for review. So come, please come prepared with questions if you can fill up the remainder of that time. >> Any questions on schedule? >> Yeah.
0:51 >> Mentioned every day but tomorrow. What are we doing tomorrow? >> Continuing lecture. >> Okay. >> So, we have two more days of content getting as far as we can. Probably not quite getting deep enough to be able to reveal the LL parsing project. So, that will have to come after Thanksgiving. >> Does that not count as revealing it right there? >> I mean, revealing it on Canvas and having enough material dulged for you to you to be able to implement it successfully. All right, we are in the middle of talking about the compilation process. And I guess I'm just thinking about this now, but there's actually something. Maybe I should do this back in the other classroom where I know the sound is set up correctly. So maybe we'll do this
1:37 tomorrow. There's a short video that I wanted. It's 3 minutes. I want to show people on the difference between compilation and interpretation because I think that's an important thing to know as as a computer scientist. I haven't built it into these slides, but it's
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Chris Cain.