Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1529 > unrolled thread

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

Back to article view | Back to comp.compilers

Contents

  I have managed to parse and evaluate using an AST. I got stuck in statements and block mehmet.coskun@gmail.com - 2015-02-18 11:20 -0800
    Re: I have managed to parse and evaluate using an AST. I got stuck in statements and block Christian Gollwitzer <auriocus@gmx.de> - 2015-02-19 10:22 +0100
    Re: I have managed to parse and evaluate using an AST. I got stuck in statements and block BartC <bc@freeuk.com> - 2015-02-19 21:51 +0000
      Re: I have managed to parse and evaluate using an AST. I got stuck in statements and block BartC <bc@freeuk.com> - 2015-02-21 20:52 +0000
        Re: I have managed to parse and evaluate using an AST. I got stuck in statements and block mehmet.coskun@gmail.com - 2015-03-05 18:53 -0500
    Re: I have managed to parse and evaluate using an AST. I got stuck in statements and block Hans Aberg <haberg-news@telia.com> - 2015-02-20 15:47 +0100

#1529 — 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]

[toc] | [next] | [standalone]

#1530

Am 18.02.15 um 20:20 schrieb mehmet.coskun@gmail.com:
> I am writing a simple interpreter. I have managed to implement:
>
>     Lexer
>     Recursive descent parser
>     Building AST

Any reason why you don't leave these steps to a tool like lex and yacc?
Would be much easier to enhance the language.

>     Evaluating AST
>
> My interpreter can evaluate arithmetic expressions and boolean expressions.
>
> But I got stuck in implementing statements, code block, if and while statements.
>  [...]
>
> 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.

Writing an interpreter is generally easier than a compiler. You just
need to execute the commands in high-level language. Compound statements
generally work by recursive invocation of the interpreter on the blocks.
This is not much different from your Evaluate() function, which evals
the subexpressions recursively. Let's assume you have a Dispatch
function which switches on the NodeType and invokes a specialized
function to interpret it. Then an if would be somthing like (pseudocode)

proc if(condition, trueblock, falseblock) {
	bool doit = Evaluate(condition);
	if (doit) {
		Dispatch(trueblock);
	} else {
		Dispatch(falsbelock);
	}
}

It's really not much more than just writing out the if-then-else in the
implementation language (which is Pascal in your case, I assume) and
decorating execution blocks with Dispatch() and expression blocks with
Evaluate(). Of course, you need to enhance your Node structure such that
it can hold three elements, instead of only two. Or an arbitrary list of
arguments, which would come handy if you choose to implement n-ary
functions.

Of course, such a simplistic interpreter does not provide the more
advanced features in modern interpreters like stackless execution (for
coroutines) or fast execution (due to branching and function calls).
Exceptions are possible using return codes on the Dispatch function.

> 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.

Your choice, it should be possible - but you should add in a another
very handy data structure, namely associative arrays (hash tables).
Linked lists are certainly awkward to implement variable lookup.

	Christian

[toc] | [prev] | [next] | [standalone]

#1531

On 18/02/2015 19:20, mehmet.coskun@gmail.com wrote:

> 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.

What you need for execution is some sort of program counter to tell you
whereabouts in the AST you are, and what to execute next. I can't quite
see that in the code you posted.

Can you at least executive linear code such as:

  write("One")
  write("Two")
  write("Three") ?


As to how to implement While; usually I would transform to linear
byte-code which would decompose it to conditional jumps and labels, but
in AST form it might be like this:

  evaluate_while(cond, body):
    if evaluate_expr(cond) = True then
       evaluate_stmt(body)
       NextLoc := Loc1
    else
       NextLoc := Loc2
    endif

(This is not Pascal...). Loc1 and Loc2 represent places in the AST. Loc1
refers to this while statement, and Loc2 is the next statment after the
while. NextLoc is some global which does the job of the program counter.

