1

我有以下野牛语法：

%error-verbose
%{
#include "node.h"
NBlock *programBlock;

#define YYDEBUG 1

extern int yylex();
void yyerror(const char *s) { printf("Error: %s\n", s); }
%}

%union {
    Node *node;
    NBlock *block;
    NBody *body;
    NHeader *header;
    NExpression *expression;
    NStatement *statement;
    NIdentifier *identifier;
    NVariableDeclaration *variableDeclaration;
    NDoWhileStatement *doWhileStatement;
    NWhileStatement *whileStatement;
    NIfStatement *ifStatement;
    NForStatement *forStatement;
    std::vector<NVariableDeclaration*> *variableDeclarations;
    std::vector<NExpression*> *expressions;
    std::vector<NStatement*> *statements;
    std:string *string;
    int token;
}

/*
The %token directive is used to associate a type to a terminal symbol.
%token <type> 'terminal_list'
associates the specific type <type> to each terminal in 'terminal_list'.
The type <type> is the same used in the %union declaration
*/

%token <string> TIDENTIFIER TINTEGER TDOUBLE
%token <token> TCEQ TCNE TCLT TCLE TCGT TCGE TEQUAL
%token <token> TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA TDOT
%token <token> TPLUS TMINUS TMUL TDIV TDO TDOUBLE_TYPE TINT_TYPE
%token <token> TELSE TFOR TIF TSEMICOLON TTHEN TWHILE

/*
The %type directive is used to associate a type to a nonterminal symbol.
%type <type> nonterminal_list
associates the specific type <type> to each nonterminal in 'nonterminal_list'.
The type <type> is the same used in the %union declaration
*/

%type <expression> expression term factor
%type <block> program body header tail statements
%type <statement> statement forStatement ifStatement doWhileStatement whileStatement variableDeclaration
%type <token> comparison
%type <string> identifier_type

/*
Operator precedence for mathematical operators
*/

%left TPLUS TMINUS
%left TMUL TDIV
%left TCEQ TCNE TCLT TCLE TCGT TCGE

/*
Start grammar symbol
*/

%start program

%%

program:                TLBRACE body TRBRACE { printf("Reduce body to program\n"); }
                        ;

body:                   header TLBRACE block TRBRACE tail { printf("Reduce header block tail to body\n"); }
                        ;

header:                 TLBRACE variableDeclarations TRBRACE { printf("Reduce variableDeclarations to header\n"); }
                        | TLBRACE TRBRACE { printf("Reduce empty to header\n"); }
                        ;

variableDeclarations:   variableDeclaration TSEMICOLON { printf("Reduce variable declaration to header\n"); }
                        | variableDeclarations variableDeclaration TSEMICOLON { printf("Reduce variable declaration list to header\n"); }
                        ;

tail:                   TLBRACE statements TRBRACE { printf("reduce statement list to tail\n"); }
                        | TLBRACE TRBRACE { printf("Reduce empty to tal\n"); }
                        ;                   

statements:             statement TSEMICOLON { printf("Reduce statement to statement list\n"); }
                        | statements statement TSEMICOLON { printf("Reduce statement list to statement list\n"); }
                        ;

statement:              ifStatement { printf("Reduce if to statement\n"); };
                        | forStatement { printf("Reduce for to statement\n"); };
                        | doWhileStatement { printf("Reduce doWhile to statement\n"); };
                        | whileStatement { printf("reduce while to statement\n"); }
                        | TIDENTIFIER TEQUAL expression { printf("Reduce assignment to expression\n"); }
                        ;

forStatement:           TFOR TLPAREN expression TSEMICOLON expression TSEMICOLON expression TRPAREN block { printf("Reduce for to for statement\n"); }
                        ;


ifStatement:            TIF expression TTHEN block { printf("Reduce if to if statement\n"); }
                        | TIF expression block TELSE block { printf("Reduce ifelse to if statement\n"); }
                        ;

doWhileStatement:       TDO block TWHILE expression { printf("reduce dowhile to while statement\n"); }
                        ;

