#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2010
    Location
    ~
    Posts
    12
    Rep Power
    0

    Simple interpreter with Lex/YACC


    How would I make an interpreter for a simple language using Lex/YACC?

    I probably can't just put the code to interpret the language in the grammar rules, because how will it handle ifs and loops?
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    Normally you have a parser (possibly constructed with lex/yacc) which reduces the source code to a data structure (usually some sort of tree). You can then execute the source code directly from the structure or convert it into some other form.

    For example an if statement might turn into a structure like
    Code:
    If
       Condition
       Then-Block
       Else-Block
    Which is evaluated by a routine like
    Code:
    Evaluate(If)
       if Evaluate(Condition) == True
          Evaluate( Then-Block )
       else
          Evaluate( Else-Block )

    You might want to start off with a language with a simpler structure (like a Lisp/Scheme variant) to get the principle down without having to worry about too many variations in syntax.
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2010
    Location
    ~
    Posts
    12
    Rep Power
    0
    That makes sense, just one thing that confuses me is the exact structure of the tree: How to store the name/type of the node, how to manage child nodes/literals, etc.

    Also, I was considering an alternative to Lex/YACC, mostly this:

    EDIT: since I can't post URLs, I wrote this Perl one-liner that will print the URL:

    Code:
    perl -e '$_ = "jvvrQWWrkwoctvcEeqoWuqhvyctgWrgiWrgiE1Ejvon"; tr|QWE[c-z][a-b]|:/.[a-z]|; print;'
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2010
    Location
    ~
    Posts
    12
    Rep Power
    0

    Lightbulb


    I came up with a nice solution for the AST, but it requires an OO language:

    Have a class Node that contains an eval() function and a list of children. The eval() function would return the value that the node evaluates to.

    For example, an IntegerLiteralNode would store its value and its eval() would return that. Then, an AdditionNode can, for example, have two IntegerLiteralNodes as children, and its eval() would call eval() on the two chirdren and return the sum.

    I just wonder how would I handle multiple data types? But I'll probably play around with a language containing only integers for now to test my AST concept.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    You can write OO in C. You just don't get fancy keywords to make the compiler do all the work for you.

    Code:
    enum TermType { INT, FLOAT };
    
    union TermData {
        int i;
        double d;
    };
    
    struct Term {
        TermType type;
        TermData data;
    };
    
    double eval( struct Term *a ) {
        if( a->type == INT ) {
            return a->data.i;
        }
        // . . .
    }
    - or if you prefer function pointers -

    Code:
    union TermData {
        int i;
        double d;
    };
    
    struct Term {
        double (*eval)(struct Term*);
        TermData data
    };
    
    void eval_int( struct Term *this ) {
        return this->data.i;
    }
    
    struct Term zero { eval_int, 0 };
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2010
    Location
    ~
    Posts
    12
    Rep Power
    0
    What is a term and why does eval return void?

    Anyway, this is more like what I was thinking (in C++, although it might be converted to C):

    Code:
    class Node
    {
        Node* children;
    
    public:
        virtual int eval();
        
        void addChild(Node* node);
        int childCount();
        Node* child(int index);
    };
    
    class AdditionNode
    {
    public:
        AdditionNode(Node* addend1, Node* addend2)
        {
            addChild(addend1);
            addChild(addend2);
        }
    
        virtual int eval()
        {
            return child(0)->eval() + child(1)->eval();
        }
    };
    
    class IntegerNode
    {
        int value;
    
    public:
        IntegerNode(int val)
        {
            value = val;
        }
    
        virtual int eval()
        {
            return value;
        }
    };
    
    Node* myNode = new AdditionNode(new IntegerNode(3), new IntegerNode(5));
    printf("3 + 5 = %d\n", myNode.eval());
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2010
    Location
    ~
    Posts
    12
    Rep Power
    0
    I made an example that compiles:

    Code:
    #include <cstdio>
    
    class Node
    {
    public:
    	virtual int eval() {}
    };
    
    class AdditionNode : public Node
    {
    	Node* a;
    	Node* b;
    
    public:
    	AdditionNode(Node* _a, Node* _b) 
    	{
    		a = _a;
    		b = _b;
    	}
    
    	virtual int eval()
    	{
    		return a->eval() + b->eval();
    	}
    };
    
    class IntegerNode : public Node
    {
    	int value;
    
    public:
    	IntegerNode(int _value)
    	{
    		value = _value;
    	}
    
    	virtual int eval()
    	{
    		return value;
    	}
    };
    
    int main()
    {
    	Node* n = new AdditionNode(new IntegerNode(3),
    	                           new AdditionNode(new IntegerNode(1),
    				                    new IntegerNode(4)));
    	printf("3 + (1 + 4) = %d\n", n->eval());
    }
    Shouldn't be too hard for YACC, leg, or something like that to build a tree with these.

    Comments on this post

    • Nylex agrees : Have some rep :).

IMN logo majestic logo threadwatch logo seochat tools logo