`
RednaxelaFX
  • 浏览: 3049037 次
  • 性别: Icon_minigender_1
  • 来自: 海外
社区版块
存档分类
最新评论

bison的运算符优先级一例

阅读更多
看到phyeas同学在试写JavaScript语法,顺便参一腿 =v=
本文里的代码放在附件里了,有需要的拿。

关于语法中左递归/右递归与规则的左结合/右结合的关系,我觉得就照着简单的表达式语法把推导过程画出来,找找感觉就能行。要注意的是推导结束后,把每步推导过程画成树(也就是解析树或者叫语法树),离根越远的节点在就越先被求值,也就是“优先级高”的表现了。写这帖的时候懒得画例子了……有必要再补充。

自顶向下的解析方法,如递归下降式或者LL式,一般无法支持左递归的语法,无聊是直接左递归还是间接左递归。这是因为它总是从推导规则中的第一个符号开始推,如果第一个符号就是自己或者间接回回到自己,那么解析过程就无法前进,就无限递归而出错了。(近年来有人提出过一些改进方案使自顶向下解析可以支持左递归,这帖里就不讨论了。有兴趣的同学可以阅读这篇论文:Packrat parsers can support left recursion)。

传统上,为了解决无法左递归的问题,可以改写语法规则,通过引入一个ε转换来把左递归变为右递归。但是这样得到的语法树的结合性就不对了,要得到正确的语法树需要做额外的工作来把树的形状转换回来。

LR系的解析方式则既支持左递归也支持右递归,写起语法来就轻松很多。结合性直接靠语法的递归位置就可以表达。

结合性有两个经典的应用场景,一是表达式的解析,二是if-else问题的解决。这帖主要着眼于前者。
表达式的形式比较固定,但传统上运算符有不同优先级,写语法的时候为了照顾优先级可以选择把相似的结构重复写在多个规则里,让这些规则的层次表达优先级的差别。但规则多了,状态图也就变复杂了。
通过显式指定运算符的优先级,语法中结构相似的规则可以写在同一条规则里,既简化了语法,对应的解析器的效率也更高。

GNU Bison是主要采用LALR(1)的解析器生成器。它支持显式指定规则的优先级以及结合性。
那么优先级能否跨规则而存在呢?先看个例子:
calc1.y
%{
#include <stdio.h>
#include <ctype.h>
#include <math.h>
%}

%union {
    double dval;
}

%token <dval> NUMBER
%token POW

%left '+' '-'
%left '*' '/'
%nonassoc UMINUS
%right POW

%type <dval> expr

%%

line
    : expr '\n'             { printf("%lf\n", $1); }
    ;

expr
    : NUMBER                { $$ = $1; }
    | expr '+' expr         { $$ = $1 + $3; }
    | expr '-' expr         { $$ = $1 - $3; }
    | expr '*' expr         { $$ = $1 * $3; }
    | expr '/' expr         {
        if (0 == $3) yyerror("divided by zero");
        else $$ = $1 / $3;
    }
    | '-' expr %prec UMINUS { $$ = -$2; }
    | expr POW expr         { $$ = pow($1, $3); }
    | '(' expr ')'          { $$ = $2; }
    ;

%%

int main() {
    return yyparse();
}

int yyerror(char* s) {
    fprintf(stderr, "%s\n", s);
    return 1;
}

int end = 0;

int yylex() {
    if (end) return 0;
    int c;
    
    /* skip space */
    while (' ' == (c = getchar())) { }
    
    if (isdigit(c)) {
        ungetc(c, stdin);
        scanf("%lf", &yylval);
        return NUMBER;
    }
    
    if ('*' == c) {
        c = getchar();
        if ('*' == c) {
            return POW;
        } else {
            ungetc(c, stdin);
            return '*';
        }
    }
    
    if ('\n' == c) {
        end = 1;
    }
    
    return c;
}

这是个简单的计算器,支持加、减、乘、除、负、幂等运算,并且可以通过括号改变表达式的结合性。注意到,所有表示“表达式”的规则都在同一个大规则expr里,它们的结合性和优先级则在语法文件的头部声明。

如果把expr改为下面的样子呢?
calc2.y
expr
    : NUMBER          { $$ = $1; }
    | expr binop expr {
        switch ($2) {
        case '+': $$ = $1 + $3; break;
        case '-': $$ = $1 - $3; break;
        case '*': $$ = $1 * $3; break;
        case '/': $$ = $1 / $3; break;
        case POW: $$ = pow($1, $3); break;
        }
    }
    | '-' expr        { $$ = -$2; }
    | '(' expr ')'    { $$ = $2; }
    ;

binop
    : '+'| '-' | '*' | '/' | POW
    ;

bison会抱怨说出现了5个递进/规约冲突。用bison -v calc2.y命令,查看calc2.output,可以看到冲突出现在状态17:
state 17

    3 expr: expr . binop expr
    3     | expr binop expr .

    POW  shift, and go to state 9
    '+'  shift, and go to state 10
    '-'  shift, and go to state 11
    '*'  shift, and go to state 12
    '/'  shift, and go to state 13

    POW       [reduce using rule 3 (expr)]
    '+'       [reduce using rule 3 (expr)]
    '-'       [reduce using rule 3 (expr)]
    '*'       [reduce using rule 3 (expr)]
    '/'       [reduce using rule 3 (expr)]
    $default  reduce using rule 3 (expr)

    binop  go to state 15

在这个状态时,下一个字符假如是+,那么既可以递进并转到状态10,也可以规约,于是就冲突了。

问题的关键就在于,这个“优先级”到底是干嘛用的。以calc1.y为例,如果没有指定运算符优先级,匹配到这样一个状态:
expr '+' expr .

(“.”表示当前匹配的位置)
假如下一个符号是*,那么到底应该选择递进,变为:
expr '+' expr '*' .

还是规约,变为:
expr .

呢?
有了优先级,bison就可以比较递进与规约的选择间涉及的优先级;看到*的优先级比+高,于是选择递进。

而在calc2.y中,加减乘除幂这几个带优先级的运算符堆在了binop规则中。匹配该规则其实不需要优先级,单靠lookahead就足够了;在遇到加减乘数幂这几个运算符时,bison肯定会选择规约为binop;规约后,binop本身就不带有任何优先级信息了。而在expr规则中,需要优先级去区分递进或规约的expr binop expr子规则却得不到任何优先级信息,于是递进/规约冲突又冒出来了。

phyeas的问题:
phyeas 写道
另外,想问下如果我在声明处定义如下:
%left PLUS
然后在规则处:
expression:
    expression op expression
;
op:
    PLUS
;

这样的华expression是否会应用上面定义的优先级?

答案是:不会。

进一步阅读:
首推自然是bison的手册
这个帖子也可以读读,也是用表达式计算器为例子来讲解的。现在好困,不想码那么多字,既然有现成的解释我也就不用码了 =v=
分享到:
评论
1 楼 phyeas 2009-09-19  
谢谢,明白了

相关推荐

    c++ 程序 表达式求值

    2. **中缀转后缀**:使用栈来处理运算符,遇到数字直接输出,遇到运算符则与栈顶运算符比较优先级,根据优先级规则决定是否入栈或输出。 3. **后缀表达式求值**:使用两个栈,一个存储操作数,一个存储运算符。遍历...

    Windows下用Bison和Lex实现中缀转后缀.zip

    这个压缩包“Windows下用Bison和Lex实现中缀转后缀.zip”显然包含了一个教程或项目,旨在教用户如何利用这两种工具将中缀表达式转换为后缀表达式,也就是我们常说的逆波兰表示法。下面将详细解释这一过程涉及的知识...

    一个逆波兰式的生成程序

    否则,将栈顶运算符弹出并输出,直到栈顶运算符的优先级低于当前运算符或栈为空。 5. **处理左括号**:遇到左括号时,将其压入栈中,表示后面的部分是一个子表达式。 6. **处理右括号**:遇到右括号时,不断弹出栈顶...

    科学计算器flex和bison

    在Flex中,我们需要为这些运算符定义规则,而在Bison中,则需要处理运算符的优先级和结合性。 2. 高级运算:幂运算(^)、对数运算(log)、阶乘(!)以及绝对值(abs)。这些运算在Bison的语法文件中需要定义相应...

    计算器有小数加减运算和运算优先级等功能

    总的来说,这个课程设计项目涵盖了基础的数学运算、运算符优先级处理、错误检测以及用户交互等多个方面,对于初学者来说,这是一个很好的实践项目,能够锻炼到编程思维、算法理解以及软件工程的基本技能。...

    flexbison语法分析自动生成工具的使用教程

    - 如何在Bison中使用`%token`、`%left`、`%right`和`%nonassoc`关键字来指定运算符优先级。 - 一个简单的示例,比如解析一个简单的算术表达式语言,演示如何组合Flex和Bison来实现解析。 - 如何处理Flex和Bison之间...

    数学表达式求值 表达式求值

    5. **运算符优先级**:在计算表达式时,必须考虑运算符的优先级,例如乘法和除法优于加法和减法。C语言中,可以使用嵌套的if-else或switch语句,或者自定义数据结构来实现优先级处理。 6. **堆栈数据结构**:在后缀...

    bison计算器编译原理

    当遇到运算符时,我们可以将其压入栈中,直到遇到一个更高的优先级运算符或者遇到一个右括号,此时我们可以弹出栈顶的运算符和操作数进行计算。 标签中的“科学计算器”意味着我们的计算器可能需要支持更复杂的数学...

    GNU Bison 中文手册

    例如,Bison符号部分会解释诸如规则、语句、动作、优先级和关联性等概念;词汇表则为用户提供了对这些术语的清晰定义。 最后,手册强调了在发现错误或提出建议时,用户应该主动联系翻译者或贡献者,这能够促进手册...

    表达式类型的实现-数据结构

    当遇到运算符时,我们将其与栈顶运算符比较优先级,如果当前运算符优先级更高,则将其压入栈;否则,弹出栈顶运算符并计算相应的操作数,直到当前运算符的优先级高于栈顶运算符或栈为空。这种方法被称为后缀表达式...

    windows版本bison的bison.simple

    在IT领域,Bison是一个非常重要的工具,尤其对于软件开发者来说。Bison是一个基于Yacc(Yet Another Compiler-Compiler)的语法分析器生成器,它能够根据用户定义的语法规则生成解析器。Windows版本的Bison使得在...

    bison词法分析 语法分析

    - **%left**、**%right** 和 **%nonassoc**:定义运算符的优先级和结合律。 - **解析规则**:描述语言的语法结构。 - **语义动作**:在解析过程中执行的代码片段。 #### 三、示例 ##### 3.1 反向波兰表示计算器 ...

    用C++编写的强悍"表达式"求值源代码

    遇到运算符时,与栈顶运算符比较优先级,如果当前运算符优先级更高或相等,则将栈顶运算符弹出并压入结果栈,直到当前运算符的优先级低于栈顶运算符。最后,将所有操作数和运算符都处理完后,结果栈中的元素就是后缀...

    系统软件开发 Bison实验1

    在系统软件开发领域,Bison(也称为Yacc)是一个重要的工具,用于构建解析器,尤其是对于编程语言的编译器或解释器。本实验主要关注如何利用Bison来编写C语言的分析器,这是一个涉及编译原理和技术的实践过程。 ...

    bison&flex

    3. **Bison 表达式处理**:`bison` 支持 LALR(1) 解析算法,允许用户定义优先级和关联性,处理运算符重载等复杂情况。 4. **冲突解决**:在解析器生成过程中可能会遇到语法冲突,`bison` 提供了处理这些冲突的方法...

    papageno:帕雷尔·帕瑟(Parrallel PArser)总经理

    基于Floyd运算符优先级语法的PArallel PArser GENeratOr PAPAGENO是功能强大且高效的并行解析器生成器。 它从语法规范开始以与Bison相同的语法生成并行C解析器。 生成的解析器是独立的,可以与常见的GNU Flex生成...

    语言编译器的实现二PPT学习教案.pptx

    此外,还需要定义语法开始符号、语义值类型、终结符和运算符的优先级及结合性。 2. **语法规则部分**:这是YACC程序的核心,包含了语言的上下文无关文法规则。每个规则都由一个非终结符(通常是左侧)和一组可能的...

    计科17-6班-陆玺文-03170908-实验bison21

    实验过程中,学生可能会遇到诸如运算符优先级、括号嵌套等问题导致的冲突。通过重新设计语法规则,如使用预定义的优先级和结合性规则,可以有效地消除这些冲突。 1.5 实验步骤 1.5.1 CentOS环境下 - 安装Bison工具...

    bison分析计算器

    【标题】"bison分析计算器"涉及的主要技术是Bison,这是一个用于生成解析器的工具,常被用于编译器和解释器的开发。在计算机科学中,解析器是将输入(如源代码或特定格式的数据)转换为内部表示的关键组件。Bison...

Global site tag (gtag.js) - Google Analytics