c++ - 转移/减少 Bison 的冲突

Question

我试图对一般的 html 代码进行简单的解析。

这是我的整个 bison 文件 (example4.y)。

%{
#include <iostream>
#include <cstring>
using namespace std;

extern "C" int yylex();
extern "C" int yyparse();
extern "C" FILE *yyin;

void yyerror(const char *str)
{
    cout<<"Error: "<<str<<"\n";
}

int yywrap()
{
    return 0;
}

main()
{
    yyparse();
}

%}

%token NUMBER LANGLE CLOSERANGLE RANGLE SLASH ANYTHING

%union
{
    int intVal;
    float floatVal;
    char *strVal;
}

%%

tag:    |   
        opening_tag anything closing_tag 
        {
          if(strcmp($<strVal>1,$<strVal>3)==0){
                cout<<"\n[i] Tag Matches: "<<$<strVal>1;
                cout <<"\n[!] The text: "<<$<strVal>2;
            } else {
                cout<<"\n[!] Tag Mismatch: "<<$<strVal>1<<" and "<<$<strVal>3;
            }
            $<strVal>$ = $<strVal>2;
        }
        |
        opening_tag tag closing_tag 
        {
          if(strcmp($<strVal>1,$<strVal>3)==0){
                cout<<"\n[i] Tag Matches: "<<$<strVal>1;
                cout <<"\n[!] The text: "<<$<strVal>2;
            } else {
                cout<<"\n[!] Tag Mismatch: "<<$<strVal>1<<" and "<<$<strVal>3;
            }
        }
        ;
opening_tag:
        LANGLE ANYTHING RANGLE
        {
            $<strVal>$ = $<strVal>2;
        }
        ;
anything:
        ANYTHING
        {
            $<strVal>$ = $<strVal>1;
        }
        ;
closing_tag:
        LANGLE SLASH ANYTHING RANGLE
        {
            $<strVal>$= $<strVal>3;
        }        
%%

我得到的错误是:example4.y: conflicts: 1 shift/reduce

我认为它必须与 opening_tag tag closing_tag 相关，但我想不出这里发生了什么？有帮助吗？

Answer 1

是因为有两条以opening_tag开头的规则.解析器必须通过查看最多一个标记来在规则之间做出决定，但它不能。 <FOO>可能导致任一规则，这需要两个以上的先行标记。

你可以这样做:

 tag     : /* nothing */
         | opening_tag contents closing_tag
         ;
 contents: tag
         | anything
         ;

UPDATE 这个新语法有不同的移位/归约冲突。 (更新 2:或者可能是同一个)。因为标记可以为空，所以解析器无法决定在此输入上做什么:

<Foo> <...
     ^
     |
     input is here

如果下一个符号是斜杠，那么我们就有了一个结束标签，应该匹配空标签规则。如果下一个符号不是斜杠，那么我们有一个开始标签，并且应该匹配非空标签规则。但解析器无法知道，它只允许查看<。 .

解决方案是为 </ 创建一个新 token LANGLE_SLASH组合。