# Recent questions tagged syntax-directed-translation

1
Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation $\text{(SDT)}$ ... The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions. The actions will lead to an infinite loop
2
Synthesized attribute can easily be simulated by an LL grammar ambiguous grammar LR grammar none of the above
3
Syntax directed translation scheme is desirable because It is based on the syntax It is easy to modify Its description is independent of any implementation All of these
4
Consider the productions $A \rightarrow PQ$ and $A \rightarrow XY$. Each of the five non-terminals $A, P, Q, X$, and $Y$ has two attributes: $s$ is a synthesized attribute, and $i$ is an inherited attribute. Consider the following rules. Rule $1$ ... $1$ is $L$-attributed. Only Rule $2$ is $L$-attributed. Neither Rule $1$ nor Rule $2$ is $L$-attributed.
5
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$.
6
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$.
7
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.
8
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
9
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
10
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.
11
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?
12
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$.
13
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$.
14
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.
15
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$.
16
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$.
17
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 L-attributed SDD to compute $S.val$ ... be the decimal number $5.625$. Hint: use an inherited attribute $L.side$ that tells which side of the decimal point a bit is on.
18
Suppose that we have a production $A\rightarrow BCD$. Each of the four nonterminals $A, B, C,$ and $D$ have two attributes: $s$ is a synthesized attribute, and $i$ is an inherited attribute. For each of the sets of rules below, tell whether the rules are consistent with an S-attributed definition the rules are consistent with ... $A.s=B.s+D.s$ $A.s=D.i,B.i=A.s+C.s,C.i=B.s,$ and $D.i=B.i+C.i.$
19
For the SDD of Fig. $5.8$, give annotated parse trees for the following expressions: int a,b,c. float w,x,y,z.
20
What are all the topological sorts for the dependency graph of Fig. $5.7$?
1 vote
21
For the SDD(SYNTAX-DIRECTED DEFINITIONS ) of Fig. $5.4$, give annotated parse trees for the following expressions: $(3+4)\ast(5+6)n.$ $1\ast2\ast3\ast(4+5)n.$ $(9+8\ast(7+6)+5)\ast 4n.$
22
Extend the SDD of Fig. $5.4$ to handle expressions as in Fig. $5.1$.
For the SDD(SYNTAX-DIRECTED DEFINITIONS ) of Fig. $5.1$, give annotated parse trees for the following expressions: $(3+4)\ast(5+6)n.$ $1\ast2\ast3\ast(4+5)n.$ $(9+8\ast(7+6)+5)\ast 4n.$