Feedback Precedence yes, parentheses no, gimmicks whatever, format your choice 

Forum: U Chicago, Com Sci 221 old messages, autumn 2000
Re: News Assignment #2, due 11 October (Mike O'Donnell)
Re: Question Assignment #2: questions (Michael C. Brizic)
Date: 2000, Oct 09
From: Mike O'Donnell <odonnell@cs.uchicago.edu>

In problem 2.1, is it safe to assume that precedence is already given to multiplication/division?
Yes, multiplication and division have precedence over addition and subtraction in the infix forms.

In problem 2.7e, how are parentheses handled? Are they an unary operator?
Parentheses are not an operator. They are part of a gimmick to organize operators. Notice that x+y and (x+y) are exactly the same thing---they are two representations of the same abstract syntax tree. So, an abstract syntax tree should never contain any structure corresponding directly to parentheses. Rather, the parentheses help you determine which tree structure is correct.

For problem 2.12... What exactly are "gimmicks"?
Well, I'm not going to say ``exactly'' what they are, but I'll come close. A gimmick is any structure in a parse tree that does not occur in the corresponding abstract syntax tree. For example, derivations that put in parentheses are gimmicks. Portions of a parse tree that go from Expression to Term to Factor without producing an operator are gimmicks. Distinctions between Expression, Term and Factor are gimmicks.

Can you explain a little further what you mean by having the parse tree correspond the the abstract syntax of the expression?
Here's an example of a piece of a parse tree: 
    <expression>
         |
       <term>
        /| \
       / |  \
      /  |   \
     /<factor>\
    /   /|\    \
   /   / | \    \
  /   /  |  \    \
 /   /   |   \    \
(  name  +  name   )
     |        |
     .        .
     .        .
     .        .
     x        y
The vertical ellipses (``...'') indicate some stuff that's left out. And here's the corresponding piece of an abstract syntax tree: 
  +
 / \
x   y

Does this just mean that we are to write our own context-free grammar using the C operators?
It means quite a bit more. Yes, you must write your own context-free grammar to generate C expressions using the operators in Figure 2.9. But just any old CFG to generate those expressions will not do. The shape of all the possible parse trees must collapse in a sensible way to the shape of the corresponding abstract-syntax trees. For example, here's an abstract syntax tree for an expression: 
    *
   / \
  +   z
 / \
x   y
Here's a parse tree that corresponds sensibly: 
         E
        /|\
       / | \
      E  |  \
     /|\  \  \
    / | \  \  \
   /  E  \  \  \
  /  /|\  \  \  \
 /  / | \  \  \  \
(  x  +  y  )  *  z
Of course, with only the letter ``E'' as a nonterminal, you probably won't be able to achieve the right correspondence for other, insufficiently parenthesized, expressions. Here's a parse tree that doesn't correspond sensibly: 
       A
      / \
     /   A
    /   / \
   /   /   A
  /   /   / \
 /   /   /   A
|   /   /   / \
|  |   /   /   A
|  |  |   /   / \
|  |  |  |   /   A
|  |  |  |  |   /\
(  x  +  y  )  *  z
The problem has nothing to do with the choice of the letter ``A'' vs. ``E'' or something else. Rather it has to do with the inappropriate grouping of the symbols, that fails to show the grouping in the abstract-syntax tree.

Finally, are there any special rules to follow for turning in this assignment? For example, can we have a .ps file that has our trees and a text file that has our responses to other questions?
There are no special rules. I will like the format better the easier it is to read and understand. Many methods for producing PostScript will produce text just as well as pictures. Using those methods, it would be silly to have separate files, unless you did some sort of hypertextual presentation linking between them. On the other hand, if you use Xfig, or some other program that only works well for pictures, then the separate files are sensible. Just make sure that you label the pictures very clearly, and make it very easy for me to correlate pictures with text when necessary.



Mike O'D.


Messages

to: "Precedence yes, parentheses no, gimmicks whatever, format your choice"