0

我正在尝试在 Bison 输入文件上描述此语法: https ://courses.engr.illinois.edu/cs421/sp2011/mps/mp2/minijavasyntax.pdf

这是我的输入:

%start Program
%token KW_CLASS KW_EXTENDS KW_PUBLIC KW_STATIC KW_BOOLEAN KW_STRING KW_FLOAT KW_INT EOF
%token KW_IF KW_WHILE KW_BREAK KW_CONTINUE KW_SWITCH KW_CASE KW_DEFAULT KW_RETURN
%token KW_NEW KW_THIS KW_NULL KW_TRUE KW_FALSE KW_PRINTLN
%token IDENT INT_LITERAL FLOAT_LITERAL STRING_LITERAL

%nonassoc "THEN"
%nonassoc KW_ELSE

%right "STATEMENTS"

%right OP_ASSIGN
%left OP_OR
%left OP_AND
%nonassoc CMP_EQ CMP_NEQ
%nonassoc CMP_GT CMP_LT CMP_GTE CMP_LTE
%left OP_ADD OP_MINUS
%left OP_MULT OP_DIV OP_MOD
%right OP_NOT OP_UNARY "NEW" 
%left "FUNCALL" "SUBSCRIPT"  '.'
%nonassoc '('
%nonassoc ')'
%%
Program:        ClassDeclp EOF
            ;

ClassDeclp:     ClassDecl
            | ClassDeclp ClassDecl
            ;
ClassDecl:      KW_CLASS IDENT ExtendsFrom
            '{' VarDecls MethodDecls '}'
            ;
ExtendsFrom:        /*empty*/
                | KW_EXTENDS IDENT
            ;

VarDecls:       /*empty*/
            | VarDecls VarDecl
            ;
VarDecl:        Type IDENT ';'
            | KW_STATIC Type IDENT ';' /*Co the sua thanh AcessModifier Type IDENT*/
            ;

MethodDecls:        /*empty*/
            | MethodDecls MethodDecl
            ;
MethodDecl:     KW_PUBLIC Type IDENT
            '('MethodParams')'
            '{'VarDecls Statements KW_RETURN Expression ';' '}'
            ;

MethodParams:       /*empty*/
            | MethodParams ',' MethodParam
            ;       
MethodParam:        Type IDENT;

Type :          Type '['']'
                | KW_BOOLEAN
            | KW_STRING
            | KW_FLOAT
            | KW_INT
            | IDENT
            ;
Statements:     Statements Statement    %prec "STATEMENTS"
            | /*empty*/ %prec "STATEMENT"
            ;
Statementp:     Statements Statement %prec "STATEMENTS"
            ;
Statement:      '{'Statements'}'
            | KW_IF '(' Expression ')' Statement %prec "THEN"
            | KW_IF '(' Expression ')' Statement KW_ELSE Statement
            | KW_WHILE '(' Expression ')'Statement
            | KW_PRINTLN '(' Expression ')' ';'
            | IDENT OP_ASSIGN Expression ';'
            | KW_BREAK ';'
            | KW_CONTINUE ';'
            | IDENT %prec "SUBSCRIPT" '['Expression']' '=' Expression ';'
            | KW_SWITCH '(' Expression ')' '{'
              Cases
              KW_DEFAULT ':' Statementp '}'
            ;

Cases:          Cases Case
            | /*empty*/
            ;
Case:           KW_CASE INT_LITERAL ':' Statementp
            ;


Expression:     Expression OP_OR Expression
            | Expression OP_AND Expression
            | Expression CMP_EQ Expression
            | Expression CMP_NEQ Expression
            | Expression CMP_GT Expression
            | Expression CMP_GTE Expression
            | Expression CMP_LT Expression
            | Expression CMP_LTE Expression
            | Expression OP_ADD Expression
            | Expression OP_MINUS Expression
            | Expression OP_MULT Expression
            | Expression OP_DIV Expression
            | Expression OP_MOD Expression
            | '-' Expression %prec OP_UNARY
            | OP_NOT Expression
            | Expression %prec "SUBSCRIPT" '['Expression']'
            | Expression '.'"length"
            | Expression '.' IDENT %prec "FUNCALL" '(' ParamList ')' 
            | INT_LITERAL
            | FLOAT_LITERAL
            | STRING_LITERAL
            | KW_NULL
            | KW_TRUE
            | KW_FALSE
            | IDENT
            | KW_THIS
            | KW_NEW Type '[' Expression ']' %prec "NEW"
            | KW_NEW IDENT '('')'        %prec "NEW"
            | '(' Expression ')'
            ;


