时间戳

首页 > 解决方案 > 如何在 yacc 中使用递归来打印 AST？

bison - 如何在 yacc 中使用递归来打印 AST？

问题描述

我正在为特定语言构建一个 compliar，我已经制作了一个 lex 扫描仪和 yacc Parsar 以及一个包含一些语言的文本文件，目标是构建一个适当的 AST 并打印它，

我已经用我需要的所有规则制作了完整的 yacc 和 lex 文件，我使用代码运行它们：

yacc -d test.y
lex test.l
cc -o test y.tab.c -ll -Ly
./test < file.t

这些文件能够从文本文件生成解析器而没有任何语法问题，因此使用 lex 和 yacc 进行扫描和解析是可行的。

我已经为构建 AST 准备了函数，为了正确打印它，我制作了一个递归函数，可以预先扫描以打印所有树。

*我删除了大部分不相关的代码

一些yacc代码：

%{
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    typedef struct node {
        char* token;
        struct node *left;
        struct node *middle; 
        struct node *right;
    }node;



    node *mknode(char *token,node *left,node *middle,node *right);

    void printTree(node *tree);

    void yyerror(const char *s);

    int yylex();

    #define printTree

    #define YYSTYPE struct node*
    extern char *yytext;

%}
%start start
%token MULTI DIVISION BOOL CHAR INT REAL STRING INTPTR CHARPTR REALPTR IF ELSE WHILE FOR VAR FUNC PROC RETURN ASSIGN AND EQUAL GREATER GREATEREQUAL LESS LESSEQUAL MINUS NOT NOTEQUAL OR PLUS ADDRESS DEREFERENCE ABSUOLUT NULLL SEMICOLON COLUMS COMMA NEGATIVE_NUM LEFTBRACE RIGHTBRACE LEFTBRACKET RIGHTBRACKET COOMMENT PRESENT MAIN BOOLTRUE LEFTPAREN RIGHTPAREN BOOLFALSE INTEGER_CONST CHAR_CONST REAL_CONST ID STRING_CONST HEX_CONST 
%right ASSIGN ELSE DIVISION
%left LEFTBRACE RIGHTBRACE LEFTPAREN RIGHTPAREN
%left EQUAL GREATER GREATEREQUAL LESSEQUAL LESS NOTEQUAL
%left PLUS MINUS AND OR 
%left MULTI 

%%
    start: Main                {printTree($1);};

    Main: proc Main            {$$=mknode("CODE",$1,$2,NULL);}  
         |empty                {$$=mknode("CODE",$1,NULL,NULL);};


    id: ID                                               {$$=mknode(yytext,NULL,NULL,NULL);};


    leftParen: LEFTPAREN                                       {$$=mknode("(",NULL,NULL,NULL);};

    rightParen: RIGHTPAREN                                     {$$=mknode(")",NULL,NULL,NULL);};

    empty:                                               {$$=mknode("",NULL,NULL,NULL);};

    proc: PROC id leftParen paramsList rightParen Problock {$$=mknode("PROC",mknode($2->token,$3,$4,$5),NULL,$6);}
         |FUNC id leftParen paramsList rightParen returnInsideFuncDeclaration Problock {$$=mknode("FUNC",mknode($2->token,$3,$4,$5),$6,$7);};


    paramsList: startparamsList SEMICOLON paramsList     {$$=mknode("start_params",$1,mknode(";",NULL,NULL,NULL),$3);}
                |startparamsList                         {$$=mknode("start_params",$1,NULL,NULL);}
                |empty                                   {$$=mknode("start_params",$1,NULL,NULL);}; 

    startparamsList: id next_param_in_proc               {$$=mknode("start_params",$1,$2,NULL);};

    next_param_in_proc: COMMA id next_param_in_proc      {$$=mknode(",",$2,$3,NULL);}
                        |COLUMS varType                  {$$=mknode(":",$2,NULL,NULL);};



    Problock: leftBrace Procbody rightBrace              {$$=mknode("PROC",$1,$2,$3);};

    Procbody: BlockBody                                  {$$=mknode("BODY",$1,NULL,NULL);}
              |BlockBody return                          {$$=mknode("BODY",$1,$2,NULL);} ; 


    HelpToStatement: ProcStatement HelpToStatement       {$$=mknode("help to statment",$1,$2,NULL);}
                     |empty                              {$$=mknode("help to statment",$1,NULL,NULL);};

    HelpToTheProcedure: proc HelpToTheProcedure          {$$=mknode("help proc",$1,$2,NULL);}
                        |empty                           {$$=mknode("help proc",$1,NULL,NULL);};

    HelpDeclare: Declaration HelpDeclare                 {$$=mknode("declartion",$1,$2,NULL);}
                 |empty                                  {$$=mknode("declartion",$1,NULL,NULL);};

    BlockBody: HelpToTheProcedure HelpDeclare HelpToStatement   {$$=mknode("Body",$1,$2,$3);};   


    ProcStatement:   exp SEMICOLON 
                     |structOfCond
                     |block;

%%
#include "lex.yy.c"

int main()
{
    return yyparse();
}

node *mknode(char *token, node *left, node *middle, node *right)
{
    node *newnode = (node*)malloc(sizeof(node));
    char *newstr = (char*)malloc(sizeof(token)+1);
    strcpy(newstr,token);
    newnode->left = left;
    newnode->middle = middle;
    newnode->right = right;
    newnode->token = newstr;
    return newnode;
}
void printtree(node *tree)
{
    printf("%s\n",tree->token);
    if(tree->left)
        printtree(tree->left);
    if(tree->middle)
        printtree(tree->middle);
    if(tree->right)
        printtree(tree->right);
}

void yyerror(const char *str)
{
    printf("%s - %s in line:%d \n",str,yytext,counter);
}

所以我设法从语言构建AST，但不打印它，由于某种原因，函数'printTree'什么也没做，

如果我尝试像这样打印：printf("%s", $1->token)或 printf("%s", $1->left->token)，那么一切都很好，每个标记都在其应有的位置，那么为什么我不能使用递归函数打印它们？

标签： bisonflex-lexeryacclex

解决方案

您正在printTree使用#define printTree. 所以printTree($1);宏扩展为($1);，这是一个空操作。另一方面，您的函数printtree（没有大写字母）永远不会被调用。

因此，您应该删除#define, 前向声明该printtree函数，然后在您的操作中调用它。

推荐阅读