Re: How to organize the data structure in a parser?

On 22 Jan 2005 18:28:14 -0500, Andy wrote:


> I am trying to design a parser for C program using C++. Currently what
> I did for syntax tree is to design a class for each nontermials in the
> grammar, and use inherentance to link them. For example, as for the
> expression part, the classes are something like the follows:
>
> ....
> class MultiplicativeExpr : public AdditiveExpr
> {
> MultiplicativeExpr * multi_expr;
> int op_type;
> PmExpr * pm_expr;
> };
>
> class AdditiveExpr : public ShiftExpr
> {
> int op_type;
> AdditiveExpr * additive_expr;
> MultiplicativeExpr * multi_expr;
> };
>
> class ShiftExpr : public RelationalExpr
> {
> int op_type;
> ShiftExpr * shift_expr;
> AdditiveExpr * additive_expr;
> };
>
> class RelationalExpr : public EqualityExpr
> {
> int op_type;
> RelationalExpr * relational_expr;
> ShiftExpr * shift_expr;
> };
>
> ....
>
> I noticed that the bad thing about this solution is that using
> inheritance, the children in the leaf of inheritance tree will be of
> large size because it comprised of all data fields of its ancestors.
> How can I organize the data structure more efficienty? Thanks a lot!


The problem with above is that you add new members, instead of
re-using (and possibly constraining) the existing ones. Actually your
syntax tree is kind of:


class Expr // Abstract operation with some result
{
public :
      virtual ~Expr () {}
      ...
};


class UnaryExpr : public Expr // Abstract operation with one argument
{
public :
      Expr * Left;
      ...
};


class BinaryExpr : public Expr // Abstract operation with two arguments
{
public :
      Expr * Left;
      Expr * Right;
      ...
};


class AdditiveExpr : public BinaryExpr // Abstract additive operation
{
      // No new members needed
};


class Addition : public AdditiveExpr // Concrete operation +
{
      // No new members needed
};


AdditiveExpr could probably constrain Left and Right of the parent type to
the class of types more specific than just any Expr. But what for? And that
is impossible in C++ anyway.


Also no member op_type is actually needed. Each concrete type (like
Addition) already caries the information about the operation.


--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Return to the comp.compilers page.
Search the comp.compilers archives again.