Transcript Chapter 1

Exam 1 Review
Questions
CS 3360
Spring 2011
BNF
Consider the following BNF grammar.
<sym-exp> -> <symbol> | <s-list>
<s-list> -> ( ) | ( <sym-exp-list> )
<sym-exp-list> -> <sym-exp> | <sym-exp> <sym-exp-list>
<symbol> -> x

Is the string ( x ( ) ) in the language described by the above
grammar? Either show how to derive the string from the nonterminal <sym-exp> or briefly explain why no derivation is possible.
2
BNF (Cont.)
Consider the following BNF grammar.
<sym-exp> -> <symbol> | <s-list>
<s-list> -> ( ) | ( sym-exp-list )
<sym-exp-list> -> <sym-exp> | <sym-exp> <sym-exp-list>
<symbol> -> x

Rewrite the grammar in E-BNF to reduce the number of rules
3
BNF (Cont.)

Given the following language fragment described in EBNF:
<statement> ::= <if-stmt> | <assign-stmt>
<assign-stmt> ::= <ident> := <expression>
<if-stmt> ::= if (<cond-expr>) <statement> [else <statement>]
Consider the statement:
if (a > b) if (a == 10) c := 1 else c := 2
The above grammar has a problem. Identify the problem and
demonstrate it by showing how the if statement is parsed using the
grammar. Explain how, in practice, this problem is solved.
4
Attribute Grammars

Consider the following BNF grammar that defines a bag of elements,
where each element is either x or y. Define an attribute grammar to
permit only those bags that have more x's than y's; e.g., x, xyx, and
xyxyx are sentences of the new language, but y, xy, and xxyyy are
not.
<bag> -> <elems>
<elems> -> <elem> | <elem> <elems>
<elem> -> x | y
5
AspectJ
Consider the following Java method.
long fibo(int x) {
return x <= 2 ? 1 : fibo(x – 2) + fibo(x – 1);
}

Define pointcuts:
(1) to denote all calls to fibo
(2) to denote only recursive calls to fibo
(3) to denote only non-recursive calls to fibo
6
AspectJ (Cont.)

Define an aspect to print an error message when the fibo function is
called with a negative argument.

Define an aspect to return factorial numbers instead for nonrecursive calls to fibo with the probability of 0.5.
(Hint: Use Math.random() to generate a random number
in [0.0, 1.0))
7