SE250:lab-8:dols008

Initial problems

To get the code to compile I had to move the declaration of error up before the expect function, because it was used in expect and not declared earlier. I also replaced the non-existent stricmp with strcmp.

Task 2

This wasn't hard. My expression was:

ParseTree* t = mkNode( '-', mkNode( '-', mkNode( 'a', 0 ), mkNode( 'b', 0 ), 0 ), 0);

Task 3/4

Task 3 took a bit of figuring out and a lot of tedious typing. I drew the graph before I wrote the mkNode expression to get a feel for everything. It turned out to be right, as far as I can see. I built it up from the bottom up, and as I went on my chunks got smaller as I got lazier. Here is the resulting code:

ParseTree* comp = mkNode( '>', mkNode( '+', mkNode( 'a', 0 ), mkNode( 'b', 0), 0), mkNode( 'c', 0 ), 0 );
ParseTree* mul = mkNode( '*', mkNode( 'z', 0 ), mkNode( '+', mkNode( 'y', 0 ), mkNode( 'b', 0 ), 0 ), 0 );
ParseTree* eq = mkNode( '=', mkNode( 'a', 0 ), mkNode( '2', 0 ), 0 );
ParseTree* lminus = mkNode( '-', mkNode( 'x', 0 ), mkNode( 'y', 0 ), 0 );
ParseTree* rminus = mkNode( '-', mkNode( 'y', 0 ), mkNode( 'x', 0 ), 0 );
ParseTree* rQuestion = mkNode( '?', eq, lminus, rminus, 0 );
ParseTree* bQuestion = mkNode( '?', comp, mul, rQuestion, 0);

Task 5

Because it is fully parenthesized, you can have operators with any number of operands without any sort of delimiter. Once all the operators inside a given pair of brackets have been evaluated, you are left with the operands of the operator outside the brackets, of which there can be any number.

Task 6

I hung around for another half hour to do task 6. Seemed only fair, since I turned up a full hour late. It was more straight forward than I expected.

int eval( ParseTree* tree) {
    if ( tree->name >= '0' && tree->name <= '9' ) {
	if ( tree->arity != 0 )
	    error( "A digit may not have operands" );
	return tree->name - '0';
    }
    if ( tree->arity > 2 )
	error( "Unexpected extra arguments in operator %c", tree->name );
    if ( tree->arity < 2 ) {
	error( "Not enough arguments in operator %c", tree->name );
	if ( tree->arity == 1 )
	    return eval( tree->arg[0] );
	return 0;
    }
    switch( tree->name ) {
    case '+':
	return eval( tree->arg[0] ) + eval( tree->arg[1] );
    case '-':
	return eval( tree->arg[0] ) - eval( tree->arg[1] );
    case '*':
	return eval( tree->arg[0] ) * eval( tree->arg[1] );
    case '/':
	return eval( tree->arg[0] ) / eval( tree->arg[1] );
    }
    error( "Unknown operator %c", tree->name );
    return 0;
}

In error cases I used the error function to print out a message, but attempted to recover gracefully. This includes continuing if an operator has more than two arguments, and even returning the value of the first argument if it only has one (which was probably not worth the effort). The idea was to make it obvious the expression was badly formed, but not crash outright (because crashing isn't nice).

Task 7?

Just from a glance at the grammar, it looks like it won't work because

<E> ::= <E> <BinOp> <E>

defines <E> recursively as itself (plus some other stuff). This will cause an infinite loop with <E> always attempting to match itself.

Task 8?

I don't think I can write a parser in 10min, so I guess I'll leave it at that.