CS 331 Spring 2013
Quiz Topics Before the Midterm

Below are all of the possible quiz topics that were posted on the class webpage prior to the Midterm Exam.

• Give an example of something immutable in C++.
• Give an example of a (formal) language.
• There are generators and there are recognizers. Which is generally more useful, and why?
• Given a grammar and a string in the language it generates, write a derivation for the string.
• Given a simple grammar, describe the language it generates.
• Given a regular grammar, construct a finite automaton based on it.
• Given a regular expression (in the limited syntax described in class) and a string, determine whether the R.E. matches the string.
• Given a regular expression, describe the language it generates.
• Given a description of a regular language, write a regular expression that generates it.
• What is a “context-free language”?
• What does it mean for a grammar to be ambiguous?
• Why are we interested in CFLs?
• Why do we split parsing into the lexical-analysis and syntax-analysis phases?
• Given a simple CFL, write a BNF/EBNF grammar for it.
• What is a “lexeme”?
• Explain the difference between keywords and reserved words.
• Why does a lexer typically not need to store the lexemes it finds (in a data structure or file)?
• What is a “state machine”?
• What does it mean for a software package to be “robust”?
• What is an “LL grammar”? An “LR grammar”?
• Explain why bottom-up parsing algorithms often go through the steps necessary to produce a rightmost derivation.
• Briefly explain how a Recursive-Descent parser works.
• Suppose a certain grammar involves ten terminal symbols and five nonterminal symbols. If we write a Recursive-Descent parser based on this grammar, how many parsing functions will it have? Or some similar question.
• What major category of parsers do Recursive-Descent parsers lie in? What does this mean? Note: There are multiple correct answers to this question.
• What major category of parsers do Shift-Reduce parsers lie in? What does this mean? Note: There are multiple correct answers to this question.
• Explain the “shift” and “reduce” operations performed by a Shift-Reduce parser.
• What is an LL(2) parser? What is an LL(2) language?
• Why is lookahead generally a more worthwhile strategy for top-down parsers than for bottom-up parsers?
• What is the time complexity (order) of the Recursive-Descent algorithm? Of the Shift-Reduce algorithm?
• What kind of typing does Haskell have?
• What is “implicit” typing?
• Haskell is “lazy”. What does this mean?
• Suppose I have a function foo. I want to call it with parameters 2 and 5. In C++ this is “foo(2, 5)”. How is it written in Haskell? Or some similar question.
• In C++ I signal the beginning and end of a block with braces (“{”, “}”). Each statement ends with a semicolon (“;”). In Haskell I can do much the same thing, but I am not required to. What other method can I use?
• C++ has no rule for distinguishing names of variables from names of types. Haskell does. What is it?
• Describe Python’s type system. In what ways is it the same/different from that of C++? In what ways is it the same/different from that of Haskell?
• How do we indicate the end of a statement in Python?
• How do we indicate the end of a block in Python?
• How do we indicate the start & end of a comment in Python?
• What is a Python “dictionary”?
• How does a Python function declaration begin?