CS3150 Assignment 1

CS3150 Assignment 1

3.)Rewrite the BNF of Example 3.4 to give + precedence over * and force +

to be right associative.

<assign> → <id> = <expr>

<id> → A | B | C

<expr> → <expr> * <term> | <term>

<term> → <factor> + <term>| <factor>

<factor> → (<expr>) | <id>

5.) Write a BNF description of the Boolean expressions of Java, including

the three operators &&, ||, and ! and the relational expressions.

Write a BNF description of the Boolean expressions of Java, including

the three operators &&, ||, and ! and the relational expressions.

<Boolean_expr> → <Boolean_expression> || <Boolean_term> | <Boolean_term>

<Boolean_term> → <Boolean_term> && <Boolean_factor> | <Boolean_factor>

<Boolean_factor> → id | ! <Boolean_factor> | (<Boolean_expr>) | <relation_expr>

<relation_expr> → id == id | id !=id | id < id | id <= id| id >= id | id > id

7.) Using the grammar in Example 3.4, show a parse tree and a leftmost

derivation for each of the following statements:

a.) A = ( A + B ) * C

<assign> => <id> = <expr>

=> A = <expr>

=> A = <term>

=> A = <factor> * <term>

=> A = (<expr>) * <term>

=> A = (<expr> + <term>) * <term>

=> A = (<term> + <term>) * <term>

=> A = (<factor> + <factor> ) * <term>

=> A = (<id> + <term>) * <term>

=> A = ( A + <term>) * <term>

=> A = (A + <factor>) * <term>

=> A = (A + <id>) * <term>

=> A = (A + B) * <term>

=> A = (A + B) * <factor>

=> A = (A + B) * <id>

=> A = (A + B) * C

b.)A = B + C + A

<assign> => <id>=<expr>

• A=<expr>
• A=<expr>+<term>
• A=<expr>+<term>+<term>
• A=<term>+<term>+<term>
• A=<factor>+<term>+<term>
• A=<id>+<term>+<term>
• A=A+<term>+<term>
• A=A+<factor>+<term>
• A=A+<id>+<term>
• A=A+C+<term>
• A=A+C+<factor>
• A=A+C+<id>
• A=A+C+A

c.) A = A * (B + C)

<assign> => <id>=<expr>

• A=<expr>
• A=<term>
• A=<term>*<factor>
• A=<factor>*<factor>
• A=<id>*<factor>
• A=A*<factor>
• A=A*(<expr>)
• A=A*(<expr>+<term>)
• A=A*(<term>+<term>)
• A=A*(<factor>+<term>)
• A=A*(<id>+<term>)
• A=A*(B+<term>)
• A=A*(B+<factor>)
• A=A*(B+<id>)
• A=A*(B+C)

d.) A = B * (C * (A + B))

<assign> => <id>=<expr>

• A=<term>
• A=<term>*<factor>
• A=<factor>*<factor>
• A=<id>*<factor>
• A=B*<factor>
• A=B*(<expr>)
• A=B*(<term>)
• A=B*(<term>*<factor>)
• A=B*(<factor>*<factor>)
• A=B*(<id>*<factor>)
• A=B*(C*<factor>)
• A=B*(C*(<expr>))
• A=B*(C*(<expr>+<term>))
• A=B*(C*(<term>+<term>))
• A=B*(C*(<factor>+<term>))
• A=B*(C*(<id>+<term>))
• A=B*(C*(A+<term>))
• A=B*(C*(A+<factor>))
• A=B*(C*(A+<id>))
• A=B*(C*(A+B))

12.) Consider the following grammar:

<S> → a <S> c <B> | <A> | b

<A> → c <A> | c

<B> → d | <A>

Which of the following sentences are in the language generated by this

grammar?

a. abcd

OK Derivation: <S> => a <S> c <B> => abc <B> => abcd

b. acccbd

NO, the letter c must be before d

c. acccbcc

NO, only a's can be placed before b

d. acd

NO, two or more c's before d

e. accc

OK, Derivation <S> => a <S> c <B> => a <A> c <B> => acc <B> => acc <A> => accc

13.) 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 but a, abb, ba, and aaabb are not.

<S> → ab | a <S> b