btyacc - 云端在线

程序：

您的姓名

btyacc — 一个 拉尔比(1) 支持回溯的解析器生成器

概要

乙型亚克 [-b 字首] [-d] [-D您的姓名 ...] [-E] [-l] [-r] [-S x.sk] [-电视]
文件名.y

描述

btyacc 是 byacc (Berkeley YACC) 的修改版本，后者又是一个公共域
原始 AT&T YACC 解析器生成器的版本。

btyacc 读取文件中的语法规范 文件名.y 并生成一个 LR(1)
解析器。 解析器由一组 拉尔比(1)解析表和驱动例程
用C编程语言编写。 btyacc 通常写入解析表和
驱动程序到文件 字首.tab.c，其中 字首 默认为“y”。

对于语法规范的格式的详细描述，以及一个优秀的
关于如何使用类似 YACC 的工具的教程，请参阅 GNU 信息手册 野牛。 btyacc-
下面解释具体的扩展。

请注意： btyacc 的上游作者提供的解析器框架只能编译为 C++。 用
骨架 /usr/doc/btyacc/examples/btyacc-c.ske 生成一个同时编译两者的解析器
作为 C 和 C++。 （不幸的是，这个替代骨架目前不检查 malloc()
返回值。）

附加选项

-b 字首 将输出文件名的前缀更改为由
字首. 默认前缀是字符“y”。

-d 创建一个名为的头文件 字首.tab.h 随着 字首.tab.c,
包含符号定义和声明 YYS型 和 伊尔瓦尔.

-D您的姓名 定义 btyacc 预处理器变量 您的姓名, 用于 %ifdef 您的姓名
语法文件中的指令。

-E 将预处理的语法打印到标准输出。

-l 不插入 ＃线 指令到生成的解析器代码中。

-r 将解析器代码和关联表写入不同的文件。 而
表可以在 字首.tab.c 和以前一样，现在编写代码
至 字首.code.c.

-S x.sk 选择不同的解析器骨架。 默认骨架硬连线到
程序，但可以在文件中找到副本 btyaccpa.ske.

-t 导致调试代码被编译到生成的解析器中。

-v 将生成的解析器的可读描述写入 y.输出。 它
包括解析器状态、前瞻标记的操作以及有关任何
冲突。

BTYACC 扩展

回溯 支持
每当 btyacc 生成的解析器在
解析表，它记住当前的解析点（堆栈和输入流状态），然后去
进入试用解析模式。 然后继续解析，忽略大多数规则操作。 如果它运行
进入错误（通过解析表或通过操作调用 YY错误）， 它
回溯到最近的冲突点并尝试不同的选择。 如果它
找到一条成功的路径（到达输入的末尾或一个动作调用 YY有效）， 它
回溯到它第一次进入试验解析模式的点，并继续一个完整的
解析（执行所有操作），遵循成功试用的路径。

btyacc 中的操作有两种形式： {} 动作，仅在不在时执行
试用模式，以及 [] 动作，无论模式如何都会执行。

示例：在 C 的 YACC 语法中，称为“词法分析器反馈技巧”的标准技巧是
用于查找 typedef 名称。 词法分析器使用语义信息来决定是否有任何给定的
identifier 是否是 typedef 名称并返回特殊标记。 使用 btyacc，您无需
不再需要这样做； 词法分析器应该总是返回一个标识符。 btyacc
语法然后需要以下形式的规则：

类型名称： ID [ if (!IsTypeName(LookupId($1))) YY错误； ]

但是，请注意添加回溯规则会减慢解析器的速度。 在实践中，你
应该尝试将语法中的冲突数量限制为绝对
必要的。 如果它是一个干净的解决方案，请考虑使用“词法分析器反馈黑客”，并且
为一些特殊情况保留回溯。

btyacc 使用规则“先尝试移动，然后尝试按顺序减少
冲突规则出现在输入文件中”。这意味着您可以实现
语义消歧规则，例如：（1）如果它看起来像一个声明，
否则 (2) 如果它看起来像一个表达式，否则 (3) 它是一个语法错误
[Ellis & Stroustrup，带注释的 C++ 参考手册，第 93 页]。 为了达到这个目的，把所有的
语法文件中表达式规则之前的声明规则。

仅当解析遇到 shift/reduce 或 reduce/reduce 时才会触发回溯
表中的冲突。 如果您的语法没有冲突，则无需额外费用，
除了一些永远不会被调用的额外代码。

