Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!news.misty.com!news.iecc.com!.POSTED!nerds-end
From: mehmet.coskun@gmail.com
Newsgroups: comp.compilers
Subject: I have managed to parse and evaluate using an AST. I got stuck in statements and block
Date: Wed, 18 Feb 2015 11:20:47 -0800 (PST)
Organization: Compilers Central
Lines: 462
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <15-02-027@comp.compilers>
NNTP-Posting-Host: news.iecc.com
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
X-Trace: miucha.iecc.com 1424303608 12391 2001:470:1f07:1126:0:676f:7373:6970 (18 Feb 2015 23:53:28 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Wed, 18 Feb 2015 23:53:28 +0000 (UTC)
Keywords: question, interpreter, comment
Posted-Date: 18 Feb 2015 18:53:28 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:1529

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]