C Lexer/Parser

[rchika]

I need to know what is the purpose of a parse tree and how it is used with a symbol table? Furthermore, what is a lex lexer, and a yacc parser? Also, what is a parsing library? One last question, can you tell me the purpose of the following code? Sorry, if these seem as very basic questions but I am a beginner and trying to do some research. Thanks for all your help! The code is as follows:

//------------------------------------
// tree.cpp
// Expression tree
//------------------------------------

#include <iostream>
using std::cout;
using std::endl;

class Node
{
public:
virtual ~Node () {}
virtual double Calc () const = 0;
};

class NumNode: public Node
{
public:
NumNode (double num) : _num (num) {}
double Calc () const;
private:
const double _num;
};

class BinNode: public Node
{
public:
BinNode (Node * pLeft, Node * pRight)
: _pLeft (pLeft), _pRight (pRight) {}
~BinNode ();
protected:
Node * const _pLeft;
Node * const _pRight;
};

class AddNode: public BinNode
{
public:
AddNode (Node * pLeft, Node * pRight)
: BinNode (pLeft, pRight) {}
double Calc () const;
};

class MultNode: public BinNode
{
public:
MultNode (Node * pLeft, Node * pRight)
: BinNode (pLeft, pRight) {}
double Calc () const;
};

BinNode::~BinNode ()
{
delete _pLeft;
delete _pRight;
}

double NumNode::Calc () const
{
cout << &quot;Numeric node &quot;<< _num << endl;
return _num;
}

double AddNode::Calc () const
{
cout << &quot;Adding\n&quot;;
return _pLeft->Calc() + _pRight->Calc ();
}

double MultNode::Calc () const
{
cout << &quot;Multiplying\n&quot;;
return _pLeft->Calc () * _pRight->Calc ();
}

void main ()
{
// ( 20.0 + (-10.0) ) * 0.1
Node* pNode1 = new NumNode (20.0);
Node* pNode2 = new NumNode (-10.0);
Node* pNode3 = new AddNode (pNode1, pNode2);
Node* pNode4 = new NumNode (0.1);
Node* pNode5 = new MultNode (pNode3, pNode4);
cout << &quot;Calculating the tree\n&quot;;
double x = pNode5->Calc ();
cout << x << endl;
delete pNode5; // and all children
}

 

[mbaranski]

First of all, this is c++, so you're 2 +'s off... Anyway, some simple answers:

A parser breaks up source code into meaningful symbols and tokens based on a grammer, yacc is the gnu parser that they provide. I believe that a lexical analyzer is kind of a syntax checker, also based on a grammer given, a simple example:

expression :=> operand operator operand | operator operand
operator :=> + | - | * | /
operand :=> a number

A parse tree takes something like 2 + 4 * 2
and representes it as:

+
/ 2 *
/ 2 4

Also, this is called an abstract syntax tree.

So, a lexical analyzer checks syntax, then passes the thing to the parser, which breaks up code into tokens, which are put into an abstract syntax tree, which is then walked and turned into machine code.

I hope that is clear enough.

MWB> As always, I hope that helped!

Disclaimer:
Beware: Studies have shown that research causes cancer in lab rats.

 

[rchika]

you were very helpful, thank you very much! Just one more question, I know that this is C++ but you may still know the answer. What does the source code,which I stated in the original thread, what does that actually do? Does it have a special purpose or does it just do the basics of what you explained the first time? Thank you once again!

 

[mbaranski]

It's an abstract syntax tree, like I drew, for adding and multiplying. It's a binary tree, with add or multiply as a root node, and numbers as child nodes.

MWB.
As always, I hope that helped!

Disclaimer:
Beware: Studies have shown that research causes cancer in lab rats.