目前，生成的解析器执行 没有 修剪备用解析路径。 避免
可能的路径（和解析时间）呈指数级增长，您需要手动告诉
解析器何时可以使用 YY有效 陈述。 在
实践证明，这很容易做到。 例如，C++ 解析器可以
包含 [YY有效;] 在每个完整的声明和语句规则之后，导致
看到“;”后回溯状态被修剪或`}' - 永远不会有
在这种情况下，回溯其中任何一个都是有用的。

优化 象征 位置 处理
编译器通常需要构建 AST（抽象语法树），以便树中的每个节点
可以与它来自的解析程序源相关。 这 易易POSN 支持的机制
by btyacc 帮助您自动化文本位置计算和分配
计算文本位置到 AST 节点。

在标准的 YACC 中，每个令牌和每个非终端都有一个 YYS型 语义值
附在它上面。 使用 btyacc，每个令牌和每个非终端也有一个 易易POSN 文本
位置附加到它。 易易POSN 是用户定义的类型。

btyacc 以与维护堆栈相同的方式维护文本位置值堆栈
语义值。 要使用文本位置功能，您需要 ＃定义 此
在以下：

YYPOSN 附加到每个文本位置的 C/C++ 类型的预处理器符号
令牌和非终端。

yyposn 类型的全局变量 易易POSN. 词法分析器必须分配
返回标记给 yyposn，就像它分配语义值一样
将令牌返回给 yylval。

YYREDUCEPOSFUNC
在正则之后立即调用的函数的预处理器符号
已执行语法规则缩减，以减少位于
堆栈。

通常，此函数从右侧规则中提取文本位置
组件并将它们分配给返回的 $$ 结构/树，或者，如果没有
返回 $$ 值，将它们放入将要放置的 ret 文本位置
后来被其他规则捡起来。 它的原型是：

无效 减少位置(
YYPOSN& RET,
yyposn* 术语位置,
YYS类型* 任期值,
INT 任期号,
INT 位置,
INT yychar,
YYPOSN& yyposn,
用户类型 额外);

ret 引用规则返回的文本位置。 你必须覆盖
这与规则产生的计算文本位置，类似于
$$ 语义值。

术语位置
右侧规则组件的数组 易易POSN 文字位置，
类似于语义值的 $1, $2, ..., $N。

term_vals 右侧规则组件的数组 YYS型 值。 这些是
$1, ..., $N 本身。

term_no 缩减规则右侧的组件数，即
term_posns 和 term_vals 数组的大小。 也等于 $1 中的 N，...，
$N。

位置 YYS型/易易POSN 减少前的堆栈位置。

yychar 先行标记，紧跟在减少的右手边
组件。

yyposn 易易POSN 紧跟在缩小的右侧之后的标记的
组件。

extra 传递给 ReducePosn 的用户定义的额外参数。

YYREDUCEPOSNFUNCAG
传递给 ReducePosn 函数的额外参数。 这个论点可以是任何
变量定义在 btyaccpa.ske.

Token 解除分配 ，我们将参加 错误 恢复
对于大多数类似 YACC 的解析器生成器，生成的解析器在遇到
解析错误是丢弃语义值和输入标记，直到规则包含
特殊的非终端 错误 可以匹配。 令牌的丢弃只是由
覆盖类型的变量和数组条目 YYS型 用新的价值观。

不幸的是，这种方法会导致内存泄漏，如果 YYS型 是指针类型。 btyacc
允许您提供用于清理语义和文本位置值的函数，通过
＃定义在语法文件的序言中输入以下符号：

YY删除
在标记的语义值之前调用的函数的预处理器符号
或非终端被丢弃。

YY删除
在标记的文本位置之前调用的函数的预处理器符号
或非终端被丢弃。

这两个函数都使用两个参数调用。 类型的第一个参数 YYS型 or 易易POSN
是将被丢弃的值。 第二个参数是类型 INT 并且是其中之一
三个值：

0 丢弃输入令牌

1 丢弃堆栈上的状态

2 中止时清理堆栈

专属 句法 错误 报告
如果你 ＃定义 预处理器变量 YYERROR_详细信息 在你的语法文件中，你必须
还定义了以下错误处理函数：

无效 yyerror_detailed(
字符* 文本,
INT 错误,
YYSTYPE&
错误值,
YYPOSN& 错误位置);

文本错误信息

导致错误的令牌的 errt 代码

错误值
导致错误的令牌的值

errt_posn 导致错误的标记的文本位置

预处理器 指令
btyacc 支持定义符号并在其中使用条件指令对它们进行操作
语法文件，与 C 预处理器不同。

％定义 您的姓名
定义预处理器符号 您的姓名. 相当于命令行开关
-D您的姓名.

%ifdef 您的姓名
如果预处理器变量 您的姓名 已定义，从这里处理文本 %ifdef 至
闭幕 ％万一, 否则跳过。

%endif 关闭指令 %ifdef. %ifdefs 不能嵌套。

％包括 文件名
处理名为的文件的内容 文件名. 只有一层嵌套 ％包括
被允许。

%标识 STRING
插入一个`#身份 STRING' 指令进入输出文件。 STRING 必须是一个
用“”括起来的字符串常量。

遗传 属性
继承的属性没有记录。 （见 读我 和 btyacc 源代码
信息很少。）如果您了解它们的工作方式，请通过以下方式与我联系[电子邮件保护]>!

错误

解析的最坏情况复杂度对于任何允许
发生回溯。 换句话说，一个 btyacc 生成的解析器构成了一个
拒绝服务错误，如果在攻击者能够提供的应用程序中使用
特制的数据作为解析器的输入。 （对于所有“常规”输入数据，
潜在的指数复杂性通常不是问题。）

野牛的 ％预计 不支持指令。

没有 ％别的 和 %ifndef. %ifdef并且 ％包括s 不能嵌套。

作者

罗伯特·科贝特[电子邮件保护]> /[电子邮件保护]> 是其中之一
伯克利 byacc 的原作者。 克里斯·多德[电子邮件保护]> 有过辉煌
添加回溯能力的想法，并负责初始回溯
变化。 瓦迪姆·马斯洛夫[电子邮件保护]> 进一步改进了代码。

本文档由 Richard Atterer 撰写[电子邮件保护]> 用于 Debian
GNU/Linux 发行版，但捐赠给公共领域，因此可以自由使用
出于任何目的。

档

/usr/doc/btyacc/examples/btyaccpa.ske

/usr/doc/btyacc/examples/btyacc-c.ske

/usr/doc/btyacc/自述文件

参见 还

野牛(1) （或“信息野牛”）， 通过acc(1), 雅克(1), 蚂蚁(1)

乙型亚克(1)

使用 onworks.net 服务在线使用 btyacc