You might also make each kind of evaluate_stmt handler return or update
the program counter (NextLoc in my example). Most statements will just
increment it to the next statement; a few will perform a different
control transfer (such as 'break' or 'goto').

--
Bartc

[toc] | [prev] | [next] | [standalone]

#1533

On 19/02/2015 21:51, BartC wrote:
> On 18/02/2015 19:20, mehmet.coskun@gmail.com wrote:
>
>> 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.

> What you need for execution is some sort of program counter to tell you
> whereabouts in the AST you are, and what to execute next. I can't quite
> see that in the code you posted.

I had a go at taking an existing byte-code compiler and adapting the
byte-code generator to execute the code instead of producing the normal
output.

It was a lot harder than I expected! Certainly, to be able to randomly
jump from one part of the code to another is difficult. But to execute
your example, that can be done with almost the same AST-scanning method
I'd been using for the byte-code.

I started with this version of your example, but in the language this
compiler processes (which happens to be the same language the compiler
is written in):

proc start=
count:=0

while count<10 do
     println count
     if count=5 then
         println "High Five"
     fi
     count:=count+1
od
end

Then I only modified the small number of lines needed to get this to
execute. The While handler was:

proc eval_while (p,cond,body,c,d)=
while eval_expr(cond) do
     eval_block(body)
od
end

The If handler:

proc eval_if (p,cond,b,c,d) =
if eval_expr(cond) then
     eval_block(b)
elsif notnull(c) then  # else part is optional
     eval_block(c)
fi
end

So the while handler involves a while-loop, and the if-then-else handler
involves an if-then-else statement, which sort of makes sense.

For handling code-blocks and statements, I use:

proc eval_block (p)=
forall s in p.a do
     eval_stmt(s)
od
end

