CQUPT CSI 311. Spring 2018. Assignment 2 - BNF
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 perators ==, !=, =, >.
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 example, 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.