CS 3723
Programming Languages 
Fall 2014
  Questions and Corrections,   
  with Responses   

Please direct questions or corrections or comments to the following email address, where δοτ is a "dot" and ατ is an "at-sign":

    <nealδοτwagnerατgmailδοτcom>

I will often post technical questions and my answers to this page, after stripping off any personal matters or identifying portions. The questions may be edited to improve them. Please do NOT use the email address reserved for submissions (the one with "extra" embedded inside) in order to ask questions.

  1. Question Wed (27 Aug 2014): I have a question about Python. On my mac, the default version of Python is 2.7.5. Is that ok? Or do I have switch back to 2.6.2?

    Response: I have a lot of material about Python online. There are answers to your question as well as many others. The short answer is: any Python at all is going to be OK. Your Apple Python 2.7.4 will be fine. But you should understand the implications of the different versions of Python. My main Python page is at:

    In the second main heading: "From the Homepage": is an item "Python2or3":

    and it gives a lot of information. The only important question is: are you using Python 2.x or 3.x? For us, the most important distinction between the two is that print is a keyword in Python 2.x and print() is a built-in function in Python 3. This is discussed in the Item 1 of my Python "Tutorial":

    Much later is a section: "Access to Python": There I say: "Python 2.7.2 on recent apples", but this is dated because you have Python 2.7.4. None of this makes any difference. The only issue that matters is: are you using Python 2 or Python 3? And even this is not crucial for us. These distinctions are mainly for big-time Python users.

  2. Question (7 Sep 2014): Do we have to read from a file named "double.data" or can we just read from "stdin" and have any file hooked up with "<" in the shell?

    Response: I want you to be able to do both of these. In general for these homeworks you should "get the job done". In examples I show both ways.

  3. Question (7 Sep 2014): I found the expression ".isdigit()" whilst googling possibilities to check for a digit, but you said not to use regular expressions. Is it OK to use this?

    Response:".isdigit()" is a method in the Python String class. It doesn't directly have anything to do with regular expressions. In general (see question above), you should do what you have to do to get the program to run. (I didn't want you to use regular expression for the whole task of recognizing a double.)

    Rather than using google, I would much prefer that you look through the section on Strings in the online documentation: Building skills in Python, specifically at Strings.

  4. Question (6 Sep 2014): In the diagram at the start of Homework 1: Doubles, what can "other" be? Could the string "aa1.2" be accepted as a double because "a" would fall into the "other" category?

    Response: This is a good question and points out that I haven't been explaining this consistently. The overview of what you are doing in in the figure at the end of Lexical Analysis. Each time the next token is called for, the program first skips over any whitespace (at state 0). This whitespace isn't included in the token. A DFA for each token is patched in as an arrow from State 0, depending on the first non-whitespace char encountered. Some non-whitespace chars are the start of more than one kind of token, as shown. (The diagram only shows a small portion of the whole DFA for all tokens.)

    For this Homework 1, I intended for you to process a sequence of doubles, ints and mistaken doubles that are floating in a sea of whitespace. In fact, the actual input file has a single return at the end of each double except for one case where there is an extra blank (by mistake), but I meant for you to handle any amount of whitespace before and after.

  5. Question (11 Sep 2014): Is there an output you would like to see for the evaluation of the continued fraction (Problem 4 of Homework 2)?

    Response: The problem asks for p(10) and p(15). You should print these with 15 significant digits, but the default for printing a double is only 12 significant digits. Here is one example that prints 1000*pi with more significant digits: 

      % cat test0.py
import math
import sys
sys.stdout.write(str(1000.0*math.pi) + "\n")
sys.stdout.write("%20.15f\n" % (1000.0*math.pi))
sys.stdout.write("%20.15e\n" % (1000.0*math.pi))