But this starts to depend on the details of how your AST is organised.
(I haven't shown assignment, since I haven't implemented variables
properly and it's just a kludge.)

The few operations I needed (<, =, +) are inside this function:

function eval_expr(p)=

switch p.tag
when j_const then
	return p.a

when j_name then        # variable name
	return p.a.code

when j_add then
	return eval_expr(p.a)+eval_expr(p.b)

when j_lt then
	return eval_expr(p.a)<eval_expr(p.b)

when j_eq then
	return eval_expr(p.a)=eval_expr(p.b)
......
end

But you seem to have that part sorted. The output from this is:

  0
  1
  2
  3
  4
  5
  High Five
  6
  7
  8
  9

So it seems to work. (To fully convert my project to execute ASTs is
quite a lot of work, and the simple approach above won't work. There is
also the problem of how to deal with programs consisting of multiple
modules - it would be necessary to store the AST in a file, a whole lot
of problems just to deal with that. For experimenting however it's fine.)

--
Bartc

[toc] | [prev] | [next] | [standalone]

#1538

On Sunday, February 22, 2015 at 5:36:56 AM UTC+2, BartC wrote:
> On 19/02/2015 21:51, BartC wrote:
> > On 18/02/2015 19:20, mehmet.coskun@gmail.com wrote:
> >
> >> 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.
>
> > What you need for execution is some sort of program counter to tell you
> > whereabouts in the AST you are, and what to execute next. I can't quite
> > see that in the code you posted.
>
> I had a go at taking an existing byte-code compiler and adapting the
> byte-code generator to execute the code instead of producing the normal
> output.
>
> It was a lot harder than I expected! Certainly, to be able to randomly
> jump from one part of the code to another is difficult. But to execute
> your example, that can be done with almost the same AST-scanning method
> I'd been using for the byte-code.
>
> I started with this version of your example, but in the language this
> compiler processes (which happens to be the same language the compiler
> is written in):
>
> proc start=
> count:=0
>
> while count<10 do
>      println count
>      if count=5 then
>          println "High Five"
>      fi
>      count:=count+1
> od
> end
>
> Then I only modified the small number of lines needed to get this to
> execute. The While handler was:
>
> proc eval_while (p,cond,body,c,d)=
> while eval_expr(cond) do
>      eval_block(body)
> od
> end
>
> The If handler:
>
> proc eval_if (p,cond,b,c,d) =
> if eval_expr(cond) then
>      eval_block(b)
> elsif notnull(c) then  # else part is optional
>      eval_block(c)
> fi
> end
>
> So the while handler involves a while-loop, and the if-then-else handler
> involves an if-then-else statement, which sort of makes sense.
>
> For handling code-blocks and statements, I use:
>
> proc eval_block (p)=
> forall s in p.a do
>      eval_stmt(s)
> od
> end
>
> But this starts to depend on the details of how your AST is organised.
> (I haven't shown assignment, since I haven't implemented variables
> properly and it's just a kludge.)
>
> The few operations I needed (<, =, +) are inside this function:
>
> function eval_expr(p)=
>
> switch p.tag
> when j_const then
> 	return p.a
>
> when j_name then        # variable name
> 	return p.a.code
>
> when j_add then
> 	return eval_expr(p.a)+eval_expr(p.b)
>
> when j_lt then
> 	return eval_expr(p.a)<eval_expr(p.b)
>
> when j_eq then
> 	return eval_expr(p.a)=eval_expr(p.b)
> ......
> end
>
> But you seem to have that part sorted. The output from this is:
>
>   0
>   1
>   2
>   3
>   4
>   5
>   High Five
>   6
>   7
>   8
>   9
>
> So it seems to work. (To fully convert my project to execute ASTs is
> quite a lot of work, and the simple approach above won't work. There is
> also the problem of how to deal with programs consisting of multiple
> modules - it would be necessary to store the AST in a file, a whole lot
> of problems just to deal with that. For experimenting however it's fine.)


Hello,

First of all, I thank all of you for your interest and sharing your
thoughts with practical examples.

First, let me tell you the good news. I have completed the AST that I
have been working on. Both in Pascal and JAVA.

I am going to get into details but I want to answer your questions:
- I don't use any parser generator at the moment since it is a learning
experiment that I write a hand coded recursive descent parser plus and AST and
its evaluator. I -nearly- completed all of those, just polishing up now.

- I don't think that it is good idea to use jumps in the AST because AST is
for that to eliminate this jumps. I can write a whole compiler without an AST
by using jumps, it works, I am %100 sure. But I don't think that an
interpreter is easy and effective thing to do using this sort of jumps. For an
interpreter, it seems that AST is better solution.
Plus, even I write a compiler, I would choose using AST since it has other
benefits like easy to understand code afterwards. But with jumps, it is more
mental switching like jumping from here to there in your mind. Besides, some
other benefits like, you can analyze the source code even only using the AST
structure. Some other example is, you can visualize the AST with the tools you
may write, etc. etc. There are a lot of benefits.

Now, I can get into details of my implementation. A friend of mine showed me
how to do it using Pascal variant type. It is an interesting data type that
you can store into it almost any kind of data, so implementing a tree data
structure that returns a node is more easier. In this node, there is int,
boolean, if, while, expression or other kind of structure. So, it is possible
to write recursive evaluator.

The tree is a data structure that every language construct is a node of the
tree. The eval function is recursive that it evaluates the tree.

So, when I wanted to write the JAVA version, I have used a node class that has
two essential properties: 1-Type 2-Parts. In type, I keep type of the node
like int, if, while, etc. In parts, I keep the parts of the language structure
like for example if the node is if statement then I keep the condition, body
and else body parts in this property.

Evaluator walks the tree recursively and evaluates every node and then returns
a new node if it needs.

After all this talk, I want to show the JAVA code here. It is not the one that
I optimized or done to be best one. But I can say that it is a good experiment
and explains the AST well in only 250 lines.

I am going to complete the polishing up the parser and will merge it with my
AST then I will have a full working -simple interpreter. Next step will be
adding sub routines to it.

Here you go the JAVA code:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
import java.util.*;

class Node
{
    public char Type;
    public char Op;
    public int  Value;
    public boolean  BooleanValue;
    public Map Parts;

    public Node()
    {
        this.BooleanValue = false;
        this.Value = 0;
        this.Op = '#';
        this.Type = '#';
    }

    public Node(char Type, int Value)
    {
        this.Type   = Type;
        this.Value  = Value;
    }

    public Node(char Type, Map Parts)
    {
        this.Type   = Type;
        this.Parts  = Parts;
    }

    public Node(char Type, char Op, Map Parts)
    {
        this.Type   = Type;
        this.Op     = Op;
        this.Parts  = Parts;
    }

    public String toString()
    {
        String str = "Type: " + this.Type + " Value: " + this.Value;
        return str;
    }
}
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~*/
class AST
{

    public static Map Env;

    public AST()
    {
        Env = new HashMap();
    }

    public static Node NewNumber(int Value)
    {
        return new Node('n', Value);
    }

    public static Node NewVar(String VarName)
    {
        Map Parts = new HashMap();
        Parts.put("VarName", VarName);

        return new Node('v', Parts);
    }

    // An assignment's var value is its right value. Right value can eithe be
an expression or a function call, or another variable
    public static Node NewAssignStmt(String VarName, Node VarValue)
    {
        Map Parts = new HashMap();
        Parts.put("VarName",    VarName);
        Parts.put("VarValue",   VarValue);

        return new Node('a', Parts);
    }

    public static Node NewBinOp(char Op, Node Left, Node Right)
    {
        Map Parts = new HashMap();
        Parts.put("Left",   Left);
        Parts.put("Right",  Right);

        return new Node('b', Op, Parts);
    }

    //It is for to add a new node for -1 -A*B alike things. TODO: What if they
enter +1 +A*B. Make a decision for it
    public static Node NewUnOp(Node Expression)
    {
        Map Parts = new HashMap();
        Parts.put("Expression",  Expression);

        return new Node('u', Parts);
    }

    public static Node NewWriteStmt(Node Expression)
    {
        Map Parts = new HashMap();
        Parts.put("Expression",   Expression);

        return new Node('w', Parts);
    }

    public static Node NewSeqStmt(Node Left, Node Right)
    {
        Map Parts = new HashMap();
        Parts.put("Left",   Left);
        Parts.put("Right",  Right);

        return new Node(';', Parts);
    }

    public static Node NewIfStmt(Node Condition, Node ThenPart, Node
ElsePart)
    {
        Map Parts = new HashMap();
        Parts.put("Condition",  Condition);
        Parts.put("ThenPart",   ThenPart);
        Parts.put("ElsePart",   ElsePart);

        return new Node('i', Parts);
    }

    public static Node NewWhileStmt(Node Condition, Node Body)
    {
        Map Parts = new HashMap();
        Parts.put("Condition",  Condition);
        Parts.put("Body",   Body);

        return new Node('h', Parts);
    }

    public static Node Eval(Node Tree)
    {
        int LeftValue = 0;
        int RightValue = 0;
        int Result = 0;
        Node node = new Node();

        if (Tree.Type == 'n') //Number
        {
            node = Tree;
        }

        if (Tree.Type == 'a') //Assignment statement
        {
            String VarName   = (String) Tree.Parts.get("VarName");
            Node VarValue  = (Node) Tree.Parts.get("VarValue");

            //TODO. Below, you can make it a late binding. Like, if you do not
evaluate it, you can put it into the Map directly as an expression
            //Then you can evaluate that expression when it needs this
expression get used somewhere in the program
            Env.put(VarName, Eval(VarValue));
        }

        if (Tree.Type == 'v') //Variable
        {
            String VarName   = (String) Tree.Parts.get("VarName");
            node = ( Node ) Env.get(VarName);
        }

        if (Tree.Type == 'u') //Unary statement
        {
            Node expression   = (Node) Tree.Parts.get("Expression");
            if (expression.Type  == 'n') node.Value = -expression.Value;else
node.Value = -Eval(expression).Value;
            node.Type = 'n';
        }

        if (Tree.Type == 'b') //Binary operations. They are +,-,*,/,|,% etc.
like two argument taking operations
        {
            Node Left   = (Node) Tree.Parts.get("Left");
            Node Right  = (Node) Tree.Parts.get("Right");

            if (Left.Type   == 'n') LeftValue  = Left.Value; else Eval(Left);
            if (Right.Type  == 'n') RightValue = Right.Value;else Eval(Right);

            switch(Tree.Op)
            {
                case '+':
                    node.Value = LeftValue + RightValue;
                    node.Type = 'n';
                break;
                case '-':
                    node.Value = LeftValue - RightValue;
                    node.Type = 'n';
                break;
                case '*':
                    node.Value = LeftValue * RightValue;
                    node.Type = 'n';
                break;
                case '/':
                    node.Value = LeftValue / RightValue;
                    node.Type = 'n';
                break;
                case '<':
                    boolean cmpRes = LeftValue < RightValue;
                    if (cmpRes)
                        node.BooleanValue = true; else node.BooleanValue =
false;
                    node.Type = 'o';
                break;
                case '>':
                    cmpRes = LeftValue > RightValue;
                    if (cmpRes)
                        node.BooleanValue = true; else node.BooleanValue =
false;
                    node.Type = 'o';
                break;
                //TODO test it very well
                case '=':
                    cmpRes = LeftValue == RightValue;
                    if (cmpRes)
                        node.BooleanValue = true; else node.BooleanValue =
false;
                    node.Type = 'o';
                break;
            }
        }

        if (Tree.Type == 'w') //Write statement
        {
            Node Expression = (Node) Tree.Parts.get("Expression");
            if (Expression != null)
                if (Expression.Type   == 'n')
System.out.println(Expression.Value); else
System.out.println(Eval(Expression).Value);
        }

        if (Tree.Type == ';') //Sequence
        {
            Node Left   = (Node) Tree.Parts.get("Left");
            Node Right  = (Node) Tree.Parts.get("Right");

            Eval(Left);
            Eval(Right);
        }

        if (Tree.Type == 'i') //If statement
        {
            Node ThenPart = (Node) Tree.Parts.get("ThenPart");
            Node ElsePart = (Node) Tree.Parts.get("ElsePart");
            Node Condition = (Node) Tree.Parts.get("Condition");

            if ( Eval(Condition).BooleanValue == true ) Eval(ThenPart); else
if ( Eval(Condition).BooleanValue == false ) Eval(ElsePart);
        }

        if (Tree.Type == 'h') //While statement
        {
            Node Body       = (Node) Tree.Parts.get("Body");
            Node Condition  = (Node) Tree.Parts.get("Condition");

            while (Eval(Condition).BooleanValue == true)
                Eval(Body);
        }

        return node;
    }
}//End class
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Greetings,

Mehmet.
---

[toc] | [prev] | [next] | [standalone]

#1532

On 2015/02/18 20:20, mehmet.coskun@gmail.com wrote:

> I am writing a simple interpreter.

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

As already pointed out, it easier to use parser generating tools like
Flex and Bison <https://gnu.org/software/bison/>. The latter has a
complete calculator example in for example C++ - easy to start with, and
then modify.

There is no clear distinction between a compiler or an interpreter, as
one can choose the point of execution; an interpreter might decide to
generate compiler code, and then execute it. This is possible with LLVM
<http://clang.llvm.org>, which has examples on how to get started.

As for code blocks and assignments/definitions, one needs a stacked name
look-up table: the lexer checks the name if it is defined on the table,
and if so, returns its correct grammatical type. If there is an inner
block (environment), one pushes a new level on the name table stack,
which is popped when the environment ends. Definitions always creates
names in the current level, whereas assignments write into existing
variables.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web