Transcript CISC 471 First Exam Review Game Questions

CISC 471 First Exam Review
Game Questions
Overview 1
• Draw the standard phases of a compiler for
compiling a high level language to machine
code, showing the input and output forms for
each phase.
Overview 2
• State 2 advantages of using an interpreter
instead of a compiler for implementing a
language.
• State 2 advantages of using a compiler instead
of an interpreter for implementing a language.
Overview 3
• What are the roles of a:
– Preprocessor
– Assembler
– Linker ?
Lexical Analysis 1
• Demonstrate that you understand the
difference between a token and a lexeme,
through an example.
• Give an example of a language feature that
makes scanning nontrivial.
Lexical Analysis 2
• Give a regular expression that represents
exactly the set of decimal numbers that
contain at least one digit representing the
whole number part, no sign, and if there is a
decimal point, then at least one digit to the
right of the decimal point. Also, 0. is illegal.
Lexical Analysis 3
• Show the partitioning of the input string
below given the following flex spec rule set:
a*b
bba+c
aaba
b|c
Input: abaabbaabaaaabbbccaabbaaba
CFG 1
Show an equivalent Context free grammar for
the regular expression:
S -> (A | B)* BA|C
A -> DA | w
B -> w | x
C -> CD | D
D -> y
CFG 2
• Show that E -> E + E | w is an ambiguous
grammar.
• How would you rewrite the grammar to
remove the ambiguity if + is left associative?
CFG 3
• Show a leftmost derivation for the string (a,a)
with the grammar:
S-> (L) | a
L-> L,S | S
Explain the difference between an abstract
syntax tree and a concrete syntax tree and
justify why most compilers use abstract syntax
trees.
Parsing 1
Explain and show an example of two properties
of grammars that cause problems for topdown
parsers, and require rewrites or special rules
in the yacc file.
Name the two different ways that are used to
build top-down parsers.
Parsing 2
Write the recursive descent routine for the
following nonterminal:
D -> D , id | id | ε
Parsing 3
Explain the actions of an LR bottom up parser
for:
Shift
Reduce
Explain how the parser determines the state to
put back on top of the stack after a Reduce.
Semantic Analysis 1
• Give 3 different examples of errors that are
caught by semantic analysis and cannot be
caught by the first two phases.
• Explain the difference between inherited and
synthesized attributes.
Semantic Analysis 2
Show the attributed tree for -101 with the rules:
Semantic Analysis 3
• Why is it a nice property to have an attribute
grammar that has only synthesized attributes?
• Why is a circular attribute grammar a bad
property?