whileStatement:         TWHILE block expression { printf("Reduce while to while statement\n"); }
                        ;

block:                  TLBRACE statements TRBRACE { printf("Reduce statement list to block\n"); }
                        | TLBRACE TRBRACE { printf("Reduce empty to block\n"); }
                        ;

variableDeclaration:    identifier_type TIDENTIFIER { printf("reduce uninitialized identifier to variable declaration\n"); }
                        | identifier_type TIDENTIFIER TEQUAL expression { printf("Reduce initialized identifier to variable declaration\n"); }
                        ;

identifier_type:        TINT_TYPE { printf("Reduce int to identifier type\n"); }
                        | TDOUBLE_TYPE { printf("Reduce double to identifier type\n"); }
                        | { printf("Reduce empty to identifier type\n"); }
                        ;



expression:             term { printf("Reduce term to expresson\n"); }
                        | expression comparison expression { printf("Reduce comparison to expression\n"); }
                        | expression TPLUS term { printf("Reduce addition to expression\n"); }
                        | expression  TMINUS term { printf("Reduce subtraction to expression\n"); }
                        ;

term:                   factor { printf("Reduce factor to term\n"); }
                        | term TMUL factor { printf("Reduce multiplication to term\n"); }
                        | term TDIV factor { printf("Reduce division to term\n"); }
                        ;

factor:                 TLPAREN expression TRPAREN { printf("Reduce nested expression to expression\n"); }
                        | TMINUS factor { printf("Reduce -factor to factor\n"); }
                        | TIDENTIFIER { printf("Reduce identifier to factor\n"); }
                        | TINTEGER { printf("Reduce integer to numeric\n"); }
                        | TDOUBLE { printf("Reduce double to numeric\n"); }
                        ;

comparison:             TCEQ { printf("Reduce eq to comparison\n"); }
                        | TCNE { printf("Reduce ne to comparison\n"); }
                        | TCLT { printf("Reduce lt to comparison\n"); }
                        | TCLE { printf("Reduce le to comparison\n"); }
                        | TCGT { printf("reduce gt to comparison\n"); }
                        | TCGE { printf("Reduce ge to comparison\n"); }
                        ;

我得到 8 个班次/减少冲突，我不知道如何解决。

以下是我使用 --report=all 参数生成的 parser.output 文件的一部分。它是受 8 个移位/减少冲突影响的状态：

State 79

   29 expression: expression . comparison expression
   29           | expression comparison expression .  [TCEQ, TCNE, TCLT, TCLE, TCGT, TCGE, TRPAREN, TLBRACE, TPLUS, TMINUS, TSEMICOLON, TTHEN]
   30           | expression . TPLUS term
   31           | expression . TMINUS term
   40 comparison: . TCEQ
   41           | . TCNE
   42           | . TCLT
   43           | . TCLE
   44           | . TCGT
   45           | . TCGE

    TCEQ    shift and go to state 56
    TCNE    shift and go to state 57
    TCLT    shift and go to state 58
    TCLE    shift and go to state 59
    TCGT    shift and go to state 60
    TCGE    shift and go to state 61
    TPLUS   shift and go to state 62
    TMINUS  shift and go to state 63

    TCEQ      [reduction with rule 29 (expression)]
    TCNE      [reduction with rule 29 (expression)]
    TCLT      [reduction with rule 29 (expression)]
    TCLE      [reduction with rule 29 (expression)]
    TCGT      [reduction with rule 29 (expression)]
    TCGE      [reduction with rule 29 (expression)]
    TPLUS     [reduction with rule 29 (expression)]
    TMINUS    [reduction with rule 29 (expression)]
    $default  reduction with rule 29 (expression)

    comparison  go to state 64

如果我理解得很好，问题是解析器不知道是继续阅读另一段文本还是立即减少规则表达式：表达式比较表达式。

我会说立即减少是正确的。但是，如果我这是正确的，那么我如何强制立即减少转移？

4

3 回答 3

5

您的语法不明确 - 输入 like1 < 2 < 3可以解析为(1 < 2) < 3or 或1 < (2 < 3).

