Bison - 如何打印解析树

Question

您好，我正在研究一只小 Bison ，以了解它的工作原理。 Bison 应该解析一个句子。 句子由表达式组成，表达式由单词组成。

以下是我的代码:

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


void yyerror(const char *str)
{
    fprintf(stderr,"error: %s\n",str);
}

int yywrap()
{
    return 1;
}

main()
{
    yyparse();
}

%}

%token ASSIGN RANGE OR AND WHITESPACE QUOTE LPAREN RPAREN NOT GREATER LESS

%union 
{
        int number;
        char *string;
}

%token <number> VALUE
%token <string> WORD

%type <string> term
%type <string> expression
%%

query:   /* empty */
    | query expression 
    {
        printf("WOrd:%s",$2);
    }
    ;

expression:
     term
    |expression term
    |expression AND term
        {
            printf("AND");
        }
    ;

term:
    WORD
    {
        $$=$1;
    }
    ;

因此，当用户输入一个单词时，它应该打印出该单词。 用户应该能够输入: 一字一字一字一字

我不确定如何使用 $$ 传递一个单词并将其从“查询表达式”规则中打印出来。 我该怎么做呢？

这是我的弹性:

%{
#include <stdio.h>
#include <string.h>
#include "y.tab.h"
%}
%%
[0-9]+                  yylval.number=atoi(yytext);return VALUE;
[a-zA-Z][a-zA-Z]*       yylval.string=strdup(yytext);return WORD;
":"                     return ASSIGN;
"and"|"&"|"&&"          return AND; 
".."                    return RANGE;
"-"                     return NOT;
"|"                     return OR;
"\""                    return QUOTE;
">"                     return GREATER;
"<"                     return LESS;
\n                      /* ignore end of line */;
\t                      /* ignore end of line */;

%%

提前非常感谢。 莎拉

Answer 1

通常，编写解析器的目的是让您最终得到一个表示输入的数据结构。然后，您以某种方式转换结构，或者，在您的情况下，只需将其打印出来。

在每个表达式产生式中，您都希望在该结构中构建一个节点，以表示您迄今为止所识别的内容。

我有点生疏了，但应该是这样的:

query:   /* empty */
     | query expression { printNode($2); /* printf()s are in here */ }
;

expression: term { $$ = makeTermNode($1); }
          | expression OR term { $$ = makeOrNode($1, $3); }
          | expression AND term  { $$ = makeAndNode($1, $3); }
;

保存节点的数据结构:

struct Node {
    int nodeType;          /* WORD or operator token like AND, OR */
    node* leftOperand;
    node* rightOperand;    /* will be null if the node is a term */
}

%union 
{
    int number;
    char *string;
    Node *node;
}

更新:

自从我用 C 编码以来已经有一段时间了，所以我不得不求助于伪代码。一旦我们完成它，这里就没有代码来回收内存。对于任何其他错误，我们深表歉意。

struct Node *makeTermNode(int word) {
    Node *node = malloc(sizeof struct Node);
    node->nodeType = word;
    node->rightOperand = null;
    node->leftOperand = null;
    return node;
}

请注意，您的 WORD 标记只是表示扫描了某种类型的字母字符串；特定的字母序列被丢弃。 (如果您想知道序列，请让您的词法分析器返回 yytext 的副本而不是 WORD 标记。)

struct Node *makeAndNode(struct Node* leftOperand, struct Node *rightOperand) {
    Node *node = malloc(sizeof struct Node);
    node->nodeType = AND;
    node->leftOperand = leftOperand;
    node->rightOperand = rightOperand;
    return node;
}

对于 makeOrNode() 也是如此。或者，您可以只编写 makeNodeWithOperator(int operator, struct Node* leftOperand, struct Node *rightOperand) 来处理“and”和“or”情况。

我将 printAllNodes() 更改为 printNode()。它从我们构建的表达式树结构的根开始，递归地首先访问每个子表达式的左侧，然后是右侧。它是这样的:

void printNode (struct Node* node) {
    switch (node->nodeType) {
    case WORD:
        printf("%i", node->nodeType);
        return;
    case AND:
    case OR:
        printf("(");
        printNode(node->leftOperand);
        printf("%i", node->nodeType);
        printfNode(node->rightOperand);
        printf(")");
        return;
    }
}