Part I: True/False Question and Justify Your Reason for Each False Statement. (20Pts)

CS4850

Fall 2011 (Oct 24, 2011)

Midterm Exam

Name ______

Part I: True/False Question and Justify your reason for each false statement. (20pts)

1. A compiler of a programming language can execute a program while parsing the program to find any syntax errors.

2.Aterminal symbol in a grammar can occur on the left hand side of a production rule.

3. If string ω that is a member of the language defined by grammar Gdoesn’t contain two distinct parse trees, then grammar G is not ambiguous.

4. In a grammar’s definition, there is no symbol that can be both a terminal symbol and nonterminal symbol simultaneously.

5.Name equivalence implies structure equivalence in terms of identical type.

6. A derivation and a parse tree are the two methods used to show why a string can be a member of the language defined by a grammar.

7. A language defined by a context free grammar is a subset of a language defined by regular grammar.

8. For production X → YZ, First(X) = First(Y) where X,Y,Z (N  T).

9. Regular expressions can be used to define terminals in a programming language.

10. In programming languages, primitive types such as Integer have a finite number of values.

Part II: Answer the following questions:

1. Answer the following question based on the following grammar: (25 pts)

Expr -> Term PLUS Expr | Term

Term -> Factor TIMES Term| Factor

Factor -> 0 | 1 | ….| 9

1). List all nonterminal symbols, terminal symbols, and the start symbol.

2) Draw the parse tree for string 0 PLUS 3 TIMES 5.

3) What associative is TIMES?

4) What is the precedence between PLUS and TIMES?

5) Revise the grammar so that the precedence of PLUS is higher than the precedence of TIMES.

6) Revise the original grammar to allow tokens ( and ). For example (0 PLUS 3) TIMES 5 is a valid string and show your parse for (0 PLUS 3) TIMES 5. (5 pts)

2. Design a grammar to accept the language: {am bn | 1 <= m <= n }

. (5 pts)

3. List four programming paradigms we have introduced in this class. (10 pts)

4. Show one useful scenario of dynamic scoping while many languages support static scoping. (5 pts)

5. Calculate the first sets based on the following grammar. (10 pts)

S -> | a | ( T )

T -> T, S | S

First(S)=

First (a)=

First(T) =

6. Consider the following program: (10 pts)

1 int h, i;

2 void B(int w) {

3 int j, k;

4 i = 2*w;

5 w = w+1;

6 ...

7 }

8 void A (int x, int y) {

9 float i, j;

10 B(h);

11 i = 3;

12 ...

13 }

14 void main() {

15 int a, b;

16 h = 5; a = 3; b = 2;

17 A(a, b);

18 B(h);

19 ...

20 }

1). For static scoping, show the stack of symbol tables at line 5.

2). For dynamic scoping, show the stack of the run-time symbol tables at line 5.

7. Give the reason of why the following grammar cannot solve the dangling else problem and use a specific string to illustrate your reason. (5 pts)

stmt -> unmatched_stmt

| matched_stmt

matched_stmt -> IF exp THEN matched_stmt ELSE matched_stmt

| O

Unmatched_stmt -> IF exp THEN stmt

exp -> E

8.i) Using a regular expression to represent the binary strings that do not contain 001. ii) use the left regular grammar to represent the above binary strings. (10 pts)

1