[HD] EECS4302 F26 - 2026-10-29 (Thursday) - Lecture 13
Overview
Jackie Wang reviews logistics for the 10% ANTLR 4 programming test, then introduces context-free grammars through production rules, derivations, parse trees, and language-design exercises. The lecture compares two expression-grammar designs, showing how grammar structure determines whether invalid expressions become syntax errors or parse successfully and require type checking.
Key takeaways
- ANTLR 4 programming-test preparation should focus on writing a context-free grammar in a .g4 file, generating parser code, building a standalone Eclipse project, and exporting a runnable Java executable.
- A context-free grammar combines recursive productions with terminating base cases; its parse tree’s left-to-right leaves form the generated terminal string.
- The binary-palindrome grammar uses P → ε | 0 | 1 | 0P0 | 1P1, while the language wwᴿ excludes the one-symbol base cases.
- Separating arithmetic, relational, and logical grammar categories can prevent some invalid operand combinations during parsing, while a broader grammar enables more informative errors through a later type-checking pass.
- A parse tree must derive the entire input string; for 1 + 2 ⇒ 5 / 4, implication is the top-level operation and the two arithmetic expressions are its operands.
Chapters
- The programming test is Thursday, November 5, from 4:00 to 5:20 PM in William Small Centre 105.
- The test is worth 10% of the course grade; students should confirm their ECS login works before arriving.
- The test requires Eclipse, a standalone project, a student-written .g4 grammar, and compilation and export of the compiler.
- ANTLR 4 tokens will be provided, so the main grammar-writing task is defining the context-free grammar.
- The test format will resemble the practice test; repeating Assignment 2 and reviewing the ANTLR 4 tutorial are recommended preparation.
- Students should practice generating ANTLR skeletons, refreshing generated files, building model classes, and exporting and running the Java executable.
- The mock session is Monday, November 2, from 3:30 to 4:30 PM in Lassonde Building 102B, with Jackie Wang and a teaching assistant available.
- Remote lab instructions provide setup commands for practice, but test-day command instructions will be supplied; the test uses the visitor pattern, not embedded Java grammar actions.
- Parsing turns the lexer’s token sequence into a parse tree, following the earlier introduction to parsers.
- Context-free grammars describe recursive string patterns that regular expressions cannot express, such as matching numbers of symbols on either side of a marker.
- The first variable is the start variable, and an arrow defines a production rule that replaces a variable with a string.
- Productions with only terminals provide base cases; productions containing variables provide recursive cases, and grammar rules do not perform semantic analysis.
- A leftmost derivation begins at the start variable and always expands the leftmost variable remaining in the string.
- For the example language with equal numbers of 0s and 1s around a hash, repeated applications of A → 0A1 add matching symbols.
- Applying the terminating production A → B, followed by B → #, produces strings such as 000#111.
- A derivation ends when the result contains terminals only, making it a string in the grammar’s language.
- A parse tree starts with the grammar’s start variable at its root, with each parent-to-children expansion representing a production rule.
- Unlike textual leftmost derivations, parse-tree construction does not require expanding variables in a particular left-to-right order.
- Reading the leaves from left to right yields the generated string, such as 000#111 in the matching-zero-and-one example.
- Parse trees and derivations will both support the later discussion of ambiguous grammars.
- For palindromes over {0, 1}, the base cases are P → ε, P → 0, and P → 1.
- The recursive productions P → 0P0 and P → 1P1 add matching symbols at both ends.
- These rules generate examples such as 00, 010, and 0110 while preserving the defining forward-and-reverse equality.
- Organizing base cases before recursive cases can make a grammar easier to inspect.
- The language wwᴿ requires a word followed by its reverse; unlike the palindrome grammar, it does not allow a single-symbol string.
- Its grammar can reuse the palindrome construction while removing the one-symbol base cases, distinguishing it from the full palindrome language.
- For strings built from blocks where each run of zeros is followed by at least as many ones, A describes one block and S describes a concatenation of blocks.
- A → ε | 01 | 0A1 | A1 handles a block, while S → ε | AS allows zero or more blocks.
- A proposed grammar must generate exactly the strings in the language described by the requirements.
- To show a grammar is wrong, find a counterexample that it generates but the specified language excludes.
- To show two language descriptions differ, identify a string that belongs to one but not the other.
- For written grammar questions, use standard context-free production rules rather than regular-expression shortcuts such as * or +.
- Version one uses Expression productions for integer and Boolean constants, unary operations, binary operations, and parenthesized expressions.
- A single BinaryOperation category groups arithmetic operators such as + and *, relational operators such as < and =, and logical operators such as ∧ and ⇒.
- Integer constants can be supplied as lexer tokens defined with regular expressions, while the grammar handles recursive expression structure.
- Because the grammar groups operator categories broadly, it can accept expressions such as adding two Boolean-valued comparisons.
- Version two separates expressions into Arithmetic, Relational, and Logical categories instead of placing all binary operators under one broad rule.
- Arithmetic operators take arithmetic operands, and relational operators compare arithmetic expressions.
- Logical operators combine logical expressions, while logical expressions may include relational expressions and Boolean constants.
- This structure rejects some ill-typed combinations during parsing, but may produce a syntax error where version one would build a parse tree.
- With version one, an expression such as (3 = 4) + (6 > 7) is syntactically accepted even though adding Boolean values is invalid.
- Version one therefore needs a later type-checking pass, which can use the visitor pattern to inspect the completed parse tree and report a targeted error.
- Version two can reject the same kind of expression as a syntax error because its grammar restricts operand categories.
- Language designers must choose between broader parsing with custom semantic diagnostics and stricter grammar rules that may rely on ANTLR’s syntax-error reporting.
- For 1 + 2 ⇒ 5 / 4 under version one, the root should expand to a binary operation for implication.
- The implication’s left and right Expression subtrees must derive the full operands, 1 + 2 and 5 / 4.
- Starting with only a parenthesized subexpression is incomplete if it leaves the rest of the input uncovered; a valid parse tree must account for the entire string.
- The expression has a parse tree but contains a type error because 1 + 2 is not a Boolean antecedent; Assignment 2’s solution and the practice test are priorities before the assessment.
Transcript excerpt
0:05 All right. So, uh, your assignment number two was due, uh, midnight yesterday. Hopefully, everybody submitted. I'm going to release the solution to assignment number two. So, you can take a look. I'll do that uh, Friday. Okay? Uh, shortly after lunchtime, I'll make sure I do it. So, you can definitely take a look. But don't worry, your programming test is no way going to be like that difficult as assignment too. That one just really for you to have some idea how you can build compiler but I'll talk about your programming test in just one moment. Uh don't forget for your minimizing DFA uh exercise the solution is already there. I show you on Tuesday already. Oh so sorry forgot to switch to iPad. Okay so the solution is already there and then okay your programming test uh it's going to be during the lecture time next Thursday November 5th. All right. So,
0:54 here's the important thing, right? About the uh location. Okay. So, there are two lab tests. Uh one will be optional like a mockup test on Monday. I'll talk about it maybe a second. Okay. Let's talk about the actual programming test. If you go to the e-class and then under programming test right here, okay, if you look at the guide, right, first of all, let's open the guide. I'll just refer you to some highlights. I can speak to you more in the actual mockup test in case you can make it. Okay? [snorts] So, it's going to be next Thursday, November 5th, uh from 4 PM to 5:20. You definitely got the whole uh entire duration, right? Not 75, you got 18 minutes. Okay? So, try to be there early. If I'm able to start you guys, uh just let you log in, etc. So, don't
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, Jackie Wang.