CS 3723
Programming Languages 
Spring 2013
  Topics for Exam 1  

    * = favorite questions.

  1. Introductory Stuff. The 3 contrasts. What a language is. Question: Given a simple DFA or NFA, describe the language recognized by it.

  2. Finite State Machines. Question: Given a simple DFA, say how to simulate it.

  3. Lexical Analysis. What tokens are. Question: Give examples of typical tokens.

  4. Context-free Grammars. What a CF grammar looks like. The names of its parts. Leftmost and rightmost derivations. Able to work with example grammars. Question: Given a CF grammar and a sentence, produce a derivation sequence deriving the sentence.

  5. Ambiguous Grammars. Recognize ambiguity when you see it. Question: Given a grammar, shows that it is ambiguous. You need to do this by finding a sentence with two distinct parse trees, or with two distinct leftmost derivations, or with two distinct rightmost derivations. (Each of these is equivalent to the others.)

  6. Unambiguous CF Grammars. * Question: Given am unmabiguous grammar and a sentence derived from the grammar, construct the leftmost derivation for it and the parse tree (both unique).

  7. Reverse Polish Notation. What it is. * Question: Given an normal expression with single-digit operands, translate it to RPN notation. Or, given an RPN expression with single-digit operands, evaluate it. (For example, (3+4)*5$ is 34+5*$ in RPN.)

  8. Shift-Reduce Parsers. * Question: Given a grammar, an S-R table, and a sentence in the language generated by the grammar, use the grammar and the table to construct a rightmost derivation backwards.

  9. Semantic Actions. Adding code to the rules of the grammar in a S-R parser to cause something to be done. (Translation, say.)

  10. Recursive-Descent Parsers. Some of the basics.

Revision date: 2013-02-05. (Please use ISO 8601, the International Standard.)