CS 3723 Programming Languages
|
(See also Last semester's questions.)
Answer: Sure, switchs are fine, just no gotos. My examples in Pascal use a case statement, which is the same as switch in C. A switch is just a fancy if-then-else.
My question is, k is missing an initialization if n were ever an even number. Do you want us to repair this issue for the program that we turn in?
Answer: The only actual input to the program is the input number to be converted to Roman numerals, here using the variable rom. I didn't use a scanf or such because I'm presenting several different languages. The variable n is used in the algorithm and must be initialized to 13 as a basic part of the algorithm. Initialization to a value besides 13 is not an option. (This only appears to be a problem because of the way I obscured the underlying algorithm, from which I derived this confusing version.)
Answer: Your question is slightly confusing to me. In part e of the submission, you are to submit a "Java source program that recovers the hidden loops and the structure of the C program in Section 4". There is no switch statement in this program to get rid of. The earlier method for getting rid of the gotos does insert a switch, but you are not working with that program. You are working with the original program in Section 4, and you are to try to recover the original program. It might have had various constructs, including loops, if-then-elses, and even switchs. Also, there is no single correct answer to this question, and a given use of gotos and labels might be translated to high-level constructs in many different ways. In particular, a switch can always be represented using an if-then-else, and it is impossible to know what the original might have been.
As an example, for '.6e-2', i can only seem to print out '0.006000000000000002', which is obviously a great deal larger than '0.0060'.
Answer: The form '0.006000000000000002' is fine as output for the input '.6e-2'. As I'm sure you know, it's actually just a tiny bit larger, but it does have a lot more significant digits. It has this form because the machine you ran it on is representing a double in binary, and it cannot represent 0.6 exactly. Hence the minutely larger value.
Java (as well as C and C++) does allow you to control the number of digits on output. For example
import java.text.DecimalFormat;
// ...
DecimalFormat twoDigits = new DecimalFormat("0.00");
DecimalFormat fifteenDigits = new
DecimalFormat("0.000000000000000");
// ...
double p = 3.141592653589792;
System.out.println(twoDigits.format(p)); // prints "3.14"
System.out.println(fifteenDigits.format(p)); // prints "3.141592653589792"
Answer: The final due date for Recitation 2 is Friday, 10 September 2004, 23:59:59. Recitation 3 is due for full credit the following Monday,13 September 2004, 23:59:59. Normally, on Saturday (this time, Saturday, 11 September 2004, I'll turn off submissions to the previous recitation, and allow submissions to the next one. (I didn't do this last weekend because I was out of town.) The only reason for this is to keep you from getting confused with two submissions that work at the same time. If there is strong feeling about this, I can change the policy.
I don't understand the function of this global variable. If we are keeping an Object (array of Strings) holding all the identifier names, shouldn't we just call a method in this object to obtain its location in the symbol table? And if we are keeping global variable for the identifier, should we have one global variable for each possible identifier? I'm most probably understanding this in the wrong way, because it doesn't make any sense ;)
Then we come to the "Floating points and integers constants" section, and we have pretty much the same situation: After converting the string to an internal double "the scanner should return a "#" character (see below) and set a global variable equal to the value of the constant as a double."
I guess my whole confussion is: will the scanner be simply outputting the information into STDOUT in the way it is shown in the recitation, or will it be returning this values to another class that will present them in the formatted output? If we actually need to use return, the class will stop execution after the first return, and it should be invoked again to restart. It makes sense that the lexical analyzer calls the scanner in a loop, but so far we have no lexical analyzer, therefore my whole confussion. [Note: the questioner meant syntax analyzer here; "lexical analyser" is another term for "scanner".]
Answer: I think my description was confusing all right. Let's start at the beginning:
Answer: Yeah, I forgot about this. Just put it into "Ascii text" form as well as you can. With just a little work, you can do this: Don't use circles for states, but just the state number, and fake the arrows, as in the comment FSM below. Also, you can write state numbers more than once to make the arrows easier to fill in.
(start) / * * /
-------> 0 -----------> 1 -----------> 2 -----------> 3 -----------> 4 (terminal)
| | | |\
|other |other |other | \
| | | | \other
| | | |* \
V V V V V
0 0 2 3 2
I was thinking for identifiers to just write: E ---> id and for integer constants to write: E ---> con
But the above seems a bit too simple... Perhaps you can give some examples of what sentences a grammar for identifiers and a grammar for integer constants each produce.
Answer: A good question. I meant for you to use individual Ascii characters as terminal symbols. Here is the way I rewrote this part in Recitation 4:
digit ----> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 letter ----> a | b | ... | z | A | B | ... | Z
and these rules satisfy the condition for being a regular grammar.]
As in question 3, you will need to use recursion (or the notation from question 3).
This is then illustrating that grammars can also handle the things that were handled by finite automata.
Answer: I don't like using the "Keyboard" class from CS 1713, since it is not standard Java, but is just a class for inputting data supplied by one author. For this reason I usually supply my own input classes, which are much simpler because they are not general-purpose.
I have cleaned up the page Recursive Descent Parsing so that the presence of the other class is clear.
The latest version of Java is supposed to have standard input classes.
Additionally, if our parser generates output similar to the examples, would it be all right if we add an additional function to print the characters that are skipped in your output examples?
Answer: You are supposed to produce parser output similar to the examples given, showing the structure of the calls needed to do the parse. (You can just copy my enter and leave functions, or do something else to convince yourself and me that the parser is working.) The sample inputs to your parser are programs in the Tiny® language. Our goal over the next two recitations is to add code to the parser that will translate Tiny programs into MIPS assemply code. These can then be executed in the MIPS simulator, and we will indeed be able to produce the Fibonacci numbers promised for the two sample programs.
My own sample output does not include all input characters. You can use your own (different) output, and this can include all input characters it you want.
Answer: The sample output is for the source program: Sample Input 2. Just before this link, Recitation 5 says: "Here is roughly what your parser output might look like with the above input (using a slightly different parser)." This was intended to show the general form of the output, but it is not exactly what your parser should produce. In particular, as you note, this parser has a non-terminal L whereas yours should not.
Answer: The syntax of the G statement is a greater than: '>', followed by a lower-case letter, followed by a semi-colon: ';'. That's all you need to worry about for Recitation 5.
The semantics of the G statement is to input an integer value (which is typed as input and is not part of the program). This value will be assigned to the variable represented by the "lower-case letter". This construct was partly suggested by the C++ input statement: cin >> x;, which reads in a value to assign to the variable x. However, I wanted only single-character tokens. You will implement the semantics in Recitation 7.
[This is an interesting question. The grammar rule G ---> '>' lower-case ';' gives the syntax, and specific input for such a statment could look like: > x; This is all at compile-time. After compilation, at run-time an actual integer constant will be handled as input, using a translation of this statement. The integer value will be put into a memory location correponding to the variable x. Notice that at run-time there will usually be no name x, but just a memory location corresponding to the compile-time name x.]
Answer: That's right. Handling '< B;' is particularly easy, since it has a fixed translation to MIPS assembly code. Other constructs require dealing with values in variables at run-time; we will go over this in class (and it's on the web site).
[There follows MIPS code including the instruction:
mult $t3, $t1, $t2which produces an error when run with spim. In fact the error is that mult has only two explicit register operands (see below).]
Can you offer any guidance for this? I haven't even tried the divide or mod yet, so if you could give some hints on implementing those as well, it would be appreciated.
Answer: See Appendix A of the third edition of the CS2733 text (on the CD) for a list of MIPS instructions, or else Appendix A (PDF) of the second edition of the text. There you see that mult (to multiply) is a hardware instruction that uses special hardware registers lo and hi, which can be accessed after the instruction using other MIPS instructions (mfhi, move from hi, and mflo, move from lo,and others). This would be kind of messy, but there is a pseudoinstruction that works for our purposes: mul, with three register operands just like add. Similarly there are pseudoinstructions div (for divide) and rem (remainder on division) that also work like add.
Answer: I didn't get around to posting answers for this one, and there is only one weird question anyway: 6. For Question 6 if you wanted more information you could just download it and run it. (You would also need my GetNext class, which is posted at various places on the class web pages.)
if(a[i] >= a[i+1]) return falseor
if(a[i] > a[i+1]) return false
This is because what if 2 numbers are the same?
Answer: If any a[i] > a[i+1] then the numbers are not sorted into order (we say "increasing" order, but we really mean "non-decreasing" order). With quicksort, It's all right if some of the numbers are equal. And that still counts as sorted order. (Given the way the random number generator is used, equal numbers have almost no chance of appearing.)
Answer: Of course you must supply sample runs of any functions you submit, as well as a listing of the function. The Submission Guidelines say: "Unless explicitly stated otherwise, programs must always be followed by the results of a run."
(defun reverse1 (list)
(cond ((null list) nil)
((null (cdr list)) (car list))
(t (cons (reverse1 (cdr list)) (car list)))
)
)
Answer: In your particular case, your last line is consing a list with an atom, to produce the final answer. That's not what you want to do.
For example, suppose your original list is (a b c d). Suppose you are at the last stage of reversing, where you have reversed the cdr to form (d c b) and want to tack and a on at the end. Your code does something like this:
[1]> (cons '(d c b) 'a) ((D C B) . A)
The result is of course not (D C B A). What you want to do (somehow) is the following at the end:
[2]> (append '(d c b) '(a)) (D C B A)
Answer: The new loaded definition will overwrite the old one, so you don't need to restart, assuming that you have a separate editor going. Here's an interactive session:
[1]> (load "fact.l") ;; mistaken definition, with 0! = 3 ;; Loading file fact.l ... ;; Loaded file fact.l T [2]> (factorial 4) 72 [3]> (load "fact.l") ;; definition corrected with editor ;; Loading file fact.l ... ;; Loaded file fact.l T [4]> (factorial 4) 24 [5]> (quit) %
I wanted to let you know that the only way I could get the (20,6) star to look the way you have it online is to have one for loop to draw the 10 sided star, then to rotate by 18 (360/20) and then run the same loop again. Is this ok to do?
Answer: Yes, that is fine to do. This problem is the reason that I suggested doing the program the way it is described in the writeup: drawing each line separately, or alternatively drawing one line, rotating by 18 (360/20) drawing the same line, and so on for the 20 lines, in the case of a (20,6) star.
This problem is surely why someone asked in class about PDF not updating. I didn't understand then, but this student was probably drawing a (10,3). Then the student tried a (20,6) as you are doing and produced the same output, so PDF was updating after all.
If you try do draw a continuous path, this is more complicated because a (20,6) has two separate paths, one like the (10,3), and the other like the (10,3) rotated by 18 degrees. This approach is more complex (although it produces better output), because in the most general case there is no limit to the number of separate paths. So for example, a (9,3) requires 3, a (16,4) requires 4 paths, and so forth. It's possible to write a program to handle this most general case, and still create each path as a complete path, and not as separate lines, but this would be a little more complicated. Instead, as I said above, I just recommended drawing each line separately, and this is fairly easy.
Answer: I looked up my code for this. I used the Date class just as I gave it to you. Then I defined a Time class that inherits (or extends) Date as I suggested in the write-up. Finally, from within my incr_hour inside Time I was able to call incr_day without any trouble. It worked just as I expected it to: Time inherits the incr_day method from Date. You must be making some other error. Email me you code and I'll look at it.