Geek Answers Handbook

Using a bison to analyze a list of items

I am writing a compiler for the shader mechanism, and each one worked fine until it came to parsing the parts.

I used the abstract syntax tree defined using classes to do all the work (to simplify the creation of labels and intermediate code generation). So I have a class of their ancestors ASTNodeand go down classes, such as ASTFloat, ASTExpression, ASTIdentifier, etc.

In the file, .yI can create the AST in the usual way:

nexp:
T_LPAR nexp T_RPAR { $$ = $2; }
| nexp OP_PLUS nexp { $$ = new ASTBExpression('+', (ASTExpression*)$1, (ASTExpression*)$3); }
| nexp OP_MINUS nexp { $$ = new ASTBExpression('-', (ASTExpression*)$1, (ASTExpression*)$3); }
| nexp OP_TIMES nexp { $$ = new ASTBExpression('*', (ASTExpression*)$1, (ASTExpression*)$3); }

and it works fine, but then I tried to create area operators (for example, the body of an if statement) as follows: I used a class ASTStatementsthat has a list ASTNode*that should be populated with a parser with every statement encountered.

So the approach would be something like this:

statements:
statement { if ($$ == null) $$ = new ASTStatements(); ((ASTStatements*)$$)->addStatement($1); } statements { $$->generateASM(); }
;

The problem is that the element needs to be initialized only once per statement block, but I don't know how to do it. Use if ($$ == null)is a hack that I tried, but it does not work, because it yylvalcan contain everything that is up to this point.

What is the normal / best way to deal with such situations using Bison?

0
source share
3 answers

I solved this problem by creating not a list of operators, but a degenerate tree. Thus, the class object:

ASTStatements
{
    ASTStatements *m_next;
    ASTStatement *m_statement;

    ....

    public:
        ASTStatements(ASTStatement *statement) // used for last one
        ASTStatements(ASTStatement *stat, ASTStatements *next) // used with a next one
}

using the rules .yas follows:

statements: /* empty */ { $$ = null; }
| statements statement { if ($1 == null) $$ = new ASTStatements($2); else $$ = new ASTStatements($2, (ASTStatements*)$1); }

, , , . " ", .

+1

:

statements: statement { $$ = new ASTStatements();
                       ((ASTStatements*)$$)->addStatement($1); }      
 | statements statement { ((ASTStatements*)$$)->addStatement($2); }

, .

+1

There are various reasons to prefer the left recursive rules for yacc, on the one hand, you can reduce it as early as possible at the input.

Anyway, when you do this, you can use a template like this:

statements:                { $$ = new ... }
    | statements statement { /* now $1 and $2 do just what you want */ }
    ;
+1
source

More articles:


All Articles