Homework #2 Solution



1) Write a regular expression to capture Java’s long literals in base 16 and then construct a finite-state automation for it.

2) Consider the following grammar:

<E> ::= a <B> | b <A> | ε

<A> ::= a <E> | b <A> <A>

<B> ::= b <E> | a <B> <B>

1. Write a leftmost derivation for the string a b a a b b.

2. Show the parse tree for the string a b a a b b.

3. Describe in English the language that the grammar generates.

3) Consider the following grammar for expressions:

<expr> ::= <expr> + <term> | <term>

<term> ::= <expr> * <factor> | <factor>

<factor> ::= id

1.Show that the grammar is ambiguous.

2.Provide an alternate unambiguous grammar that defines the same set of expressions.

4) Consider the grammar

S -> ( L ) | a

L -> L, S | S

1. Re-write the grammar in the EBNF notation.

2. Write a recursive-descent parser based on the EBNF notation.

(a) A number consists of digits from 0 to 9. For example, 1234 is a number. Give two different grammars to define a number, one using a left-recursive rule and the other using a right-recursive rule.

(b) A decimal number can be defined as a number followed by a decimal point (.) and another number. For example, 123.045 is a decimal number. Define attributes and write an attribute grammar to compute the value of any decimal number.