- At a high level, we can characterize a compiler as a sequence of stages:
lexical analysis, syntax analysis, semantic analysis, optimization, and
code generation. Describe each stage in one phrase each.
- Why do we use regular expressions to model a programming language's
concrete syntax and context-free grammars to model its abstract
syntax?
- What are the relative advantages and disadvantages of writing a
recursive descent parser and writing a table-driven parser.
- What do we mean when we say that a grammar is "ambiguous"?
Show two techniques for eliminating ambiguity from a grammar.
- Write regular expressions that define the strings in each of the
following languages:
- integers divisible by 5
- strings over the alphabet
{$, ¢, .,
0 .. 9}
that are legal descriptions of American money -- for example,
$43, $5.22, and
54¢
- Give a non-deterministic finite state machine that corresponds to this
regular expression:
a(a|b)*b | b(a|b)*a
Then give an equivalent deterministic finite state machine.
Use this grammar for the next four problems:
stmt := for identifier := expr to expr stmt
| print expr
expr := number
| identifier
- Define the abstract syntax for this grammar.
- Define the FIRST and FOLLOW sets for the grammar.
- Use your FIRST and FOLLOW sets to create the top-down parsing table
for this grammar.
- Use your parsing table to trace the operation of a table-driven parser
as it recognizes this token stream:
for i := 1 to n
print n