Here are some solutions for hw1; if you have questions, ask!
(1) 20 points
(i)
It's the way that different features of the language can be combined and
interact with one another in any context. For example, in Pascal, you
can pass parameters by reference with the keyword "var" and write a
procedure like
procedure swap( var x, y : integer );
{ Swap values of two integers }
var
t : integer;
begin
t := x;
x := y;
y := t
end;
{ called with }
swap( foo, bar );
In C, however, the concept of a reference (pointer) is _orthogonal_ to
parameter passing--you can create references in any context (not just
passing parameters) with the address-of operator (&). As a result,
there is no keyword for "reference parameter"--one creates a reference,
and then passes that:
void swap( int *x, int *y )
{
int t = *x;
*x = *y;
*y = t;
}
/* called with */
swap( &foo, &bar );
In this respect, C is more orthogonal than Pascal, as references
(pointers) can be made independently of parameter passing.
(ii)
Some examples of things to mention include...
For:
- rapid prototyping; less to type when building system
- more flexibility; so long as operation works at run-time, you're fine
Against:
- poor reliability/correctness; static type checking helps find errors
- incurs run-time costs
(iii)
You could probably argue it either way, depending on what historical
examples you choose to cite. Some things you could argue include:
- Ada, committee, good
- PL/I, committee, bad
- Pascal, individual, good
- C, individual, bad
(iv)
Many possible answers.
---------------------------------------------------------------------------
(2) 10 points
"b + b + b" has multiple parse trees:
S S
| |
A A
/|\ /|\
A + A A + A
/|\ \ / /|\
A + A id id A + A
| | | | | |
id id b b id id
| | | |
b b b b
therefore the grammar is ambiguous. It can be rewritten as:
S -> A
A -> A + id | id
id -> a | b | c
to specify the same language but no longer be ambiguous. (There are
many other possible rewrite solutions.)
---------------------------------------------------------------------------
(3) 20 points
assign, id, expr are given one-letter abbreviations:
a -> i := e
a -> A := e
a -> A := e * e
a -> A := i * e
a -> A := C * e
a -> A := C * (e)
a -> A := C * (e*e) -or- a -> A := C * (e+e)
a -> A := C * (i*e) a -> A := C * (e*e+e)
a -> A := C * (A*e) a -> A := C * (i*e+e)
a -> A := C * (A*e+e)
a -> A := C * (A*i+e)
a -> A := C * (A*C+e)
a -> A := C * (A*C+i)
a -> A := C * (A*C+B)
a -> i := e
a -> A := e
a -> A := e+e
a -> A := i+e
a -> A := A+e
a -> A := A+(e)
a -> A := A+(e+e)
a -> A := A+(i+e)
a -> A := A+(B+e)
a -> A := A+(B+(e))
a -> A := A+(B+(i))
a -> A := A+(B+(C))
(I haven't drawn parse trees, but they are easy to construct given the
derivation; for a sample parse tree, see #2.)
---------------------------------------------------------------------------
(4) 5 points
All strings containing matched parentheses. (That is, all strings
containing the symbols '(' and ')' such that, when reading from left to
right, the number of '('s encountered so far is always greater than or
equal to the number of ')'s, and the total number of each in the entire
string is equal.)
---------------------------------------------------------------------------
(5) 20 points
lexemes tokens lexical value
~~~~~~~ ~~~~~~ ~~~~~~~~~~~~~
int INTEGER
main ID "main"
( LEFT_PAREN
) RIGHT_PAREN
{ LEFT_BRACE
int INTEGER
x ID "x"
= EQUALS
10 LITERAL_INTEGER "10"
; SEMICOLON
printf ID "printf"
( LEFT_PAREN
"Hello, world! %d\n" LITERAL_STRING "Hello, world! %d\n"
, COMMA
x ID "x"
) RIGHT_PAREN
; SEMICOLON
} RIGHT_BRACE
Either of the first two columns, along with the third, was sufficient to
earn credit.
---------------------------------------------------------------------------
(6) 10 points
All binary strings.
All binary strings containing exactly three 1s.
---------------------------------------------------------------------------
(7) 15 points
Note: I'm assuming we don't bother with "break" and "continue".
C code VM code
~~~~~~ ~~~~~~~
foo foo
while( E ) top: if E goto loop
{ goto end
bar loop: bar
baz baz
} goto top
qux end: qux
C code VM code
~~~~~~ ~~~~~~~
foo foo
do top: bar
{ baz
bar if E goto top
baz qux
} while(E);
qux
--
-Brian McNamara (lorgon@cc.gatech.edu), your friendly CS 3411 TA