0

这是我的代码：

%{
#include<string.h> 
#include "y.tab.h"
#define DEBUG 0
void yyerror(char* s);
void debug(char* string) {
    if (DEBUG) {
        printf(string);
    }
}
%}  
selector   "selector"[0-9]+
positive   "+"
negtive    "-"
contains   "."
before     "->"
or         "||"
and        "&&"
delim      [ /n/t]  
ws         {delim}*
%%  
{selector} { debug("Lex:SELECTOR\n"); yylval.string = yytext; return     SELECTOR; }  
{positive} { debug("Lex:POSITIVE\n"); return POSITIVE; }  
{negtive}  { debug("Lex:NEGTIVE\n"); return NEGTIVE; }  
{contains} { debug("Lex:BELONGS\n"); return CONTAINS; } 
{before}   { debug("Lex:BEFORE\n"); return BEFORE; }  
{or}       { debug("Lex:OR\n"); return OR; }  
{and}      { debug("Lex:AND\n"); return AND; } 
{ws}       ;
.          { debug("Lex Parser Error"); exit(1); }    
%%

.y:
%{
#include <stdio.h>
#define YYDEBUG 0
int yyparse(void);
void yyerror(char* s);
%}

%union {
    char *string;
}

%token <string> SELECTOR 
%token POSITIVE
%token NEGTIVE
%left CONTAINS
%left BEFORE
%token OR
%token AND

%%
logical_expr : assertion { printf("[reduce] L->A\n"); } 
    | logical_expr AND assertion { printf("[reduce] L->L && A\n");}   
    | logical_expr OR assertion { printf("[reduce] L->L || A\n"); }        
;
assertion : POSITIVE prefix_relation { printf("[reduce] A->+P\n"); }
    | NEGTIVE prefix_relation { printf("[reduce] A->-P\n"); }
;
prefix_relation : prefix_relation BEFORE contain_relation { printf("[reduce] P->P->C\n"); }
    | contain_relation { printf("[reduce] P->C\n");;}
;
contain_relation : contain_relation CONTAINS SELECTOR { printf("[reduce] C->C.S[%s]\n", $3); }
    | SELECTOR { printf("[reduce] C->S[%s]\n", $1); }
;
%%
int main()
{
    return yyparse();
}
void yyerror(char* s)
{
    fprintf(stderr,"%s",s);
}
int yywrap()
{
    return 1;
}

我的输入字符串是：+selector1.selector2||-selector4->selector4

此输入的解析树预计为： 预期的解析树

我的 yacc 生成的程序给出如下输出：

[reduce] C->S[selector1]     // stack: +C
[reduce] C->C.S[selector2]   // stack: +C
[reduce] P->C                // stack: +P
[reduce] A->+P               // stack: A
[reduce] L->A                // stack: L
[reduce] C->S[selector3]     // stack: L||-C
[reduce] P->C                // stack: L||-P
[reduce] C->S[selector4]     // stack: L||-P->C

似乎程序停止执行 shift&& reduce 一次无法从 yylex() 获取更多符号，但我希望它减少堆栈中剩余的符号，L||-P->C因此，我可以在我的代码中生成整个解析树。

我的预期输出是：

[reduce] C->S[selector1]     // stack: +C
[reduce] C->C.S[selector2]   // stack: +C
[reduce] P->C                // stack: +P
[reduce] A->+P               // stack: A
[reduce] L->A                // stack: L
[reduce] C->S[selector3]     // stack: L||-C
[reduce] P->C                // stack: L||-P
[reduce] C->S[selector4]     // stack: L||-P->C
[reduce] P->P->C             // stack: L||-P
[reduce] A->-P               // stack: L||A
[reduce] L->L||A             // stack: L
4

1 回答 1

3

您的扫描仪 (flex) 定义存在许多问题。

  1. 您的默认 flex 规则只是在exit没有任何错误消息的情况下调用（除非DEBUG已定义且非零），因此任何词法错误都会导致程序静默停止。在这种情况下调用会更好yyerror，并产生可见的错误消息。

  2. 正如 EJP 在评论中指出的那样，您的delim定义使用/nand/t而不是\nand \t，因此它既不匹配换行符也不匹配制表符。换行符也不会被您的默认规则匹配，因此它将落入 flex 生成的默认规则，该规则只是将不匹配的字符打印到stdout. （最好包含%option nodefault，如果某些输入与您的任何规则都不匹配，这将导致 flex 产生错误消息。）

  3. 你的selector规则集yylval.string = yytext。您不能这样做，因为yytext指向扫描仪的内部存储并且它指向的字符串将在下次yylex被调用时被修改。如果要将匹配的令牌从扫描器传递给解析器，则必须复制令牌，然后free在不再需要字符串时确保为它分配的存储空间，以避免泄漏记忆。

  4. 您需要注意，解析器生成的bison或yacc通常需要在执行归约之前读取前瞻令牌。因此，在扫描器返回令牌之前，您期望的最后一系列缩减不会执行END，它只会在读取文件结尾时执行。ctrl D因此，如果您以交互方式测试解析器，则在您通过键入（在 Unix 上）发出文件结束信号之前，您不会看到最终的缩减。

最后一点，两者flex都bison能够生成调试输出，指示匹配的规则 (flex) 以及一系列移位、减少和其他解析器操作 (bison)。使用这些功能比尝试实现自己的调试输出更简单、更可靠。

于 2015-01-18T07:03:32.133 回答