Show the code gerated by the code generator for the following TST atom. Assume that the value of L1 is hex 23 and the variables A and B are stored at locations 0 and 1, respectively.
Use the register allocation algorithm of this section to show a weighted syntax tree for the expression a – b/c + d ∗ (e-f + g∗h), and show the resulting instructions, as in Figure 6.9.
Assume we have a Pascal compiler for a Mac (both source and executable code) as shown in Figure 6.1. We are constructing a completely new machine called a RISC, for which we wish to construct a Pascal compiler. Show how this can be done without writing the entire compiler and without writing any machine or assembly language.
Assume the array M has been declared to have two planes, four rows, and five columns (int M[2][4][5]). Show the attributed derivation tree generated by grammar G23 for the array reference M[x][y][z]. Use Factor as the starting nonterminal, and show the subscripting expressions as Expr, as done in Figure 5.11. Also show the sequence of atoms which would be put out as a result of this array reference.
Write a yacc program to build simple expression trees. Assume that the operands may be only single letters or single digits and that the operations are addition, multiplication, subraction, and division, with the usual precedence rules. The yylex() function may be generated by lex or written directly in C. The input should be a single infix expression on each line. After the expression tree is built, dump it to stdout in prefix order. Ex-ample:
Show the sequence of stack, input, action, and goto configurations for the input var∗var using the parsing tables of Figure 5.7.
Show the sequence of stack and input configurations as the string caab is parsed with a shift reduce parser, using grammar G19.
Show a pushdown machine and a recursive descent translator for arithmetic expressions involving addition and multiplication using grammar G16.
Show the sequence of stacks that occurs when the pushdown machine of Figure 4.11 parses the string bccN.
Find the selection sets for the following grammar. Is the grammar quasi-simple? If so, show a pushdown machine and a recursive descent parser (show functions S() and A() only) corresponding to this grammar.
Show a one state pushdown machine and a recursive descent parser (show functions S() and A() only) for the following grammar:
Show the sequence of stacks and states which the pushdown machine of Figure 3.8 would go through if the input were: a+(a∗a)
Determine whether the following grammar is ambiguous. If so, show two different derivation trees for the same string of terminals, and show a left-most derivation corre-sponding to each tree.
Classify each of the following grammar rules according to Chomsky’s classification of grammars (in each case give the largest – i.e., most restricted – classification type that applies):
Improve the lex program shown above to recognize identifiers, assignment operator (=), arithmetic operators, comparison operators, and the keywords if, while, else for a language such as C++.
Design a finite state machine, with actions, to read numeric strings and convert them to an appropriate internal numeric format, such as floating point.