I have managed to parse and evaluate using an AST. I got stuck in statements and block

Hello,


I am writing a simple interpreter. I have managed to implement:


        Lexer
        Recursive descent parser
        Building AST
        Evaluating AST


My interpreter can evaluate arithmetic expressions and boolean expressions.


But I got stuck in implementing statements, code block, if and while statements.


The grammar is pretty simple:


<b-expression> ::= <b-term> [<orop> <b-term>]*
<b-term> ::= <b-factor> [AND <b-factor>]*
<b-factor> ::= <b-variable> | <relation>
<relation> ::= | <expression> [<relop> <expression]
<expression> ::= <term> [<addop> <term>]*
<term> ::= <factor> [<mulop> factor]*
<factor> ::= <integer> | <variable> | (<b-expression>)
<if> ::= IF <bool-expression> <block> [ ELSE <block>] ENDIF'
<while> ::= WHILE <bool-expression> <block> ENDWHILE
<block> ::= ( <statement> )*
<statement> ::= <if> | <while> | <assignment>


Here is an example program I want to be able to interpret with my interpreter:


~~~~~~~~~~~~~~~~~~~~~~
counter = 0;
while (count<10)
begin
        write count
        if count == 5 write("High Five")
        count = count + 1
end
~~~~~~~~~~~~~~~~~~~~~~


Here is my implementation:


//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
program AST;


const TAB = ^I;
const CR = ^M;
const LF = ^J;


var Look : Char;
var Token : String;
var Value : Integer;


Type
Node = ^TokenRec;
TokenRec = record
        NodeType: char;
        Value : integer;
        Left : Node;
        Right : Node;
end;


function CreateNode(NodeType: char; left: Node; right: Node): Node;
var Temp: Node;
begin
                new(Temp);
                Temp^.NodeType := NodeType;
                Temp^.Left := left;
                Temp^.Right := right;
                Temp^.Value := 0;


                CreateNode := Temp;
end;


function CreateNodeNumber(value: integer): Node;
Var Temp: Node;
begin
                new(Temp);
                Temp^.NodeType := 'N';
                Temp^.Value := value;


                CreateNodeNumber := Temp;
end;


function Evaluate(Subtree: Node): integer;
var eval_result_left, eval_result_right: integer;
var op: char;
begin


        if(Subtree^.NodeType = 'N') then
        begin
                Evaluate := SubTree^.Value;
        end;


        if Subtree^.NodeType in ['*','/','+','-'] then
        begin
                op := Subtree^.NodeType;
                eval_result_left := Evaluate(Subtree^.left);
                eval_result_right := Evaluate(Subtree^.right);


                if (op = '*') then Evaluate := eval_result_left * eval_result_right;
                if (op = '/') then Evaluate := eval_result_left div eval_result_right;


                if (op = '+') then Evaluate := eval_result_left + eval_result_right;
                if (op = '-') then Evaluate := eval_result_left - eval_result_right;
      end;
end;


function EvaluateBool(Subtree: Node): Boolean;
var eval_result_left, eval_result_right: integer;
var op: char;
begin


        if Subtree^.NodeType in ['=','<','>','#','|'] then
        begin
                op := Subtree^.NodeType;
                eval_result_left := Evaluate(Subtree^.left);
                eval_result_right := Evaluate(Subtree^.right);


                if (op = '=') then EvaluateBool := eval_result_left = eval_result_right;
                if (op = '<') then EvaluateBool := eval_result_left < eval_result_right;


                if (op = '>') then EvaluateBool := eval_result_left > eval_result_right;
                if (op = '#') then EvaluateBool := eval_result_left <> eval_result_right;
      end;
end;




procedure GetChar;
begin
      Read(Look);
end;


procedure Error(s: string);
begin
      WriteLn;
      WriteLn(^G, 'Error: ', s, '.');
end;


procedure Abort(s: string);
begin
      Error(s);
      Halt;
end;


procedure Expected(s: string);
begin
      Abort(s + ' Expected');
end;


function IsAlpha(c: char): boolean;
begin
      IsAlpha := upcase(c) in ['A'..'Z'];
end;


function IsDigit(c: char): boolean;
begin
      IsDigit := c in ['0'..'9'];
end;


function IsAlNum(c: char): boolean;
begin
      IsAlNum := IsAlpha(c) or IsDigit(c);
end;


function IsAddop(c: char): boolean;
begin
      IsAddop := c in ['+', '-'];
end;


function IsMulop(c: char): boolean;
begin
      IsMulop := c in ['*', '/'];
end;


function IsWhite(c: char): boolean;
begin
      IsWhite := c in [' ', TAB];
end;


procedure SkipWhite;
begin
      while IsWhite(Look) do
            GetChar;
end;


procedure NewLine;
begin
        while Look in [CR, LF] do
        begin
                GetChar;
                SkipWhite;
        end;
end;


function GetName: string;
var TempStr: string;
begin
        TempStr := '';
        NewLine;
        if not IsAlpha(Look) then Expected('Name');


        while IsAlNum(Look) do
        begin
                TempStr := TempStr + UpCase(Look);
                GetChar;
        end;
        GetName := TempStr;
        SkipWhite;
end;




