CS 410: Homework 2

Fall 2006 [Bono]
Due: Friday, Sept. 29, 2006, by 2pm to receptionist in Sal 300

Problem 1

Consider the following grammar: 
A --> x A x
    | y
What is the language defined by the grammar? If it is regular, describe it with a regular expression; if not, give a description in English.

Problem 2

Show that the following grammar is ambiguous: 
A --> A x B 
    | x

B --> x B
    | x

Problem 3

Consider the following grammar 
A --> x A1 y
    | z
Write semantic rules to compute the boolean attribute A.evenx, which is true if and only if the sentence parsed has an even number of x's. For the purposes of this problem consider 0 an even number.

Note: multiple instances of a non-terminal in a production above are subscripted to distinguish them.

Problem 4

Consider the following grammar with numbered productions 
1) E --> E x T
2) E --> E x
3) E --> y T
4) T --> y T
5) T --> z
Construct the SLR parsing tables for the grammar. In particular, show the following:
  1. The augmented grammar
  2. The DFA to recognize viable prefixes, including the set of items for each state.
  3. The FIRST and FOLLOW sets for all the non-terminals
  4. The action and goto tables

The University of Southern California does not screen or control the content on this website and thus does not guarantee the accuracy, integrity, or quality of such content. All content on this website is provided by and is the sole responsibility of the person from which such content originated, and such content does not necessarily reflect the opinions of the University administration or the Board of Trustees