final exam
1. Write strict BNF for the following language constructs: a C++ class header; a while loop; a switch statement. Simplify your grammar by rewriting it using EBNF.
2. Describe why the following grammar is ambiguous. Correct the grammar.
S --> A | B A --> A + A | id B --> A - B | id id --> a | b | c
3. Identify the lexemes and tokens in the following BASIC program:
10 REM *** SAMPLE PROGRAM 20 LET X$ = "WELCOME TO MY BASIC PROGRAM" 30 PRINT X$ 40 LET Y = 10 50 END
4. Given the following grammar:
<program> --> begin <stmts> end <stmts> --> <stmt> | <stmt> ; <stmts> <stmt> --> <var> = <expr> <var> --> a | b | c | d <expr> --> <term> + <term> | <term> - <term> | <term> <term> --> <var> | literal-integer-value
Show a rightmost derivation to obtain the following valid sentence:
begin b = 10 ; c = 12 ; d = b + c end
Which of the following sentences are valid according to this grammar?
a. begin a = 10 end
b. begin a = 10 ; b = 12 ; end
c. begin b = 12 ; c = b + b end
d. begin c = 200 ; c = c - 1 ; d = c end
e. begin d = 1 ; e = d - 4 end
5. Given the following grammar:
S --> aB | aC | b B --> bc | cbB C --> cB | c
Which of the following sentences are generated by this grammar?
a. acbbc b. bb c. b d. bbb e. accbbbc f. accbbc g. ac
Show leftmost derivations to generate the following valid sentences:
a. acbcbcbbc
b. accbcbbc
c. abc
Does this grammar pass the pairwise disjointness test? Why or why not? If not, correct the grammar.
6. Write a grammar using strict BNF to represent a FOR...NEXT loop in BASIC, which looks like this for variable X:
50 FOR X = 1 TO 13 60 PRINT X 70 NEXT X
You can also count by a step value (e.g. 3) as follows:
50 FOR X = 1 TO 13 STEP 3 60 PRINT X 70 NEXT X
In general, a FOR...NEXT loop looks like this:
50 FOR VARIABLE = START TO END STEP STEP ... 60 STATEMENTS ... 70 NEXT VARIABLE
Show a derivation to generate the following code (skipping over line 80), then draw the parse tree:
70 FOR Y = 0 TO 100 STEP 5 80 PRINT Y 90 NEXT Y
Incorporate semantics information into the above grammar to transform it into an attribute grammar that ensures that the loop variable matches in both the FOR and the NEXT statements.
7. Given the following grammar:
E --> E + T | T T --> T * F | F F --> ( E ) | id
Show how the direct left recursion can be removed by rewriting the given grammar (rendering it suitable for an LL parser).
8. Given the following LR parse table (not shown here), show a complete parse, including the parse stack contents, input string, and action for the strings below (also not shown here).
9. Rewrite the following for loop using the operational semantics language described in Chapter 3.
for ( i = 1 ; i <= 100 ; i++ ) {
sum += i;
product *= i;
}
10. Rewrite the following expression using the operational semantics language described in Chapter 3.
int q = (y * 10) + (x * 20);
11. Given a LeBlanc-Cook symbol table implementation and the given C code (not shown here), number each scope, draw the hash table for each name, and show the scope stack at POINT A in the code.
12. Write Python code to ....
13. What is the exact output of the given Python code ....
14. What is the exact output of the given object-oriented C++/Java code (e.g. a Queue class) ....
15. Extend the given object-oriented C++/Java code to (e.g. a Queue class) ....
16. Write a Scheme function to ....
17. What is the exact output of the given Scheme code ....
18. Write a Prolog relation to ....
19. What is the exact output of the given Prolog queries ....
20. Given the Prolog knowledge base, is goal Z provable? If so, show using forward chaining. Also show using backward chaining.