CST 8152 - Pre-Final Exam Review Material

Numbers in parentheses refer to the course text chapter sections.

This is a quick combination of several sets of review questions; there is much redundant material:

• Be familiar with the notational conventions for context-free grammars (4.2).

• Error handling: Aho p. 11; and section 4.1
• Symbol table routines: Aho p. 11; 72, 77 (insert, lookup); early parts of section 7.6 discuss implementation and efficiency issues.
• Postfix Converter (as an example of embedding action symbols in a grammar): Aho section 2.3, p.33; example 2.8, section 2.5
• Aho sections 2.1, 2.2: parsing, syntax definition, context free grammars, parse trees, ambiguity, associativity, precedence
• 2.4: top-down parsing, predictive parsing, function of lookahead, FIRST sets, designing a predictive parser
• Recursive Descent parsing functions: Fig 2.24, 2.27, 2.28
• Matching statements by using reserved words: Fig 2.34
• 4.1: role of the parser, error recovery, nature of syntax errors
• Parts of section 4.2: Context Free Grammars, terminology and notation, ambiguity
• Parts of section 4.3: how are grammars built?
• Parts of section 4.4: recursive-descent parsing, predictive parsers, transition diagrams
• Error handling: Aho p. 11 and section 4.1

• What is an ambiguous grammar? Show that a grammar is ambiguous. (2.2)
• List and describe various types of error recovery in a Parser (4.1)
• Write a function that implements panic mode error recovery in a language that uses ';' to separate statements.
• Modify the panic() function to stop on commas as well as semicolons.
• What are Aho's three goals of an error handler in a parser? (4.1)
• Of what use are reserved words to a predictive parser?
• What are the four components of a Context Free Grammar? (2.2)
• Show how parse trees for left- and right-associative grammars differ. (2.2)
• Write a parse tree for a given sentence and grammar.
• What is a parse tree? (2.2)
• Why not use a CFG to define the lexical syntax of a language, instead of using regular expressions? (4.3)
• Describe some methods of error repair and recovery.
• Describe four error recovery strategies. (4.2)

• Given a Grammar (possibly one you have never seen), construct a Parse Tree that shows how a sentence in the language is recognized (2.2, 4.2, 4.4), e.g. 3 * A + 7 * B + 9
• Given a Grammar (possibly one you have never seen), and a Scanner that returned the next Token, derive the simple C Language functions for a recursive descent parser that would recognize each of the production rules in the grammar, e.g. functions similar to statement(), assignment(), print(), dump(), expression(), factor(), term(), etc.

• Define briefly (4.2,4.5): handle, leftmost (rightmost) derivation, shift, reduce, ambiguous grammar, left (right) recursion, a sentential form, a sentence
• Given a grammar and a sentence in the language defined by the grammar, show the rightmost and leftmost derivations of the sentence. Show the parse trees corresponding to the two derivations.
• What is meant by an "LL" parser? What is an "LR" parser?
• Is top-down parsing LL or LR? What about bottom-up parsing?
• Can a top-down parser handle: (1) left-recursive grammars? (2) right-recursive grammars?
• Know how to recognize left recursion in a grammar (2.4, 4.3). Know how to eliminate immediate left recursion from a grammar (p.176). Why would one want to do this?
• Why use a stack to locate handles in shift-reduce parsing? (4.5)

• Define briefly (8.1, 9.1, 9.2): intermediate representation, target language, quadruple notation, triple notation (p.470)
• How are constants handled in a compiler if only addresses or names can be pushed on the value stack?
• Why use an Intermediate Representation (IR)? Why not generate the target language (machine code) directly?
• Name the three forms of IR described in class.
• With respect to code generation , why must the symbol table contain both the type and the address of a name? Why is the type necessary?
• Given the following expression, show the IR quadruples that might be generated when the code is compiled. Variables i,j,k are integer; x is floating-point:
  i = j * k + j * x
• What changes are needed in the data structures of your interpreter to turn it into a compiler?
• How do the semantic functions (e.g. execute(op)) differ between an interpreter and a compiler?

• Define briefly: backtracking, predictive parsing, recursive-descent parsing, grammar production, terminal symbol, non-terminal symbol, top-down parsing, bottom-up parsing, semantic action symbols, translation scheme, token, look ahead token, white space, lexeme, value stack, panic-mode recovery, phrase-level recovery, error productions, unary minus.
• Why can’t a recursive-decent parsing function be written for the following grammar rule?
  <expr> --> <expr> ‘+’ <term> (Hint: Try to write the function.)
• Define and document a C language data structure that would hold one element of the symbol table needed for Assignment 5.
• Define and document a C language data structure implementing the global data returned by the scanner() in Assignment 5.
• What are three goals of the error handler in a parser?
• Describe four levels at which errors may occur in a program. Which level has been given the most attention by compiler writers and why?
• Statistically, are the errors that occur in real programs simple or moderately complex?
• What is the difference between error recovery and error repair in a parser?
• Why not quit the parser upon finding the first error?
• Briefly describe three error recovery methods for a parser.
• How can a parser distinguish between different statement types in a language, e.g. between for() and while()
• statements?
• Draw a block diagram showing the difference between an interpreter and a compiler.
• List some advantages of an interpreter over a compiler.
• List some disadvantages of interpreters.
• Why are loops so difficult for interpreters?
• How can the scanner differentiate between “subtract” and “unary minus”?
• How can the parser differentiate between “subtract” and “unary minus”?
• Write a recursive descent parsing function that implements any of the grammar productions in the Toy Grammar from the notes. No semantic actions are required; the functions need only recognize the input.
• Write pseudocode functions that show what code is needed to write a recursive descent parser, with semantic actions, for the following simple grammar of assignment statements:
  <stmt> -> ID ‘=’ <item> ‘;’
  <item> -> ID