Assignment 2, Due 1/27/04 09:30 a.m.
(Must be done with your group)

You will need to refer to mystery grammar to answer these questions.

  1. Problem set, page 157, #10

  2. Problem set, Page 158, #12

  3. Consider the following two grammars for <Expr>.  Note that the first  grammar is part of <Expr>'s grammar in mystery.  <Operator>  and <Operand> in both grammars are the same as <Operator> and <Operand> in mystery's grammar.  You need not look at the definition of <Operand> to answer this question.

    <Expr> →<Operand> | <Expr> <Operator> <Operand>

    <Expr> → <Operand> <ExprSuffix>
    <ExprSuffix> → <Operator> <Operand> <ExprSuffix> | ε

    1. Intuitively describe the expressions generated by two grammars. 

    2. Do these grammars generate the same or different expressions?  Explain

  4. Consider the following two grammars for <Operand>.  The first grammar is part of <Operand>'s grammar in mystery.  <Expr> in both grammars is the same as <Expr> in mystery's grammar.  You need not look at the definition of <Expr> to answer this question. 

    <Operand> →Number | id |  <Operand> [<Expr>]

    <Operand> → Number <OperandSuffix> | id <OperandSuffix>
    <OperandSuffix> → [<Expr>] <OperandSuffix> | ε

    The square brackets ([...]) are for array references and do not mean "optional" as in EBNF.

    1. Intuitively describe the expressions generated by two grammars. 

    2. Do these grammars generate the same or different expressions?  Explain

  5. Write a program that demonstrates whether + has higher precedence than * or vice versa in the C++ programming language. Make sure that you are checking for precedence in your program and not for left or right associativity.  Submit your program, the output produced by running your program, and an argument indicating how you arrived at the relative precedence of + and * based on the output.

  6. From the syntax of mystery (you will need to look at the full syntax for this question), we see that a mystery program is a collection of declarations.  One of the required declarations is a procedure called main that does not take any arguments.  When you run a mystery program, execution starts at main.  The rule for <ProcDecl> gives the syntax for declaring a procedure.  For example

    PROCEDURE f(): INTEGER = ...

    is equivalent to the C syntax:

    int f() { ... }

    The first case <Decl>'s rule (VAR id ...) says how to declare a variable.  For example

    VAR i: INTEGER;

    is equivalent to the C syntax:

    int i;

I have designed mystery to be as small as possible yet large enough to illustrate many of the concepts that we will cover in this class.  Thus, mystery is missing many features that you may be used to in your favorite programming language.  On the other hand, you will find later this semester that mystery has some features that are more powerful than features in your favorite programming language.

  1. Write a program that prints out 1 through 100 (inclusive).  You should test your program using this form.  Use your group id as the "User id", enter your code in the "Input" space, and click "Submit".  This will compile and run your program and present any errors or output in a new browser window.  You may use as many attempts as you wish.  As an additional challenge to yourself, try to do this in as few attempts as you can.  Be sure to brag about how many tries it took in your submission!

  2. Write a program that has two procedures, sum and main.  sum takes two integers as arguments and returns their sum.  Main calls sum with two arguments and prints out the result.    Once again, you should use this form to test your program.