% file: a10new.pro (slightly revised from a10.pro) % author: Robert Keller % due date: Sunday, 11 April 2010, 11:59 p.m. % There is just one problem on this assignment. % This is a starter file. Only one test will succeed as it is. % Construct a compiler for a simple programming language % targeting the NoRM (No-Register Machine), % a stack-based machine with random-access memory. % There are separate memories for instructions vs. data. % I provide a grammar for the language, but without semantics (code generation). % You need to fill in the code-generation part of the grammar. % % I also provide a simulator for the NoRM, so that your code can be tested. % In order to compile the language, it will be necessary to refer to the simulator. % Recommendation: Start by compiling the simplest programs, % then work toward the more complex. % The grammar rules for the language are given first, then the definition of the NoRM. % You will need to add arguments such as the Code argument in the first production. % This argument is the way of transmitting the compiled code back to the caller. traceLevel(0). % Change 0 to 1 to trace NoRM instructions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Grammar Rules for a little language % % Your task is to complete the rules so as to generate NoRM code for a tokenized list. % The Code variable will get bound to a list of NoRM code for the corresponding % syntactic entity. % You will have to provide, in the grammar rules, the Prolog code that does this. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Base environment for the compiler, relating variables to locations in data memory % This is not strictly necessary to compile a program, however we want these % variables to be in the same memory locations so we can test the results. :- dynamic env/2, lastLoc/1. % Allow the environment predicate to add new clauses env(u, 1). env(v, 2). env(w, 3). env(x, 4). env(y, 5). env(z, 6). lastLoc(6). % Initial NoRM memory contents corresponding to variables above % Locations are indexed 1, 2, 3, ... initialMemoryLoad([10,20,30,40,50,60]). % This "magic" clause uses the built-in 'phrase' goal to invoke the grammar rule for % program, based on the token list Tokens. This can be left as is. compile(Program, Code) :- phrase(program(Code), Program). % If compilation is successful, Code will be bound to the generated NoRM code. % As it stands, the returned Code is wrong most of the time. You need to % revise the Prolog aspect of the grammar rules to generate correct code. % The non-terminals of the grammar are: program, stmt, assignmentStmt, etc. % Items in square brackets are literal input. % Items in curly braces are executable Prolog code. % Commas on the right-hand side of productions mean concatenation. % | on the right-hand side indicate alternatives. % program is the start symbol. A program must be a statement, according to this. % Code is the variable holding the result of compilation, which will be NoRM code. program(Code) --> stmt(Code). % Below, change [halt] to the code that should be generated. % Add similar arguments to each non-terminal in each production. % statement stmt(Code) --> assignmentStmt(Code) | compoundStmt(Code) | conditionalStmt(Code) | iterationStmt(Code). % assignment statement % % Variable = Expression; assignmentStmt(Code) --> lhsVar, ['='], exp, [';'], {Code = [push(5), store(4), halt]}. % Above is just a sample of the code. % It must be changed, because it is only correct for statements such as % 'x = 5;'. % (x corresponds to location 4 in data memory). % compound statement % % { ... 1 or more statements ... } compoundStmt([halt]) --> ['{'], stmt(_Code), stmtSequence(_MoreCode), ['}']. compoundStmt --> ['{'], stmt(_Code), ['}']. % statement sequence stmtSequence([halt]) --> stmt(_Code), stmtSequence(_MoreCode). stmtSequence([halt]) --> stmt(_Code). % two-sided conditional % % if ( boolean expression ) statement else statement conditionalStmt([halt]) --> ['if', '('], booleanExp, [')'], stmt(_TrueCode), ['else'], stmt(_FalseCode). % one-sided conditional % % if ( boolean expression ) statement conditionalStmt([halt]) --> ['if', '('], booleanExp, [')'], stmt(_Code). % iteration % % while ( boolean expression ) statement iterationStmt([halt]) --> [while, '('], booleanExp, [')'], stmt(_Code). % Expressions exp --> sum. sum --> product, ['+'], sum. sum --> product. product --> primary, ['*'], product. product --> primary. primary --> ['('], exp, [')']. primary --> rhsVar. primary --> [C], {integer(C)}. % Boolean expressions booleanExp --> [true]. booleanExp --> [false]. booleanExp --> exp, relop, exp. relop --> ['<']. relop --> ['=']. % Variables have the same syntax, but different semantics, % depending on whether they are on the right-hand side or left-hand side % of an assignment ("R-values" vs. "L-values"). % Right-hand side variables rhsVar --> variable. % Left-hand side variables lhsVar --> variable. variable --> [V], {isVar(V)}. % A variable is an atom with a valid starting symbol and which is not a reserved word. isVar(V) :- atom(V), validStart(V), \+reserved(V). validStart(V) :- atom_chars(V, [F | _]), member(F, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]). % Reserved identifiers reserved(if). reserved(else). reserved(while). % Dynamic predicates for record keeping and such :- dynamic tokenization_successes/1, tokenization_failures/1, run_successes/1, run_failures/1. % Initial values of dynamic predicates tokenization_failures(0). tokenization_successes(0). run_failures(0). run_successes(0). % getLoc returns the location corresponding to a variable. % If the variable was not allocated yet, it is allocated to % the next free location in the NoRM data memory. getLoc(Var, Loc) :- env(Var, Loc) -> true % binding exists ; retract(lastLoc(OldLoc)), % no binding exists, so make one Loc is OldLoc + 1, assert(env(Var, Loc)), assert(lastLoc(Loc)). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % purpose: Execution model for NoRM (No-Register Machine) % It should not be necessary to modify any of this. % NoRM is a stack-based machine % with random access to separate instruction and data memories. % run runs a given instruction sequence with an Instruction Memory initialized to % successive location contents (starting at location 1), returning % the final state (Stack, Location, Instruction Memory, Data Memory) run(InstructionSequence, InitialDataSequence, FinalState) :- traceLevel(N), run(InstructionSequence, InitialDataSequence, FinalState, N). % option with non-zero trace level run(InstructionSequence, InitialDataSequence, FinalState, TraceLevel) :- StartLocation = 1, InstructionMemory =.. [instructions | InstructionSequence], DataMemory =.. [data | InitialDataSequence], InitialStack = [], InitialState = state(InitialStack, StartLocation, InstructionMemory, DataMemory), StartStep = 1, norm(InitialState, FinalState, StartStep, TraceLevel). % norm is iterates the basic cycle of the NoRM % If cycle execution fails (as it will for the halt instruction, for example) % norm stops and returns the current state norm(State, FinalState, Step, TraceLevel) :- (TraceLevel > 0 -> showState(Step, State) ; true), ( cycle(State, NewState) -> (Step1 is Step + 1, norm(NewState, FinalState, Step1, TraceLevel)) ; FinalState = State ). % Note: DataMemory is updated destructively for efficiency purposes % While this is not routinely advisable nor necessary, we do it anyway. % cycle does one execution cycle: % It fetches the instruction at Location from Instruction Memory % then executes the instruction. It also returns the next instruction's % location. The latter is normally the next location in instruction memory, % but it may be altered by a jump instruction. cycle(state( Stack, Location, InstructionMemory, DataMemory), state(NewStack, NewLocation, InstructionMemory, NewDataMemory)) :- fetch(Location, InstructionMemory, Instruction), next(Location, NextLocation), execute(Instruction, Stack, NewStack, NextLocation, NewLocation, DataMemory, NewDataMemory). % Display the state at a specific step. showState(Step, State) :- write('step '), write(Step), write(': '), nl, State = state(Stack, Location, InstructionMemory, DataMemory), write('stack '), write(Stack), nl, write('memory '), write(DataMemory), nl, write('memory '), write(InstructionMemory), nl, fetch(Location, InstructionMemory, Instruction), write('instruction '), write(Location), write(': '), write(Instruction), nl, nl. % execute executes the various NoRM instructions. % execute(Instruction, Stack, New Stack, Location Now, Next Location, DataMemory, NewDataMemory) % NoRM Instruction Repertoire, one instruction per clause. % Most instructions do not have an argument. % The ones that do are: push, jump, fetch, and store. % NoRM push(Constant) instruction pushes a constant (number) onto the stack. execute(push(Constant), Stack, [Constant | Stack], Location, Location, DataMemory, DataMemory). % NoRM pop instruction removes the top of the stack and discards it. execute(pop, [_ | Stack], Stack, Location, Location, DataMemory, DataMemory) . % NoRM rep instruction replicates the top element of the stack. execute(rep, [V | Stack], [V, V | Stack], Location, Location, DataMemory, DataMemory) . % NoRM flip instruction flips the top two stack elements. execute(flip, [V1, V2 | Stack], [V2, V1 | Stack], Location, Location, DataMemory, DataMemory) . % NoRM add instruction pops the top two stack elements and pushes the sum. execute(add, [V1, V2 | Stack], [V3 | Stack], Location, Location, DataMemory, DataMemory) :- V3 is V1 + V2. % NoRM subtract instruction pops the top two stack elements and pushes the % top minus the second. execute(subtract, [V1, V2 | Stack], [V3 | Stack], Location, Location, DataMemory, DataMemory) :- V3 is V1 - V2. % NoRM multiply instruction pops the top two stack elements and pushes the product. execute(multiply, [V1, V2 | Stack], [V3 | Stack], Location, Location, DataMemory, DataMemory) :- V3 is V1 * V2. % NoRM divide instruction pops the top two stack elements and pushes the % quotient of the top divided by the second (integer division). execute(divide, [V1, V2 | Stack], [V3 | Stack], Location, Location, DataMemory, DataMemory) :- V3 is V1 // V2. % NoRM mod instruction pops the top two stack elements and pushes the % remainder of the top divided by the second (integer division). execute(mod, [V1, V2 | Stack], [V3 | Stack], Location, Location, DataMemory, DataMemory) :- V3 is V1 mod V2. % NoRM equal instruction tests the top two elements for equality. % The tested elements are removed from the stack. A 1 is pushed if the values are equal, % and a 0 is pushed otherwise. execute(equal, [V1, V2 | Stack], [V3 | Stack], Location, Location, DataMemory, DataMemory) :- V1 == V2 -> V3 = 1 ; V3 = 0. % NoRM less instruction tests the top two elements for inequality % The tested elements are removed from the stack. A 1 is pushed if the top value is less % than the second, and a 0 is pushed otherwise. execute(less, [V1, V2 | Stack], [V3 | Stack], Location, Location, DataMemory, DataMemory) :- V1 < V2 -> V3 = 1 ; V3 = 0. % NoRM 'not' instruction replaces the top value on the stack by 1 if it is 0, % and by 0 otherwise. execute(not, [V1 | Stack], [V2 | Stack], Location, Location, DataMemory, DataMemory) :- V1 == 0 -> V2 = 1 ; V2 = 0. % NoRM jump instruction, with argument Offset, pops the top value on the stack. % If that value was 0 then the next instruction is taken from the instruction location % that is Offset away from the current instruction. Otherwise the next instruction is % from the next location as normal. execute(jump(Offset), [Value | Stack], Stack, Location, NewLocation, DataMemory, DataMemory) :- Value == 0 -> NewLocation is Location + Offset - 1 % zero: jump taken ; NewLocation is Location. % non-zero: jump not taken % NoRM fetch instruction pushes the contents of the addressed data memory location % onto the stack. execute(fetch(Address), Stack, [Value | Stack], Location, Location, DataMemory, DataMemory) :- fetch(Address, DataMemory, Value). % NoRM store instruction stores into the addressed data memory location % the top value on the stack (which stays there). execute(store(Address), [Value | Stack], [Value | Stack], Location, Location, DataMemory, NewDataMemory):- store(Address, DataMemory, Value, NewDataMemory). % NoRM halt instruction produces a failure, so that cycling stops. execute(halt, Stack, Stack, Location, Location, DataMemory, DataMemory) :- !, fail. % Any other instruction also causes failure, and an error message. execute(Other, Stack, Stack, Location, Location, DataMemory, DataMemory) :- write('*** Unidentified operation: '), write(Other), nl, fail. % Get the contents of a memory location, where the entire memory is % represented by a single Prolog term (treated as an array). fetch(Location, MemoryTerm, Value) :- arg(Location, MemoryTerm, Value) -> true ; write('*** Memory fetch of address '), write(Location), write(' failed for memory '), write(MemoryTerm), nl, fail. % Store a value in the specified memory location. % Caution: Updating is destructive, using setarg. store(Location, DataMemory, Value, NewDataMemory) :- DataMemory =.. [data | List], setList(Location, List, Value, NewList), NewDataMemory =.. [data | NewList], !. store(Location, DataMemory, Value, _NewDataMemory) :- write('*** Memory store of '), write(Value), write(' into address '), write(Location), write(' failed for memory '), write(DataMemory), nl, fail. setList(1, [_ | X], Value, [Value | X]) :- !. setList(1, [], Value, [Value]) :- !. setList(N, [A | X], Value, [A | Y]) :- N > 1, N1 is N-1, setList(N1, X, Value, Y). setList(N, [], Value, [0 | Y]) :- N > 1, N1 is N-1, setList(N1, [], Value, Y). % Compute the location of the next instruction. next(Location, NextLocation) :- NextLocation is Location + 1. % end of NoRM definitions %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Testing code. Should not be modified, except to add more tests. % Get variable value for test purposes. getVarValue(Var, Memory, Value) :- env(Var, Location), fetch(Location, Memory, Value). % Check expectation checkExpectations([], _). checkExpectations([[Var, Value] | More], Memory) :- checkExpectation(Var, Value, Memory), checkExpectations(More, Memory). checkExpectation(Var, Expected, Memory) :- write('Expectation '), write(Var), write(' = '), write(Expected), getVarValue(Var, Memory, Actual), Expected = Actual -> record_success_run ; record_failure_run. record_success_tokenization :- write('Tokenization succeeded '), nl, increment(tokenization_successes(_)). record_failure_tokenization(Actual) :- write(' failed, actual is '), write(Actual), write(' <<<<<< test failed '), nl, increment(tokenization_failures(_)). record_failure_tokenization :- write(' failed'), write(' <<<<<< tokenization failed '), nl, increment(tokenization_failures(_)). record_success_run :- nl, write('Run succeeded '), nl, increment(run_successes(_)). record_failure_run :- nl, write(' failed '), write(' <<<<<< test failed '), nl, increment(run_failures(_)). increment(Term) :- retract(Term), Term =.. [Functor, Arg], Arg1 is Arg + 1, NewTerm =.. [Functor, Arg1], assert(NewTerm). report :- write('Test summary: '), nl, tokenization_successes(TS), write(TS), write(' tokenization successes.'), nl, tokenization_failures(TF), write(TF), write(' tokenization failures.'), nl, run_successes(RS), write(RS), write(' run successes, '), nl, run_failures(RF), write(RF), write(' run failures.'), nl. % Test a program against syntactic and semantic expectations. % By compiling, and if compilation is successful, running on NoRM. test(Program, Expectation, ExpectedFinalState) :- write('Program: '), write(Program), nl, tokenize(Program, Tokens), write('Tokens: '), write(Tokens), nl, write('Expectation: '), write(Expectation), nl, (compile(Tokens, Code) % compile token list into code -> (Expectation == success -> ( record_success_tokenization, runNoRM(Code, ExpectedFinalState) ) ; record_failure_tokenization(failure)) ; (Expectation == failure -> record_success_tokenization ; record_failure_tokenization) ), nl. % Run Code on Norm and check with expectations about final state: runNoRM(Code, ExpectedFinalState) :- write('NoRM Code: '), write(Code), nl, initialMemoryLoad(MemoryLoad), run(Code, MemoryLoad, FinalState), FinalState = state(Stack, Location, _, DataMemory), write('Final Instruction Location: '), write(Location), nl, write('Final Stack Contents: '), write(Stack), nl, write('Final Data Memory: '), write(DataMemory), nl, write('Expected Final State: '), write(ExpectedFinalState), nl, checkExpectations(ExpectedFinalState, DataMemory), nl. % Tokenizer for our language % Program is a list of characters. % Tokens is returned as the list of tokens. tokenize(Program, Tokens) :- atom_chars(Program, Chars), phrase(tokens(Tokens), Chars). % Tokenizer productions in DCG Notation. % Note that pure Prolog code can be used inside braces { }. % Produce a list of tokens from a list of characters. tokens(Tokens) --> whitespace, {!}, tokens(Tokens). tokens([Token | Tokens]) --> token(Token), {!}, tokens(Tokens). tokens([]) --> []. % Note that {!} (called "cut") intentionally prevents backtracking. % Produce a single token, one of three types. token(Token) --> numeric(Token) | identifier(Token) | specialChar(Token). % An identifier is defined to be a letter (the "head") % followed by 0 or more letters and digits (the "tail") % Built-in atom_chars makes an atom (token) from a list of characters, or vice-versa. % This code is not efficient, but this is only a prototype. identifier(Token) --> identifierHead(H), {!}, identifierTail(T), {atom_chars(Token, [H | T])}. identifierHead(C) --> [C], {atom_chars('abcdefghijklmnopqrstuvwxyz', L), member(C, L)}. identifierTail([C | T]) --> identifierChar(C), {!}, identifierTail(T). identifierTail([]) --> []. identifierChar(C) --> [C], {atom_chars('abcdefghijklmnopqrstuvwxyz0123456789', L), member(C, L)}. % A 'numeric' is essentially a numeral, but we convert the numeral as an atom % to a Prolog number so that we can do arithmetic on it at a later time. numeric(N) --> numeral(L), {atom_chars(A, L), safe_atom_number(A, N)}. numeral([S | L]) --> sign(S), unsigned(L). numeral(L) --> unsigned(L). unsigned([D | L]) --> digit(D), unsigned(L). unsigned([D]) --> digit(D). digit(D) --> [D], {member(D, ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'])}. sign(S) --> [S], {member(S, ['+', '-'])}. specialChar(C) --> [C], {member(C, ['{', '}', '(', ')', ';', '+', '*', '=', '<'])}. % Whitespace can appear at various places in a valid string. whitespace --> whitespaceChar. whitespace --> whitespaceChar, whitespace. whitespaceChar --> [C], {member(C, [' '])}. % convert atoms that are numeric into numbers, if possible safe_atom_number(Atom, N) :- catch(atom_number(Atom, N), _, fail) -> true ; N = Atom. /* Tests for the syntax-checking only version */ test :- test('x = 5 ;', success, [[x, 5]]), test('x = z ;', success, [[x, 60]]), test('x = y + z ;', success, [[x, 110]]), test('x = u + v + w ;', success, [[x, 60]]), test('x = u + v * w ;', success, [[x, 610]]), test('x = u * v + w ;', success, [[x, 230]]), test('x = u * v * w ;', success, [[x, 6000]]), test('x = ( u + v ) * w ;', success, [[x, 900]]), test('x = u * ( v + w ) ;', success, [[x, 500]]), test('x = ( u + y ) * ( v + w ) ;', success, [[x, 3000]]), test('x = u * y + ( v * w ) ;', success, [[x, 1100]]), test('x = u * 9 + ( 8 * w ) ;', success, [[x, 330]]), test('{ x = 5 ; y = 10 ; }', success, [[x, 5], [y, 10]]), test('{ x = 5 ; y = x ; }', success, [[x, 5], [y, 5]]), test('if ( y < 60 ) x = 5 ;', success, [[x, 5]]), test('if ( y = 50 ) x = 5 ;', success, [[x, 5]]), test('if ( y = 55 ) x = 5 ;', success, [[x, 40]]), test('if ( y = 50 ) x = 5 ; else x = 6;', success, [[x, 5]]), test('if ( y = 55 ) x = 5 ; else x = 6;', success, [[x, 6]]), test('{ x = 0 ; while ( x < 5 ) x = x + 1 ; }', success, [[x, 5]]), test('{ x = 0 ; y = 0 ; while ( x < 5 ) { x = x + 1 ; y = y + 5 ; } }', success, [[x, 5], [y, 25]]), test('a = 5 ;', success, [[a, 5]]), test('{a = 5 ; b = 6; c = a + b;}', success, [[a, 5], [b, 6], [c, 11]]), test('{ x = 0 ; z = 0; \ while ( x < 5 ) \ { y = 0; \ while ( y < x ) { z = z + 2; y = y + 1;} \ x = x + 1; \ } \ }', success, [[x, 5], [z, 20]]), report. /* Sample output running test.: While all tokenizations should succeed, only a couple of runs will, because the generated code is mostly wrong until you code the semantics. /opt/local/bin/swipl -f a10new.pro % /Users/keller/Desktop/a10new.pro compiled 0.01 sec, 39,956 bytes Welcome to SWI-Prolog (Multi-threaded, Version 5.6.49) Copyright (c) 1990-2007 University of Amsterdam. SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- test. Program: x = 5 ; Tokens: [x, =, 5, (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 5]] Expectation x = 5 Run succeeded Program: x = z ; Tokens: [x, =, z, (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 60]] Expectation x = 60 failed <<<<<< test failed Program: x = y + z ; Tokens: [x, =, y, +, z, (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 110]] Expectation x = 110 failed <<<<<< test failed Program: x = u + v + w ; Tokens: [x, =, u, +, v, +, w, (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 60]] Expectation x = 60 failed <<<<<< test failed Program: x = u + v * w ; Tokens: [x, =, u, +, v, *, w, (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 610]] Expectation x = 610 failed <<<<<< test failed Program: x = u * v + w ; Tokens: [x, =, u, *, v, +, w, (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 230]] Expectation x = 230 failed <<<<<< test failed Program: x = u * v * w ; Tokens: [x, =, u, *, v, *, w, (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 6000]] Expectation x = 6000 failed <<<<<< test failed Program: x = ( u + v ) * w ; Tokens: [x, =, (, u, +, v, ), *, w, (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 900]] Expectation x = 900 failed <<<<<< test failed Program: x = u * ( v + w ) ; Tokens: [x, =, u, *, (, v, +, w, ), (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 500]] Expectation x = 500 failed <<<<<< test failed Program: x = ( u + y ) * ( v + w ) ; Tokens: [x, =, (, u, +, y, ), *, (, v, +, w, ), (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 3000]] Expectation x = 3000 failed <<<<<< test failed Program: x = u * y + ( v * w ) ; Tokens: [x, =, u, *, y, +, (, v, *, w, ), (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 1100]] Expectation x = 1100 failed <<<<<< test failed Program: x = u * 9 + ( 8 * w ) ; Tokens: [x, =, u, *, 9, +, (, 8, *, w, ), (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[x, 330]] Expectation x = 330 failed <<<<<< test failed Program: { x = 5 ; y = 10 ; } Tokens: [{, x, =, 5, (;), y, =, 10, (;), }] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[x, 5], [y, 10]] Expectation x = 5 failed <<<<<< test failed Expectation y = 10 failed <<<<<< test failed Program: { x = 5 ; y = x ; } Tokens: [{, x, =, 5, (;), y, =, x, (;), }] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[x, 5], [y, 5]] Expectation x = 5 failed <<<<<< test failed Expectation y = 5 failed <<<<<< test failed Program: if ( y < 60 ) x = 5 ; Tokens: [if, (, y, <, 60, ), x, =, 5, (;)] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[x, 5]] Expectation x = 5 failed <<<<<< test failed Program: if ( y = 50 ) x = 5 ; Tokens: [if, (, y, =, 50, ), x, =, 5, (;)] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[x, 5]] Expectation x = 5 failed <<<<<< test failed Program: if ( y = 55 ) x = 5 ; Tokens: [if, (, y, =, 55, ), x, =, 5, (;)] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[x, 40]] Expectation x = 40 Run succeeded Program: if ( y = 50 ) x = 5 ; else x = 6; Tokens: [if, (, y, =, 50, ), x, =, 5, (;), else, x, =, 6, (;)] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[x, 5]] Expectation x = 5 failed <<<<<< test failed Program: if ( y = 55 ) x = 5 ; else x = 6; Tokens: [if, (, y, =, 55, ), x, =, 5, (;), else, x, =, 6, (;)] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[x, 6]] Expectation x = 6 failed <<<<<< test failed Program: { x = 0 ; while ( x < 5 ) x = x + 1 ; } Tokens: [{, x, =, 0, (;), while, (, x, <, 5, ), x, =, x, +, 1, (;), }] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[x, 5]] Expectation x = 5 failed <<<<<< test failed Program: { x = 0 ; y = 0 ; while ( x < 5 ) { x = x + 1 ; y = y + 5 ; } } Tokens: [{, x, =, 0, (;), y, =, 0, (;), while, (, x, <, 5, ), {, x, =, x, +, 1, (;), y, =, y, +, 5, (;), }, }] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[x, 5], [y, 25]] Expectation x = 5 failed <<<<<< test failed Expectation y = 25 failed <<<<<< test failed Program: a = 5 ; Tokens: [a, =, 5, (;)] Expectation: success Tokenization succeeded NoRM Code: [push(5), store(4), halt] Final Instruction Location: 3 Final Stack Contents: [5] Final Data Memory: data(10, 20, 30, 5, 50, 60) Expected Final State: [[a, 5]] Expectation a = 5 failed <<<<<< test failed Program: {a = 5 ; b = 6; c = a + b;} Tokens: [{, a, =, 5, (;), b, =, 6, (;), c, =, a, +, b, (;), }] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[a, 5], [b, 6], [c, 11]] Expectation a = 5 failed <<<<<< test failed Expectation b = 6 failed <<<<<< test failed Expectation c = 11 failed <<<<<< test failed Program: { x = 0 ; z = 0; while ( x < 5 ) { y = 0; while ( y < x ) { z = z + 2; y = y + 1;} x = x + 1; } } Tokens: [{, x, =, 0, (;), z, =, 0, (;), while, (, x, <, 5, ), {, y, =, 0, (;), while, (, y, <, x, ), {, z, =, z, +, 2, (;), y, =, y, +, 1, (;), }, x, =, x, +, 1, (;), }, }] Expectation: success Tokenization succeeded NoRM Code: [halt] Final Instruction Location: 1 Final Stack Contents: [] Final Data Memory: data(10, 20, 30, 40, 50, 60) Expected Final State: [[x, 5], [z, 20]] Expectation x = 5 failed <<<<<< test failed Expectation z = 20 failed <<<<<< test failed Test summary: 24 tokenization successes. 0 tokenization failures. 2 run successes, 28 run failures. Yes ?- */