% python test0.py
3141.59265359
3141.592653589792917 (only 15-16 digits are accurate)
3.141592653589793e+03

    You may have additional debug output, but that is not required.

  6. Question (21 Sep 2014): Will the program be tested for inputs other than the inputs given in the problem

    Response: No, the given ones are enough. If this were commercial software, one should test it exhaustively and even try to prove that all cases are handled correctly, but we don't have to be that compulsive.

  7. Question (21 Sep 2014): For parts 2 and 3 can we set it up like part 1 where the program reads the dates from a file?

    Response: Yes, of course, either way is fine.

  8. Question (22 Sep 2014): I have all of H3: Python REs done except for the part of Problem 1 that handles data with or without a middle initial. I have separate programs for the two cases, but I can't combine them.

    Response: Hey, one crude method is to check for a character "." in a given record. (Can use Python String methods.) Then use your two solutions after an if-else, all written as one program. This works.

    But there are (slightly) sneaky REs that will match with or without the initial.

  9. Question (23 Sep 2014): I feel that there's a good chance I don't understand the NFA/DFA with epsilon in H4: NFAs with ε-moves. After looking at the first question, I came up with the following table. Something tells me I did this wrong.
      State      |  a         | b
-----------+------------+----------
{0,2,4}    |  {0,1,2,4} | {2,3,4}
{0,1,2,4}  |  {0,1,2,4} | {2,3,4}
{2,3,4}    |  -         | {2,3,4}
-          |  -         | -

    Response: This is not correct. Start with {0} and take ε-closure({0}) = {0,2,4}. You did this correctly. For the first entry under "a", you need to look for transitions from 0, 2, or 4 labeled with "a". There is only one of those, from 0 to 1. (Notice, the arrow of this transition points to the state 1.) So for the first entry, you start with {1} and take the ε-closure: ε-closure({1}) = {1} (nothing added). So the first new state under "a" is {1}. Now do the rest yourself.

    You should also write { } for the empty state or error state, instead of using "-". I used "-" on an NFA to mean there was no transition at all, but a DFA should have a transition in all cases. Finally, you need to label the start state and the terminal state or states.

    You should get 5 states including the empty one. But you can do a sanity check on the resulting DFA: it should accept any string with an even number of a's (including none) followed by an even number of b's (including none). Anything else is an error.

  10. Question (11 Oct 2014): Wrong RPN in Table for HW6:
    In the table, for problem 3 in HW6, the RPN given for (5+3)^(2+1)^2, which = 262144, is 53+21+2^^, which = 134217728. The correct RPN should be 53+21+^2^ = 262144.

    Response: This is a useful question, since it brings up several confusing facts about the exponentiation operator (for which we are using ^) and about RPN.

    Initially, everything below is an ordinary arithmetic expression (AE), not RPN.

    ^ associates from right to left, so that

      a^b^c = a^(b^c), so for example 4^2^3 = 4^(2^3) = 4^8 = 65536

      (a^b)^c = a^(b*c), so for example (4^2)^3 = 4^(2*3) = 4^6 = 4096

    So in the example here:

      (5+3)^(2+1)^2 = 8^3^2 = 8^(3^2) = 8^9 = 134217728

    Now lets talk about RPN. RPN is parenthesis-free and unambiguous. It knows nothing about associating left-to-right or right-to-left -- the association of a given operator is build into the RPN expression. In the case of the RPN expression you were given: 53+21+2^^, it is indeed the correct translation of the RE (5+3)^(2+1)^2 into RPN. If we evaluate the given RPN, we push 5+3=8 on the stack, the push 2+1=3 on the stack, and finally push 2 on the stack, so we have (from bottom to top) 8, 3, 2 on the stack. The ^ operator is applied to the top two stack entries, to get 3^2 = 9. Now he stack has 8, 9 on it. The final ^ applies to these entries, giving 8^9, the correct answer.

    Note that in completing this assignment, you didn't need to know anything about ^ associating from right-to-left. That fact is only needed to translate an arithmetic expression correctly to RPN form. (We'll see more of this in the next homework.)

    In case this is confusing, let me just say that this question is correct as stated and has value 134217728.

  11. Question (11 Oct 2014): Are we supposed to be converting the regular arithmetic expression to RPN or are we simply evaluating RPN for its value? I've been doing the former for several hours, trying to come up with some algorithms to convert the strings over, and then I just realized it actually sounds like we're only calculating the RPN... Please let me know.

    Response: I have said and the homework states that the arithmetic expressions on the left are just for reference. You are asked to evaluate each RPN as a double. The homework gives an algorithm for this. We will use the Python evaluation code in the next homework (not yet posted), where the input will be an arithmetic expression. We will first translate to RPN, and then use the current code to evaluate it.

    It turns out that converting to RPN is trivial once you have a parser.

  12. Question (13 Oct 2014): On number 1 part c of Homework 6, I don't understand what you want as an answer.

    Response: Somehow produce a sentence, that is, a string of terminal symbols that can be derived from the start symbol using the given grammar. One such sentence is the one given in part 1a: $b((aa)a)b$. The sentence you give must be longer than that one.

  13. Question (22 Oct 2014): In Homework 7, Problem 3, you stated that your program had found 6 errors in the test data, but I'm getting 7 errors.

    Response: I stated this in a confusing way, and I've rewritten the homework. There are 6 error messages in my program code, that is, 6 separate places in the code that detect errors. Each of my types of errors is represented by 1 or more test examples. (Now there are more than 7 actual erroneous inputs since I added some more.)

  14. Question (27 Oct 2014): I'm working on Homework 7, Problem 2 and have a question about the grammar for F. Do the plus and minus in curly braces (zero or more) mean our parser needs to accept terms like - - b? If so, how does that factor into RPN?

    Response: The { '+' | '-' } at first on the right side of the rule for F means that this grammar accepts any number of prefix unary minus or plus operators. We don't have such an operator in RPN (although we could have if we used a new symbol for it), and none of the input examples have any such operators.

    I've decided that these operators are confusing and contribute almost nothing, so I'm doing away with them in this course from now on.

  15. Question (27 Oct 2014): In Problem 4, do we need to add the $ to the end of every line in dae.txt or do we modify the code to use new line as the end point?

    Response: I had in mind using the same code as in problem 2, so you would add a $ at the end of each line. However, in matters like these you can always deal with such a simple problem however you wish.

  16. Question (29 Oct 2014): I'm still having trouble. I can't seem to print the letters a-z at all. I tried to do the following to see if I could even print out the letter a: 
      li    $v0, 3
