Java Reference
In-Depth Information
6. Run your solution to Exercise 5 through any LL(1) parser generator to
verify that it is actually LL(1). How do you know that your solution
generates the same language as the original grammar?
7. Show that every regular language can be defined by an LL(1) grammar.
8. A grammar is said to have
cycles
if it contains a nonterminal A such that
A
⇒
+
A (this derivation notation, covered in Chapter 4, means that A
derives itself using at least one step). Show that an LL(1) grammar must
not have cycles.
9. Recall that an LL(k) grammar allows
k
tokens of lookahead. Construct
an LL(2) parser for the following grammar:
1 Stmt
→
id ;
2
|
id(IdList);
3 IdList
→
id
4
|
id , IdList
10. Show the two distinct parse trees that can be constructed for
if expr then if expr then other else other
using the grammar given in Figure 5.17. For each parse tree, explain the
correspondence of then and else.
11. In Section 5.7, it is established that LL(1) parsers operate in linear time.
That is, when parsing an input, the parser requires
on average
only a
constant-bounded amount of time per input token.
Is it ever the case that an LL(1) parser requires more than a constant-
bounded amount of time to accept some particular symbol? In other
words, can we bound by a constant the time interval between successive
calls to the scanner to obtain the next token?
12. Design an algorithm that reads an LL(1) parse table and produces the
corresponding recursive-descent parser.
13. An
ambiguous grammar
can produce two distinct parses for some string
in the grammar's language. Explain why an ambiguous grammar is
never LL(
k
)forany
k
, even if the grammar is free of common prefixes
and left recursion.
