FAQs for Machine Problem 3

Notice that what's called "pack" and "unpack" in this faq is the same as "pair" and "unpair" in the problem. As you read these, don't worry if you don't understand the questions. Remember that these students are struggling with the concepts, so their questions may be pretty hard to understand.
  1. "cond" with no tests
    > I have a problem about the "cond" -- should we output error message
    > for "cond  end" (no expressions follows cond) or return 0?  
    The problem says "if none of the tests succeed, the expression should
    report an error".  If there are no tests, then none of them succeed, so
    you report an error.  
  2. MP3: dreaded "grammar not LL(1)" message
          From: Mitchell Wand 
    Sender: com3351-bounces@lists.ccs.neu.edu
    To: com3351 mailing list 
    Cc: Matthias Felleisen 
    Subject: [COM 3351] MP3: dreaded "grammar not LL(1)" message
    Date: Wed, 9 Apr 2003 23:06:27 -0400
    X-MW-Autoarchive: com3351
    X-MW-Autoarchive: mp3
    >> Attached is my original scheme file that results in an error
    >> My original production: 
    >> (expression
    >>      ("cond" (arbno "[" expression "==>" expression "]")) 
    >>      cond-exp) 
    >> does not cause an error message.  But when I write it up without the
    >> square brackets  "[", "]" : 
    >>    (expression
    >>      ("cond" (arbno expression "==>" expression)) 
    >>      cond-exp)
    >> I get the dreaded:
    >> parser-generation: grammar not LL(1): shift conflict detected for class
    >> "+" in nonterminal expression38:
    >> (("+" "-" "*" "minus" "zero?" "add1" "sub1" "print" "cons" "car" "cdr"
    >> "list" "(" "proc" "let" "cond" "if" id number) (non-term expression)
    >> (string "==>") (non-term expression) (goto expression38))
    >> ((end-marker "," "then" "else" "==>" "let" "proc" "(" "list" "cdr"
    >> "car" "cons" "print" "sub1" "add1" "zero?" "minus" "*" "-" "+" number
    >> id "if" "cond" ")" "in") (emit-list))
    OK, that's a good one!  If you look carefully at the problem, it uses
    the syntax
    expression::= "cond" {expression "==>" expression}* "end"
    This production always knows when it's reached the end, because it
    sees the "end".  In your production, without the "end", if it saw the
    (f cond x ==> y z
    it wouldn't know whether the z was part of the cond expression or
    whether it was the 2nd argument to f.
    Your production with the square brackets avoids this difficulty,
    because you have to write either
    (f cond [x ==> y] z  % z must be an argument to f
    (f cond [x ==> y] [z     % z must be the next predicate to cond.
    >> Also, if I write it up with round brackets instead of square brackets:
    >> (expression
    >>      ("cond" (arbno "(" expression "==>" expression ")" )) 
    >>      cond-exp) 
    >> I get this error message:
    >> parser-generation: grammar not LL(1): shift conflict detected for class
    >> "(" in nonterminal arbno38:
    >> (("(") (string "(") (non-term expression) (string "==>") (non-term
    >> expression) (string ")") (goto arbno38))
    >> ((end-marker "," "then" "else" "==>" ")" id "list" "cdr" "car" "cons"
    >> "print" "sub1" "add1" "zero?" "minus" "*" "-" "+" number "if" "cond"
    >> "let" "proc" "(" "in") (emit-list))
    >> Why did this happen?
    Similar deal:  if you see the fragment
    cond (x
    you don't know whether the x is the cond predicate, or whether the
    cond predicate is an application whose operator is x.
    How did I extract this explanation from the error messages?  I
    didn't.  Since we knew that the problem was right around the first
    nonterminal in the right-hand side, I looked to see how you could
    confuse the parser near there.  (Kinda like model checking, for those
    of you who might know what that means).
    Research problem:  write an LL-checker that produces an error message
    that's closer to this explanation, rather than what sllgen produces.
  3.     >> What should be the output of the expression consisting of nested "cond"?
    >> For example:
    >> "cond [zero?(0) ==> +(3,4)][zero?(1) ==> *(3,4)].... end"
    >> If none of the tests succeeds, the output is 0. However, what happens when
    >> there are at least 2 tests that do succeed - is the output 1?
    The problem says that your "cond" is supposed to behave analogously to
    a Scheme "cond".  That means that the value of the cond expression is
    the value of the first conseq-exp whose test-exp returns a true
    value.  So in
    cond zero?(1) ==> 44 zero?(0) ==> +(3,4) 1 ==> *(3,4) end
    the answer should be 7.
    >> Also, if there is a single cond expression, should it
    >> return the value of "conseq-exps" or 1 (for consistency purpose)?
    cond test-exp ==> conseq-exp end
    should return the value of conseq-exp if the value of test-exp is a
    true value, otherwise it should return 0.
    Also, kindly note that the brackets in your example code do not
    conform to the specified syntax.
  4. How much like Scheme's "cond"?
    >> Exercise 3.13 in the book states:
    >> "Add to the defined language a facility that extends if as cond does in
    >> Scheme.
    >> Use the grammar
    >>   <expression> ::= cond {<expression> ==> <expression>}* end ..."
    >> To which of the following should our cond have similar semantics?
    >> 1.   (cond { (guard expression) }* )   ; standard use of cond
    >> 2.   (cond { (test => receiver) }* )     ; use of "=>" with cond
    >> Asked another way, is use of "==>" in our language meant to convey a
    >> meaning similar to "=>" in scheme?  Or is this what is known in natural
    >> languages as a "false cognate"?  (i.e. a word that appears to have a
    >> similar meaning to one in another language, but in fact means something
    >> different).
    No, I meant the "standard use" of cond, not Scheme's idiosyncratic
    "=>" syntax.  
  5. >> I would like to just verify that the only way a pair can be made in
    >> our language is with 'pack'.  In other words,
    >> unpack (2,3) as (.....  
    >> would not work in our language.  
    >> It has to be
    >> unpack {a packed expression} as (...
    Yes, that is correct.  (2,3) is not an expression in our language.
  6. More "cond" questions
    >> we are implementing Q2 and just to make sure we want to know if the "cond"
    >> functionality has to imitate the "cond" in scheme, specifically in the part
    >> where if a test case is true, we have to execute all the expressions and
    >> just return the last expression:
    >> so in
    >>         (condition3 "cond zero? (3) ==> 4 zero? (0) ==> 2 +(7, 8) 0 ==> 3 1
    >> ==> 5 end" 15)
    >> should return 15, but also we don't know how to put together all those
    >> expressions at the right of zero? (0), should them be with a parenthesis
    >> grouping all of them or how?
    The grammar in the problem says:
    <expression>::= cond { <expression> ==> <expression> }* end
    So each right-hand side is supposed to consist of exactly one
    Your example does not match the grammar.
  7. Do we have to modify the-field-names
    >   How do we denote the parameters in the list the-field-names when an
    > arbno appears in the grammar? is it as simple as specifying it as a
    > list-of X?
    An arbno becomes a single field in the AST node.  So just a single name will
    do nicely.
    But the-field-names is only used by the SLLGEN-to-TeX translator.  So you
    don't really need to worry about it.
  8. Must we write rules of inference?
    > I've been hearing a nasty little rumor that we should include rules of
    > inference for the new additions to the language.  Is this 
    > correct?
     That is not a rumour. Look at the last sentence on the MP3 
     web page. What we are looking for is something similar to 
     what is in the book (pg. 69, the text in the boxes above 
     the actual code) and in the notes from last week. 

Last modified: Tue Feb 6 17:01:55 EST 2007