Java Reference
In-Depth Information
See [Aho et al., 1975] for an introduction to YACC. The canonical open-source implemen-
tation of the LALR(1) approach to parser generation is given by [Donnelly and Stallman,
2011]. See [Burke and Fisher, 1987] for a nice approach to LALR(1) parser error recovery.
Other shift-reduce parsing strategies include both simple-precedence and operator-
precedence parsing. These are nicely discussed in [Gries, 1971].
3.7 Exercises
Exercise 3.1. Consult Chapter 18 of the Java Language Specification [Gosling et al., 2005].
There you will nd a complete specication of Java's context-free syntax.
a. Make a list of all the expressions that are in Java but not in j--.
b. Make a list of all statements that are in Java but not in j--.
c. Make a list of all type declarations that are in Java but not in j--.
d. What other linguistic constructs are in Java but not in j--?
Exercise 3.2. Consider the following grammar:
S ::=
(
L
)
j
a
L ::= L S j
a. What language does this grammar describe?
b. Show the parse tree for the string
(a()(a(a)))
.
c. Derive an equivalent LL(1) grammar.
Exercise 3.3. Show that the following grammar is ambiguous.
S ::=
a
S
b
S j
b
S
a
S j
Exercise 3.4. Show that the following grammar is ambiguous. Come up with an equivalent
grammar that is not ambiguous.
E ::= E
and
E j E
or
E j
true
j
false
Exercise 3.5. Write a grammar that describes the language of Roman numerals.
Exercise 3.6. Write a grammar that describes Lisp s-expressions.
Exercise 3.7. Write a grammar that describes a number of (zero or more)
a
's followed by
an equal number of
b
's.
Exercise 3.8. Show that the following grammar is not LL(1).
S ::=
ab
j A
b
A ::=
aa
j
cd
Exercise 3.9. Consider the following context-free grammar:
Search WWH ::
Custom Search