Recent questions tagged ullman

1
Write regular definitions for the following languages: All strings of lowercase letters that contain the five vowels in order. All strings of lowercase letters in which the letters are in ascending lexicographic order. Comments, consisting of a string surrounded by /* and */, without ... 's that do not contain the substring abb. All strings of a's and b's that do not contain the subsequence abb.
2
Most languages are case sensitive, so keywords can be written only one way, and the regular expressions describing their lexeme is very simple. However, some languages, like SQL, are case insensitive, so a keyword can be written either in lowercase or in ... regular expression for a keyword in a case-insensitive language. Illustrate the idea by writing the expression for "select" in SQL.
1 vote
3
In a string of length $n$, how many of the following are there? Prefixes. Suffixes. Proper prefixes. Substrings. Subsequences.
4
Describe the languages denoted by the following regular expressions: $a(a\mid b)^{\ast}a.$ $((\epsilon\mid a)b^{\ast})^{\ast}.$ $(a\mid b)^{\ast}a(a\mid b)(a\mid b).$ $a^{\ast}ba^{\ast}ba^{\ast}ba^{\ast}.$ $(aa\mid bb)^{\ast}((ab\mid ba)(aa\mid bb)^{\ast}(ab\mid ba)(aa\mid bb)^{\ast})^{\ast}.$
5
Consult the language reference manuals to determine the sets of characters that form the input alphabet (excluding those that may only appear in character strings or comments), the lexical form of numerical constants, and the lexical form of identifiers, for each of the following languages: C C++ C# Fortran Java Lisp SQL
6
Tagged languages like HTML or XML are different from conventional programming languages in that the punctuation (tags) are either very numerous (as in HTML) or a user-definable set (as in XML). Further, tags can often have parameters. Suggest how to divide the ... you liked that one. <P> into appropriate lexemes. Which lexemes should get associated lexical values,and what should those values be?
7
Divide the following C + + program: float limitedSquare(x) float x { /* returns x-squared, but never more than 100 */ return (x<=-10.0 || x>=10.0)?100:x*x; } into appropriate lexemes, using the discussion of Section $3.1.2$ as a guide. Which lexemes should get associated lexical values? What should those values be?
8
The programming language C does not have a boolean type. Show how a C compiler might translate an if-statement into three-address code.
9
For-statements in C and Java have the form: for $( expr_l ; expr_2 ; expr_3 ) stmt$ The first expression is executed before the loop; it is typically used for initializing the loop index. The second expression is a test made before each iteration of the loop; the loop is exited if the ... $2.43$ .
10
Extend the lexical analyzer in Section $2.6.5$ to recognize floating point numbers such as $2. , 3.14$, and $.5$.
11
Extend the lexical analyzer in Section $2.6.5$ to recognize the relational operators $<, <=, ==, !=, >=, >$.
12
Extend the lexical analyzer in Section $2.6.5$ to remove comments, defined as follows: A comment begins with $//$ and includes all characters until the end of that line. A comment begins with $/\ast$ and includes all characters through the next occurrence of the character sequence $\ast/$.
13
Construct recursive-descent parsers, starting with the following grammars: $S\rightarrow +SS \mid -SS \mid a$ $S\rightarrow S(S)S \mid \epsilon$ $S\rightarrow 0S1 \mid 01$
14
Construct a syntax-directed translation scheme that translates postfix arithmetic expressions into equivalent infix arithmetic expressions.
15
Construct a syntax-directed translation scheme that translates roman numerals into integers.
16
Construct a syntax-directed translation scheme that translates integers into roman numerals.
17
Construct a syntax-directed translation scheme that translates arithmetic expressions from postfix notation into infix notation. Give annotated parse trees for the inputs $95-2*$ and $952*-$.
1 vote
18
Construct a syntax-directed translation scheme that translates arithmetic expressions from infix notation into prefix notation in which an operator appears before its operands; e.g., $-xy$ is the prefix notation for $x - y$. Give annotated parse trees for the inputs $9-5+2$ and $9-5*2$.
19
Construct a context-free grammar for roman numerals.
20
Show that all binary strings generated by the following grammar have values divisible by $3$. Hint. Use induction on the number of nodes in a parse tree. $num\rightarrow 11 \mid 1001 \mid num \ 0 \mid num \ num$ Does the grammar generate all binary strings with values divisible by $3$?
21
Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct. Arithmetic expressions in postfix notation. Left-associative lists of identifiers separated by commas. Right-associative lists of identifiers separated by commas. Arithmetic ... binary operators $+, -, *, /$. Add unary plus and minus to the arithmetic operators of $(d)$.
1 vote
22
Which of the grammars are ambiguous? $S\rightarrow 0S1 \mid 01$ $S\rightarrow +SS \mid -SS \mid a$ $S\rightarrow S(S)S \mid \epsilon$ $S\rightarrow aSbS \mid bSaS \mid \epsilon$ $S\rightarrow a \mid S+S \mid SS \mid S^{\ast} \mid (S)$
23
What language is generated by the following grammars? In each case justify your answer. $S\rightarrow 0S1 \mid 01$ $S\rightarrow +SS \mid -SS \mid a$ $S\rightarrow S(S)S \mid \epsilon$ $S\rightarrow aSbS \mid bSaS \mid \epsilon$ $S\rightarrow a \mid S+S \mid SS \mid S^{\ast} \mid (S)$
24
Consider the context-free grammar $S\rightarrow SS+\mid SS^{\ast}\mid a$ Show how the string $aa+a^{\ast}$ can be generated by this grammar. Construct a parse tree for this string. What language does this grammar generate? Justify your answer.
25
What is printed by the following C code? #define a (x+1) int x = 2; void b() {x = a; printf("%d\n",x);} void c() {int x = 1; printf("%d\n"),a;} void main() {b(); c();}
26
For the block-structured code, assuming the usual static scoping of declarations, give the scope for each of the twelve declarations. { int w,x,y,z; /* Block B1 */ { int x,z; /* Block B2 */ { int w,x; /* Block B3 */ } } { int w,x; /* Block B4 */ { int y,z; /* Block B5 */ } } }
27
For the block-structured C code, indicate the values assigned to $w,x,y$ and $z$. int w,x,y,z; int i = 3; int j = 4; { int i = 5; w = i + j; } x = i + j; { int j = 6; i = 7; y = i + j; } z = i + j;
For the block-structured C code, indicate the values assigned to $w, x, y$, and $z$. int w,x,y,z; int i = 4; int j = 5; { int j = 7; i = 6; w = i + j; } x = i + j; { int i = 8; y = i + j; } z = i + j;
It is undecidable whether the complement of a CFL is also a CFL. Exercise $9.5.2$ can be used to show it is undecidable whether the complement of a CFL is regular, but that is not the same thing. To prove our initial claim, we need to define a different language that ... $7.2.5(b)$.