ParamList:      /*empty*/
            | ParamList ',' Expression
            | Expression
            ;
%%
main(int argc, char** argv[])
{
    extern FILE *yyin;
    ++argv; --argc;
    yyin = fopen(argv[0], "r");
    yydebug = 1;
    errors = 0;
    yyparse();
}

yyerror(char *s)
{
    printf("%s\n", s);
}

/* Co 3 conflict RR can xu ly khi bien thuoc kieu bool
   giua BoolExpr va Expresstion */

我在编译时遇到了两个 16 冲突。冲突之一,我用 --report=lookahead 运行 Bison:

OP_NOT Expression . [OP_OR, OP_AND, CMP_EQ, CMP_NEQ, CMP_GT, CMP_LT, CMP_GTE, CMP_LTE, OP_ADD, OP_MINUS, OP_MULT, OP_DIV, OP_MOD, ')', ';', ',', '[', ']']

我期望的是 '[' 不在 OP_NOT 前瞻标记中,因为 SUBSCRIPT 优先级必须高于 Operator !。其他的冲突是这样的。我该如何解决。Tks

4

1 回答 1

2

这不是优先级的工作方式。

编辑:如果您发现以下描述令人困惑,或者您不想浏览这么多英文文本,您可以接受我通常的建议:不要使用优先级。您几乎总是可以编写不需要优先声明的明确语法。如果你这样做,你就不需要理解优先级。(虽然,老实说,如果您了解 LR 解析的工作原理,它并没有那么复杂。)/编辑

优先级总是比较可能的归约(即右侧与当前解析器堆栈顶部匹配的产生式)和前瞻符号。

在这一点上:

Expression : Expression · '[' Expression ']'

唯一可能的解析器动作是移位,因为只有当点位于右侧末端时才会发生归约。

但是,在该点出现的其中一种状态下,还有另一种产生式:

Expression : OP_NOT Expression ·

这个可以减少,因为点在最后。

由于这两个点都处于相同的状态,因此它们必须都是有效的。这意味着我们正在关注:

OP_NOT Expression · '[' Expression ']'

我们正试图弄清楚该怎么做。我们可以减少OP_NOT ExpressionExpression,此时我们将有:

Expression · '[' Expression ']'

或者我们可以移动'[',留下我们

OP_NOT Expression '[' · Expression ']'

由于这两种情况都是可能的,因此存在shift/reduce 冲突。如果存在优先规则,Yacc/Bison 将尝试使用优先规则来解决该冲突。特别是,它需要比较可能减少的产生的优先级:

Expression : OP_NOT Expression

以及可能被移动的符号'[': 。

但是,仔细查看优先级声明表明没有分配优先级'['。因此 yacc/bison 无法针对生产(其优先级由右侧的最后一个终端定义,OP_NOT,因为没有%prec声明。

如果您希望后缀下标运算符([表达式']')具有比前缀运算符更高的优先级OP_NOT,则必须声明一个[高于的优先级OP_NOT

顺便说一句,我看不出这里的不一致之处。你本可以使用!for OP_NOT(和-forOP_MINUS等等),这样会更容易阅读和减少工作量。

你似乎认为%prec声明在

Expression %prec "SUBSCRIPT" '['Expression']'

是相关的。它不是。仅当解析器可以 reduce 时才适用Expression '[' Expression ']'。但这也是没有意义的,因为您不需要创建一个假终端来保持该生产的优先级;它的优先级由右侧的最后一个终端定义']',因此您可以为该终端声明一个优先级。

声明中的假令牌Expression : OP_MINUS Expression %prec OP_UNARY是必需的,因为'-'它有两个不同的优先级,或者更准确地说,因为OP_MINUS Expression具有不同的优先级Expresson OP_MINUS Expression。不过,您实际上并不需要发明假令牌;您可以使用具有正确优先级的任何标记,例如OP_NOTor OP_NEW

如果这还不够的话,我试图用几个不同的 SO 答案来解释这一点。这是一个这是另一个这是另一个。另外,这里是 Chris Dodd 的一篇,这里是野牛手册中的文档。如果幸运的话,您可能会找到用您自己的语言进行的描述,方法是使用最适合您的任何互联网搜索引擎,或者与您的教授交谈(如果有的话)。

顺便说一句,前瞻报告会告诉您哪些符号可能遵循给定的产生式。优先级对此没有影响。[绝对可以跟随!a。优先级告诉解析器是减少还是移位,但可能触发减少或移位的标记肯定在前瞻集中。

于 2016-05-17T04:05:24.293 回答