欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 > 编程资源 > 编程问答 >内容正文

编程问答

Bison介绍[转]

发布时间：2024/3/26 编程问答 57 豆豆
生活随笔 收集整理的这篇文章主要介绍了 Bison介绍[转] 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

转载自：https://zhuanlan.zhihu.com/p/89479111

Bison是一种通用解析器生成器，它将带注释的上下文无关文法转换为使用LALR（1）解析器表的确定性LR或广义LR（GLR）解析器 。作为一项实验性功能，Bison还可以生成IELR（1）或规范的LR（1）解析器表。一旦您精通Bison，就可以使用它来开发各种语言解析器，从用于简单台式计算器的语言解析器到复杂的编程语言。 Bison与Yacc向上兼容：所有正确编写的Yacc语法都应与Bison一起使用，而无需进行任何更改。熟悉Yacc的任何人都应该可以轻松使用Bison。您需要精通C或C ++编程才能使用Bison。还支持将Java作为实验功能。

Bison由三部分组成

  • 定义部分
  • %%
  • 规则部分
  • %%
  • 用户附加的C语言部分

定义部分

代码部分

%{ ... %}，或%code { ... }的内容都是C代码，并将代码照搬到生成的C文件中，可以定义一些函数声明，结构体，类型等，还可以重定义一些Bison的宏，从而改变程序的规则。

声明%name

与flex %option类似，提供一定机制来控制bison默认规则。

  • %pure-parser，指定希望解析器是可重入的。
  • %expect 0，希望冲突数量为0
  • %name-prefix="base_yy"，代表生成的函数和变量名从yy改成base_yy
  • %locations，生成处理位置的代码。 语法使用特殊的'@n'标记后便会启用此模式，但是如果您的语法不使用它，则使用'％locations'可以获取更准确的语法错误消息。
  • %parse-param {core_yyscan_t yyscanner}，声明一个或多个参数声明是其他yyparse参数。 在声明函数或原型时使用参数声明。 参数声明中的最后一个标识符必须是参数名称。
  • %lex-param {core_yyscan_t yyscanner}，指定参数声明是其他yylex参数声明。 您可以传递一个或多个这样的声明，等效于重复％lex-param。
  • %union，嵌入动作返回值类型，一般为非终结符的类型定义。如：
    • %union {core_YYSTYPE core_yystype;/* these fields must match core_YYSTYPE: */int ival;char *str;const char *keyword;char chr;bool boolean;JoinType jtype;DropBehavior dbehavior;OnCommitAction oncommit;………………InsertStmt *istmt;VariableSetStmt *vsetstmt;PartitionElem *partelem;PartitionSpec *partspec;PartitionBoundSpec *partboundspec;RoleSpec *rolespec; }

    8. %type<>，Bison构造％type用于声明非终结符。 以前我们以前没有使用％type，因为非终结符通常由定义它们的规则隐式声明。 但是必须显式声明exp，以便我们可以指定其值类型。

    9. %token<>，token类型定义。在PostgreSQL中为关键字定义。

    10. 优先级定义，为了避免过多的语法冲突，在这里定义一些语法优先级，从上到下优先级依次递增

    %nonassoc SET /* see relation_expr_opt_alias */ %left UNION EXCEPT %left INTERSECT %left OR %left AND %right NOT %nonassoc IS ISNULL NOTNULL /* IS sets precedence for IS NULL, etc */ %nonassoc '<' '>' '=' LESS_EQUALS GREATER_EQUALS NOT_EQUALS %nonassoc BETWEEN IN_P LIKE ILIKE SIMILAR NOT_LA %nonassoc ESCAPE /* ESCAPE must be just above LIKE/ILIKE/SIMILAR */ %left POSTFIXOP /* dummy for postfix Op rules */

    规则部分

    规则分为规则/行为行和C代码行。

    规则/行为

    bison语法是由一系列的规则组成。每个规则由非终结符开始，然后是“:”和可能为空的符号、文字记号和动作的列表。 例如：

    simple_select:SELECT opt_all_clause opt_target_listinto_clause from_clause where_clausegroup_clause having_clause window_clause{SelectStmt *n = makeNode(SelectStmt);n->targetList = $3;n->intoClause = $4;n->fromClause = $5;n->whereClause = $6;n->groupClause = $7;n->havingClause = $8;n->windowClause = $9;$$ = (Node *)n;}|………………;
  • “:”左边为非终结符。
  • “:”右边为规则，由一系列的终结符或非终结符构成。
  • “$$”，表示simple_select。
  • “$number”，表示“:”右边符号，数字为几，则表示第几个符号。
  • “|”，表示或，“simple_select”其他规则。

    • 代码段

    此段落，postgresql, 定义了一些在规则段中使用的工具函数。

    移进/归约

    移进：bison语法分析器通过查找能够匹配当前token的规则来运作。当bison处理一个语法分析器时，他创建一组状态，每个状态都反应出一个或者多个部分分析过的规则中可能的位置。当语法分析器读取记号时，每当它读到的记号无法结束一条规则时，它将把这个记号压入一个内部堆栈，然后切换到一个新状态，这个状态能够反映出刚刚读取的记号。这种行为被称为移进。

    归约：当它发现压入的所有语法符号已经可一以组成规则的右部时，他将把右部符号全部从堆栈中弹出，然后把左部语法符号压入堆栈。这种行为被称为归约。因为它通常消减了堆栈中一定数量的符号。每当bison归约一条规则时，它会执行该规则关联的用户代码。

    二义性

    只要是对于语言的解析，往往都会伴随二义性的问题。bison把语法翻译为成语法分析器时有可能会报告冲突。一些情况下，语法确实有歧义；也就是说。对于一个输入的字符串，存在两种可能的语法分析器，而bison无法处理这种情况。（当然也有可能是bison对于某些规则不支持的缘故）。 bison的二义性冲突分为移进/归约冲突和归约/归约冲突。 移进/归约冲突：

    %% e: 'X'| e '+' e;

    在这里，当我们输入X+X+X时，存在两种可能，（X+X）+X和X+（X+X）。移进会按照第二条规则进行，而归约会按照第一条规则进行，这时就会存在矛盾。 移进/归约冲突：

    %% prog: proga | progb ;proga: 'X'; progb 'X';

    移进不会产生歧义，但当归约时，X既是proga又是progb，这就会造成归约/归约冲突。

    工作流程

    图片来自于同事，bret.shao

    flex&bison协作方式

    官方文档

    https://www.gnu.org/software/bison/

    总结

    以上是生活随笔为你收集整理的Bison介绍[转]的全部内容，希望文章能够帮你解决所遇到的问题。

    如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。