Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 361

Fall 2022

MIDTERM 2

1. Compilation process

What are the stages of the compilation process? Explain each stage in 1-2 sentences. In particular, describe the purpose, input and output at each stage. You can present your answer visually.

Note: The number of rows in the table is not a hint!

2. BNF Grammar

We consider the following BNF grammar that recognizes sentences.

sentence -> subject predicate

subject -> article noun

predicate -> verb direct-object

direct-object -> article noun

article -> THE | A

noun -> MAN | DOG

verb -> BITES | PETS

a. What is the start symbol of this grammar?

b. What are the terminals of this grammar?

 

c. What are the non-terminals of this grammar?

 

d. Show that THE DOG BITES A MAN is a legal term using a parse tree.

 

e. Show that THE DOG BITES A MAN is a legal term using a rightmost derivation.

 

3. BNF Grammars and Regular Expressions

Let us consider the grammar G below.

S -> cb | cSb

S is a non terminal.  

c and b are terminals.

a. Provide 4 examples of expressions recognized by G.

 

b. What is the language described by G? in plain English - understandable by everybody

 

c. Can this language be described by a regular expression? Explain your answer.

Yes / No

Explanation:

d. Provide us with a BNF grammar that recognizes integers that are divisible by 10.

e. Provide us with a regular expression that recognizes integers that are divisible by 2.

f. Provide us with a regular expression that recognizes identifiers defined as a sequence of letters and digits beginning with a lower letter. Examples: aA2 is an identifier. Aa2 is not an identifier. 12 is not an identifier.

 

4. KAY

In this exercise, you will use the handouts and code describing Kay.

a. How many separators are there in Kay?

b. What are the tokens in Kay? How many tokens are there?

 

c. Syntax error. Are there syntax errors in the following Kay program? How many? If yes, describe the syntax error(s).

void main(){

  int i = 5

}

Yes / No

How many?

Explanation

d. Syntax error. Is there a syntax error in the following Kay program? If yes, describe the syntax error.

main{

integer i;

i := 5

}

Yes / No

How many?

Explanation

e. Write a Kay program. Write a Kay program that computes the sum of the n first even natural numbers.

 

f. Lexical syntax of Kay. What is the output of the lexical analysis for the following JAY program? 

main{

  integer i;

  i := 5;

}

Output

g. Concrete syntax of Jay. Using the concrete syntax of Jay, draw the concrete syntax tree for the following Jay program.

main{

  integer i;

  i := 5;

}

Concrete syntax tree