Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end
From: mehmet.coskun@gmail.com
Newsgroups: comp.compilers
Subject: Re: I have managed to parse and evaluate using an AST. I got stuck in statements and block
Date: Thu, 5 Mar 2015 18:53:50 -0500 (EST)
Organization: Compilers Central
Lines: 440
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <15-03-002@comp.compilers>
References: <15-02-027@comp.compilers> <15-02-029@comp.compilers> <15-02-031@comp.compilers>
NNTP-Posting-Host: news.iecc.com
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: miucha.iecc.com 1425599630 73695 2001:470:1f07:1126:0:676f:7373:6970 (5 Mar 2015 23:53:50 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Thu, 5 Mar 2015 23:53:50 +0000 (UTC)
Keywords: interpreter, design
Posted-Date: 05 Mar 2015 18:53:50 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: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.
---