> 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.
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
fragment
(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
or
(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.
>> 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.
>> 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.
>> 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.
>> 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
expression.
Your example does not match the grammar.
> 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.
> 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