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

On 01/24/2005 08:57 AM, Dmitry A. Kazakov wrote:
> 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 spirit method may be some help. See


      http://www.boost.org/libs/spirit/doc/trees.html


and search for "Example". I think spirit has several example's
of AST's; hence, you might get more ideas there. The interesting
thing about these AST is that they minimize the need for virtual
functions.

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