CS 4337 — Programming Language Paradigms, Homework 2

Download PDF

Show a parse tree for string aacacab according to the following grammar, where the start symbol is

Given the grammar, draw a parse tree for the sentence if (A > D) if (B = D) C = E else C = F

Consider the following grammar, which of the following sentences are in the language generated by this grammar? Explain your answer

abcd

Yes. Since and , S can reach all the terminals without creating other nonterminals

acccbd

No. It is not possible to genrate a “” after a “”

acccbcc

Yes. All of the characters can be reached in order

acd

No. It is not possible to generate an empty , and so the first is unable to make a string less than 4 characters long.

Rewrite the following BNF to give + precedence over * and force + to be right associative

Convert the following BNF to EBNF.

Write the EBNF descripiton for the C switch statement

Rewrite the following EBNF grammar in BNF

Consider the following BNF grammar

Prove that this grammar is ambiguous.

This grammar is ambiguous. Take the following string: . It in unclear if the parse tree should take or

Convert this grammar into an unambiguous grammar.

Consider the following BNF grammar for a language with two infix operators represented by # and $. Note The order of the rules in a grammar is not significant.

What is the associativity of the # operator?

Right associative.

What is the associativity of the $ operator?

Left associative.

Which operator has higher precedence?

#

The grammar is

Both left and right recursive

Draw a parse tree for the string: