|
|
|
Parsing
Exercises
- Define
a little language for describing finite state automata.
The language should allow you to define states and transitions
including identifying start and accept states and labeling of
transitions. Give an ANTLR spec for your language.
Implement and test your scanner/parser combination on examples
shown in lecture and others of your choosing.
- Take the following "+" and "*" expression grammar
E : E + E | T
T : T + T | F
F : int | ( E )
and implement it in ANTLR. ANTLR will tell you that
the grammar is left-recursive. You can eliminate
that recursion simply by replacing the left-most non-terminal in the recursive
rules with the right-hand side of the alternative production for that
non-terminal, e.g.,
E : T + E | T
- What does ANTLR tell you now?
- How can you transform the grammar to resolve this problem?
- What options can you enable in ANTLR to resolve the ambiguity without transforming the grammar?
- Does the option yield the same parse tree as the transformed grammar?
- Solve Exercises 4.2.1 in Dragon book (page 206).
- Solve Exercises 4.2.3 in Dragon book (page 207).
- Solve Exercises 4.3.1 in Dragon book (page 216).
- Solve Exercises 4.4.3 in Dragon book (page 231).
Reading
- ANTLR documentation
- Dragon, 4.1-4.4, 4.8
- StaticJava.g ANTLR spec for SJC
Materials
Parsing Basics
Top Down Parsing
Bottom Up Parsing (brief overview)
ANTLR
Examples
In the compiler SVN repository, check out the project
compiler-examples. This project contains a series of
ANTLR examples that implement different variations on the
grammars we studied in the
Top Down Parsing
slides. Each example has a separate ANTLR input
and set of JUnit tests; note that these tests write their output to stdout,
which for Eclipse is the console window.
Be adventurous in modifying these examples to try different formulations
of the grammar.
Be even more adventurous in exploring the capabilities of ANTLRworks. In particular, the Debugger is amazingly useful in helping you understand how the parse proceeds and how the parse tree is constructed. Note that when the "backtrack" option is enabled the Interpreter mode of ANTLRworks doesn't work - but the Debugger mode still works correctly.
|
