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 つの shift/reduce 競合の影響を受ける状態です。

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

あなたの文法はあいまいです - 入力 likeはor1 < 2 < 3として解析できます。(1 < 2) < 31 < (2 < 3)

これに対処するには 2 つの方法があります。/ / ディレクティブを追加%leftし%rightて%nonassocbison の内部優先順位処理を使用するか、追加レベルのルールを導入して処理します。

他の演算子 ( * / + -) については、これらの両方を実行しています。これは通常、間違いであり、どちらか一方だけを実行する必要があります。ただし、両方を行うと、追加のルールが優先され、優先順位のディレクティブが無視され、驚くべき問題が発生することがあります。

このようなリレーションの「通常の」処理は、それらを複数持つことはできないと言うことです (これ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 に答える