Exam Topics

Starred topics were not covered in class but could be on the exam.
 

*Syntax-directed translation (Section 2.3)

• syntax-directed definitions
• synthesized attributes
• translation schemes
• relation between depth-first traversal and translations

Context-free grammars

• regular expressions vs. CFGs
• ambiguity
• left-most and right-most derivations
• parse trees and derivations
• *eliminating ambiguity
• *verifying the language a grammar generates
• left recursion
• why it causes a problem for top down parsing
• eliminating left recursion
• left factoring*

Non-CFG constructs

• basic idea of what is not context-free (no need to do proofs)
• constructs in a programming language that are not context free, and why
• use of a declared variable
• procedure call

Top-down parsing and LL grammars

• relation between a left-most derivation and top-down parse (including moves and stack contents)
• LL grammars
• what makes a grammar not LL(1)
• is a certain grammar not LL(1) but LL(2)
• construction of FIRST and FOLLOW sets for a grammar
• construction of LL(1) parsing table
• *error recovery methods using FIRST and FOLLOW

Bottom-up parsing and LR Grammars

• construction of a non-deterministic bottom-up machine, given a grammar
• LR grammars
• is a grammar an LR(1) grammar
• is a grammar not LL(1) but LR(1)
• general notion of reduction process, use of handles
• relation between right-most derivation and bottom-up parse (including moves and stack contents)
• LR parsing algorithm
• construction of SLR parsing tables
• constructing sets of LR(0) items
• relation between sets of LR(0) items and DFA used for the parse
• constructing the parse table from the sets of items
• constructing canonical LR parsing tables
• what is different from SLR method
• how this solves the problem with SLR
• can a grammar be parsed using canonincal LR method but not SLR
• LALR parsing
• basic idea of difference between LALR and other methods
• *error recovery in LR parsing