Simple interpreter with Lex/YACC

Dev Shed Forums Sponsor:

November 22nd, 2010, 05:08 PM

MTK358

Registered User

Join Date: Nov 2010

Location: ~

Posts: 12

Time spent in forums: 4 h 24 m 50 sec
Reputation 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?

November 23rd, 2010, 08:17 PM

OmegaZero

Contributing User

Join Date: May 2007

Posts: 737

Time spent in forums: 3 Weeks 5 Days 8 m 19 sec
Reputation Power: 928

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);

November 24th, 2010, 08:01 AM

MTK358

Registered User

Join Date: Nov 2010

Location: ~

Posts: 12

Time spent in forums: 4 h 24 m 50 sec
Reputation 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;'

November 24th, 2010, 03:24 PM

MTK358

Registered User

Join Date: Nov 2010

Location: ~

Posts: 12

Time spent in forums: 4 h 24 m 50 sec
Reputation Power: 0

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.

November 25th, 2010, 12:32 PM

OmegaZero

Contributing User

Join Date: May 2007

Posts: 737

Time spent in forums: 3 Weeks 5 Days 8 m 19 sec
Reputation Power: 928

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 };

November 25th, 2010, 02:16 PM

MTK358

Registered User

Join Date: Nov 2010

Location: ~

Posts: 12

Time spent in forums: 4 h 24 m 50 sec
Reputation 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());

November 25th, 2010, 03:16 PM

MTK358

Registered User

Join Date: Nov 2010

Location: ~

Posts: 12

Time spent in forums: 4 h 24 m 50 sec
Reputation 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

Simple interpreter with Lex/YACC

Developer Shed Advertisers and Affiliates