CS 631, Fall 2009


Assignment #3: 10 points

Date Due: Friday, 9/25/09


	Read Sections 2.7, 3.1, 3.3 and Lex documentation.

(4)  1.	Compile and test the C implementation of the infix to postfix 
	expression translator described in sections 2.5-2.7.  The files 
	are available on the class website in the aho/postfix directory.
	Note that the translator implementation is based on an extension of
	the expression grammar in Figure 2.23 and the psudocode of Figure 
	2.25, to which multiplication and division operators have been added.**

        (a) Construct a set of test expressions that use every grammar
            production at least once in some expression.  Indicate
            where each production is used.
        (b) Draw the parse trees for each test expression.
        (c) Hand in the output from the translator for each expression.
        (d) Comment on the error handling capabilities of the translator.

(2) 2.	Exercise 3.3.3(a,d).  Explain your answers.

(2) 3.  Using concise (no more than 6 words) English, accurately describe
        the languages defined by the following regular expressions:
        (a)  (A|B|...|Z)(a|b|...|z)*
        (b)  1*01*01*

(2) 4.  Write Lex regular expressions for the following patterns.
        Use auxiliary definitions where convenient.

        (a) The set of english words having the letters a, e, i, o,
            and u appearing in that order, but not necessarily consecutively.
        (b)  All strings of digits that represent odd numbers
             with no leading zeros.


      **For full credit, turn in commented program listings and the
	output of the computer runs for this problem.