function GetNum: integer;
var Val: integer;
begin
        Val := 0;
        if not IsDigit(Look) then Expected('Integer');
        while IsDigit(Look) do
        begin
                Val := 10 * Val + Ord(Look) - Ord('0');
                GetChar;
        end;
        GetNum := Val;
        SkipWhite;
end;


procedure Match(x: char);
begin
      if Look = x then GetChar
      else Expected('''' + x + '''');
      SkipWhite;
end;


function Expression: Node; Forward;


function IsOrop(c: char): boolean;
begin
      IsOrop := c in ['|', '~'];
end;


function IsRelop(c: char): boolean;
begin
      IsRelop := c in ['=', '#', '<', '>'];
end;


function Greater: Node;
begin
        Match('>');
        Greater := Expression;
end;


function Less: Node;
begin
        Match('<');
        Less := Expression;
end;


function NotEquals: Node;
begin
      Match('#');
      NotEquals := Expression;
end;


function Equals: Node;
begin
      Match('=');
      Equals := Expression;
end;


function Relation: Node;
var TempNode: Node;
begin
      TempNode := Expression;
      if IsRelop(Look) then
      begin
            case Look of
              '=': Relation := CreateNode('=', TempNode, Equals);
              '<': Relation := CreateNode('<', TempNode, Less);
              '>': Relation := CreateNode('>', TempNode, Greater);
              '#': Relation := CreateNode('#', TempNode, NotEquals);
            end;
      end;
end;


function BoolFactor: Node;
begin
        if Look = '(' then
        begin
                Match('(');
                BoolFactor := Relation;
                Match(')');
        end;
        if IsAlNum(Look) then
        begin
                BoolFactor := Relation;
        end;
end;


function Factor: Node; forward;


function BoolTerm: Node;
begin
        BoolTerm := BoolFactor;
        while Look = '&' do
        begin
                Match('&');
                BoolTerm := CreateNode('&', BoolTerm, BoolFactor);
        end;
end;


function BoolOr: Node;
begin
      Match('|');
      BoolOr := BoolTerm;
end;


function BoolExpression: Node;
begin
        BoolExpression := BoolTerm;
        while IsOrOp(Look) do
        begin
                case Look of
                        '|': BoolExpression := CreateNode('|', BoolExpression, BoolOr);
                end;
        end;
end;


function Factor: Node;
begin
        if Look = '(' then
        begin
                Match('(');
                Factor := Expression;
                Match(')');
        end;


        if IsDigit(Look) then
        begin
                Factor := CreateNodeNumber(GetNum);
        end;
end;


function Multiply: Node;
begin
      Match('*');
      Multiply := Factor;
end;


function Divide: Node;
begin
      Match('/');
      Divide := Factor;
end;


function Term: Node;
begin
        Term := Factor;
        while Look in ['*','/'] do
        begin
                case Look of
                '*': Term := CreateNode('*', Term, Multiply);
                '/': Term := CreateNode('/', Term, Divide);
                end;
        end;
end;


function Add: Node;
begin
      Match('+');
      Add := Term;
end;


function Subtract: Node;
begin
      Match('-');
      Subtract := Term;
end;


function Expression: Node;
begin
        Expression := Term;
        while Look in ['+','-'] do
        begin
                case Look of
                '+': Expression:= CreateNode('+', Expression, Add);
                '-': Expression := CreateNode('-', Expression, Subtract);
                end;
        end;
end;


procedure Block; forward;


procedure Assignment;
begin
        Writeln('ASSIGNMENT');
end;


procedure DoWrite;
begin
        Writeln('EXECUTE WRITE COMMAND');
end;


procedure DoIf;
var TempBool: boolean;
begin
        Writeln('EXECUTE DOIF STATEMENT');
end;


procedure Block;
begin
        Token := GetName;
        while (Token <> 'END') and (Token <> 'ENDIF') do
        begin
                begin
                        case Token of
                                'IF' : DoIf;
                                'WRITE' : DoWrite;
                                else Assignment;
                        end;
                end;
                Token := GetName;
        end;
end;


procedure Init;
begin
        Token := '';
        GetChar;
end;


begin
        Init;
        Writeln(EvaluateBool(BoolExpression));
end.
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


I am following Jack Crenshaw's Let's Build a Compiler book. So, you
will notice that the code I write is based on his book. Here is the
link: http://compilers.iecc.com/crenshaw


My approach is a bit different since I am writing an interpreter, not
a compiler. So, instead of putting assembly code generation direcly
into the parser, I needed an AST to keep some state and then evaluate
that AST.


I am going to use linked list to keep variables as a symbol table. I
can implement it without any problem. I just did not place it in the
code here to make it some more shorter, at least for now.


Can you please help me to design if, while, statement and statement
block functions? How can I implement this? What do I miss here in my
implementation that caused me getting stuck without a working
interpreter.


Please note that I have to use data structures like linked list, tree
and similars. But not object oriented or a more high level language.


Thanks in advance.
[You just make nodes in the AST to describe the various statements.
An IF statement has three subtrees, the condition, the true branch,
and the false branch. A WHILE has two subtrees, the condition, and
the loop body. The code subtrees likely need something to represent
a sequence of statements, such as an array or a sub-list. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.