Final Study Guide

The final will cover language paradigms, intermediate representation via abstract syntax trees, and code optimization.

Be able to write programs using Flex and Bison from scratch.

Concepts that may appear on the exam:

Parse an input for a given grammar and draw the resulting AST (Study Abstract Syntax Trees 1 and 2 on Canvas)

Write simple programs in a non-declarative language (See Lisp 1 and 2 on Canvas).

Consider different ways that code can be optimized. Be able to apply them to unoptimized ASTs (Study Code Optimization 1 and Lisp 2 on Canvas)

Study all notes related to parsing, ASTs, and code optimization. Be able to modify a make_node function in order to perform some kind of folding, dead code elimination, or simplification.

Additional practice problems:

Write a Lisp function that has two arguments, a and b. Then, it loops from a to b on iterator i, adding each to make a total sum if i is greater than zero. When the loop completes, print the sum.

Consider a graph-writing language that accepts inputs to be used in mathematical software. For example: graph { node A; node B; node C; node D; edge A -> B; edge B -> C; edge C -> A,B,D; } Write simple Flex regular expressions along with a Bison grammar that accepts inputs of this form, where edges can be directed from a node to any number of other nodes as shown in the example above.

Write a grammar in Bison for a simple logic language like Prolog. Consider the input: p. forall X function(X). some X likes(X, john). forall X some Y parent(X, Y). Here, predicate names and constants are p, john, alice. Variables are X and Y.

Consider this simple shell language:

%union {
    char* str;
    AST* node;
}

%token <str> WORD
%token PIPE

%type <node> line pipeline command

%%

line
    : pipeline                { $$ = $1; }
    ;

pipeline
    : command                 { $$ = $1; }
    | pipeline PIPE command   { $$ = make_pipe($1, $3); }
    ;

command
    : WORD                    { $$ = make_cmd($1, NULL); }
    | WORD WORD               { $$ = make_cmd($1, $2); }
    ;

For each valid input below, draw the entire parse tree using an LALR approach (carefully label all tokens and variables). Then, draw the abstract syntax tree created after parsing the entire input.

ls
ls file
cat file | grep foo | write a

Apply any number of code optimization techniques, including constant folding, algebraic simplification, dead code elimination, loop-invariant code motion, and unreachable code elimination to generate the most-optimized equivalent of the following C-style code:

x = 10;
y = 0;
z = x * 1;
a = z + 0;
b = 3 * 4;
c = b + 2;
d = c;
e = d;

if (true && (x > 0)) {
    p = a;
} else {
    p = 999;
}

q = p;
u = 5;
u = 6;

while (y < 3) {
    m = b * 2;
    n = x + 0;
    t = m;
    y = y + 1;
    r = n + y;
}

return q;
s = 100;