| CS 331 Spring 2009 > Midterm Exam Topics |
The midterm exam will be given in class on Wednesday, March 18. It will be worth 75 points. The exam will cover all the material of the class from the beginning through Friday, March 6.
Referring to books, notes, electronic devices, or other people during the exam will not be permitted.
Here is a summary of the topics covered on the exam. This is not a complete list of the facts you need to know, but rather of the ideas you need to know about. Exactly what you need to know about them is not all here. See the text, slides, and my “notes” pages.
Important terminology is shown in boldface.
This topic was a quick run through of Chapter 1 in the text. In particular:
This material came from Chapter 3 in the text.
We began with an overview of the topic, as well as terminology:
Then we talked about grammars. I introduced Chomsky’s Hierarchy, which is not in the text. See the Additional notes from 1/26. In this class, we concentrate on context-free grammars; we also touch on regular grammars.
Grammar related terminology:
We discussed parse trees, ambiguity and how to (sometimes) eliminate it, how to represent various language features in a grammar, in particular, precedence and associativity of operators.
Backus-Naur Form, or simply BNF is a formal standard for writing grammars. It has various extensions; we discussed one we called EBNF.
An attribute grammar is a way of representing various language requirements (e.g., type compatibility) that are difficult or impossible to represent in a CFG. Sometimes such requirements are referred to as static semantics. Terms: attribute, synthesized, inherited, and intrinsic, decorating the parse tree.
More precisely: dynamic semantics. We looked at three methods, none of which is entirely satisfactory:
Strictly speaking, all this is syntax analysis. We generally separate out lexical analysis (know why!).
How do we specify the lexical structure of a language? State machines vs. regular expressions. Automatically generated vs. manually written code.
Computational power required is usually at the level of a regular grammar.
Computational power required is usually at the level of a CFG.
Syntax analysis = parsing. What does a parser do? Top-down parsing vs. bottom-up parsing. Computational complexity (time efficiency) of various parsing algorithms (and what about using an ambigious grammar?).
Recursive-descent parser, LL grammar, problem with left-recursive grammar rule.
LR parsers and LR grammars. Terminology: handle, phrase, simple phrase. Shift-reduce algorithms, table-based.
About the language:
The basics:
Lists & Loops
I/O:
Types, type classes, monads:
| CS 331 Spring 2009: Midterm Exam Topics / Updated: 7 Mar 2009 / Glenn G. Chappell / ffggc@uaf.edu |
|