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

Larry Evans <cppljevans@cox-internet.com>
25 Jan 2005 23:21:21 -0500

          From comp.compilers

Related articles
How to organize the data structure in a parser? gnu04@yahoo.com (Andy) (2005-01-22)
Re: How to organize the data structure in a parser? mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2005-01-24)
Re: How to organize the data structure in a parser? j1k1cki@hotmail.com (2005-01-24)
Re: How to organize the data structure in a parser? cppljevans@cox-internet.com (Larry Evans) (2005-01-25)
Re: How to organize the data structure in a parser? gnu04@yahoo.com (Andy) (2005-01-30)
| List of all articles for this month |

From: Larry Evans <cppljevans@cox-internet.com>
Newsgroups: comp.compilers
Date: 25 Jan 2005 23:21:21 -0500
Organization: Posted via Supernews, http://www.supernews.com
References: 05-01-072 05-01-077
Keywords: parse, OOP

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.


Post a followup to this message

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