COMS W4115
Programming Languages and Translators
Lecture 13: Midterm Review
March 4, 2015

1. What you should know for the midterm

1. The different kinds of programming languages
• Lecture 1
2. The basic elements of programming languages
• Lecture 2, ALSU Chs. 1 and 2
3. The structure of a compiler
• Lecture 3, ALSU Chs. 1 and 2
4. The structure of a compiler
• Lecture 3, ALSU Chs. 1 and 2
5. Regular languages, regular expressions, finite automata
• Lectures 3 and 4, ALSU Ch. 3 except for Sect. 3.9
6. Implementing a lexical analyzer
• Lectures 4 and 5, ALSU Ch. 3 except for Sect. 3.9
7. Context-free grammars and languages
• Lectures 6 and 7, ALSU Ch. 4 except for Sect. 4.7
8. Top-down parsing
• Lecture 8, ALSU Chs. 2 and 4 except for Sect. 4.7
9. Bottom-up parsing
• Lectures 9 and 10, ALSU Ch. 4 except for Sect. 4.7
10. Syntax-directed translation
• Lecture 11, ALSU Chs. 2 and Ch. 5 except for Sect. 5.5
11. Generating abstract syntax trees
• Lecture 12, ALSU Ch. 5 except for Sect. 5.5

2. Automata and language theory background

• Regular languages
• Finite automata
• Regular expressions
• Closure properties of regular languages
• Decision properties of regular languages
• Pumping lemma for regular languages and its uses
• Context-free languages
• Context-free grammars
• Parse trees, derivations, and ambiguity
• Pushdown automata and deterministic pushdown automata
• Closure properties of CFLs
• Decision properties of CFLs
• Pumping lemma for CFLs and its uses
• Syntax-directed translation
• Syntax-directed definitions and translation schemes
• Attribute grammars, inherited and synthesized attributes
• S-attributed and L-attributed SDDs
• Generating abstract syntax tress

3. Deterministic context-free grammars and languages

• LL1) grammars
• Every LL(1) grammar is unambiguous.
• Every LL(1) grammar can be parsed top down by a deterministic predictive parser.
• There are LL(1) grammars that are not SLR(1), for example

S → AaAb | BbBa
A → ε
B → ε

• Every LL(1) is an LR(1) grammar.
• No left-recursive grammar is LL(1).


• LR(1) grammars
• The class of languages generated by LR(1) grammars is exactly the same as the class of deterministic context-free languages.
• Yacc will generate a deterministic shift-reduce parser with no parsing action conflicts for any LALR(1) grammar.
• Every SLR(1), LALR(1), and LR(1) grammar is unambiguous.
• Every SLR(1) grammar is LALR(1) but not the other way around.
• Every LALR(1) grammar is LR(1) but not the other way around.
• There are SLR(1) grammars that are not LL(1), for example

S → SA | A
A → a

• There are context-free languages (the inherently ambiguous CFLs) that have no unambiguous grammar.
• Determining whether a context-free grammar is ambiguous is an undecidable problem.