Java Reference
In-Depth Information
5. Describe the language denoted by each of the following grammars:
(a) (
{
A
,
B
,
C
},{
a
,
b
,
c
},∅,
A)
(b) (
{
A
,
B
,
C
},{
a
,
b
,
c
},{
A
→
BC
},
A)
(c) (
{
A
,
B
,
C
},{
a
,
b
,
c
},{
A
→
Aa
,
A
→
b
},
A)
(d) (
{
A
,
B
,
C
},{
a
,
b
,
c
},{
A
→
BB
,
B
→
a
,
B
→
b
,
B
→
c
},
A)
6. What are the di
culties associated with constructing a grammar whose
generated strings are decimal representations of irrational numbers?
7. A grammar for infix expressions follows:
1 Start
→
E$
2 E
→
TplusE
3
|
T
4 T
→
T times F
5
|
F
6 F
→
(E)
7
|
num
(a) Show the leftmost derivation of the following string.
num plus num times num plus num $
(b) Show the rightmost derivation of the following string.
num times num plus num times num $
(c) Describe how this grammar structures expressions, in terms of the
precedence and left- or right- associativity of operators.
8. Consider the following two grammars.
(a)
1 Start
→
E$
2 E
→
( E plus E
3
|
num
(b)
1 Start
→
E$
2 E
→
E ( plus E
3
|
num
Which of these grammars, if any, is ambiguous? Prove your answer by
showing two distinct derivations of some input string for the ambiguous
grammar(s).