l.d   $f12, 80($s1)
syscall
    But this just prints out a zero. Are you expecting us to fill the addresses starting at 80 with letters a-z ourselves?

    Response: You are missing the point somewhat. The letters a-z exist only in the Tiny language. Our MIPS knows nothing about them. In Tiny, we use the location 80($s1) as a place in the MIPS program to store what a Tiny program thinks the value of 'a' is. Initially only the first 10 MIPS locations have values: doubles 0.0 through 9.0. The next 26 locations, starting at 80($s1) are used for Tiny's variables a-z. Initially these are uninitialized, and they come out equal to 0.0. In Tiny, if we write "a = 7;", then to translate this to MIPS, we need MIPS code that will stick a "7" (double) into the location 80($s1). So the sequence of Tiny instructions: "< a; a = 7; < a; $" will output first 0.0 and then 7.0, taking each number from the location 80 bytes past the start of M.

  17. Question (3 Dec 2014): Could you give an explanation for how you want us to accomplish the continued fraction computations for Test Code B of Homework 11? I'm attempting it but I don't see how to do it without a creating a Fraction() within a Fraction() like Fraction(a, Fraction(b, c)).

    Response: We don't create complicated fractions with an initial declaration, but we declare simple fractions initially and build up complicated ones by using arithmetic operations: + − * /.  So to get your example above, start with x=Fraction(a,1) and y=Fraction(b,c). Then z=x/y is what you want.

    Or even: x=Fraction(a,1), y=Fraction(b,1), w=Fraction(c,1), and z=x/(y/w) is what you want.

    In fact, the box at the end of Test Code B shows this process explicitly. There, all the operations are done on objects that are already fractions. The result is a single fraction.

  18. Question (6 Dec 2014): In Test Code A of Homework 11, when I try to do divsion the program returns a runtime error.

    Response: If you are working with Python 3, you need to use __truediv__ instead of __div__. This came up several times in class.

  19. Question (7 Dec 2014): I'm confused as to what we have to put in to test for Test C of Homework 11. Could you explain just what I should put into the fraction code?

    Response: At the end of section C is the Python program pi_iter.py that evaluates the continued fraction as a double. You should start with this program or with your own or one of the recursive ones. Then each constant or variable needs to be an instance of type Fraction. In particular, in the first assignment statement, the variable i, and constants 2 and 1, need to be fractions. (You can feed the value of the formal parameter in as a fraction.) With the assignment, t will be of type Fraction. (If you miss one, Python will complain about mixing a fraction type with one of the standard types.)

(Revision date: 2014-12-06. Please use ISO 8601, the International Standard.)