CS5318 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.


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


  1. 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.


  1. 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.


error: Content is protected !!