Here's my very terse outline of solutions to selected
midterm problems:
-
Clarity, simplicity, modularity.
-
In addition to the above, efficiency: DFA-based scanner is
faster than CFL parser-based scanner for the same
language. Also, the grammar would be significantly more
complicated; e.g., allowing whitespace everywhere.
-
-- Context-free but not regular: balanced parens or other nested
structures like begin/end blocks, nested loops, etc. Not
sufficient to say "recursion" - you needed to give an example
like these where recursion gives something extra.
-- Not context-free, but compile-time checkable: matching
names to declarations, type checking. (Checking for
break only in loop, as in PL/0 could be done with CFG,
but is awkward.)
-
-- RE: "(B | \A)*", where A denotes the set of all allowable
characters, B denotes A minus double quote and backslash, and
()|* are the usual meta-characters.
-- DFA: kinda hard to draw in HTML; something like:
>(1) --"--> (2) --"--> ((3))
with an edge from 2 to 2 labeled B, and one from 2 to 4 labeled
backslash, and from 4 back to 2 labeled A.
- (e)
ast* procedure parseTprime() {
if scanner->peek("^") {
scanner->read("^");
return parseT();
} else if scanner->peek(")") {
return nil;
} else abort();
}
-
xi = xi for all i under both definitions. In addition:
-- Name equivalent: x1 = x2, x3 = x4;
-- Structurally equivalent: x1 = x2 = x3 = x4 = x5.
-
Abstract Syntax Tree:
=
/ \
/ \
i .
/ \
/ \
-> x
/ \
/ \
barp y
|
Typecheck as usual traverses the tree, evaluating bottom
up. TC for "->" verifies that left subtree has
type "pointer_to_struct", and that right child is an ID node
whose string name is declared in the symbol table for that
struct; result type is the type of that field, foo_t in
this case. TC for "." is similar: left subtree must be a
struct type, right child must be a field name therein; result
type int. TC for "=" checks that left
subtree is lvalue, and that right is of same type.
|
|
