Compiler/AST interpreter: Difference between revisions
Added
m (Fix embedded // in string handling) |
(Added) |
||
Line 158:
<hr>
__TOC__
=={{header|ALGOL W}}==
<lang algolw>begin % AST interpreter %
% parse tree nodes %
record node( integer type
; reference(node) left, right
; integer iValue % nString/nIndentifier number or nInteger value %
);
integer nIdentifier, nString, nInteger, nSequence, nIf, nPrtc, nPrts
, nPrti, nWhile, nAssign, nNegate, nNot, nMultiply
, nDivide, nMod, nAdd, nSubtract, nLess, nLessEqual
, nGreater, nGreaterEqual, nEqual, nNotEqual, nAnd, nOr
;
string(14) array ndName ( 1 :: 25 );
integer MAX_NODE_TYPE;
% string literals and identifiers - uses a linked list - a hash table might be better... %
string(1) array text ( 0 :: 4095 );
integer textNext, TEXT_MAX;
record textElement ( integer start, length; reference(textElement) next );
reference(textElement) idList, stList;
% memory - identifiers hold indexes to locations here %
integer array data ( 1 :: 4096 );
% returns a new node with left and right branches %
reference(node) procedure opNode ( integer value opType; reference(node) value opLeft, opRight ) ; begin
node( opType, opLeft, opRight, 0 )
end opNode ;
% returns a new operand node %
reference(node) procedure operandNode ( integer value opType, opValue ) ; begin
node( opType, null, null, opValue )
end operandNode ;
% reports an error and stops %
procedure rtError( string(80) value message ); begin
integer errorPos;
write( s_w := 0, "**** Runtime error " );
errorPos := 0;
while errorPos < 80 and message( errorPos // 1 ) not = "." do begin
writeon( s_w := 0, message( errorPos // 1 ) );
errorPos := errorPos + 1
end while_not_at_end_of_message ;
writeon( s_w := 0, "." );
assert( false )
end rtError ;
% reads a node from standard input %
reference(node) procedure readNode ; begin
reference(node) resultNode;
% parses a string from line and stores it in a string in the text array %
% - if it is not already present in the specified textElement list. %
% returns the position of the string in the text array %
integer procedure readString ( reference(textElement) value result txList; string(1) value terminator ) ; begin
string(256) str;
integer sLen, sPos, ePos;
logical found;
reference(textElement) txPos, txLastPos;
% get the text of the string %
str := " ";
sLen := 0;
str( sLen // 1 ) := line( lPos // 1 );
sLen := sLen + 1;
lPos := lPos + 1;
while lPos <= 255 and line( lPos // 1 ) not = terminator and line( lPos // 1 ) not = "!" do begin
str( sLen // 1 ) := line( lPos // 1 );
sLen := sLen + 1;
lPos := lPos + 1
end while_more_string ;
if lPos > 255 then rtError( "Unterminated String in node file." );
% attempt to find the text in the list of strings/identifiers %
txLastPos := txPos := txList;
found := false;
ePos := 0;
while not found and txPos not = null do begin
ePos := ePos + 1;
found := ( length(txPos) = sLen );
sPos := 0;
while found and sPos < sLen do begin
found := str( sPos // 1 ) = text( start(txPos) + sPos );
sPos := sPos + 1
end while_not_found ;
txLastPos := txPos;
if not found then txPos := next(txPos)
end while_string_not_found ;
if not found then begin
% the string/identifier is not in the list - add it %
ePos := ePos + 1;
if txList = null then txList := textElement( textNext, sLen, null )
else next(txLastPos) := textElement( textNext, sLen, null );
if textNext + sLen > TEXT_MAX then rtError( "Text space exhausted." )
else begin
for cPos := 0 until sLen - 1 do begin
text( textNext ) := str( cPos // 1 );
textNext := textNext + 1
end for_cPos
end
end if_not_found ;
ePos
end readString ;
% gets an integer from the line - no checks for valid digits %
integer procedure readInteger ; begin
integer n;
n := 0;
while line( lPos // 1 ) not = " " and line( lPos // 1 ) not = "!" do begin
n := ( n * 10 ) + ( decode( line( lPos // 1 ) ) - decode( "0" ) );
lPos := lPos + 1
end while_not_end_of_integer ;
n
end readInteger ;
string(256) line;
string(16) name;
integer lPos, tPos, ndType;
tPos := lPos := 0;
readcard( line );
% get the node type name %
while line( lPos // 1 ) = " " do lPos := lPos + 1;
name := "";
while lPos < 256 and line( lPos // 1 ) not = " " and line( lPos // 1 ) not = "!" do begin
name( tPos // 1 ) := line( lPos // 1 );
lPos := lPos + 1;
tPos := tPos + 1
end while_more_name ;
% determine the node type %
ndType := 1;
resultNode := null;
if name not = ";" then begin
% not a null node %
while ndType <= MAX_NODE_TYPE and name not = ndName( ndType ) do ndType := ndType + 1;
if ndType > MAX_NODE_TYPE then rtError( "Malformed node." );
% handle the additional parameter for identifier/string/integer, or sub-nodes for operator nodes %
if ndType = nInteger or ndType = nIdentifier or ndType = nString then begin
while line( lPos // 1 ) = " " do lPos := lPos + 1;
if ndType = nInteger then resultNode := operandNode( ndType, readInteger )
else if ndType = nIdentifier then resultNode := operandNode( ndType, readString( idList, " " ) )
else % ndType = nString % resultNode := operandNode( ndType, readString( stList, """" ) )
end
else begin
% operator node %
reference(node) leftNode;
leftNode := readNode;
resultNode := opNode( ndType, leftNode, readNode )
end
end if_non_null_node ;
resultNode
end readNode ;
% interprets the specified node and returns the value %
integer procedure eval ( reference(node) value n ) ; begin
integer v;
% prints a string from text, escape sequences are interpreted %
procedure writeOnText( reference(textElement) value txHead; integer value txNumber ) ;
begin
reference(textElement) txPos;
integer count;
txPos := txHead;
count := 1;
while count < txNumber and txPos not = null do begin
txPos := next(txPos);
count := count + 1
end while_text_element_not_found ;
if txPos = null then rtError( "INTERNAL ERROR: text not found." )
else begin
% found the text - output it, handling escape sequences %
integer cPos;
cPos := 1; % start from 1 to skip over the leading " %
while cPos < length(txPos) do begin
string(1) ch;
ch := text( start(txPos) + cPos );
if ch not = "\" then writeon( s_w := 0, ch )
else begin
% escaped character %
cPos := cPos + 1;
if cPos > length(txPos) then rtError( "String terminates with ""\""." )
else begin
ch := text( start(txPos) + cPos );
if ch = "n" then % newline % write()
else writeon( s_w := 0, ch )
end
end;
cPos := cPos + 1
end while_not_end_of_string
end
end writeOnText ;
% returns 1 if val is true, 0 otherwise %
integer procedure booleanResult ( logical value val ) ; begin
if val then 1 else 0
end booleanResult ;
v := 0;
if n = null then v := 0
else if type(n) = nIdentifier then v := data( iValue(n) )
else if type(n) = nString then v := iValue(n)
else if type(n) = nInteger then v := iValue(n)
else if type(n) = nSequence then begin
% sequence - evaluate and discard the left branch and return the right branch %
v := eval( left(n) );
v := eval( right(n) )
end
else if type(n) = nIf then % if-else % begin
if eval( left(n) ) not = 0 then v := eval( left(right(n)) )
else v := eval( right(right(n)) );
v := 0
end
else if type(n) = nPrtc then % print character % writeon( s_w := 0, code( eval( left(n) ) ) )
else if type(n) = nPrts then % print string % writeOnText( stList, eval( left(n) ) )
else if type(n) = nPrti then % print integer % writeon( s_w := 0, i_w := 1, eval( left(n) ) )
else if type(n) = nWhile then % while-loop % begin
while eval( left(n) ) not = 0 do v := eval( right(n) );
v := 0
end
else if type(n) = nAssign then % assignment % data( iValue(left(n)) ) := eval( right(n) )
else if type(n) = nNegate then % unary - % v := - eval( left(n) )
else if type(n) = nNot then % unary not % v := booleanResult( eval( left(n) ) = 0 )
else if type(n) = nMultiply then % multiply % v := eval( left(n) ) * eval( right(n) )
else if type(n) = nDivide then % division % begin
integer lv, rv;
lv := eval( left(n) );
rv := eval( right(n) );
if rv = 0 then rtError( "Division by 0." )
else v := lv div rv
end
else if type(n) = nMod then % modulo % begin
integer lv, rv;
lv := eval( left(n) );
rv := eval( right(n) );
if rv = 0 then rtError( "Right operand of % is 0." )
else v := lv rem rv
end
else if type(n) = nAdd then % addition % v := eval( left(n) ) + eval( right(n) )
else if type(n) = nSubtract then % subtraction % v := eval( left(n) ) - eval( right(n) )
else if type(n) = nLess then % less-than % v := booleanResult( eval( left(n) ) < eval( right(n) ) )
else if type(n) = nLessEqual then % less or equal % v := booleanResult( eval( left(n) ) <= eval( right(n) ) )
else if type(n) = nGreater then % greater-than % v := booleanResult( eval( left(n) ) > eval( right(n) ) )
else if type(n) = nGreaterEqual then % greater or eq % v := booleanResult( eval( left(n) ) >= eval( right(n) ) )
else if type(n) = nEqual then % test equal % v := booleanResult( eval( left(n) ) = eval( right(n) ) )
else if type(n) = nNotEqual then % not-equal % v := booleanResult( eval( left(n) ) not = eval( right(n) ) )
else if type(n) = nAnd then % boolean "and" % begin
v := eval( left(n) );
if v not = 0 then v := eval( right(n) )
end
else if type(n) = nOr then % boolean "or" % begin
v := eval( left(n) );
if v = 0 then v := eval( right(n) );
end
else % unknown node % begin
rtError( "Unknown node type in eval." )
end;
v
end eval ;
nIdentifier := 1; ndName( nIdentifier ) := "Identifier"; nString := 2; ndName( nString ) := "String";
nInteger := 3; ndName( nInteger ) := "Integer"; nSequence := 4; ndName( nSequence ) := "Sequence";
nIf := 5; ndName( nIf ) := "If"; nPrtc := 6; ndName( nPrtc ) := "Prtc";
nPrts := 7; ndName( nPrts ) := "Prts"; nPrti := 8; ndName( nPrti ) := "Prti";
nWhile := 9; ndName( nWhile ) := "While"; nAssign := 10; ndName( nAssign ) := "Assign";
nNegate := 11; ndName( nNegate ) := "Negate"; nNot := 12; ndName( nNot ) := "Not";
nMultiply := 13; ndName( nMultiply ) := "Multiply"; nDivide := 14; ndName( nDivide ) := "Divide";
nMod := 15; ndName( nMod ) := "Mod"; nAdd := 16; ndName( nAdd ) := "Add";
nSubtract := 17; ndName( nSubtract ) := "Subtract"; nLess := 18; ndName( nLess ) := "Less";
nLessEqual := 19; ndName( nLessEqual ) := "LessEqual" ; nGreater := 20; ndName( nGreater ) := "Greater";
nGreaterEqual := 21; ndName( nGreaterEqual ) := "GreaterEqual"; nEqual := 22; ndName( nEqual ) := "Equal";
nNotEqual := 23; ndName( nNotEqual ) := "NotEqual"; nAnd := 24; ndName( nAnd ) := "And";
nOr := 25; ndName( nOr ) := "Or";
MAX_NODE_TYPE := 25; TEXT_MAX := 4095; textNext := 0;
stList := idList := null;
% parse the output from the syntax analyser and intetrpret parse tree %
eval( readNode )
end.</lang>
{{out}}
<pre>
3 is prime
5 is prime
7 is prime
11 is prime
...
83 is prime
89 is prime
97 is prime
101 is prime
Total primes found: 26
</pre>
=={{header|C}}==
| |||