Usando bisonte à lista de análise de elementos

Question

Eu estou escrevendo um compilador para um motor de sombreamento e cada bem trabalhado até chegar as declarações parsing parte.

Eu usei um Sumário da árvore de sintaxe definida com classes para fazer todo o trabalho (para typechecking simplificar e geração de código intermediário) .. então eu tenho um ASTNode classe ancestral e todas as classes descendo como ASTFloat, ASTExpression , ASTIdentifier e assim por diante ..

No arquivo .y eu sou capaz de construir a AST na forma comum:

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); }

e ele funciona muito bem, mas então eu tentei gerar declarações de um escopo (por exemplo, o corpo de um se declaração) desta maneira: Eu tenho usado um ASTStatements classe que tem uma lista de ASTNode* que deve ser preenchido pelo analisador com cada declaração encontrado.

Assim, a abordagem seria algo semelhante a isto:

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

O problema é que o item deve ser inicializada apenas uma vez por bloco de declarações mas eu não sei como fazê-lo. Usando if ($$ == null) é um hack eu tentei, mas ele não funciona porque yylval pode conter o que até aquele ponto.

Qual é a melhor forma normal / para lidar com este tipo de situações usando Bison?

Answer 1

Eu resolvi esse problema, gerando não uma lista de declarações, mas uma árvore degenerada. Assim, o objeto de classe envolvida é:

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
}

usando regras em .y da seguinte maneira:

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

E, de fato este é deixado-recursiva, permitindo declarações de ser reduzido o mais rápido possível sem sobrecarregar a pilha. Eu segui a mesma abordagem para qualquer outro tipo de "lista de símbolos" envolvido em minha língua ..

Answer 2

Tente uma gramática aumentada como o seguinte:

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

Não sei se isso vai ajudar.

Answer 3

Existem várias razões para preferir regras deixaram-recursivo para yacc, para uma coisa que você pode, então, reduzir o mais cedo possível na entrada.

Em qualquer caso, quando você faz isso, você pode usar um padrão como este:

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