CQUPT CSI 311. Spring 2018. project 2 – BNF


Due: EOD before Discussion 4.


Your submission should be in the form of MS Word file (MAC users need to save a document created in Pages as a MS Word .doc or .docx file).


You may use textbook, lecture slides, and materials from your discussion to solve the problems below. You may also discuss this with your classmates. But you should submit your individual work. If you are suspected cheating (coping your classmate’s or somebody’s else work) your grade will be zeroed. Consider the risk to learn and to earn nothing vs. learning and earning at least something if you do your work yourself.




1. (10%) Write BNF descriptions for a C/C++ for-loop statement.


2. (24%) Write a BNF description of the Boolean expression in Java, including the three operators &&, ||, and !, and the relational expressions with operators ==, !=, <, <=, >=, >.


3. (10%) Assume there is following grammar in BNF:


->=-> A | B | C->+|*| (

Using the above grammar show a parse tree and a leftmost derivation for each of the following statements: A = A * (B + ( C )).



4.  (10%) Describe, in English, the language defined by the following grammar in BNF



->    -> a  | a  -> b  | b-> c| c




5.  (15%) Consider the following grammar in BNF:



-> a  c  |  | b  -> c  | c  -> d |


Which of the following sentences are in the language generated by this grammar? Explain your answers.

a) abcd

b) acccbd

c) acccbcc

d) acd

e) accc



6. (16%) Given the following gramma in BNF:



->=-> A | B | C->+|->*|-> () |




a) Rewrite the given grammar to give + precedence over * and force + to be right associative.

b) Rewrite the given grammar to add ++ and – – unary operators of Java



7. (15%) Write a grammar for the language consisting of strings that have n copies of the letter a followed by the same number of copies of the letter b, where n > 0. For ple, the strings ab, aaaabbbb, and aaaaaaaabbbbbbbb are in the language nut a, abb, ba, and aaabb are not.

Draw parse trees for the sentences aabb and aaaabbbb, as derived from the grammar.