有两种方法可以解决这个问题——要么添加//%left指令以使用 bison 的内部优先级处理，要么引入额外级别的规则来处理它。%right%nonassoc

现在，对于您的其他运算符 ( * / + -)，您正在同时执行这两项操作——这通常是一个错误，您只想执行其中一项。但是如果你同时做这两个，额外的规则将优先，优先指令将被忽略，有时会导致令人惊讶的问题。

像这样的关系的“正常”处理是说你不能有多个（这1 < 2 < 3是一个语法错误，不应该被解析为左或右递归。）要使用其他规则来做到这一点，你会改变你的表达规则：

expression:           add_expression
                    | add_expression comparison add_expression
                    ;
add_expression:       term
                    | add_expression TPLUS term
                    | add_expression TMINUS term
                    ;

使用优先指令，摆脱term, factor, 和comparison( 将它们全部移入expression并添加：

%nonassoc TCEQ TCNE TCLT TCLE TCGT TCGE
%left TPLUS TMINUS
%left TMUL TDIV
于 2013-03-27T16:56:56.513 回答
1

问题是关联规则（如您的%left指令）不能通过语法间接工作。如果您取消comparison规则并将所有比较运算符拉到expression规则中，问题就会消失。（我用 Bison v2.4.1 验证了这一点。）

这可能很不方便，因为它expression比您想要的更冗长。一种解决方法是将决定推回扫描仪。定义COMPARISON为单个标记，并将比较的风格作为单独的枚举类型传递yylval，因此它可以作为$n.

于 2013-03-27T16:17:24.573 回答
0

感谢您的回答。这是完整的 Bison 语法：

%error-verbose
%{
#include "node.h"
#include <iostream>
#include <string>
NBlock *programBlock;

#define YYDEBUG 1

extern int yylex();
void yyerror(const char *) { printf("Error: %s\n", s); }
%}

%union {
    Node *node;
    NBlock *block;
    NBody *body;
    NHeader *header;
    NExpression *expression;
    NStatement *statement;
    NIdentifier *identifier;
    NVariableDeclaration *variableDeclaration;
    NDoWhileStatement *doWhileStatement;
    NWhileStatement *whileStatement;
    NIfStatement *ifStatement;
    NForStatement *forStatement;
    std::vector<NVariableDeclaration*> *variableDeclarations;
    std::vector<NExpression*> *expressions;
    std::vector<NStatement*> *statements;
    std:string *string;
    int token;
}

%token <string> TIDENTIFIER TINTEGER TDOUBLE
%token <token> TCEQ TCNE TCLT TCLE TCGT TCGE TEQUAL
%token <token> TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA TDOT
%token <token> TPLUS TMINUS TMUL TDIV TDO TDOUBLE_TYPE TINT_TYPE
%token <token> TELSE TFOR TIF TSEMICOLON TTHEN TWHILE TLSQUARE TRSQUARE

%type <expression> expression term factor
%type <block> program body header tail
%type <statements> statements
%type <statement> statement
%type <forStatement> forStatement
%type <ifStatement> ifStatement
%type <doWhileStatement> doWhileStatement
%type <whileStatement> whileStatement
%type <variableDeclaration> variableDeclaration
%type <token> comparison
%type <string> identifier_type
%type <variableDeclarations> variableDeclarations

/*
Start grammar symbol
*/

%start program

%%

program:                TLBRACE body TRBRACE { printf("Reduce body to program\n"); }
                        ;

body:                   header TLBRACE block TRBRACE tail { printf("Reduce header block tail to body\n"); }
                        ;

header:                 TLBRACE variableDeclarations TRBRACE { printf("Reduce variableDeclarations to header\n"); }
                        | TLBRACE TRBRACE { printf("Reduce empty to header\n"); }
                        ;

variableDeclarations:   variableDeclaration TSEMICOLON { printf("Reduce variable declaration to header\n"); }
                        | variableDeclarations variableDeclaration TSEMICOLON { printf("Reduce variable declaration list to header\n"); }
                        ;

tail:                   TLBRACE statements TRBRACE { printf("reduce statement list to tail\n"); }
                        | TLBRACE TRBRACE { printf("Reduce empty to tal\n"); }
                        ;                   

statements:             statement TSEMICOLON { printf("Reduce statement to statement list\n"); }
                        | statements statement TSEMICOLON { printf("Reduce statement list to statement list\n"); }
                        ;

statement:              ifStatement { printf("Reduce if to statement\n"); };
                        | forStatement { printf("Reduce for to statement\n"); };
                        | doWhileStatement { printf("Reduce doWhile to statement\n"); };
                        | whileStatement { printf("reduce while to statement\n"); }
                        | TIDENTIFIER TEQUAL expression { printf("Reduce assignment to expression\n"); }
                        | TIDENTIFIER TLSQUARE TINTEGER TRSQUARE TEQUAL expression { printf("Reduce array assignment to expression\n"); }
                        ;

forStatement:           TFOR TLPAREN expression TSEMICOLON expression TSEMICOLON expression TRPAREN block { printf("Reduce for to for statement\n"); }
                        ;


ifStatement:            TIF expression TTHEN block { printf("Reduce if to if statement\n"); }
                        | TIF expression TTHEN block TELSE block { printf("Reduce ifelse to if statement\n"); }
                        ;

doWhileStatement:       TDO block TWHILE expression { printf("reduce dowhile to while statement\n"); }
                        ;

whileStatement:         TWHILE block expression { printf("Reduce while to while statement\n"); }
                        ;

block:                  TLBRACE statements TRBRACE { printf("Reduce statement list to block\n"); }
                        | TLBRACE TRBRACE { printf("Reduce empty to block\n"); }
                        ;

variableDeclaration:    identifier_type TIDENTIFIER { printf("Reduce uninitialized identifier to variable declaration\n"); }
                        | identifier_type TIDENTIFIER TLSQUARE TINTEGER TRSQUARE { printf("Reduce  array to variable declaration\n"); }
                        | identifier_type TIDENTIFIER TEQUAL expression { printf("Reduce initialized identifier to variable declaration\n"); }
                        | identifier_type TIDENTIFIER TLSQUARE TINTEGER TRSQUARE TEQUAL expression { printf("Reduce initialized array to variable declaration\n"); }
                        ;

identifier_type:        TINT_TYPE { printf("Reduce int to identifier type\n"); }
                        | TDOUBLE_TYPE { printf("Reduce double to identifier type\n"); }
                        | { printf("Reduce empty to identifier type\n"); }
                        ;


expression:             add-expression { printf("Reduce add-expression to expression\n"); }
                        |add-expression comparison add-expression { printf("Reduce add-expression comparison add-expression to expression\n"); }


add-expression:         term { printf("Reduce term to expresson\n"); }
                        | add-expression TPLUS term { printf("Reduce addition to expression\n"); }
                        | add-expression  TMINUS term { printf("Reduce subtraction to expression\n"); }
                        ;

term:                   factor { printf("Reduce factor to term\n"); }
                        | term TMUL factor { printf("Reduce multiplication to term\n"); }
                        | term TDIV factor { printf("Reduce division to term\n"); }
                        ;

factor:                 TLPAREN expression TRPAREN { printf("Reduce nested expression to expression\n"); }
                        | TMINUS factor { printf("Reduce -factor to factor\n"); }
                        | TIDENTIFIER { printf("Reduce identifier to factor\n"); }
                        | TINTEGER { printf("Reduce integer to numeric\n"); }
                        | TDOUBLE { printf("Reduce double to numeric\n"); }
                        ;

comparison:             TCEQ { printf("Reduce eq to comparison\n"); }
                        | TCNE { printf("Reduce ne to comparison\n"); }
                        | TCLT { printf("Reduce lt to comparison\n"); }
                        | TCLE { printf("Reduce le to comparison\n"); }
                        | TCGT { printf("reduce gt to comparison\n"); }
                        | TCGE { printf("Reduce ge to comparison\n"); }
                        ;
于 2013-03-28T08:46:50.810 回答