2021/4/20 : Quiz Submissions - Quiz 3 - CSCI 485: TOPICS IN SYSTEMS - S21 N01 N02 - Vancouver Island University https://learn.viu.ca/d2l/lms/quizzing/user/quiz_submissions_attempt.d2l?isprv=&qi=86398&ai=699198&isInPopup=0&cfql=0&fromQB=0&ou=163515 1/5 Quiz Submissions - Quiz 3 Xiaofeng Gu (username: VIUD2L_1035567) Attempt 1 Written: Mar 3, 2021 7:29 AM - Mar 3, 2021 8:18 AM Submission View Released: Mar 8, 2021 3:22 PM Question 1 7 / 10 points In the current labs for the course, variables must be declared before they are used. Suppose we were to change the language specifications so that variables could be used before they are declared, as long as a suitable declaration follows at some point in an accessible scope. Outline a solution you would adopt, detailing the specific kinds of changes this would involve in your .lex and .yacc files, and the specific type and scope checking issues you expect to encounter. Hide Feedback The main idea is that we need an additional table to store the type information and variable information we need to check against. And we perform the check only after the whole file is scanned. .lex will be fine. But in .yacc, we won't be able to perform the type check and scope checking, right after each grammer rule is applied. Since in the original .yacc, we checked against the symbol table which only contains variables already declared. We need to store the information instead of checking right away and perform checking after the file is scanned. Definitely on the right track, but very vague - see some of the thoughts below. Sample solution: In our current lab, we have no type conversions possible and we only have global scope, so if we see an undeclared variable used we can identify from its enclosing expression what kind of variable it should be, and we can add it to the symbol table, BUT we should add an extra flag to the symbol table that indicates (for each variable) if we have seen an explicit declaration for the variable. In this case, the flag would be set to false. If we see a variable declaration for a variable that is not yet in the symbol table then we treat it normally. 2021/4/20 : Quiz Submissions - Quiz 3 - CSCI 485: TOPICS IN SYSTEMS - S21 N01 N02 - Vancouver Island University https://learn.viu.ca/d2l/lms/quizzing/user/quiz_submissions_attempt.d2l?isprv=&qi=86398&ai=699198&isInPopup=0&cfql=0&fromQB=0&ou=163515 2/5 Question 2 8 / 10 points For the HLL code segment below, provide a translation to a one-address code representation, and briefly describe each of the one-address operations you used (e.g. how many operands it expects and in what order on the top of the stack) x = 13 - y y = 7 + x * y / 100 View Feedback Question 3 10 / 10 points For the HLL code segment below, provide a translation to a three-address code representation, and briefly describe each of the operations you used. x = 13 - y y = 7 + x * y / 100 If we see a variable declaration for a variable that has been added to the symbol table but has not yet been explicitly declared then we check the data type is correct (error if not) and change the explicit declaration flag to true. If we get to the end of the program and the table contains variables that are lacking an explicit declaration then we generate an appropriate error message. push y push 13 sub(pop 13, y, performs -, push result as x) push y mul(pop y, x, perform *, push result) push 100 div(pop result of x * y, pop 100, perform /, push result) push 7 add(pop 7, result of x * y / 100, perform +, push result) pop x (pops result off stack into x) ------- mul, div, add all take 2 operands and top of stack as first and second top of stack as second. 2021/4/20 : Quiz Submissions - Quiz 3 - CSCI 485: TOPICS IN SYSTEMS - S21 N01 N02 - Vancouver Island University https://learn.viu.ca/d2l/lms/quizzing/user/quiz_submissions_attempt.d2l?isprv=&qi=86398&ai=699198&isInPopup=0&cfql=0&fromQB=0&ou=163515 3/5 View Feedback Question 4 9.5 / 10 points For the HLL statement given below, assuming it was to be represented using a syntax graph: (i) identify the common subtrees that could be used in reducing the graph size. (Assume standard arithmetic precedence and associativity rules.) (ii) based on your DAG from (i), if we assumed a value-number array-based implementation, how many leaves and how many nodes would actually be stored in the resulting array? x = a + x * y - a + x * y - x * y + x + x * y View Feedback Question 5 6 / 10 points We discussed the use of control flow graphs together with linear codes to model possible execution flows in a program. If we were to apply a similar idea with the HLL code segment R1 = 13 R2 = y R3 = R1 - R2 (subtract as result of 13 - y) X = R3 (copy result back to program variables) R4 = R3 * R2 (multiply as result of x * y) R5 = 100 R6 = R4 / R5 (division as result of x * y / 100) R7 = 7 R8 = R7 + R6 (add as the result of 7 + x * y / 100) Y = R8 (copy result back to program variables) (i) common subtrees: t1 = x * y, t2 =a, t3 = y, t4 = x. (ii) leaves: 3 nodes: 7 2021/4/20 : Quiz Submissions - Quiz 3 - CSCI 485: TOPICS IN SYSTEMS - S21 N01 N02 - Vancouver Island University https://learn.viu.ca/d2l/lms/quizzing/user/quiz_submissions_attempt.d2l?isprv=&qi=86398&ai=699198&isInPopup=0&cfql=0&fromQB=0&ou=163515 4/5 below, identify the statements that would be identified as leaders, and for each leader identify the statement that would be last in its associated block and briefly justify your choice of that leader/endpoint pair. int f(int a, float b){ if (a < 0) a = -a; do { a += a; } while (a < b); return a; } float g(int c){ c *= 2.5; return 7.0 - c; } int i; float j; int main(){ i = 27; j = 1.3; while (i < g(i)) { i = f(i,j); j *= 0.5; } j = g(i); } Hide Feedback leader/endpoint pairs: in function main: l: i = 27; e: j = 1.3; (before the while loop) l: i = f(i,j); e: j *= 0.5; (in the while loop) j = g(i)l (after the while loop) in function f: l: a = -a; e:a = -a; (first branch of if) l: a += a; e:a += a; (inside do block) l:return a; e:return a;(after the do block) in function g: l: c *= 2.5; e:return 7.0 - c; (g only have single block) The "justification" part not provided. Sample solution: 2021/4/20 : Quiz Submissions - Quiz 3 - CSCI 485: TOPICS IN SYSTEMS - S21 N01 N02 - Vancouver Island University https://learn.viu.ca/d2l/lms/quizzing/user/quiz_submissions_attempt.d2l?isprv=&qi=86398&ai=699198&isInPopup=0&cfql=0&fromQB=0&ou=163515 5/5 Attempt Score: 40.5 / 50 - 81 % Overall Grade (highest attempt): 40.5 / 50 - 81 % Done Here we're still faced with the basic problem of unique entry and exit points to blocks. One we identify what qualifies as a leader to each block then we can identify the exit points as well. If statements and while statements are tricky, since they involve both a test and a possible branch, so I'm going to treat an "if (expr)" as both an entry and exit point, where branches would go to the first statement in the block or the first statement after the block. While statements will be treated similarly. Function call/return is even worse, since there is a clear transfer of control, and they can actually occur in the midst of any of our other statements. For the discussion below I'll actually treat the function call as an exit point, and the return as the leader to a subsequent block. [This is why we usually think of this process in conjunction with something like a three-address code, where the point of transfer can be clearly separated from the rest of the operations.] With that as a pre-amble, lets establish our set of leaders and, based on that, their exit points 1. f's if statement: leader and exit point 2. f's do block: leader and only statement is the a += a 3. f's while statement: leader and exit point 4. f's return statement: leader and exit point 5. g's c += 2.5: leader, exit point is the return statement 6. main: leader is i=27, exit point is the j=1.3 7. main's while statement: leader and exit point is the call to g(i) in the test condition 8. main's while body: leader the (i < ...) on return from the call in 7, exit point is the call to f 9. rest of main's while: leader is the i=... on return from the call in 8, exit is j+=0.5 (where control would go back to 7) 10. post-while: leader and exit point is the call to g(i) 11. finale: leader is the j=... on return from call in 10, is also the exit point (ignoring an implied return 0 at the end of main)
欢迎咨询51作业君
