# CMPU-331 Compilers (Spring 2019)

## Written Examination

### Overview

The course has a single written examination. It focuses primarily on material from the textbook, though it will also touch on material covered in lectures.

The examination counts for 40% of your grade for the course.

### Logistics

#### Schedule

The examination will be a take-home exam. It will be made available at the end of class on Thursday, 25th April, and will be collected at the beginning of class on Tuesday, 30th April.

#### Reference Material

You **may** use:

- The course textbook.
- Any secondary reading material provided in class.
- Class lecture slides.
- Notes you have taken during lectures (hand-written or electronic).
- Any solutions or working-out for homework assignments.
- Notes from coaching hours or office hours.

You **may not** use:

- The Internet. At all. (Surpriseā¦)
- Other textbooks besides the course textbook.
- Your friends' exam paper.

#### Academic Integrity

This exam is provided as a take-home as I want to give you the best chance possible to do well. (This is also why there is no project work or homework scheduled for the week of the exam.)

### Examination Topics

This is a non-exhaustive but fairly comprehensive list of examination topics.

**Context-Free Grammars.**- Ambiguity and how to resolve it.
- Left recursion:
- Why it causes a problem for top-down parsing.
- How to resolve these problems.

- Left factoring.
- Leftmost and rightmost derivations.
- Parse trees and derivations.
- Programming language constructs which are not context-free (e.g. variable declaration, type constraints), and why.

**Syntax-Directed Translation.**- Attribute grammars.
- Syntax-directed definitions.
- Synthesised
*vs*inherited attributes. - Use of synthesised and inherited attributes.
- Translation schemas.
- Relations between DFS and translations.
- Forms of output from translation (e.g. intermediate code, AST).

**Lexical Analysis.**- Creating a DFA from a description.
- Relevance of token types to input.

**Parsing.**- Abstract syntax tree (AST)
*vs*parse tree. - Use of AST in semantic analysis.
- Top-down
*vs*bottom-up. - Definitions of LL, LR, SLR, LALR and what they mean.

**Top-Down Parsing and LL(***k*) Grammars.- General notion of the top-down parsing algorithm.
- Relation between grammar and contents of the parse stack.
- 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), etc.?

- Construction of FIRST and FOLLOW sets for a grammar.
- Construction of LL(1) parsing table.

**Bottom-up parsing and LR(***k*) Grammars.- General notion of reduction process, including use of handles.
- LR grammars:
- Is a grammar an LR(0), LR(1), etc. grammar?
- Is a grammar not LL(1) but LR(1)?
- Relation between right-most derivation and bottom-up parse (including moves and stack contents).

- LR parsing:
- LR parsing (shift-reduce) algorithm.
- Conflicts in parse table (shift-reduce, reduce-reduce) and how to correct them.
- 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 LR(1) parsing tables:
- What is different from SLR method?
- What problem does this solve in SLR? How does it solve the problem?
- Can a grammar be parsed using LR method but not SLR?
- Constructing the parse table from the sets of items.

- LALR parsing:
- Constructing item sets for LALR(1).
- Difference between LALR and SLR, LR(1).
- Constructing the parse table from the sets of items.

### Sample Papers

2002 examination and its solution.

2004 examination and its solution.

2005 examination and its solution.

2006 examination and its solution.

2007 examination and its solution.

2009 examination and its solution.