CS 651-451   Hour Exam Ideas     Oct 2009


These questions will form the basis of much of the hour exam (perhaps with slight modifications ;-)

1.  Regular Expressions and grammars

(Although we didn't spend much time on them, you are expected to know the basics of Regular Expressions)

1a.   My office room number is S-3-088.  The classroom is M-1-062.  Write a RE which describes valid room numbers for the Science center, McCormack, Quinn and Wheatley.   To make it more complex, let's say that rooms in the Science center can have an optional 'a' or 'b' after the room number, but this does not apply to any of the other buildings.

Assume all buildings have up to 4 floors (1 thru 4).   You may certainly use notation like "[a-z]".  You can abbreviate [0-9] as "dig" if you want.


1b.   Give an example of a language containing strings which cannot be "recognized" by an RE.  Give a CFG which can recognize it.


1c. Give an example of an "ambiguous" CFG.  Why is it ambiguous?-- give an example of a relevant input, and show the parse tree.  Fix the problem -- i.e., provide an alternative grammar for [essentially] the same language


2. PROJECT           NOTE:  for programs, don't bother with debug output or comments.

 ((this is not meant to be a trick question .. rather an opportunity to show you understand the homework project))

There will likely be a question about the project:  for example, how would you add a relational operator, such that one can write
    if (a+4 < b*5)
without additional parentheses.  Show the grammar, and also to code to build the relevant tree.  Would you need a new node type, or could you reuse an existing one?



3. GRAMMAR / PARSE

Consider the following grammar, using (hopefully) obvious terminals:
stmt ::= expr SEMI;
expr ::= NUM  |  op expr expr;
op   ::= PLUS | MINUS | TIMES | DIVIDE;
Here are some sample inputs
   + 2 - 3 + 4 5 ;
   + - + 2 3 4 5 ;
3a. what does the parse tree look like for each input?

3b. what value will be computed when this is executed, using the obvious interpretation of the operators and tree?
(i.e., what semantics are implied by this grammar)

3c. What input would correspond to the "normal" expression  (2 + 3) * (3 + 4)?

Now consider this input:
      +  *  2  3  4 ;

3d. Show the actions of an LR(1) parser while it is analyzing this input.  Use a table like we've talked about recently:  alternate lines,  first with two columns showing
    PARSER STACK(->TOP)                                NEXT SYMBOL
and the next showing, in one column,
                                        ACTION
and so on.

 (suggestion:  first draw the derivation or parse tree)


4. PARSER

Your job is to create a recursive-descent parser for the following application -- for which you'll first need to formalize with a BNF grammar.  The parser should build data structures.
 
Assume a scanner returning tokens which are words, PERIOD's, or any other categoryyou'd like to specify.   (DO specify!)

Input is the name of a person, or a married couple.   Output is an object of class Person or Couple. 

Sample input:
    Mr. John Q. Public
    Miss Sally Ann Public
    Bill Clinton
    Mr. & Mrs. William Clinton
    Bill and Hillary Clinton
    J. Pierpont Morgan

Titles are optional.  You may decide how to handle periods: they can be optional or required.  ("Miss", in English, does not have a period however)
Middle initials (or first initials) do have periods.
For simplicity, we can omit middle names for couples -- though if it's easier to include them, by all means do so.

Class Person has fields corresponding to title, first/middle/last name;  also a boolean for "isInitial" for first and middle name.
Class Couple has fields corresponding to title1, title2, first1, first2, last name