# Recent questions tagged ullman

1 vote
1
As in Ada, suppose that each expression must have a unique type, but that from a subexpression, by itself, all we can deduce is a set of possible types. That is, the application of function $E_{1}$ to argument $E_{2}$ ... and, once the unique type of the overall expression is determined, proceeds top-down to determine attribute $unique$ for the type of each subexpression.
2
Assuming that function $widen$ in Fig. $6.26$ can handle any of the types in the hierarchy of Fig. $6.25(a)$, translate the expressions below. Assume that c and d are characters, $s$ and $t$ are short integers, $i$ and $j$ are integers, and $x$ is a float. $x=s+c$ $i=s+c$ $x=(s+c)\ast(t+d)$
3
$A$ real array $A[i, j, k]$ has index $i$ ranging from $1$ to $4$, index $j$ ranging from $0$ to $4$, and index $k$ ranging from $5$ to $10$. Reals take $8$ bytes each. Suppose array $A$ is stored starting at byte $0$. Find the location of: $A[3,4,5]$ $A[1,2,7]$ $A[4,3,9]$ if $A$ is stored in column-major order.
4
$A$ real array $A[i, j, k]$ has index $i$ ranging from $1$ to $4$, index $j$ ranging from $0$ to $4$, and index $k$ ranging from $5$ to $10$. Reals take $8$ bytes each. Suppose array $A$ is stored starting at byte $0$. Find the location of: $A[3,4,5]$ $A[1,2,7]$ $A[4,3,9]$
5
An integer array $A[i, j]$ has index $i$ ranging from $1$ to $10$ and index $j$ ranging from $1$ to $20$. Integers take $4$ bytes each. Suppose array $A$ is stored starting at byte $0$. Find the location of: $A[4,5]$ $A[10,8]$ $A[3,17]$ if A is stored in column-major order.
6
An integer array $A[i, j]$ has index $i$ ranging from $1$ to $10$ and index $j$ ranging from $1$ to $20$. Integers take $4$ bytes each. Suppose array $A$ is stored starting at byte $0$. Find the location of: $A[4,5]$ $A[10,8]$ $A[3,17]$
7
Generalize formula $(6.7)$ to multidimensional arrays, and indicate what values can be stored in the symbol table and used to compute offsets. Consider the following cases: An array $A$ of two dimensions, in row-major form. The first dimension has indexes running from $l_{1}$ ... has indexes running from $l_{j}$ to $h_{j}$.The same as $(c)$ but with the array stored in column-major form.
8
Revise the translation of Fig. $6.22$ for array references of the Fortran style, that is, $id[E_{1}, E_{2},\cdot\cdot\cdot,E_{n}]$ for an $n-$dimensional array.
9
Use the translation of Fig. $6.22$ to translate the following assignments: $x=a[i]+b[j]$ $x=a[i][j]+b[i][j]$ $x=a[b[i][j]][c[[k]]$
10
Add to the translation of Fig. $6.19$ rules for the following productions: $E\rightarrow E_{1}\ast E_{2}$ $E\rightarrow + E_{1}\:$(unary plus)
11
Add to the translation of Fig. $6.19$ rules for the following productions: $E\rightarrow E_{1}\ast E_{2}$ $E\rightarrow + E_{1}\:$(unary plus)
12
Extend the handling of field names in Fig. $6.18$ to classes and single-inheritance class hierarchies. Give an implementation of class $Enu$ that allows linked symbol tables, so that a subclass can either redefine a field name or refer directly to a ... in a class, including inherited fields. Inherited fields must maintain the relative addresses they were assigned in the layout for the superclass.
13
Determine the types and relative addresses for the identifiers in the following sequence of declarations: float x; record { float x; float y; } p; record { int tag; float x; float y; } q;
14
Show how to transform a three-address code sequence into one in which each defined variable gets a unique variable name.
1 vote
15
Translate the following arithmetic expression into: $a=b[i]+c[j]$ $a[i]=b\ast c-b\ast d$ $x=f(y+1)+2$ $x=\ast p + \&y$ A Syntax tree Quadruples Triples Indirect triples
16
Translate the arithmetic expression $a + -(b + c)$ into: A syntax tree. Quadruples. Triples. Indirect triples
17
Construct the DAG and identify the value numbers for the subexpressions of the following expressions, assuming $+$ associates from the left. $a+b+(a+b)$ $a+b+a+b$ $a+a+((a+a+a+(a+a+a+a))$
1 vote
18
Construct the DAG for the expression $((x + y)-((x + y)\ast(x -y))) + ((x+y)\ast(x-y))$
19
Modify the SDD of Fig. $5.25$ to include superscripts denoted by operator sup between boxes. If box $B_{2}$ is a superscript of box $B_{1}$, then position the baseline of $B_{2}\:0.6$ times the point size of $B_{1}$ above the baseline of $B_{1}.\text{Add}$ the new production and rules to the SDT of Fig. $5.26$.
20
Modify the SDD of Fig. $5.25$ to include a synthesized attribute $B.le$, the length of a box. The length of the concatenation of two boxes is the sum of the lengths of each. Then add your new rules to the proper positions in the SDT of Fig. $5.26$.
21
Write L-attributed SDT's analogous to that of Example $5.19$ for the following productions, each of which represents a familiar flow-of-control construct, as in the programming language C. You may need to generate a three address statement to jump to a particular ... have a jump from its middle to the next statement, so it is not sufficient simply to generate code for each statement in order.
22
Write L-attributed SDD's analogous to that of Example $5.19$ for the following productions, each of which represents a familiar flow-of-control construct, as in the programming language C. You may need to generate a three address statement to jump to a particular ... have a jump from its middle to the next statement, so it is not sufficient simply to generate code for each statement in order.
1 vote
23
The following SDT computes the value of a string of $0's$ and $1's$ interpreted as a positive, binary integer. $B\rightarrow B_{1}0\:\{B.val=2\times B_{1}.val\}\mid B_{1}1\:\{B.val=2\times B_{1}.val+1\}\mid 1 \:\{B.val=1\}$ Rewrite this SDT so the underlying grammar is not left recursive, and yet the same value of $B.val$ is computed for the entire input string.
1 vote
24
Rewrite the following SDT: $A\rightarrow A\{a\}B\mid AB\{b\}\mid 0$ $B\rightarrow B\{c\}A\mid BA\{d\}\mid 1$ so that the underlying grammar becomes non-left-recursive. Here, $a, b, c$, and $d$ are actions, and $0$ and $1$ are terminals.
25
We mentioned in Section $5.4.2$ that it is possible to deduce, from the LR state on the parsing stack, what grammar symbol is represented by the state. How would we discover this information?
26
Give an SDD to differentiate expressions such as $x\ast(3\ast x + x\ast x)$ involving the operators $+$ and $\ast,$ the variable $x$, and constants. Assume that no simplification occurs, so that, for example, $3\ast x$ will be translated into $3\ast 1+0\ast x$.
27
Give an SDD to translate infix expressions with $+$ and $\ast$ into equivalent expressions without redundant parentheses. For example, since both operators associate from the left, and $\ast$ takes precedence over $+, ((a\ast(b+c))\ast(d))$ translates into $a\ast(b + c)\ast d$.
Below is a grammar for expressions involving operator $+$ and integer or floating-point operands. Floating-point numbers are distinguished by having a decimal point. $E\rightarrow E+T\mid T$ $T\rightarrow num.num\mid num$ Give an SDD to determine the type ... SDD of $(a)$ to translate expressions into postfix notation.Use the unary operator intToFloat to turn an integer into an equivalent float.
Implement Algorithm $3.23$, which converts a regular expression into a nondeterministic finite automaton, by an L-attributed SDD on a top-down parsable grammar. Assume that there is a token char representing any character, and that char.$lexval$ is the character it ... that is, a state never before returned by this function. Use any convenient notation to specify the transitions of the $NFA$.
This grammar generates binary numbers with a "decimal" point: $S\rightarrow L.L\mid L$ $L\rightarrow LB\mid B$ $B\rightarrow 0\mid 1$ Design an S-attributed SDD to compute $S.val$, the decimal-number value of an input string. For example, the translation of string $101.101$ should be the decimal number $5.625$.