CS 456/656 Assignment 2

Due date: October 4, 2005, 4:00 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.
  1. Consider the following context-free grammar:
    • S -> empty string
    • S -> SaSb
    Write left-most and right-most derivations for the following strings:
    • ab
    • abaabb
  2. Work Exercise 2.4 on page 128 of your textbook.
  3. Let L be the language over {x,y,z,+,-,*,/,(,)} consisting of all strings over that alphabet which could be valid expressions in C++, with the restriction that all variable names consist of only one letter. The minus sign "-" can be used for both subtraction and negation. To simplify things, do not allow a unary plus sign: thus, for example, "+x" is not a valid expression.
    Design an unambiguous context-free grammar for that language which respects the semantics of C++, that is, such that the unique parse tree for each string permits an expression to be evaluated from the bottom up, using the precedence rules of C++. Your grammar should only be about one-fourth of a page long. Read this disclaimer.
  4. Give a parse tree for the string -x-y*-(x/z*y) using the grammar you designed in the previous problem.
  5. Work Exercise 2.9 on page 129 of your textbook.

Back to Course Page