GNU Bison 2.1 中文手册

20060121 GNU Bison 2.1中文手册翻译完成

Bison 2.1 是 Bison 的最新版本。本版本的主要改进包括支持使用 C++ 语言作为输出工具，并且在分析器的本地化输出界面中也进行了多项优化工作。有关这些改进的详细说明与实现细节，请参考最新的 BISON 手册。

GNU Bison实际上是基于最广泛使用的与Yacc兼容的分析器构建工具。它能够生成多种类型的解释器、编译器和协议实现。此外，它不仅与Yacc兼容，并且拥有许多其他分析器不具备的独特功能。

这个手册编写得极为完善,助您深入了解Bison在使用中的诸多细节(值得注意的是,并非实现细节)

因个人能力有限,如有发现错误或语言表达不够通顺之处,恳切希望得到您的指正与帮助！如需进一步帮助,请及时通过邮件联系（http://cn.f156.mail.yahoo.com/ym/Compose?To=sirouni@yahoo.com.cn），提供您的修改意见或正确翻译建议。非常感谢！

英文原件页面

Bison 2.0 中文手册手册页面

这份翻译版手册同样遵循GNU Free Documentation License的规定发行。

提供以下格式:(会陆续增加格式)

• html格式(558,990字节,整个页面)

一些参考:

• GNU Bison Project
• The LEX & Yacc Page
• GNU Flex Project
• Yacc编译器: 另一个编译器的编译器Stephen C. Johnson authored,寒蝉退士

/head>

Bison

这个手册是针对GNU Bison (版本2.1,16 September 2005), GNU分析器生成器.

Copyright © 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.

Chinese(zh_CN) translation: sirouni (sirouni@yahoo.com.cn)

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with no Invariant Sections, with the Front-Cover texts being "A GNU Manual," and with the Back-Cover Texts as in (a) below. A copy of the license is included in the section entitled "GNU Free Documentation License."

(a) The FSF's Back-Cover Text is: "You have freedom to copy and modify this GNU Manual, like GNU software. Copies published by the Free Software Foundation raise funds for GNU development."

    GLRGLR

    rpcalcrpcalc

    ltcalcltcalc

    mfcalcmfcalc

    yylexyylex

||

Bison简介-Introduction

Bison 是一种广泛用途的编译程序生成工具. 该系统将LALR(1)上下文无关文法表示为相应的C语言解析程序. 熟练掌握_Bison_后, 您将能够利用它来创建涵盖从简单桌面计算器到复杂编程语言等多样的语言解析器.

支持与BISON协同工作的Yacc语法将无需额外修改即可无缝集成。
那些精于Yacc的人都能在短时间内熟练掌握并运用BISON。
为了更好地操作BISON并深入研究这份手册，请确保你具备扎实的C编程基础。

我们会在这份教程的起始几章为BIson的基本概念进行阐述，并举例说明三个详细的实例，在后续部分会构建这些实例。如果对此一无所知，请您首先阅读这些章节。在后面的章节中深入阐述了BIson的各种方面。

初始版本主要由罗伯特·科贝特编写代码. 罗伯特·斯蒂尔曼通过其贡献使得Bison能够与其Yacc工具兼容. 卡内基梅隆大学的威尔富德·汉森在Bison的基础上增添了多字符字符串（multi-character string literals）以及其它一些功能模块.

这个版本的手则主要与Bison2.1相一致.

使用Bison的条件-Conditions for Using Bison

为使非自由软件能够利用Bison生成的LALR分析器C代码，在Bison版本1.24期间我们更新了yyparse的相关发布条款。在此之前，这类分析器仅限于支持免费软件的应用。

除了 GNU 编程工具外，在某些情况下也会发现类似的例外情况。例如 GNU C 编译器曾经缺乏类似的限制条件。这些工具通常广泛应用于发布非自由软件系统中。然而,Bison 与其他 GNU 工具的不同之处并非源于特定策略的选择,而是因为将通用公共许可（General Public License）应用于所有Bison源代码所导致的结果。

该程序通过（the）Bison分析器文件（file）实现了（实现）动态生成（generation）不同长度和结构的代码段。这些代码段由特定功能模块（module）生成。在不影响其他功能模块的前提下，在指定位置（position）插入语法动作。通过将GPL许可协议应用于yyparse源码库（source code），我们确保了生成的所有目标程序均能在自由软件框架下运行。

我们没有更改条款是因为对那些希望拥有 Software 自由化的人抱有同情心. 所有的 Software 都应该是 Free Software. 我们的结论认为：仅允许使用 Bison 的项目必须属于 Free 软件类别. 这在鼓励其他 Software 成为 Free 软件方面的作用非常有限. 因此我们决定将使用 Bison 的条件与使用其他 GNU 工具的条件保持一致. （注：即和 GCC 一样可以在非 Free 软件中应用.)

此例外情况仅限于使用Bison生成LALR(1)分析器的C代码场景。.否则情况下,GPL条款通常会正常执行..你可采取的方法是查看相关代码文件,以确定其中是否存在类似说明:As a special execption,当本文件被Bison导入一个Bison输出文件时,you may使用该输出文件而不受限制.

GNU GENERAL PUBLIC LICENSE

Version 2, June 1991

||

Preamble

Most software licenses are structured in a way that restricts your ability to share and modify them. In contrast, the GNU General Public License (GPL) is designed specifically with these freedoms in mind: ensuring that you can freely share and modify free software without restriction, thereby safeguarding your rights as a user of free software across all platforms. This license applies not only to a majority of Free Software Foundation's products but also extends coverage under certain conditions when other programs adopt this license. You are not required by law or contract not only in this context but also in many others where you may wish or need such freedoms.

When discussing free software, we are emphasizing freedom rather than cost. Our General Public Licenses are crafted to ensure that users have the freedom to distribute copies of free software (potentially charging for this service), access the source code or obtain it themselves, modify the software or incorporate its components into new free programs; and remain informed about these rights.

Mandating the protection of your rights requires us to establish restrictions that prevent anyone from denying these rights or compelling them to surrender them. These restrictions incorporate specific obligations for distributing software copies or making modifications.

As an instance, when you redistribute copies of such a program—whether distributed without charge or for a fee—you are obligated to provide all the rights that pertain to you to the recipients. Additionally, ensure that they are made aware either directly or indirectly of their legal entitlements concerning the software. Furthermore, it is imperative to clearly outline these conditions in writing so that both parties are fully informed and understand their respective obligations.

Through two distinct measures, we ensure your rights are safeguarded. (1) register the software for copyright protection, and (2) grant you a license that permits copying, distributing, or modifying the software as permitted.

Also, ensuring each author's right to be protected as well as our own rights, we aim to make certain that all parties involved understand clearly that no formal warranties are provided with this free software. If the software has been altered by another party and distributed further, we strongly advise its recipients to be made aware that what they possess is a modified version, so as not to damage the reputation of the original authors in any way.

Finally, any free software is constantly threatened by software patents. We aim to prevent the scenario where redistributors of a free software may individually acquire patent licenses, effectively converting the software into a proprietary product. To mitigate this, it has been clearly stipulated that every patent must be granted access for all users without cost or remain unlicensed altogether.

The strictly defined provisions for reproduction, dissemination, and changes or alterations follow.

该许可适用于包含某些 NOTICE 文件的作品。
此处的'程序'指任何此类程序或作品；而基于'程序'的作品则指程序本身或根据版权法产生的衍生作品：即包含程序或其中一部分（无论是原文还是经过修改和/或其他语言翻译）。简而言之，在此条款下，“包含程序或其中一部分（无论是原文还是经过修改和/或其他语言翻译）”。注意：在此之后，“翻译被包括在‘修改’项中。”每位受许可人以‘您’称呼。

除复制、分发及修改之外的其他活动均未受到本许可保护；它们超出了本许可的范围。运行该程序的行为不受限制，在其生成的输出中只有当其内容构成基于该程序的作品时才会受到保护（不论输出是否仅通过运行该程序而产生）。这是否成立将取决于该程序的行为。

2. 您可以按原文逐字复制并分发程序代码副本，在任何介质中接收。
   只要您显著并适当地标记这些副本上的版权信息和免责声明。
   同时保留所有与本许可证相关以及无担保声明的说明。
   并将该许可证副本连同源代码发送给其他人。

You may set a fee for the physical process of transferring a copy. You may, at will, provide warranty coverage in return for payment.

3. 您可能对Program及其任何部分进行复制或修改（形成基于Program的作品），并在本节第一项规定的前提下，在不侵犯本条款任何条款的前提下复制或分发这些修改作品或作品，请务必满足以下所有条件：
4. 您必须向修改后的文件明显显示（如醒目位置）表明您更改了文件，并标注任何更改的时间。
5. 您必须确保任何包含或源自Program及其任何部分的作品（无论是全部还是部分）在分发或出版时，在不向第三方收取费用的前提下按本许可协议整体授权。
6. 如果修改后的程序通常在运行时交互式地读取命令，请您确保在其启动后（以最普通的方式）会打印或显示包含适当版权说明以及明确指出无保证（或其他情况下表明您提供无保障）的通知，并告知用户在此情况下可以分发该程序以及如何获取本许可协议副本的特别说明。（例外情况：如果原始程序无需交互即可运行而无需打印此类通知，则基于其的您分发的作品无需此类通知）

These license terms apply to any modified version of this work. Unless identifiable sections of that work are not derived from the Program and can reasonably be considered entirely independent creations, this License does not exclude such portions when they are distributed separately. However, if you distribute any such portions as part of a larger work based on this Program, those portions must also be distributed under this License's conditions. This means that all users who obtain copies of this entire collection must adhere to its stipulations, thereby encompassing every individual component irrespective of its original authorship.

Thus, its purpose is not to assert rights or challenge your ownership claims regarding works you have entirely written; instead, it aims to grant rights over derivative or collective works built upon your original work.

In addition, simple aggregation of another work that is not derived from the Program with the Program (or works derived from it) on storage or distribution volumes does not include such works within the scope of this License.

4. You may copy and distribute the Program (or a work based on it, under Section 2) in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following:
   1. Accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or,
   2. Accompany it with a written offer, valid for at least three years, to give any third party, for a charge no more than your cost of physically performing source distribution, a complete machine-readable copy of the corresponding source code, to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or,
   3. Accompany it with the information you received as to the offer to distribute corresponding source code. (This alternative is allowed only for noncommercial distribution and only if you received the program in object code or executable form with such an offer, in accord with Subsection b above.)

源代码是工作的主要版本。
对于一个可执行程序而言，
完整的源代码包含所有组成部分的源代码，
再加上与之相关的接口定义文件，
以及用于控制编译和安装的脚本。
然而，在特殊情况下，
分发时不需要包含通常随主程序（不论是源代码还是二进制）一并分发的那些内容，
除非该组件本身也随主程序一起分发。

If distributions of executable or object codes are achieved by granting access to copies from a designated location, then providing equivalent access for copying the source code at the same location constitutes distribution of that source code, irrespective of whether third parties are legally required to include copies of the source alongside executables.

5. You may not copy, modify, sublicense, or distribute the Program except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense or distribute the Program is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.
6. You are not required to accept this License, since you have not signed it. However, nothing else grants you permission to modify or distribute the Program or its derivative works. These actions are prohibited by law if you do not accept this License. Therefore, by modifying or distributing the Program (or any work based on the Program), you indicate your acceptance of this License to do so, and all its terms and conditions for copying, distributing or modifying the Program or works based on it.
7. Each time you redistribute the Program (or any work based on the Program), the recipient automatically receives a license from the original licensor to copy, distribute or modify the Program subject to these terms and conditions. You may not impose any further restrictions on the recipients' exercise of the rights granted herein. You are not responsible for enforcing compliance by third parties to this License.
8. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program.

If any portion of this section is found unenforceable under specific conditions, its application is intended for the remainder of the section.

本节并非旨在引起你侵犯任何专利或其他财产权利声明，并争议这些声明的有效性;其唯一目的乃是为了维护该自由软件分发系统的完整性,这种系统是基于公有许可实践所实施的。许多人均基于对这一系统的贯使用而慷慨地提供了大量通过其广泛范围软件分发所获益匪浅的作品;至于作者/捐赠者是否愿意采用其他分发系统则是他/她们自己的选择,而授权方则无权强加此种选择。

本节旨在详细阐述各方应如何看待此协议的后续发展

9. If the distribution and/or use of the Program is restricted in certain countries either by patents or by copyrighted interfaces, the original copyright holder who places the Program under this License may add an explicit geographical distribution limitation excluding those countries, so that distribution is permitted only in or among countries not thus excluded. In such case, this License incorporates the limitation as if written in the body of this License.
10. The Free Software Foundation may publish revised and/or new versions of the General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns.

Each version receives a distinct serial number. If the Program refers to a serial number under this License that applies to it and any subsequent release, you can comply with either that specific release's terms or those outlined in any later release by the Free Software Foundation. In cases where the Program does not specify a serial number under this License, you are free to choose any release ever made by the Free Software Foundation.

11. If you wish to incorporate parts of the Program into other free programs whose distribution conditions are different, write to the author to ask for permission. For software which is copyrighted by the Free Software Foundation, write to the Free Software Foundation; we sometimes make exceptions for this. Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally.
12. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
13. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.

Appendix: How to Apply These Terms to Your New Programs

Upon developing a new program, if your goal is for it to be most effectively utilized by the public, then creating open-source software that allows anyone within these terms to redistribute and modify it would be the optimal approach.

为此目的，请将以下通知粘贴到程序中。最安全的做法是将它们放在每个源文件的开头以最有效地传达保修排除；同时建议每个文件至少包含‘版权’行，并附有指向完整说明的位置指示。

||

    one line to give the program's name and a brief idea of what it does.yyyyname of author

Also add information on how to contact you by electronic and paper mail.

If the application has an interactive interface, instruct it to display a concise alert when it initiates operation in its initial interactive phase:

||

    yyname of author

These hypothetical commands, labeled show w' and show c', are intended to display the specific sections of the General Public License. However, the commands you employ might have alternative names, such as mouse-clicks or menu items, depending on your program’s preferences.

It is advisable that you also obtain signatures from your employer (or organization) or school (if applicable), for the program's copyright disclaimer, especially when necessary. As an example, you can refer to this sample and adjust the names accordingly.

||

    signature of Ty Coon

该通用许可协议禁止将您的程序整合到商业软件中。如果您的程序是一个子例程库，则允许将商业软件与之连接可能更具优势。如果这就是您希望实现的目标，请考虑使用GNU通用许可证代替当前协议。

1. 和Bison相关的一些基本概念-The Concepts of Bison

本章阐述了若干核心概念,但未涉及难以察觉的一些细节. 为了更好地掌握Bison/Yacc的操作流程,我们推荐您深入研读本章内容.

1.1 语言与上下文无关文法-Languages and Context-Free Grammars

为了支持Bison进行语义分析能力的发展需求，所选择的语言必须要能够用上下文无关文法（context-free grammar）来进行描述。换言之，在设计该类编程语言时，请明确至少一组或多个语法组（syntactic groupings）及其构建整个结构的方式。举个例子，在C/C++等高级编程语言中就存在被称为expression（表达式）的一种语法组。生成该类结构的具体方式之一是"任何一个表达式都可以由一个运算符连接两个操作数构成"。此外还可以采用"任何一个合法变量名可以直接作为一个独立的值参与运算"这种方式来构造复杂的语义实体。正如你所观察到的一样这些生成规则往往都是通过递归来定义的但在实际应用中必须要确保至少存在一条非递归终止条件。

用于表示这些规则的通用 Backus-Naur 范式（Backus-Naur Form）或 BNF 被用来表示。该语言旨在阐述 Algol 60。所有由 BNF 描述的语言都是上下文无关语言。Bison 被要求使用 BNF 对其输入进行描述。

上下文无关 grammar has many important subsets. Although bison can handle almost all context-free grammars but it was optimized for lalr（1）. To summarize, in these cases （note referring to lalr（1）), we can specify how to analyze the input string with a single lookahead scan. More formally, this is a description of an lr（1）。lalr（1） parsers include additional constraints that make them more difficult to analyze. Fortunately, in practice it's rare to find an example that's purely lr（1） without being lalr（1）。参阅神秘的归约/归约冲突-Mysterious Reduce/Reduce Conflicts以获取更多信息。

LALR(1) parsers are deterministic, implying that the next grammar rule to match is determined by the preceding input and the known remaining input (referred to as a lookahead symbol). A context-free grammar may be ambiguous, meaning multiple rules could match certain inputs. Even non-ambiguous grammars might still be non-deterministic, lacking a fixed lookahead that can always determine the next applicable rule. The well-known GLR technique allows Bison to parse these more general context-free grammars when any given string has a unique analysis.

根据正式语言学中的语法规则定义，任何一种语法单元或组合都可被视为_符号（symbols）。其中能够进一步分解为更小结构的部分被称为_非终结符（nonterminal symbols）。它们无法再进一步分解的部分被称为_终端标记（terminal symbols）_或者称作_token类型的标记（token types）。与这些终端标记对应的连续字符序列称为_token（tokens）；而与每个非终端标记相关的连续字符序列称为_groupings（groupings）。

以C语言为例可以阐述符号的概念及其区分终结符与非终结符。在C语言中使用的标识包括标识符、常量（数字或字符串）以及一系列关键字、运算符号和标点。因此，在C语言语法中识别出的关键元素包括标识符、数字或字符串类型以及每一个关键字对应的运算符号、标点或其他特殊字符。需要注意的是（这些标记本质上属于词法分析而非语法分析范畴。

这是一个如何将C函数分解成记号的例子:

||

C语言中的语法组成部分包含表达式、语句、声明以及函数定义。这些由C语言中的非终结符expression、statement、declaration以及function definition表示。完整的语法还采用了多种额外的语言结构，并为每一种结构单独设置了对应的non-terminal符号来体现上述四者的关联。以上举例展示了一个函数定义的具体情况，它整合了相应的声明与语句。对于任意变量x来说都是一个合法的表达式；特别地，像x乘以X这样的运算结果同样也是合法的表达式。

每一个非终结符应有其构成方式说明；例如，在C语言中，“return”语句的非正式使用将通过以下语法规则来描述。

一种语句由三个部分构成：带有return关键字的部分、包含了一个expression以及分号;.

还有许多其它对应`statement'的规则,每一种规则对应一种C语句.

不可忽视的一种特殊非终结符值得我们予以关注。它决定了该语言的完整表达方式，并被指定为_起始符号(start symbol)_\textsubscript{1}。在编译器体系中,它代表着一个完整的输入程序\textsubscript{2}. 在C\textsubscript{3}语言中, `sequence of definitions and declarations`扮演了这一角色\textsubscript{4}$.

例如,1+2是一个有效的C表达式--作为一个有效的C程序的一部分--但它不能作为一个完整的C程序的一部分.entirely. 在上下文中,C语言遵循了expression并非起始符号这一事实。

该分析器从输入中读取符号序列，并通过语法规则将其组合起来。当输入正确时,该分析器会将整个符号序列解析并归位到起始标记位置。若采用基于C语言的语法规范, 输入必须构成一个完整的定义和声明序列; 若不具备此结构特征, 分析系统将会报错。

1.2 从正规文法转换到Bison的输入-From Formal Rules to Bison Input

正则文法属于一种数学结构类型. 在定义分析器时, 需要按照Bison语法构建表示该语言的文档, 即编写一个_BISON 语法(BISON_grammar)_文件. 参考_BISON_的文档 - BISON_Grammar_Files.

类似于C语言中的标识符，在Bison语法输入中（类似于C语言中的标识），每个正规文法中的非终结符号都使用特定的小写字母作为名称（例如expr、stmt或declaration），这些遵循通常的习惯。

在Bison中,终结符也被称作_符号类型(token type)_. 这些符号类型通常遵循与C语言类似的命名规则,并且为了便于区分非终结符和其他类型的标识符,一般采用大写字母的形式进行表示. 根据约定俗成的规定,这些标识符主要包括诸如INTEGER, IDENTIFIER, IF以及RETURN等常见类型. 每个编程语言的关键字对应的终结符名称则应与其本体紧密相连地命名,例如对应于关键字'IF'的大写字母形式则被命名为'IFE'. 终结符ERROR则被保留下来专门用于程序运行中的错误处理功能. 更详细的说明可参阅文档中的相关部分.

一个终结符也可以由类似于C语言中的常量的一个字符来表示。当一个标识符就是一个字符（括号、加号等）时，你可以这样做：使用同一个字符作为该标识符的结束符号。

一种常见的表示终结符的方法是通过包含特定的字符在C字符串常量中进行标识或标记. 查阅相关资料可获得更多信息.

在Bison中有对应的表示方式。例如，在C语言中有一个返回语句的例子。如下面所示，在括弧内的分隔符被视为一个字符符号。括弧内未包含的分隔符和标点符号将被用作每条规则的标点符号。

||

获取这方面更多信息,参阅 语法规则的语法-Syntax of Grammar Rules.

1.3 语义值-Semantic Values

规范文法仅通过类别来选择标记符号：例如，在一个规则中提到终结符`integer constant'时，则表示任何一个整数常量在该位置都会被视为合法。具体数值大小与解析过程无关（这一点对LL(1)解析器来说并不重要）：若表达式‘x + 4’是合法的，则‘x + 1’或‘x + 3989’同样会被接受。

然而，在分析输入时，其准确数值至关重要。通过准确数值可以洞察输入的意义。显然，在编译器无法辨别程序中的4、1和3989等常量的情况下，则该编译器毫无价值！因此说，在Bison语法中的每一个符号不仅包含一种符号类别还拥有_语义信息(semantic information)。了解更多这方面的情况，请参阅《定义语言的语义》

符号的类型是在语法中定义的标识符,例如INTEGER,IDENTIFIRE或者','. 它说明可能有效出现的位置以及如何将它与其他记号组合的信息. 语法规则仅能识别符号所属的类别,并不具备其他相关信息.

语义值涵盖了所有符号所包含的额外信息。例如数值型数据以及变量名等术语都是语义值的一部分。（值得注意的是像这样的符号只是一个标点符号本身，并不携带任何意义。）

例如，在被分类为\texttt{INTEGER}类型的符号中包含了数值4；另一个也被归类到\texttt{INTEGER}类别中的符号具有数值3989。一旦语法规则确定\texttt{INTEGER}作为合法类型时，则允许多个这样的符号被视为可接受；这是因为它们都属于同一个类别。一旦解析器接收了一个符号后，则会追踪其相应的语义值。

任何语法组及其非终结符都具有预设的语义值。比如，在计算器系统中，当处理一个表达式时，其语义值是一个数值；而在程序语言编译器中，则可能是一个树状结构来表示其意义。

1.4 语义动作

为了更具实用性，
不仅需要对输入进行分析还需要执行其他功能。
程序应具备从输入中提取信息并生成相应结果的能力。
在Bison语法体系中，
每个文法规则可包含一组多条C语言指令构成的动作块。
每当解析器识别到一条文法规则匹配时，
相应的操作会被触发。
如需进一步了解，
请参考‘动作-Actions’部分。

通常情况下,动作旨在从子结构中推导出整个结构的语义值。举例来说，在现有规则下,如果一个表达式由两个子表达式相加组成，则当分析器识别出一个加法运算符后，则每个子表达式的都会有相应的语义信息描述其构建方式。该操作的目的即在于为新识别的大规模或复杂表达式提供类似的语义构建依据。

例如,这里的一个规则表明一个表达式可由两个表达式相加而成.

||

这个动作表明了如何从子表达式的语义值产生加法和表达式的语义值.

1.5 编写GLR分析器-Writing GLR Parsers

在某些文法体系中,Bison遵循的标准LALR(1)分析算法,无法为给定输入确定一个明确适用的语言规则.这意味着,Bison可能无法在当前输入基础上做出决定,究竟是选择使用两个可能的缩减选项中的哪一个,还是先读取部分输入后再进行缩减.这两种情况分别被称为 缩减/缩减(reduce/reduce) 突触(参阅缩减/缩减-Reduce/Reduce一节)和 移进/缩减(shift/reduce) 突触(参阅移进/缩减-Shift/Reduce一节).

当试图将一个难以构建成LALR(1)文法的结构用于Bison解析器时,Bison不得不依赖通用分析算法. 在你的源代码中添加声明%glr-parser（参阅语法大纲中的相关内容）会使Bison生成通用LR(GLR)分析器. 这些生成的分析器（例如,在应用特定声明后）在处理那些无未解决冲突的情况下, 会采用与基于LL(1)方法构建的LALR(1)解析器相同的处理机制. 然而,当遇到未解决的移进/归约冲突以及归约/归约冲突的情况时, GLR解析器会巧妙地复制自身以便跟踪这两种可能性. 每次复制出来的分析器还可以进一步复制, 从而保证在任何给定时刻都能处理任意数量的可能性. 分析过程是逐步进行的：所有分析器在进入下一个输入符号之前都会消耗当前输入符号. 每个被复制出来的分析器最终只会导向两种结局之一：如果它因解析错误而终止, 它将与其他终止于相同符号集的状态合并.

每当多个解析程序共存时,Bison只会记录它们引发的行为而不主动执行这些行为.
一旦某个解析程序退出系统,其相关的语义操作将被删除并永久失效.
如果某个规范使两个解析程序等价并合并为一,则Bison会记录这两者的联合行为.
每当最后两个独立解析程序整合成一个统一的整体时,Bison将处理尚未完成的任务.
这些操作既可能按照常规语法优先级自动处理也可能由Bison自行管理.
在处理完所有操作后,Bison会调用预先设定好的评估函数来生成最终的结果.

1.5.1 使用GLR分析器分析非歧义文法

对于那些无二义性但不属于LALR（1）类的文法，在最简单的分析场景下，你可以直接运用GLR算法来进行处理。通常情况下，这类文法则需要至少两个超 lookahead符号或（罕见情况下）因LALR方法过于简略而无法归类于LALR（1），然而它们确实属于LR（1），有关冲突的情况可参阅相关资料。

探讨一个问题涉及Pascal语言中的枚举和子界类型声明之间的关系, 具体实例包括：

||

最初的编程语言规范明确规定了仅限于数字与常量标识符构成子界（如lo'和hi'）。然而，在扩展版本的Pascal（ISO/IEC10206）及其许多实现中仍可找到独立使用的表达式。这也带来了下面包含过多括号的一个情况。

||

考虑如下这个仅含一个值的枚举类型的声明.

||

(在这里人工构造的一些例子虽然显得不够自然,但它们在语法上仍然是完整的. 在实际编程中可能会遇到更加复杂的情况)

这两个例子在结构上一致直至..符号的出现。对于仅包含一个lookahead scan token的标准LALR(1)解析而言，在解析符号a时（注：指语法上的），编译器无法立即确定是哪一种情况（注：指枚举或子界类型）中的正确答案。因为，在第二种情况下符号a必须被重新定义为一个新的标识符以表示枚举类型；而在第一种情况下，则需要利用符号s a 及其意义来推断其可能代表常量或函数调用。因此我们期望编译器能够做出相应的选择。

你可将其解读为在括号中作为说明的标识符以供后续分析使用. 但若该括号嵌入到表达式的递归定义中时, 则这种标记方式将引起对语义操作和大部分语法规则的相应调整.

或许你会考虑利用词法分析器返回已知和未知标识符的方式来进行区分。然而，在这种情况下需要注意以下几点：当这些声明位于局部范围时，即使变量名a'在外部已经定义过，在这种情况下也会有两种可能性：一种是当前环境中变量名a'被重新声明（即局部重命名），另一种则是继续引用外部存在的变量名a'. 因此这种方法并不适用

为了解决这一问题,我们可以采用一种较为简单的方法——GLR算法。当GLR解析器进入关键区域时,它会同时向两个方向进行分析。其中一个分支最终将陷入解析错误。如果在一个‘;’之前的‘..’记号存在；由于枚举类型不允许出现‘..’符号,因此该方法行不通；否则,子界类型的规则也会失效；因为这种类型不允许出现‘..’符号。因此，在这种情况下只有一个分支能够正常工作，并且处理所有在分割阶段被延迟处理的操作。

如果输入不符合语法规范，则这两个分支的分析均会失败，并且通常会报告一个语法错误。

分析器的作用似乎是推测正确的语法路径。换句话说, 它采用了比LALR(1)算法所允许的更为丰富的超前扫描符号。尽管如此,LALR(2)仍能有效解析此句。然而，在某些情况下（如当任意数量的_k_被引入时）会出现不一致现象。

通常情况下,一个基于GLR的解析器在最坏情况下将会经历平方或立方的时间复杂度, 即使当前版本的Bison也会因某些特定文法而耗费指数时间. 在实际应用场景中,这些极端情况极少出现, 而且对于多数文法而言, 证明其不可能发生也是可行的. 当前所讨论的例子仅涉及两个规则之间的单个冲突关系, 并且含有冲突类型的声明不允许嵌套使用. 因此在此时阶段的分支数量受到常数2的限制, 分析过程仍能维持线性时间复杂度.

这相当于上述所述的一个实例。它源自于Pascal声明语言的大幅简化。如果输入不符合语法规范,两个分支将会常规地输出相应的语法错误信息。

||

每当采用常规的LALR(1)文法时,Bison会在遇到情况时报告一个归约型冲突. 在这种情况下,分析器会面对多个选项,最终选择其中一个——通常会选择最先声明的那个. 因此,那些正确的输入将无法被解析.

||

在Bison输入文件中加入这两个声明（位于第一个%%之前），可以使解析器生成一个GLR解析器，并无需报告归约/归约冲突。

||

无需对语法结构进行任何修改. 分析器借助上述语法规则处理后,能够识别所有的合法声明. 用户几乎察觉不到分析器所执行的语义分割过程. 该机制确保了系统在识别声明时不会遗漏任何合法情况

这表明我们采用GLR方案几乎不会带来负面效果。
即便像这样的简单案例,我们也必须关注至少两个潜在问题。
首先,我们必须仔细分析Bison的冲突报告,以确定GLR拆分何时发生是我们预期的时间段。
其次,LALR解析器在冲突处理时会更直观地做出错误选择,而使用GLR可能会导致更为隐蔽的问题。
某些与词法解析相关的操作可能被用来消除基于GLR方法从词法到语法阶段的时间复杂度问题。
由于在拆分过程中被处理的记号并未引发任何操作行为,因此词法解析器无法通过观察这些行为来获取相关信息。
另外值得注意的是,
因为 在进行拆分的过程中所消耗的一些标记并没有触发任何动作,
所以 语义解析模块无法通过观察这些动作来推断出相应的状态信息.
这就要求我们在设计基于动态规划机制的方法时,
必须确保剩余情况下的正确性。

在这个案例中,由于中间没有引入新的符号到类型声明中,因此词法解析器按照当前符号表中的意义返回记号的方式被认为是安全的.然而,即使当我们尝试为枚举常量在其相同类型的声明中定义它们时,这也是不可能的.因此在这种情况下并不存在实质性的区别.

1.5.2 使用GLR解决歧义-Using GLR to Resolve Ambiguities

让我们考虑由C++语法大大简化而来的例子.

||

这个例子模拟了有问题的C++语法--某些声明和语句中的歧义.例如,

||

既可以被视为一个expr也可以被视为一个stmt（假设T'被识别为一种TYPENAME并且x'被识别为一种ID）。生物传感器检测到了在规则expr: ID与规则derator: ID之间出现的归约/归约冲突。当解析器遇到标识符x时仍无法解决该冲突。由于这种GLR解析器的工作机制 distinctive, 它会将问题分解为两个独立的解析器来分别处理两种不同的归约冲突情况。与上一节的例子不同（参见《简单的GLR解析器》一章），这两个子解析器并不会因无法独自解决问题而终止运行；相反地, 由于原始语法存在歧义性特征, 这两种不同的解决方案最终都会收敛到同一个语法结构上. 最终其中一个子解析器将完成到stmt: expr ';', 而另一个则完成到stmt: derator. 在此之后, 两个子解析器进入了相同的语法状态：它们都已观察到当前的程序行并具有相同的未处理输入缓冲区. 我们称这两种不同的子解析路径最终实现了状态的合并。

GLR解析器在此时被要求提供有关如何在两个竞争解析器间进行选择的一个指南。上述案例中, 两个%dprec声明揭示了Bin Son给予decl以优先级的方式进行解释。从而可以看出x是一个声明符. 由此可见, 分析器将输出:

||

%deprc声明仅在多于一个分析幸存的情况下起作用. 考虑这个分析器的一个不同的输入字符串:

||

如图所示（参考简单的GLR分析器-Simple GLR Parsers一章），这是一个利用GLR方法解析非歧义结构的例子。在此情况下并无歧义（该不能被视为一个声明）。然而，在Bison解析器处理字符'x'时却面临归约/归约冲突问题（即无法确定'x'究竟是一个表达式还是一个声明符）。在这种情况下缺乏必要的优先级信息。为此解析器被分解为两部分：一部分假设'x'是一个表达式；另一部分则假设其为声明符。其中第二个解析体在遇到运算符加号时会被终止；并在此处打印出相关信息

||

假设你想探索所有可能性而非寻求解决方案. 你不得不整合两个分析器的作用域而非单独处理其中之一. 为了实现这一目标,你需要按照如下方法修改stmt的声明:

||

并且定义stmtMerge函数如下:

||

并且在文件的开头要伴随一个前置声明在C声明中:

||

借助这些声明后,该分析器将第一个示例既解析为一个expr又解析为一个decl, 同时输出相关信息。

||

Bison强制规定所有参与特定合并操作的产品(productions)必须遵循相同的`%merge'规则. 如果这些条件未能得到满足，则会导致无法消除语法歧义，并使系统在任何违反该规定的合并情况中发出警告信息.

在编译GLR解析器的过程中需关注的关键点-Potential considerations for compiling GLR parsers

GLR解析器必须支持基于ANSI C89或更高版本的标准编译器。此外,Bison采用关键字inline这一机制,尽管这一功能并不是ANSI C89标准所定义,但却被ANSI C++技术委员会(C++TC)认可为后续版本所采纳的功能之一,并为许多先前版本的编译器提供了额外的支持。这一机制旨在帮助开发者处理跨平台开发中的移植性挑战。例如，在配置系统时使用Autoconf和相关的宏定义如AC_C_INLINE时,能够实现对单文件包含的支持。

||

就足够用了,否则我们建议使用

||

1.6 位置-Locations

在现代编程环境中,诸如解释器与编译器等程序在运行过程中需要生成正确的提示信息或错误报告. 以实现这一目标为基础,我们必须记录每个语法构造的真实位置及其相应的上下文环境. 比如说,Bison则提供了一套机制来记录这些关键点及其上下文.

每个符号都有一个对应的语义值；每个符号都有一个特定的位置；对于所有的符号和组别来说它们的位置类型是一致的此外在输出结果中，默认配置了一个用于存储位置信息的数据结构（如需进一步了解请参阅《位置-Locations》章节）

如同语义值那样,位置可以在动作中遵循一套特定的访问机制来获取. 在上述例子中,该组的位置定位是 @, while 子表达式的定位是 @1 和 @3.

一旦某个规则被触发（参考动作-Actions章节），则会执行相应的操作。类似地，在计算位置时也会执行另一个默认的动作。然而，默认的动作通常已经足够普遍，并不需要为每个规则详细说明@是如何生成。每当创建一个新的位置时，默认的行为是获取该位置的第一个字符开始和最后一个字符结束的位置。

1.7 Bison的输出:分析器文件-Bison Output: the Parser File

当你使用Bison运行时,你需要为此提供其作为输入的一个语法文件. BISON处理该语法文件生成的结果将是一个用于描述该语言的C源代码文件. 此文档将其命名为_Bison解析器（BISON解析）_. 我们必须认识到这两个程序之间存在明显的区别: 使用_BISON解析器_作为基础构建其功能。此_BISON解析器_将作为你整个系统的组成部分而存在。

Bison分析器的工作是遵循语法规则去构建符号——如将标识符与操作符结合起来形成表达式。在构建表达式的过程中它还需要按照语法规则进行相应的操作。

称该程序为_词法解析器_更为合适。为实现此功能，需以特定语言（如C）实现该解析器。每当Bison解析器需识别新的符号时，会调用相应的解析函数。Bison解析器并未深入探查符号的内容（即便其语义值可能揭示相关信息）。传统的字符解析方法通常用于生成相应的标记符号。获取更多细节，请参考 《词法解析函数》 yylex-The Lexical Analyzer Function yylex。

Bison解析器文件声明了一个名为yyparse并实现了所述文法的C函数。该函数无法独立构成一个完整有效的C程序；你需要补充其他辅助功能。其中之一是词法解析器模块；另一个则是错误处理相关的报告功能。此外；一个完整的C程序必须以带有名称为main的标准入口函数开头；你需要实现并调用该主程序；这样才能确保解析过程正常运转；建议参阅Bison C语言接口文档中的相关内容。

除了你在编写的动作中所定义的标记类型名称和符号之外，在Bison分析器文件中自行定义的所有符号均采用前缀'y y''或'y Y''的方式表示。这些标识符涵盖了诸如词法解析器中的yylex函数、错误处理中的yyerror函数以及解析模块中的yyparse函数等接口功能。此外，这些标记还包括了一些内部用途标识。因此，在编写Bison语法规则时，请务必避免引入除本手册外其他来源定义的新'y y''或'y Y''类型的C语言标识符。

在某些情况下,Bison解析器头文件会包含系统库. 在这种情况下,你的代码应特别关注被这些库保留的关键标识符. 在非GNU系统中,通常会包含像<alloca.h>、<stddef.h>以及<stdlib.h>这样的头文件,用于声明内存分配相关的函数类型. 如果程序采用了消息国际化功能,则必须包含<libintl.h>. 参考国际ization一章,如果你定义了YYDEBUG为非零值,其他可能涉及的系统头文件也可能被包含进来. (参阅跟踪你的解析器-Tracing Your Parser一章)

1.8 使用Bison的流程-Stages in Using Bison

遵循Bison设计语言的流程进行开发,其过程主要包含以下几个阶段：首先是从语法规范出发进行理论分析,然后是基于此实现对目标语言的正确解读。整个开发过程大致分为三个步骤:

1. 按照Bison可识别的标准格式详细阐述语法结构，并对每个语法规则的具体执行动作进行规范描述。这些动作通过C语言程序实现，并遵循《Bison语法文件》的相关指导原则。
2. 开发一个词法解析程序来接收输入并将其符号传递给语法解析模块。该程序既可以手动编写成C代码（参考《词法解析函数yylex》相关章节），也可以通过工具自动生成（如Lex），但本手册未涉及Lex的具体应用。
3. 制定并实现一个辅助函数序列，用于调用生成式文法解析系统的核心模块。
4. 确保系统能够捕获并报告所有潜在的解析异常情况，并将相关信息反馈至主程序以便后续处理。

将这些源代码转换成可执行程序,你需要按以下步骤进行.

遵循语法规范下生成Bison分析器。
按照与其它源代码相同的编译操作对Bison输出的代码进行处理。
连接目标文件夹以生成最终产品文件夹。

1.9 Bison语法文件的整体布局-The Overall Layout of a Bison Grammar

按照 ANSI CSI 标准配置参数值时，默认情况下会遵循 ANSI CSI 标准配置参数值的标准设置方式进行处理。
该默认设置的具体内容如需进一步了解，请参考 $CSI-? 命令的帮助信息。

||

    PrologueBison declarationsGrammar rulesEpilogue

%%',%{' 和`%}'是Bison在每个Bison语法文件中用于分隔部分的标点符号.

prologue可用于在动作中定义类型和变量。你可以通过预处理命令在其处定义宏，或者通过包含这些内容的头文件来实现。你需要在那些用于解析动作的全局标识符之前申明词法分析器yylex及其错误处理程序yyerror。

Bison定义了标识符和非标识符，并规定了运算符的优先顺序以及各类符号意义值的不同类别.

语法规则是如何确立每一个非终结符部分所对应的完整语法结构。

Epilogue部分通常会包含所需的代码片段。这些函数通常被定义在Prologue区域，并且它们会在尾随执行时被引用。对于较为简单的程序来说，在尾随部分执行所有后续操作是一个常见做法。

2. 实例-Examples

现在我们演示并说明三个基于Bison编译器编写的示例程序：逆波兰记号计算器、代数符号（中缀）计算器以及多功能计算器。这些程序已在BSD Unix 4.3系统上经过验证无误；每个虽然功能较为有限但仍具实用性作为交互式的桌面式计算器。

这些简单的例子尽管简单,而通过Bison语法构建真正程序设计语言的理论基础与此相似

2.1 逆波兰记号计算器-Reverse Polish Notation Calculator

我们的第一个例子是由双精度型 _Reverse Polish Notation (RPN)运算设备_完成的（该设备采用后缀运算符）。这个案例是一个理想的起始点,因为它省去了操作符优先级的复杂性. 下一个案例将展示如何处理这些优先级.

该计算器的源代码文件名为``rpcalc.y'`。.y'被称作Bison惯用的常用输入文件的扩展名。

2.1.1 rpclac的声明部分-Declarations for rpcalc

这是基于逆波兰记号的计算器代码编写方法。如同C语言那样，在/*…*/块内放置注释内容。

||

声明段落（参见Prologue中的相关内容）涵盖了两项预设指令以及两项前言说明。

该规则说明YYSTYPE是宏，并指出符号名及其所属类别（参阅语义值的数据类型-Data Types of Semantic Values一章）。此宏指出符号名及其所属类别所对应的C数据类型的语义值。Bison解析器采用由该规则指定的所有数据类型的属性; 若无明确指定，默认采用int类型。因为我们在本节中明确设定了double作为双精度浮点数..., 所以每个符号都被赋予了一个相应的数值。

#include用来声明幂函数pow.

因为C语言规定函数应在被调用前进行声明, 所以前置声明yylex和yyerror是必不可少的. 这些关键函数将在epilogue部分进行定义, 然而，在分析器调用这些函数时，则需要提前将它们在prologue部分进行 declaration.

在第二部分中讨论了标记类型的相关信息（参见《Bison Declarations》一章）。除了单字符符号外的所有终结符都需要在此处进行定义（单字符符号通常无需在此处定义）。在这个示例中所有算术运算符均为单字符形式因此我们只需为数字常量定义标记类型即可。

2.1.2 rpcalc的语法规则-Grammar Rules for rpcalc

这就是逆波兰记号计算器的语法规则:

||

在定义此语言组时: 表达式命名为exp, 输入行命名为line, 全部输入脚本命名为input. 这些非终结符均设有多个可选规则, 这些规则由'|'符号分隔开来. 我们将符号'|'读作"或者"; 后续部分阐述了各条规则的意义.

语法的语义在当组被识别时由相应的动作来实现。每个动作都包含位于大括号内的C代码内容。请参见《动作-Actions》章节。

为了指定这些动作,C语言被选用。然而,Bison还提供了一种方法，在规则之间传递语义信息。在每个操作中,伪变量代表了即将构建组的语义信息。赋值给伪变量是大多数操作的核心任务。规则组成部分中的语义信息通常由1,2等标识符表示

2.1.2.1 解释input-Explanation of input

考虑input的定义:

||

这个定义也可以被视为："一个完整的输入或许是一个空字符串, 或许是一个完整输入后紧跟一个输入行". 我们应该注意到"完整输入"在其特定条款中被重新定义. 其中，在符号序列的最左边出现的位置是用于标识符的位置. 这种情况下,我们称这种定义为 左递归(left recursive). （参阅 递归规则-Recursive Rule.)

第一个可选择的规则为空是由于在冒号和第一个|'之间没有任何符号; 这意味着input可以匹配一个空字符串的输入(没有符号). 我们这样编写规则是因为在你启动计算器后,在右端输入Ctrl-d是合法的. 把空规则放在最开始并伴随注释/* empty */'是使用惯例.

第二个可选规则(input line)执行了所有非平凡情况. 其功能是'在读取任意个数的line后,如果可能的话读取更多的line'. 通过递归实现该规则以达到循环效果. 因为第一个可选规则在遇到空输入时会触发匹配,所以循环可能运行零次到多次.

分析器函数yyparse从接收到的第一个输入符号开始持续解析直至遇到语法错误或确定不存在后续的输入符号; 我们会在检测到无更多输入时自动执行该操作.

2.1.2.2 解释line-Explanation of line

现在我们考虑line的定义:

||

第一个选项为回车符; 它表示rpcalc会处理后会忽略空行（因无相关操作）。第二个选项是在表达式后紧跟回车符; 此选项使rpcalc功能更为实用。变量$1代表exp组的语义值; 由于exp为所有选项中的首字符符号; 因此其值即为所需的计算结果。相关操作输出该结果。

这一操作独一无二,因为它没有将变量$$赋值. 其后果是与关联变量line相关的语义初态处于不确定状态(其初始状态不可预知). 而未使用该变量的情况下,不会引入潜在风险. rpcalc在处理完用户的输入行数据后即终止对该数值的处理.

2.1.2.3 解释expr-Explanation of expr

exp组包含多种规则,每个规则都对应一种特定的表达形式. 其中,第一个规则专注于最基础的表达式,这些表达式仅由数字构成. 第二个规则处理的是形如两个子表达式连接使用逻辑或符号的加法运算. 第三个则涉及减法运算等相关内容.

||

我们已经使用|'将exp`的规则连接起来. 但是我们也可以将它们分开来写:

||

许多规则都涉及从其组成部分中计算出表达式的具体数值这一过程. 比如，在加法法则中,1标识第一个组件exp,2标识第二个组件. 如果第三个操作符如果没有意义，则无法用3表示其意义. 如果有的话,可以用3$$来表示其意义. 当程序解析器应用此法则识别一个由两个自定义数值构成的算术运算时, 它会将这两个数值相加以确定整个运算的结果. 参阅动作-Actions部分

无需对每个条文都明确指定操作。若某条文无操作定义，则编译器会自动将变量1赋值给引用变量$。这种情况发生在第一条条文被(NUM形式的条文)识别的时候。

在这里展示的是推荐的惯用格式, 但是Bison并没有要求一定要这么做. 你可以增加或者更改任意你想要的数量的空白. 例如,这个:

||

与这个的意义相同

||

然而,后一种写法明显更可读.

2.1.3 rpcalc的词法分析器-The rpcalc Lexical Analyzer

词法分析器的职责是负责处理初级阶段的字符或字符序列，并将其转换为符号。Bison解析器通过调用词法解析器来识别相应的符号。参考相关文献：关于此函数的详细信息，请参阅《Lexical Analyzer Function》一节中的描述。

即使是最低级的词法分析器也必须具备RPN计算器所需的基础。该词法分析器省去了空格与制表符，并将所有数字解析为双精度数值，并以NUM标记的形式返回。非数字字符被视为分隔符。特别地，在这种情况下，单个字符本身就是其对应的标记。

词法解析器返回的结果对应于标记类型的数值代码。
相同的文字（在Biosn规则中被定义为该标记类型）同样可以表示该类型的数值代码。
它采用两种不同的方式运作。
当标记类型为单个字符时，其数值代码即为此字符；
在词法解析器中可以利用相同的字符来表示该数值代码。
当标记类型为标识符时，则该标识符被Bison定义为适当的数值，并因此在此情境下’NUM’成为’yylex’所使用的名称。

标识符如果有意义值，则该意义值会被包含于全局变量yylval中。Bison解析器会在需要时获取其意义值。（其中，yylval是一个C数据类型为YYSTYPE的数据体，在语法表的起始位置被定义；参考 rpcalc 的声明部分-Declarations for rpcals 一章）

当输入完成时, 符号类型码0会被系统输出. (Bison会将任何无效的值视为输入完成的状态)

这就是词法分析器的代码:

||

2.1.4 控制函数-The Controlling Function

为了使这一实例保持其巧妙性, 控制函数得以维持最小规模. 它仅需通过调用yyparse来进行初步解析.

||

2.1.5 错误报告的规则-The Error Reporting Routine

每当程序解析器yyparse检测到语法错误时, 它会通过触发函数yyerror来输出一个错误提示(通常不是总显示为'syntax error'). yyparse依赖于程序员来实现函数yyerror(参阅分析器C语言接口-Parser C-Language Interface一章). 因此我们采用如下定义:

||

一旦yyerror返回成功（参见《错误恢复》一章），如果语法遵循了适当的一套错误规则，则Bison解析器能够在出现语法错误时进行修复并继续解析。否则，在这种情况下（如未遵循正确规则），Bison会将syparse返回一个非零值。在这个示例中，默认情况下并未为Bison配置任何特殊的语法修复机制；因此，在遇到所有无效输入时都会导致计算器停止运行。这种默认行为对于普通的计算器来说显然是不够智能的解决方案；然而，在当前的情况下它已经足够。

2.1.6 运行Bison来产生分析器-Running Bison to Make the Parser

（参见《Bison语法文件布局——The Overall Layout of a Bison Grammar》一章）。在编译器构建过程中,我们需要确定如何将源代码分配到一个或多个源文件进行组织与管理。对于这种相对简单的案例而言,最直接的方式是将所有内容集中在一个文件中。yylex, yyerror以及main函数应放置在程序的尾部epilogue区域。

在大型项目中，通常会涉及成百上千份源代码文件。这时建议采用Make工具来进行编译管理。

由于所有代码都集中在一个单一的源文件中, 你将通过执行以下指令将其转换为相应的Analyzer源代码文件:

||

    file_name

在这一实例中，在这个例子中,该文件是rpcalc.y'`(即 "Reverse Polish CALCulator").Bison生成名为file_name.tab.c'的一个文件，并将其``.y'扩展名移除。输入中的额外函数（如yylex、yyerror及main）逐字复制至输出文件。

2.1.7 编译分析器文件-Compiling the Parser File

这就是如何编译并运行分析器文件:

||

    ls`-lm'powcc -lm -o rpcalc rpcalc.tab.cls

文件rpcalc'现在包含着可执行代码。这展示了如何通过 rpcalc 实现对话的过程。

||

    rpcalc4 9 +3 7 + 3 4 5 *+-3 7 + 3 4 5 * + - n`n'5 6 / 4 n +3 4 ^^D

2.2 中缀符号计算器:calc-Infix Notation Calculator: calc

通过修改rpcalc程序，我们可以使其能够处理中缀操作符。中缀操作符的处理需要考虑运算符优先级规则，并且能够处理任意层次嵌套的括号结构。这里给出的是calc.y源代码的一个实现片段。

||

yylex,yyerror和main可以与上一个例子一样.

这段代码展示了两个重要的新特征.

在第二部分(Bison declarations)中，在%Bison语法糖定义域内%，使用%p_left来指定运算符类型并明确它们作为左结合操作符这一事实。同时，默认情况下会使用%p_left和%p_right（右结合）来替代%p_token来定义运算符符号；而%p_token则用于定义那些没有结合性的运算符符号这一行为则较为特殊——注释：这些符号（如'+','-','*','/','NEG'）原本无需显式声明即可表示为单字符运算符；然而，在%Bison语言环境中我们通过指定这些运算符的行为（例如是否左结合或右结合），从而明确其运算顺序这一过程较为复杂

该操作符的优先级由其所在的行次序决定。位于页面底部或屏幕低端的操作符拥有更高的优先级。因此，在此规则下，幂运算享有最高的优先权；负号（NEG）紧随其后；随后是乘法（*）和除法（/）等运算。参阅 操作符优先级-Operator Precedence。

另外一个显著的特点是在语法部分的符号运算符中采用了%prec. 这种运算符仅仅告知Bison规则中的| '-' exp'与NEG具有相同的优先级--在前述提到的优先级规则中. 参考文献依赖上下文的优先级-Context-Dependent Precedence.

这就是一个运行``calc.y'`的例子:

||

    calc4 + 4.5 - (34/(8*3+-3))-56 + 23 ^ 2

2.3 简单的错误恢复-Simple Error Recovery

在之前的章节中未对错误恢复（error recovery）的内容进行说明--即分析器检测到错误后该如何继续分析问题。我们所需要做的主要任务是实现一个专门处理这种情形的函数。我们可以回顾以前的相关知识，在编译器处理错误的方式中，每当调用完yyerror函数后会返回相应的状态码。这意味着任何输入错误都会导致程序退出。现在我们就展示如何改进这一缺陷。

Bison语言内置了可用于嵌入于语法规则中的保留关键字error。在这一实例中,该关键字被指定为属于line的一个可选组成部分。

||

此规则允许在语法错误发生时执行简单的恢复操作。当输入一个无法求值的表达式时, 错误会被识别为line中的第三条规则, 并导致解析继续进行。(yyerror函数仍用于输出相关信息)。该语句yyerrok是编译器自动生成的一个宏, 其作用即是完成所有误差处理（可参见《误差处理》章节）。必须明确yyerror与yyerrok的区别, 并确认它们均无印刷问题。

这种机制专门用于处理语法错误. 此外还有其他形式的错误; 例如,除数为零会产生一个通常致命的异常信号(an exception signal). 真正的计算器必须处理这种信号并使用longjmp返回到main并继续分析输入行; 它(注:真正的计算器)也可以丢弃剩余的部分. 我们为了避免超出讨论范围而没有深入探讨这个问题.

2.4 带有位置追踪的计算器:ltcalc-Location Tracking Calculator: ltcalc

通过扩展该中缀符号计算器使其具备位置追踪功能的例子. 该特征可用于提升错误信息的呈现. 该例子作为一个简洁的整数计算器展示了这一特性. 用于实现位置功能的所有工作都将在词法分析器中执行。

2.4.1 ltcalc的Declarations-Declarations for ltcalc

位置追踪计算器的C语言及Bison工具的声明部分与MPS运算符优先级解析器的声明部分一致。

||

I notice that there is no specific notation for positions. It's unnecessary to define a data type for storing positions. We utilize Bison's default type (see the chapter on position data types). This data type comprises a structure with four integer fields: first_line, first_column, last_line and last_column.

2.4.2 ltcalc的语法规则-Grammar Rules for ltcalc

是否处理位置对于你的语言的语法明确没有影响。因此,这个语言的语法规则与前一个例子极为接近; 仅需稍作修改即可获得所需的变化.

为此处除数为零的情况和错误的表达式或子表达式的出现提供位置信息。

||

这段代码通过伪变量定位技术展示了如何利用伪变量@n对规则部件进行定位，并结合伪变量定位机制实现了对组元素在其语义动作中的精准控制。

无需对@进行赋值操作:输出分析器将自动执行该操作. 通常情况下,在每个动作执行之前,系统会对包含n个部分的规则进行处理,将@设置为从@1开始延伸至@n. 为此,我们可以重新定义此操作(参阅位置的默认动作-Default Action for Locations一章),以便针对某些特定的情况手动计算其范围.

2.4.3 ltcalc的词法分析器-The ltcalc Lexical Analyzer.

目前我们仍然基于Bison的默认设置来触发位置追踪功能。下一步我们将重构词法解析器，并以确保其与语法分析器的记号位置兼容（类似于它之前所做的工作）。

在最后,为了避免计算的位置出错,我们必须对每个输入字符进行计数.

||

词法分析器主要采用了与前一个实例相似的处理策略: 它先是跳过了空格和制表符,随后又成功地读取了一系列单字符标记符号. 在另一处,该词法分析器修改了包含标记位置信息的全局变量(其数据类型为YYLTYPE)并将其存储在yyloc字段中.

当下每当该函数释放出一个标识符与语义值相等时 分析器将为其获取相应的索引信息以及具体的位置信息 最特别需要注意的是 在初始化yyloc时要确保其正确性 这一点可以通过在编程过程中特别设置来实现 比如 在控制函数中 或者其他关键组件中进行相应的配置

||

请记住：计算位置并非属于语法范畴。每一个字符都需要被赋予一个位置更新机制，并且无论是在合法输入、注释区域还是字符串环境中进行操作时都应遵循此规则。

2.5 多功能计算器:mfcalc-Multi-Function Calculator: mfcalc

到目前为止,我们已经探讨了Bison的基础知识. 现在是我们转入处理一些复杂话题的时候. 上述提到的计算器仅限于支持五个基本运算符: +, -, *, /和^. 为我们的计算器添加诸如sin, cos等其他三角函数功能是一种明智的选择.

当新操作符仅由单一字符构成时，在中缀计算器中实现这些运算相对直接。通过词法分析器yylex识别并返回所有非数字字符作为标记符号后发现现有的语法结构已经能够处理这些新增的操作符。然而，在现有框架下仅依靠这些机制可能无法满足复杂需求的情况下我们考虑引入更具灵活性的内置函数集合。

||

    function_nameargument

为此目的,我们通过创建命名变量来实现计算器的记忆功能. 为了方便后续操作,我们将这些数值存储起来,并在后续步骤中使用. 这正是多用途计算器的一次会话过程的体现：

||

    mfcalcpi = 3.141592653589sin(pi)alpha = beta1 = 2.3alphaln(alpha)exp(ln(beta1))

注意到多重赋值和嵌套函数是允许使用的.

2.5.1 mfcalc的声明-Declarations for mfcalc

这就是多功能计算器的C和Bison声明部分:

||

上述的语法仅引入了Bison语言中的两个关键特性. 这些特性支持语义值拥有多种数据类型. （参阅《多种值类型》一章）

%联合体定义了所有可能类型的清单，并替代了YYSTYPE。
该联合体现在允许使用的类型包括双精度数（用于表示exp和NUM）以及指向符号表目录项的指针。
参阅值类型集-The Collection of Value Types。

考虑到当前支持的语义分类体系较为丰富, 对于每个使用场景中的语法符号来说, 明确其所属的语义类型是非常重要的. 这些符号包括NUM、VAR、FNCT以及exp. 它们在声明时已经指定好了相应的语义类型（通常位于中括号内）。

该命令用于标识非终止符的定义,类似于使用%token来指定符号类型的注释(其中, :%token表示标记类型的术语). 在之前的版本中,我们未显式声明:%type,因为通常情况下,非终止符在其规则定义中会隐式地进行声明. 然而:%exp必须被明确标识以便获取其语义值类型的信息. 参阅 非终止符-Nonterminal Symbols.

2.5.2 mfcalc的语法规则-Grammar Rules for mfcalc

这代表了多功能计算器所遵循的语言规范. 其中大部分规则源自于代码库中的基础模块. 新增了三个关键规则涉及变量(VAR)和函数(FNCT)定义.

||

2.5.3 mfcalc的符号表-The mfcalc Symbol Table

多功能计算器必须具备一个符号表用于追踪变量和符号的名称与意义。
这表明语法规则仅受动作影响，并未对Biosn声明产生任何变化。
然而这仅需求求实现一些额外的C函数支持。

符号表本质上是基于记录的链表结构构建的。其定义可在包含在源代码中的(calc.h)头文件中找到。该结构赋予了将函数或变量纳入符号表的能力。

||

在本次更新中所涉及时的功能模块中包含了对功能模块...的一个核心组件。其中包含了用于初始化符号表的关键逻辑。这就是功能模块main和辅助模块$init_table$的功能实现：

||

通过直接修改初始化列表并导入相关代码库, 你能够给计算器增加多种实用功能。

两种关键功能可执行搜索与定位操作于符号表中。$ putsym$ 函数将接受待定位对象的名字及其数据类型（变量名或函数名）。该对象将作为链表头节点加入，并通过一个指针最终得到其引用。$ getsym$ 函数则用于获取指定符号的名字。若查找到对应项，则会提供该符号对应的引用；若未找到，则返回零值。

||

yylex函数必须能够识别出变量、数值以及单字符运算符。当处理以非字母或数字开头的字符串时，该系统将判断其为变量还是函数，并取决于符号表对其的定义。

该字符串通过调用函数getsym来进行符号表的查询操作。当符号表中存在该名称时,yyparse将获得指向该名称所在位置的指针及其类型信息。若该名称当前不在符号表中,则它会被预先分配为一个变量节点，并通过调用函数putsym进行处理。类似地,yyparse将获得指向变量节点的指针及其对应的数据类型。

yylex中处理数字制和算术运算符的代码并不需要更改.

||

这个程序不仅高效而且具有良好的适应性.
你很容易地插入新的功能模块.
在预设的数值体系中包含如π或e这样的常量，并且操作非常便捷且无需额外配置.

2.6 练习-Exercises

1 在math.h文件中加入新的函数至起始表单
2 创建另一个包含所有const及其值的数据结构，并将其更新进init_table以使其出现在symbol table中 所有新增加的const都被明确分类为var类型的
3 让该程序在访问未初始化的所有variable时触发error reporting mechanism

3. Biosn的语法文件-Bison Grammar Files

Bison基于一种称为"上下文无关文法描述文件"的标准文件作为输入，并生成了一个完整的C语言函数来实现对实时修改功能的支持.

Bison语法输入文件通常以`.y'结尾.参阅 调用Bison-Invoking Bison.

3.1 Bison语法的提纲-Outline of a Bison Grammar

一个Bison文法文件包含四个核心部分, 如下所示, 由合适的分隔符分隔。

||

    PrologueBison declarationsGrammar rulesEpilogue

注释嵌入于/* … */'内部，并可在任何位置出现。此外，在这一行之前结束前会有一个由//`引入的注释作为 GNU 扩展的一部分存在。

3.1.1 Prologue部分-The prologue

Prologue部分包含了宏定义以及用于语法规则操作中的函数与变量声明。这些会被复制到解析器文件的开头，并且会在'yyparse'之前进行定义。你可以通过'#include'指令来引用头文件中的声明。如果不需要任何C类型的声明，则可省略这部分括号分隔符%'%'。

允许将多个Prologue部分与Bison声明混合使用，并支持它们之间的相互引用关系。比如，在包含头文件时（如.cpatch），你可以利用现有的数据类型进行操作，并且希望将带有特定参数类型的函数作为引用对象进行处理。具体而言，在构建这样的机制时，请注意以下几点：第一点是需要确保所有的语义关系都能正确解析；第二点是在编写代码时要特别注意前后文环境的一致性；第三点是可以通过设置两个独立的Prologue块来实现这一点：第一个放置在'%union'之前的位置上。

||

    tree`ptypes.h'tree`ptypes.h'

3.1.2 Bison Declarations部分-The Bison Declarations Section

Bison declations中的内容涵盖了对终结符及其优先级等的明确声明。对于相对简单的语法结构而言,通常无需做出任何声明。参考Bison Declarations部分（即-Bison Declarations）。

3.1.3 语法规则部分-The Grammar Rules Section

该部分涉及一至几个Bison语法规则. 请参考关于...的Syntax部分.

必须存在一个符合规范的语法规则,特别强调这一点是因为它位于文档的起始位置.其在文件中的位置必须占据首位,并且第一个`%%'(先于语法规则的那个)绝对不能省略,以确保整个文档结构的一致性和完整性.

3.1.4 Epilogue部分-The epilogue

类似于将Prologue内容复制至开头的做法，在此我们也将Epilogue内容逐字复制至解析器文件尾部。如果你希望放置代码而不受使用前声明的影响，则最佳位置是将它们放置在此处——尤其是在你的分析器文件尾部附近时会发现这一点非常有用。例如，在这种情况下（即当你希望避免在解析器中提前声明某些功能时），将这些代码项放置在此处会带来便利。通常来说，在Prologue中声明这些函数是必要的；即便已经在Epilogue中进行了定义。参阅 分析器C语言接口-Parser C-Language Interface.

如果最后一部分为空,你可以省略分隔它的分隔符`%%'.

Bison分析器自身包含了大量以yy'和YY'开头的宏与标识符定义。因此，在Epilogue部分尽量避免采用这类名称（除非涉及文档讨论以外的内容）是一个明智的选择。

3.2 符号,终结符和非终结符-Symbols, Terminal and Nonterminal

Bison语法中的 符号(Symbols) 代表着语言的语法类型.

一个 终结符（terminal symbol）也被称作_符号类型_（token type），它表示一类从构造上等价的标记。当我们在语法中使用符号时就意味着允许使用这种类型的标记。Bison解析器将这些符号转换为数字编码。通过调用yylex函数返回一种表示当前读入符号类型的标记类型。无需关心那个编码的具体数值；只需关注其对应的标记即可。

一个 非终结符(noterminal symbol)被定义为一类从构造上等价的组. 符号名称用作书写语法规则的语言工具. 通常情况下,所有这些非终结符应当采用小写字母的形式.

符号名称包括字母、数字（除首位外）、下划线以及句点。仅限于非终结符中的存在才有意义的只有句点。

在语法中书写终结符有三种方法:

• 一个 命名符号类型(named token type) 用类似C语言的标识符书写. 按照惯例,它们应该是大写字母. 每一个这种名称必须由一个Bison声明%token定义. 参阅 符号类型的名称-Token Type Names.
• 一个 字符记号类型(character token type(或者 文字字符记号(literal character token) 用如同C语言字符常量相同的语法书写; 例如,'+'是一个字符记号类型. 除非你要指明字符记号类型的语义值类型(参阅语义值的数据类型-Data Types of Semantic Values一章), 结合性或优先级(参阅操作符优先级-Operator Precedence一章), 否则没有必要声明它们.

依照传统规范,单一字符符号类别专指代表特定单一字符的那个符号. 因此,符号类型的‘+’被用来将‘+’作为一个符号来对待. 需要指出的是:无需严格遵守该传统规范,若你违背这一通用准则,你的程序可能会让其他读者难以理解.

在Bison环境中支持所有常用C语言字符转义序列的应用。需要注意的是，在这种情况下你无法将一个空字符单独视为一个合法字符文字——因为其对应的数值为零（0），这意味着输入已达到终点。（参考关于yylex调用惯例的相关章节.）此外，请注意与标准C中的三字符转义（trigraphs），即以'??'开头并具有九种特殊含义的方式不同，在Bison环境中这些特殊含义被移除了，并且反斜杠加换行的操作也不被允许。

一种_C-string literal token_采用与C语言中字符串常量相似的书写方式；例如，在程序中使用如"<="这样的符号即可表示_C-string literal token_。除非你在代码中明确指定该_C-string literal token_的数据意义、结合性和运算顺序（可参考《值类型-Value Type》章节以及《优先级-Precedence》章节），否则无需对其进行声明。

通过引用文档中的符号声明部分（参考Token Definitions一章），我们可以指定字符串标记为特定名称以实现别名效果。（参考Calling Convention章节）如果不进行这样的操作，则词法解析器需从YYT_NAME表中查找相应的字符串标记代码以完成解析任务.

警告 : 文字串记号在Yacc中不能工作.

遵循通常的习惯,单个字符序列被用来标识由一组特定字符组成的序列. 因此,建议在代码中使用字符序列'<='来标识字符序列 '<='. 尽管Bison并未强制执行这种规范,但如果偏离传统做法，则可能导致程序读者产生困惑. 因此，在编写代码时，请严格遵守这一规范.

在Bison环境中支持所有的常用C语言控制字符编码序列。然而，在Bison中您无法将空格视为单独的一个字符文字；这是因为空格对应的编码值为0，在此情况下表示输入已结束。（请参阅关于yylex调用惯例的知识部分。）并且，在标准C语言中使用的三字组合（trigraphs）（注释：指以??开头并有特定含义的标准字符串编码），但在Bison环境中这些三字组合并不具有特殊意义。此外，在某些情况下（如反斜杠加换行符），这种编码方式是不被允许使用的。请注意，在构造字符串标记时必须确保其包含至少两个以上的有效代码点；如果您的标记仅有一个代码点，则应直接采用单个字符表示。（如需进一步了解，请参阅以上相关说明。）

如何选择终结符的写法对它的语法意义没有影响？这种符号仅取决于它在规则中的位置以及分器何时触发返回该符号。

通常情况下，\YYLEX\()会返回终结符；但如果返回的是0或负值，则表示输入已结束。\n\n
在定义\YYLEX\()时，请采用与语法规则一致的方式书写相应的符号类型。\n\n
对于单字符符号类型而言，其数值码即对应于该字符的标准编码。\n\n
即使\char\()是带有符号位的数据类型，在将其传递给\YYLEX\()之前，请将其转换为无符号类型以防止主机上的扩展问题。\n\n
这样做的结果是，默认情况下\YYLEX\()仍能利用相同的数值生成所需的代码。\n\n
每个命名记号都会被编译为一个C宏，在分析器文件中，默认情况下请通过名称引用这些编码。\n\n
这也是为什么标点符号如句点通常不作为终结符的原因。\n

如果yylex是在另外一个文件中被定义的, 那么你需要确保符号类型的宏定义在该位置是可以被看见的. 在运行Bison时, 如果你希望它能够将这些宏定义保存到一个新的头文件``name.tab.h', 可以通过执行-d'选项来实现这一目标. 你可以将其整合到其他依赖它项目的代码中;参考关于调用Bison的信息.

为了编写能够移植至任意标准C宿主语法的系统,开发人员必须严格依赖于基本标准C字符集来选择非零类型的标记符号. 该集合由以下组成部分构成：其中包括10个数字、52个大小写字母以及一些在以下所述的C语言字符串中出现的特殊符号.

||

yylex函数和Bison必须采用统一的字符集合与编码方案进行字符符号的一致表示。举例说明，在一个ASCII环境下运行Bison系统时，在与其他非兼容如EBCDIC等环境联合编译并运行最终代码时可能会导致最终程序无法正常运行。这是因为Bison生成的结果表中对字符符号采用了ASCII数值进行处理的缘故。发布基于ASCII环境下生成的标准C源代码是软件发布者遵循的标准做法之一；因此，在与非ASCII兼容的操作系统上安装依赖于此的结果文件需预先对该文件进行专门处理以确保正确性。

符号\texttt{error}被标记为一个被保留用于错误恢复处理的特殊字符（参阅《错误恢复》一章）。特别指出，在此上下文中,yylex函数永远不会返回这个特殊值（注释说明）。除非在声明中标明该符号赋值为256,否则该符号默认取值也是256.

3.3 描述语法规则的语法-Syntax of Grammar Rules

一个Bison语法规则通常有如下的下形式:

||

    resultcomponents

属于该规则所定义的非终结符的是reault所在变量；而components 由该规则所定义的各种终结符和非终结符构成。（参阅符号-Symbols一章）

例如:

||

表明两组exp类型和一个+'记号在中间, 可以结合成一个更大的exp`类型组.

规则中的空白只用来分隔符号.你可以在你希望的地方添加额外的空白.

决定规则的语义的动作可以分散在部件中.一个动组看起来是这样:

||

    C statements

通常只有一个动作跟随着部件. 参阅 动作-Actions.

result的多种规则可以分别书写或者由垂直条`|'按如下的方法连接起来:

在这种方式下依然有我们之特考虑的特殊规则.

如果一个规则中的components字段为空，则表示result字段可以匹配空字符串。例如，则表示这是一个由逗号分隔的一组零个或多个exp字段：

||

我们通常对每个没有部件的规则加上一个`/* empty */'的注释.

3.4 递归规则-Recursive Rules

称作该规则为递归规则的情况下（如果其result非终结符出现在右手边）。
由于这种方法是唯一能够定义任意数字序列的独特方式，并且几乎所有基于Mellanox技术的编译器都依赖于这种机制。
考虑基于逗号分隔的一组表达式或其组合的递归定义。

||

在有手端环境中使用时, expseq1的最左符号引发一种称为 _左角recursions (left-corner recursions) 的情况. 另一方面,当在同一上下文中右侧被引用时, 这种情况被称为 _右角recursions (right-corner recurrences) 的情况.

||

任何序列都可以以递归或右递归的方式进行定义；然而，在大多数情况下推荐采用左递归来处理；这是因为其能够利用固定大小的栈结构来处理任何数量的元素序列；即便规则仅应用一次，在此之前所有元素都必须先被推入栈中；此外，右递归所使用的Bison栈空间与其处理的元素数量呈正相关；参阅《Bison分析器算法》- The Bison Parser Algorithm获得更深入的解释和相关信息。

在递归中使用非直接的相互作用关系时（即_I）或_J），其定义会基于其他非终结符_J_或_K_的情况。

例如:

||

定义了两个相互递归的非终结符,因为它们互相引用.

3.5 定义语言的语义-Defining Language Semantics

由语言的语法规则所决定的是语言的语法。
其语义值实际上是与多种记号及相关的语义值以及在识别各类别时所执行的动作所共同决定。

例如,正是因为对每个表达式建立了正确的数值联系,计算器才能准确运行. 由于组`x + y'的操作是将x与y的值进行相加处理, 因此计算器能够正确执行加法运算.

3.5.1 语义值的数据类型-Data Types of Semantic Values

对于一个基本的程序设计来说，在这种情况下对所有的语言结构的语义值采用统一的数据类型就能够充分表示。在这些典型的表达式处理案例中，在逆波兰记号计算器章节的例子证实了这一点。

Bison在默认情况下对所有的语义值采用整数类型. 如果需要指定其他类型的语义值,可以通过以下方式为$YYSTYPE$定义一个宏:

||

该类比性宏定义位于语法文件的引言部分。（参照《Bison语法大纲-Outline of a Bison Grammar》一书）

3.5.2 多种值类型-More Than One Value Type

在大多数程序设计中,通常会根据符号的不同类别选择相应的数据类型以实现高效存储与操作。例如,整数值型变量通常采用int或long\ int来存储数值信息; 字符型变量则常用内存地址引用的方式表示字符内容; 同时,标识符在编程语言内部映射到特定的位置时,其语义值由指向该位置的内存地址来决定。

为了在一个分析器中使用多种语义值类型, Bison要求你做两件事情:

• 使用Bison声明%union明确指定了所有可能的数据类型集合。（参考《值类型集》一章）
• 从这些数据集合中给每个符号（包括终止符和非终止符）分配相应的语义值集合. 可以通过标记符实现这一功能（参考《符号类型的名称》一章）；同时针对组别进行设置（参考《非终止符》一章）.

3.5.3 动作-Actions

当一个规则实例被识别时, 同该规则相关联并包含C代码的动作会被执行. 主要的动作是从记号的语义值或者更小组别别的语义值计算整个组别别的语义值.

此操作通常由一系列嵌入大括号中的C语句执行，其功能与单独的一个C语句相当。此操作可能同时处理大量并行执行的多个C指令。然而,Bison并不搜索三字符词(trigraphs)，所以如果代码中使用了trigraphs你需要确保它们不会干扰嵌套结构或其他注释内容。字符串或单个字符会被正确处理。

任何一个动作都可以放置在规则的任何地方，并在那里被执行。通常情况下,每个 规则只有一个位于其所有组成部分末端的动作.其中,在中间位置执行的动作则具有高超的技术性,并且专门用于完成特定目标（参考关于中间位置动作的章节）.

在动作中使用的C代码可以通过引用结构n来访问匹配规则组件对应的语义信息。其中n表示第n个组件对应的语义信息。构建中的组拥有语义信息为. 当这些信息被复制至分析器源代码时, Bison会将这些数据转换为相应的表达式类型。其中$$会被解析为一个可修改的目标变量。

这里是一个典型的例子:

||

该规则基于两个通过加号连接的小规模exp组件构成一个较大的exp。在这一操作过程中,1和3分别代表两个参与组合的exp组件所携带的意义。这些符号位于该规则右部的第一位和第三位，并被存储到变量中以供后续使用。其意义信息储存在变量中，并用于构成当前识别出的加法表达式的整体意义。如果+运算符拥有有意义的意义，则可通过变量$$中的内容进行引用。

值得注意的是，在这种情况下，垂直杠字符确实起着分隔符的作用，并且每个动作都会被单一的规则所继承。这正是与其他如Flex工具明显的区别所在。而在Flex工具中，则允许使用符号表示逻辑上的‘或’关系的同时也支持与后续规则共享相同的行为。例如，在示例代码段中所示的情况是：只有当字符 `b’ 被检测到时才会执行特定的动作。

||

当某条Bison规则未指定明确的动作时,Bison采用了默认动作：$$ = $1。由此可知，第一个符号的位置被赋值为整个规则的结果。然而，在数据类型不匹配的情况下，默认动作无法应用。当某条规则为空时，默认动作无从选择；只有在特定情况下（如该规则的结果不影响系统运行），才允许省略显式动作。

允许在变量n中使用非正数值。
此操作用于引用当前规则匹配前栈中的符号或组。
这种尝试具有高度风险性。
正确理解当前规则的应用环境是进行可靠操作的前提。
以下是一个可靠的方法应用实例：

||

仅当bar按照如上所示的方式被使用时, $0$始终引用在它之前定义的foo的定义中所包含的expr$.

3.5.4 动作中值的数据类型-Data Types of Values in Actions

如果你为语义值只选择了一种数据类型, 那么$$和$n结构总是那种类型.

当您已设置了%union指定过多种数据类型的场景下, 必须确保对于这些指定过的每一种可能拥有语义值的终结符或非终结符都明确声明其对应的数据显示类型. 随后，在每次运用````````或者$n``进行操作时, 其数据类型的确定基于所引用符号所属的数据类型的规则. 例如，在以下情形中:

||

1和3引用了exp类型的实例, 因此它们都声明了与非终结符exp相关的数据类型. 当采用$2时,该符号将拥有与终结符'+’相关联的数据类型,不论该符号具体代表什么.

此外，在您引用数值时，请在引号开始处添加$符号，并在其后紧跟<type>标识符来明确具体的数据类型。例如，在本节展示的例子中

||

那么你可以用$<itype>1$作整数引用规则的第一个子单元, 或者用$<dtype>1$作为双精度数值表示该值。

3.5.5 规则中的动作-Actions in Mid-Rule

有时将一个动作纳入到规则中会有很大作用。这些规则的表现形式类似于在它们之后执行的动作；然而它们是在分析器识别出相关部件之前的阶段被安排好的。

一个规则中的动作可以使用符号$n$指涉其前面的部分；然而无法指涉后续的部分，在此情况下。

该规则中的各项措施被视为其自身的一部分。与之相对的是另一项操作（通常位于句尾）：特别地，在应用序号n时，请确保将此操作及其相关符号一同纳入考量。

该规则所涉及的动作均具备语义属性。此操作可通过复制至特定位置的方式进行赋值，并将后续的动作可依此利用 $n 引用该数值。由于缺乏明确的标识符用于此操作符, 相关数值的数据类型无法在初始化阶段进行静态声明。每当访问该数值时，则需采用 `$<…>n' 格式指定其实体的数据类型。

无法在规定的行为序列内设置某个全局行为参数（注：参见上文）。唯一的方式是对全局行为参数进行设置的方法是通过执行常规操作位于该序列末端的位置。

该机制有一个源自假想编译器的例子。 该机制用于处理 let 语句。 该格式由以下两部分组成：一部分是 `let (variable) statement' 的结构；另一部分是在 statement 存存期间创建并命名为 variable 的临时变量。 为了分析这个结构，在 statement 被解析时，必须将 variable 插入符号表，并在稍后移除它。 这就是该规则的工作原理：

||

一旦识别出let (variable)这一语法结构，则首先会触发相应的处理流程。在数据类型联合体中提取上下文信息，并创建一个可复用的变量列表副本。随后将新变量通过调用特定函数加入该列表。在第一个操作完成后，则可以对嵌入的指令集进行进一步解析。注意此处的动作编号为5，则嵌入指令块的编号自然成为6。

在嵌入的语句stmt经过处理后,它的语义值被更新为整个let-语句所对应的值.(注:$$=$6;)随后,前一个动作所涉及的语义值(注$<context>5)用于存储先前定义的变量列表.(注:pop_context ($<context>5))这将临时地从该列表中移除该let-变量.这种处理方式旨在确保该变量不会出现在后续分析中.

为了使分词器能够正确处理中文分词问题，在尚未完成模式识别的情况下就立即触发分词操作可能会导致识别错误。

||

但是当我们向下面这样添加一个规则中的动作时,规则就失效了:

||

现在，在解析器尚未到达左括号时（即尚未完全解析左边内容），它被迫决定是否执行当前规则中的动作。
换句话说，在解析器缺乏足够信息做出正确选择的情况下，
它就会强制使用一个或其它可用的规则。（这种情况下，
由于解析器仍在尝试做出决策，
左大括号符号被称之为 look-ahead marker（超前标记）。
参阅 超前扫描记号-Look-Ahead Token.）
（注：此时两个规则的超前扫描标记均为{。

你可能认为给这两个规则放置相同的动作可以解决这个问题,就像这样:

||

但是这种方法显然不可行,因为它未能认识到这两个操作本质上是一样的. (因此,Bison绝不会尝试解析这些代码中的.ccode.)

当语法结构如下时：借助第一个符号（如同C语言中的做法）可以识别出一个声明。那么将此操作放置于左花括号内则成为一个切实可行的解决方案。例如：

||

现在的后续说明或指示的第一个符号（注：用于超前扫描标记）无论是在何种情况下都会被告知Bison应采用哪个规则。

另外一种解决方法是将动作放入一个做为子规则的非终结符.

||

当前情况下,Bison并未明确最终使用哪一个可执行指令,但明确指定了子例行务（subroutine）中的操作.请注意,目前所有中间操作均被整合到一个统一结尾处的操作中.使用这种方法,Bison能够将所有这些中间操作统一到一个尾部操作中,这是其处理这类操作的独特方法.

3.6 追踪位置-Tracking Locations

然而，在编写功能完善的分析器方面，在仅仅依靠语法规则和语义值已经足以完成任务的情况下，在某些情况下还需要进一步提升分析能力以处理更为复杂的信息来源。特别是在自然语言处理系统中发现的某些特定现象的处理上尤其需要注意这些细节信息的准确性，并且在识别这些特殊现象时也需要更加精确地定位它们在整个文本中的具体位置以确保系统的准确性与可靠性。

处理位置的方法由一个数据类型和规则被匹配时执行的动作定义的.

3.6.1 位置的数据类型-Data Type of Locations

因为所有的符号和组始终采用相同的数据类型，在定义位置数据类型时相较于定义语义值更为便捷。

类型的属性由宏常量YYLTYPE进行指定. 在未预先定义的情况下, Bison则采用具有四个字段的标准结构作为默认配置.

||

3.6.2 动作和位置-Actions and Locations

行为不仅作为定义语言语义的原因, 而且可以依靠位置描述输出的分析器的行为来实现.

在语法结构中，确定位置的方式与计算语义值的方式具有相似之处。在一个给定的框架中, 多个途径可以用于访问被匹配元素的位置。相反地，在右侧的第n个部分位于位置...处, 而在左侧的分组则位于...处。

这是一个基本的使用位置的默认数据类型的例子:

||

类似于处理语义值的方式,存在一个每当规则匹配发生时指定操作的目标位置点. 该操作将@\ 的起始位置定位在起始符号之前,并将其结束位置定位在终止符号之后.

可以通过借助这一预设的动作设定，在执行自动化的定位追踪流程中起关键作用来实现位置追踪的全自动. 例如：以下是如何对这一示例进行优化的具体步骤:

||

3.6.3 位置的默认动作-Default Action for Locations

值得注意的是, 计算位置并非最佳选择. 由于位置更为通用, 在解析器中设置了默认动作（针对位置）的空间. YYLLOC_DEFAULT 宏会在任何规则匹配且尚未执行相关动作时被激活. 当处理语法错误并需计算错误定位时, 此宏也会介入.

大多数时候, 这个宏足以胜过语义动作中专注于位置的代码.

该宏具有三个可配置的参数。其中第一个指定计算结果所在的组位置，在匹配特定规则时其第二个参数指示所有右端元素在该规则中的位置；第三个则表示这些元素所占据的空间大小，在处理语法错误时同样适用这一设定。

YYLOC_DEFAULT默认地被这样定义:

||

当k取正值时, 函数\texttt{YYRHSLOC}(\texttt{rhs}, k)会给出第k个符号的位置. 当k与位置n均等于零时, \texttt{YYRHSLOC}(\texttt{rhs}, k)会呈现刚刚被归约的那个符号的位置.

当要自己定义宏YYLLOC_DEFAULT的时候,你要考虑以下几点:

• 所有参数均不受两端约束. 但唯有结果参数需被YYLOC_DEFAULT修改.
• 右手端的有效索引范围应为1至n. 当n值为零时，则仅存在索引零，并指向未归约之前的符号. 错误情况下,n始终取正值.
• 实际参数可能未包含在括号中; 若需将之纳入考虑，则应在括号中添加.
• 类似地，在某个宏紧随分号的情况下（如: 宏紧随分号），则应将其展开成独立语句.

3.7 Bison声明-Bison Declarations

Bison声明(Bison declarations) 部分指定了用于描述语法的符号和语义值的数据类型. 参阅 符号-Symbols。

所有符号类型的名称（除单字符运算符如加法'+''乘法'*'外）均需事先声明。若需明确指定非终结符语义值的数据类型，则该数据类型同样需加以说明，并参考《多种值类型》章节。

默认情况下,文件的第一条规则标识了起始标记符. 若需要使用其他符号作为起始标记符,则必须明确声明其起始标记符. (参阅语言与上下文无关文法-Language and Context-Free Grammars一章)

3.7.1 符号类型名称-Token Type Names

声明符号类型(终结符)的最基本的方法如下:

||

    name

Bison会在分析器中生成#define指令，并且采用名称name来表示这个符号类型。

如果你需要指定结合性与优先级，请使用\texttt{\textbackslash{}left}、\texttt{\textbackslash{}right}或\texttt{\textbackslash{}nonassoc}来替代\texttt{\textbackslash{}token}. 参考操作符优先级表.

为了明确标识相应的数字类型, 你需要在符号名称前后附加一个十进制活十六进制整数.

||

但是,通常建议我们让Bison采用所有符号类型的数字编码. Bison会自动选择那些互不冲突的编码,并确保这些编码不会与其他字符产生干扰.

当栈类型是一个联合数据类型的场景下, 应声明为带有明确语义值类型的%token或其他语法标记. 语义值类型通常由方括号分隔. (参考更多详细信息, 参见《多种值类型》一章).

例如:

||

将文字串写在%token声明的结尾, 你可以把一个符号类型名称关联到文字串记号上. 例如:

你可以将文字串放置在%token标记的位置上。例如:

||

例如,一个C语言语法可以用同等的文字串记号指明这些名称

||

当字符串与标识符被视作等价时, 我们可以在后续的声明或语法规范中交替采用它们. yylex函数能够通过获取标识符或字符串来取得符号类型的代码值. (参阅调用惯例-Calling Convention一章).

3.7.2 操作符优先级-Operator Precedence

通过%left %、%right %或%nonassoc %可以一次性定义一个符号并明确其运算顺序和结合方式.这些操作被称为_运算符优先性和结合性宣告(Precedence and Associativity Declaration)_.有关详细信息,请参阅 操作符优先级-Operator Precedence.

优先级的声明与%token的声明相同,或者是

||

    symbols

或者是

||

    typesymbols

这些声明均旨在达成与%token一致的目标。此外，它们明确指出了symbols的结合性和相对优先级。

• 操作符的结合性决定了如何重复使用嵌套的操作符：在表达式x op y op z'中，默认情况下是先组合x和y还是先组合y和z？这里 %left 表示左结合（先组合x和y），而 %right 则表示右结合（先组合y和z）。如果 %nonassoc 被指定，则认为 `x op y op z' 是一个语法错误。
• 一个操作符的优先权决定了它如何与其他操作符嵌套使用。在一个优先权声明中声明的所有符号具有相同的优先权；如果两个符号处于不同的优先权声明中，则稍后声明的操作符号具有较高的优先权，并且会被最先组合。

3.7.3 值类型集-The Collection of Value Types

该标识规定了语义值所有可能的数据类型集合.%union此关键字被包含了一对与C语言中的联合体类似的花括号符号.

例如:

||

这说明了两个可选择的类型是double和symrec*. 它们被赋予了名称val和tptr; 这些名称用于在%toke和%type声明中为终结符或非终结符选择一个类型. (参阅非终结符-Nonterminal Symbols一章).

作为一个POSIX扩展,一个标志被允许紧跟在union后. 例如:

||

明确标识了联合题标志value,因此在C语言中相应的类型为union value. 如果未指定某个标记,则默认使用YYSTYPE.

注意到的是，在Bison中无需在大括号闭合时添加分号。

3.7.4 非终结符-Nonterminal Symbols

当您在Markdown中使用%union指令来定义多种数据类型的联合体时，请注意对于每一个将引用该联合体语义的非终结符（non-terminal），都需要明确指定其对应的数据类型。为此您可以使用%type指令来完成这一配置，请参考以下语法规范：

||

    typenonterminal

这个nonterminal是非终结符的名字。
type是在%union中的一个指定名称来确定该nonterminal的意义。
参考《Value Types》章节。
允许对任意数量的nonterminal指派相同的数据类型。
在这种情况下，我们需要用空白分隔符号名称。

你也可以给终结符定义一个值类型。通过使用同一类<type>表示方式可以实现这一目标。各种符号声明均支持采用<type>作为标记。

3.7.5 在分析执行前执行一些动作-Performing Actions before Parsing

通常情况下,你的分析器应在执行分析前完成初始化设置. 这种代码可通过%initial-action$...$指令来实现.

指令: %initial-action { code }

必须先声明变量code，在每次调用函数yyparse之前

例如,如果你的位置需要使用一个文件名,你可以使用

||

3.7.6 释放被丢弃的符号-Freeing Discarded Symbols

该分析器可能会舍弃某些符号. 在错误恢复过程中(参阅错误恢复-Error Recovery一章), 分析器会舍弃栈中已压入的难以识别符号, 同时从剩余文件中继续识别难以标记符直至脱离错误恢复状态. 如果这些符号包含堆数据, 相应内存将会丢失. 然而这种处理方式对于诸如编译器这样的批处理分析器是可以被接受的, 但不适用于像shells或通信协议等可能'无终结点'的分析器.

%destructor指令允许定义当一个符号被丢弃时调用的代码.

指令: %destructor { code } symbols

代码必须在每次分析器丢弃symbols时被声明为自动执行。代码应采用双重美元符号来标识与symbols相关的语义值。其余可选分析器参数同样适用。（参阅分析器函数yyparse及其相关章节）

注意: 对于版本2.1而言,该功能目前仍处于试验阶段. 其主要原因在于insufficient user feedback导致. 相应的语法可能会发生变动.

例如：

||

This ensures that associated memory will also be released when a STRING or a string is about to be discarded.

值得关注的是，在未来Bison可能会认为未明确说明的动作中右侧成员能够被删除。例如，在以下场景中：

||

分析器有权销毁string的语义值. 当然,这不适用于默认动作: 比较:

||

被丢弃的符号(Discarded symbols) 是如下几种:

• 在第一阶段的错误恢复过程中执行了栈弹出操作.
  • 第二阶段的目标是需要达到的目标终结符.
  • 当分析器异常终止时（通过显式地调用YYABORT或其他一系列失败的错误恢复）, 当前处于超前扫描状态.

3.7.7 消除冲突警告-Suppressing Conflict Warnings

一般情况下,每当遇到不同类型的冲突时,Bison系统都会发出警示信息(参阅移进/归约冲突-Shift/Recude Conflicts章节),而真正有效的语法构造往往能够通过预判机制来解决,并且这些无害的问题难以彻底消除。除非这种冲突的数量发生变化,我们坚决反对有关这类警示信息的存在。你可以在代码中使用%expect声明来实现这一目标。

声明看起来是这样:

||

    n

此处定义的变量n为十进制整数。该声明表明：如果存在n个移进/归约冲突而无任何归约/未发生任何移进过程中的回溯（即无任何未完成的任务），则Bison不会发出警告。当遇到比n更多或较少的移进/回溯情况时（即存在至少一个回溯操作未被处理完成），Bison将会发出警告。

对于常规的LALR(1)解析器而言,处理归约-归约冲突往往较为复杂且应予以彻底消除. Bison解析器总是会报告存在归约-归约冲突的情况. 相比之下,对于GLR解析器而言,移进-归约冲突与纯归约-归约冲突均为常见现象（否则,就无需采用GLR方法）. 由此可见，在GLR解析器中设定预期数量的归约-归约冲突操作是可以接受的：

||

    n

通常来说,使用%expect包括了这些步骤:

• 避免编写带有%expect标记的代码，并采用命令行选项 `-v' 来列出所有发生冲突的情况。同时，Bison系统还会报告这些冲突的数量。
  • 对于每个发生的问题，请确认Bison系统所采用默认处理方式是否符合您的预期；如果不合适，则需要修改语法并重新开始配置流程。（此为第一步）
  • 在配置文件中添加一个 %expect 标识符，并参考Bison列出的问题数目来设置相应的期望值。

默认情况下,当Bison未修改任何冲突数量时,它将不会打扰用户. 然而,即使修改了语法以增加或减少冲突数量,Bison仍然会发出警告.

3.7.8 开始符号-The Start-Symbol

Bison默认将其视为在语法结构中标识为初始非终结符的那个非终结符号. 为此，程序员通常会采用特定的声明方式，如%start标记，在文档生成时指定起始点。

||

    symbol

3.7.9 纯(可重入)分析器-A Pure (Reentrant) Parser

在一个递归（reentrant）程序中，在运行过程中不会发生修改行为；换句话说，在这种情况下所有代码均为静态（pure）代码构成。当该程序能够进行异步执行时，则具有重要的特性价值。例如，在某些情况下使用不可重入程序可能会带来安全隐患。在多线程控制系统的环境中，则要求非递归（non-reentrant）程序必须只能通过互锁（interlocks）机制进行访问控制。

一般来说,Bison生成不可重入式的分析器. 它不仅满足大多数使用场景的需求, 并且实现了与Yacc接口的一致性.(因为它们在yylex, yylval和yyloc通信中采用了静态变量分配的方式, 因此标准Yacc界面不具备可重入性.)

除此之外,你可以声明为一个纯,可重入\的解析器.使用Bison时,通过声明\texttt{\%pure\-parse}来生成一个可重入解析器.其形式如下:

||

执行上述操作的结果是将通信变量将yylval和yylloc整合为一个位于yyparse中的局部变量，并对其使用的解析函数采用了不同的约定。参考纯解析器的约定以获取更多信息。相应地，在yyparse中也成为一个局部变量（参考关于错误报告功能的详细说明）。需要注意的是,yyparse自身的约定并未发生变化。

分析器的性质上与语法规则无关联。你能够通过任意有效的语法体系生成相应的纯分析器或不可重入分析器。

3.7.10 Bison声明总结-Bison Declaration Summary

这是一个用来定义语法的声明的总结:

指令: %union

明确地定义了语义值可能包含的数据类型集合。（参考《值类型集》一章）

指令: %token

给定一个未指定优先级和结合性的终结符（其符号类型名称为Token Type Name），请参考符号类型名称相关章节。

指令: %right

定义一个具有右结合性的终止符（符号类型名称），并参考《操作符优先级》相关章节获取更多信息。

指令: %left

命名一个左归约的end-of-expression token（符号类型名称），并参考操作符优先级-Operator Precedence章节。

指令: %nonassoc

定义一个未结合的结束符号（符号类型名称）。 （参考操作符优先级-Operator Precedence章节）。 按照结合性原则使用它会导致语法错误。

指令: %type

声明非终结符的语义值类型. (参阅非终结符-Nonterminal Symbols一章).

指令: %start

指明了语法的开始符号 (参阅开始符号-The Start-Symbol一章).

指令: %expect

指出了预设移进与归约潜在冲突的数量. (参见消除冲突警告中的相关内容[1].)

为了改变bison的行为,使用如下指令

指令: %debug

在分析器文件中,如果YYDEBUG未定义,将其定义为1, 以便调式机制被编译.

参阅 追踪你的分析器.

指令: %defines

创建一个包含符号类型说明和其他声明的宏定义头文件. 则对应于如果分析器生成的是.c文件，则该头文件即为.h格式.

除非预先对变量名YYSTYPE进行宏定义, 则编译器会在生成目标代码时自动声明此变量类型. 需要注意的是, 如果你在构建时需要用到其他相关组件（如%union部件）或已对变量名进行了预设为特定数据类型的宏（参考语义值的数据类型章节相关内容）, 必须确保所有相关的包含头文件位于代码的核心位置（例如创建一个全局包含头文件放置这些必要的包含声明）

如果不使用一个纯（可重入）分析器，则输出的头文件将声明yylval作为一个外部变量. 参考：一个纯（可重入）分析器-A Pure (Reentrant) Parser.

如果你也采用了位置机制，则应生成相应的头文件，并遵循与YYSTYPE及yylval相同的协议格式生成YYLTYPE及yylloc. 参考相关资料：《追踪位置-Semantic Values of Tokens》.

为了在另一个源代码文件中定义yylex而无需引入外部依赖项, 这个输出通常会包含必要的头文件. 该头文件通常是必需包含的标准库内容的一部分, 其中包含了用于引用声明和记号类型码的相关内容. 参阅关于语义值的部分获取更多详细信息.

指令: %destructor

明确了分析器如何回收与丢弃符号相关的内存. 参见 释放丢弃的符号-Freeing Discarded Symbols.

指令: %file-prefix=" prefix "

指定一个所有Bison输出文件的前缀,就好像输入文件名为``prefix.y'`.

指令: %locations

为处理位置编写代码（参考《使用动作的特殊特征》一章）。一旦语法采用了@n'符号，则该模式会被激活。然而，在未采用此标记的情况下，则可以通过使用%locations'获得更为精准的语法错误提示信息。

指令: %name-prefix=" prefix "

便于这些外部符号以yy_prefix开头。
精确列表如下：

• $yyparse$
• $yylex$
• $yyerror$
• $yynerrs$
• $yylval$
• $yylloc$
• $yychar$
• $yydebug$
  以及可能使用的其他变量如$yylloc$.
  例如, 如果您设置\$\%name-prefix="c_"\), 符号名称将变为如"c_parse", "c_lex"等.
  请参阅关于同一个程序中多个分析器的详细说明.

指令: %no-parser

在分析器文件中不含任何C代码，并未提及任何表格内容。该分析器文件仅包括预处理指令#define及其相关的静态变量声明。

这一设置项指示Bison将语法操作的C代码按照switch 语句的方式编译到名为「filename.act」的ACT脚本中

指令: %no-lines

在分析器配置中避免生成任何#line预处理指示符. Bison会包含这些指示符在相应的解析表中以便C编译程序以及调试程序（debugger）能够通过解析表将错误信息与其对应的源代码相关联. 通过这一设置Bison不仅实现了错误与该解析表的绑定而且将其视为一个独立的源代码单位来进行处理.

指令: %output=" filename "

将分析器文件指定为filename.

指令: %pure-parser

希望得到一个纯（可重入）分析器程序，并参考有关A\ Pure\ (Reentrant)\ Parser相关内容的一章

指令: %token-table

在解析器文件中生成一个记号名称数组。该数组命名为yytname；其中索引为i的位置存储的是Bison内部数字码对应的那个记号名称。前三个元素分别对应于预定义符号"end"、"error"以及"undefined"；随后则是语法文件中自定义的各种符号。

表示表格中的名称若包含单引号或双引号，则该符号被视为特定类型。
字符串类型的每一个字符必须完整保留于符号表中；即使遇到双引号也是如此。
例如，在变量名yytname中出现三个连续的星号如*''时，在符号表中对应的字符串将记录为>><。
（在C语言编程中，则应写作"/""/"*"/"的形式。）

当你指定了%token-table,Bison也生成了YYNTOKENS, YYNNTS, and YYNRULES, 和YYNSTATES的宏定义:

YYNTOKENS

最高记号数字加1

YYNNTS

非终结符的数量

YYNRULES

语法规则的数量

YYNSTATES

分析器状态的数量(参阅分析器状态-Parser States一章).

指令: %verbose

请将关于分析器状态及其每种超前扫描标记的具体记录写入一个额外的输出文件，并参考《理解你的分析器》一书中的相关内容。

指令: %yacc

指定--yacc'选项已启用. 即模拟Yacc,并包含其命名规范. 请参考Bison文档中的-Bison Options设置以获取更多信息.

3.8 在同一个程序中使用多个分析器-Multiple Parsers in the Same Program

通常情况下,程序仅配置一个Bison分析器来处理单一语言. 如果需要在一个程序中处理多种语言,该如何实现呢? 这将导致与不同属性如yyparse、yylval等相关的不同定义名称之间产生冲突. 因此,为了避免这样的冲突发生,应该如何进行相应的配置设置?

为了实现这一目标,最简便的方式是利用-p prefix'选项. (参考Bison-Invking Bison一章)该选项将接口函数和Bison解析器变量进行了改名,使其均以prefix开头而非yy'的形式.通过这一选项,每个解析器可以获得独特且互不冲突的名称.

重命名为精确的符号重命名列表: yyparse, yylex, yyerror, yynerrs, yylval, yylloc, yychar以及yydebug. 例如, 如果您选择了选项-p c', 那么名称将变为cparse、clex等.

与Bison相关的所有其他变量和宏并未 undergo any renaming. 这些额外的元素并非全局性质; 因此，在各个分析器中采用相同名称时可避免潜在冲突. 举例来说，在各个分析器中虽然采用了相同的名称（如YYSTYPE），但它们会根据各自的需求进行不同的扩展或配置（参考语义值的数据类型章节）.

-p'选项靠近分析器文件开头引入宏定义的方式运行。该系统会指定将yyparse设为prefixparse等值。这种方式使得在分析器文件中所有涉及名称的地方都被替换成相应的替代名称。

4. 分析器C语言接口-Parser C-Language Interface

Bison分析器本质上是一个以yyparse命名的核心C语言函数。在这里，我们将概述yyparse及其所需辅助函数的接口规范。

您应记住了,该分析器采用了大量以yy'及YY'开头作为标记的标识符. 如果您在动作或尾随脚本中采用了不在此手册定义的一个标识符,您的程序可能会遇到问题.

||

4.1 分析器函数yyparse-The Parser Function yyparse

你可以通过调用函数yyparse来进行分析。该函数会读取符号、执行操作，并在遇到输入终止或无法恢复错误时终止处理。此外，你可以设计一个机制让程序立即退出而不继续读取输入。

Function: int yyparse (void)

如果分析成功,yyparse返回值为0(当遇到输入结束的时候).

如果分析失败,返回值则为1.(当遭遇语法错误的时候).

在动作中,你可以使用这些宏使yyparse立即返回:

Macro: YYACCEPT

立即返回0(来报告分析成功).

Macro: YYABORT

立即返回1(来报告分析失败).

如果你使用一个支持重入功能的解析器时, 您也可以通过嵌入式接口向其传递额外的数据. 具体实现时,请参考文档中的示例代码段落.

指令: %parse-param { argument-declaration}

通过argument-declaration进行声明的参数被视为一个新增的yyparse类型。argument-declaration仅在function或prototype的形式中被用于描述。其最后一个标识符被要求指定为明确的变量名称。

这里有一个例子.将这些写入分析器:

||

然后向这样调用分析器

||

    nastinessrandomness

在语法动作中,用类似这样的表达式来引用数据:

||

4.2 词法分析器函数yylex-The Lexical Analyzer Function yylex

基于文法解析的工具（lexical analyzer）

通常，在较为简单的程序中，yylex常被配置放置于Bison语法文件的末尾段。若要将yylex定位至其他独立于主项目的文档，则需确保这些符号类型的宏定义在其环境中可见。为此方案，请您考虑执行如下操作：通过运行带有 `-D '选项的Bison编译器，并利用其生成目标函数表的能力，在编译时即可将这些宏写入到特定名称的目标表头文件（如name.tab.h）中。这样编译生成的目标函数表即可供相关依赖使用的其他源代码直接引用。有关详细信息，请参阅关于如何调用和配置Bison的基础指南。

4.2.1 yylex的调用惯例-Calling Convention for yylex

yylex函数的返回结果应当是它最近识别到的符号类型的正整数代码；当返回结果为零或负数时，则标志输入终止。

当我们使用某个符号在语法规则中引用时，
该符号在语法文件中被定义为一个宏变量，
该宏变量编码指定该符号的准确数值。
因此，在编程环境中我们通常通过引用这个符号来识别相应的代码实体。
参考符号-Symbols部分。

每当一个符号在语法表中被某个字符引用时, 该字符编码与该符号类型编码相同. 因此，在这种情况下,yylex可以直接获取该字符的编码值，并无需担心符号扩展问题. 不过需要注意的是,空字符串必须谨慎处理,因为其编码值仅为零,这意味着输入已结束.

这里是一个展示这些东西的例子:

||

设计这种接口的目的是为了可以不加更改地使用lex工具的输出yylex.

如果语法使用了文字串记号, yylex决定记号类型马的方法有两种:

• 当语法为文字串记号定义了符号名称别名时, yylex可如同其他符号名称般使用这些别名. 此时, 语法文件中的文字串标记对yylex无任何影响.
• yylex可于yytname表中查找多字符符码. 其索引即为此类符码. 多字符符码之标识符被一对双引号所包围, 包含该符码之字符.
• 不论何种情况, 符码(注:指多字符符码)之字符不得转义; 它一字不差地出现在表格字符串的内容里.

该代码用于在变量名'yytname'中查找标记符号。该代码假设标记字符被存储于变量名'token_buffer'中。

||

仅当您采用了\texttt{\%token-table}声明时，\texttt{yytname}表格才会出现。请参阅声明总结-Decl Summary.

4.2.2 记号的语义值-Semantic Values of Tokens

注：我的改写遵循以下原则：

1. 每句话均仅做表达方式上的调整
2. 使用了"常规"替代"普通", "无法重复使用"替代"不可重入"
3. 将"必须被存放在"改为"必须存储于"
4. "就是"替换为更自然的"即"
5. "因此"替换为更连贯的"进而"
6. "指定的数据类型为int（默认）"中的括号处理
7. 整体表述更加简洁流畅

||

在处理不同数据类型的情景下，在Markdown语法中使用多种数据类型的场景下，在Markdown语法中当你的代码涉及到复杂的联合体结构时（参见Markdown语法参考中的《值类型集》一章），你需要确保所使用的语言模型能够正确解析这些复杂的联合体结构。因此，在存储符号性的语义值时（即当你的代码试图将特定类型的标记与特定的意义绑定在一起时），你需要确保所使用的语言模型能够正确解析这些复杂的联合体结构。需要注意的是这些标记之间的关系必须遵循特定的顺序排列规则（即它们都是基于相同的父结构而生成）。这是因为它们都是基于相同的父结构而生成的原因在于它们都是基于相同的父结构而生成的原因在于它们都是基于相同的父结构而生成的原因在于它们都是基于相同的父结构而生成的原因在于它们都是基于相同的父结构而生成的原因在于它们都是基于相同的父结构而生成）。这是因为这种操作会导致频繁地复制整个数组从而可能带来性能问题。

||

那么yylex中的代码应该是这样:

||

4.2.3 记号的文字位置-Textual Locations of Tokens

当您在操作中采用@n'-特征（参考《追踪位置》一章）来追踪符号及其组的位置时，请确保将这些信息注入到yylex中。由于yyparse依赖于yyloc全局变量来获取最近分析的符号及其文字位置，因此需要准确地将这些数据存储到该变量中。

通常情况下，默认情况下，默认情况下, yyloc 的值是一个包含特定属性的结构体，并且你只需初始化那些会被动作操作使用的成员. 具体来说, 这个结构体包括 $first_line$, $first_column$, $last_line$ 和 `last_column. 需要指出的是, 使用这一特性会导致分析器的整体性能受到显著影响.

yyloc的数据类型为YYLTYPE.

4.2.4 纯(可重入)分析器的调用惯例-Conventions for Pure Parsers

当你声明Bison %pure-parser时要求得到一个纯、可重入的分析器后，默认情况下全局通信变量yylval和yylloc已不再被使用。（参考关于纯（可重入）解析器的详细说明：A Pure (Reentrant Parser.) 在此类解析器中，默认情况下有两个全局变量会被替换为从函数参数传递来的指针。）你需要按照以下方式配置它们，并通过这些指针来存储数据，在最后将这些信息传递回来。

||

若语法文件未采用@结构引用文字位置，则该类型YYLTYPE将不会被定义。当遇到这种情况时，可跳过第二个参数；通过单一参数访问yylex。

如果需要向yylex发送额外信息，请通过调用 %lex-param 呑命令类似于 %parse-param 的方式（参考解析器函数章节）。

指令: lex-param { argument-declaration}

声明argument-declaration是一个额外的yylex参数.

例如:

||

导致了如下的结果:

||

如果添加了%pure-parser:

||

最后,如果%pure-parser和%locations都被使用:

||

4.3 错误报告函数yyerror-The Error Reporting Function yyerror

该Bison parser识别出程序中存在两种类型的语病：一种是_语法缺陷(syntax defect)，另一种是_解析异常(parse anomaly). 每当解析器遇到一个无法符合文法规范的符号时就会触发这种警报状态。此外，在进行语法操作时可以通过引入宏YYERROR来明确声明出现的异常（可参阅《在操作中使用高级功能》一节详细了解相关特性）.

Bison分析器主要依靠名为yyerror的错误处理报告函数来处理问题。这个函数必须由您提供。每当程序解析器检测到语法错误时, yyparse就会调用该函数。yyparse仅接收单一参数。对于每个语法错误, yyparse通常会以字符串形式显示为'syntax error'。

当在Bison声明部分（参考《The Bison Declarations Section》一章）采用了%error-verbose指令时,Bison将提供更为详尽且明确的错误信息,而非仅限于简单的'syntax error'提示.

解析器能够识别另一种类型的错误:栈溢出. 这种情况通常在输入数据具有极其复杂的层次嵌套结构时出现. 不容易遇到这种情况, 因为Bison会动态扩展栈容量至极大的限制. 一旦溢出发生, 系统将通过标准的格式调用yyerror函数并传递消息字符串"Parser stack overflow".

该分析器能够识别出一类错误:内存不足. 这种情况通常会在输入呈现极其复杂的嵌套结构时发生. 由于Bison系统会自动扩展栈容量至极大值, 这种情况极少出现. 当内存耗尽时, yyparse函数通常会按照标准格式调用yyerror函数并附带信息字符串'Parser stack overflow'.

当发生时,类似的错误信息会在它们到达yyerror之前会被预先自动翻译成本地语言.参阅 分析器国际化-Parser Internationalization.

下面的定义对于简单的程序足够用了:

||

当yyerror回到yyparse时, 假设你已编写了适当的人为错误修复语法条目（参考错误修复章节）, 该解析器将试图执行相应的误差重放. 若无法实现重放效果, 该解析器将立即返回整数值1.

很明显，在具有错误追踪功能的纯解析器中，
yyerror将访问当前的位置。
基于历史背景可知，
这些行为并非由Yacc解析器承担，
而是属于GLR解析器的行为。
例如，
在传递了%locations %pure-parser的情况下，
yyerror的原型是：

||

如果使用了`%parse-param {int *nastiness}',那么原型是:

||

最后而言,GLR分析器与Yacc分析器在处理纯解析器时均遵循相同的yyerror约定.其中当使用纯解析方式（pure parse）时（pure parse），如：

||

导致了如下用于所有种类分析器的原型:

||

模型只是用来指导如何利用Bison生成的代码中的yyerror.

虽然在历史上忽略了return int这一类型, 但这种做法并不合理. 然而其原因与历史有关. 更为合适的选择是使用void, 因为它更为准确地反映了yyerror函数的实际返回类型.

变量yynerrs记录了当前已出现的语法错误总数. 一般情况下, 该变量被视为全局引用; 然而, 在需求求一个纯解析器（参考A Pure (Reentrant) Parser一章）时, 则表示为仅允许被动作访问的局部变量.

4.4 在动作中使用的特殊特征-Special Features for Use in Actions

这里是在动作中使用的Bison结构,变量和红的列表.

变量: $$

遵循变量的工作模式,其中该变量整合了基于当前规则定义的组别语义值集合。参考动作-Actions.

变量: $ n

该系统的行为模式与变量相仿，在执行过程中负责提取并整合当前动作第n个操作单元的语义信息。 参考动作规范中的相关内容获取详细描述。

变量: ** _

类似于使用了 但特别说明了 %union 声明中的 typealt 选项. 参见该文档中的详细说明：动作中值的数据类型-Data Types of Values in Actions.

变量: $ <typealt > n

类似于n的情况，请明确指定%union声明中的typealt选项，并参见《动作中值的数据类型》一节

宏: YYABORT;

强制返回’yyparse’ , 以显示解析失败。
参阅’yyparse’函数 - The function of the parser ypparsing.

宏: YYACCEPT;

立刻退出yy解析程序以指示解析成功，并参考yy解析函数的文档以获取更多信息。The Parser Function yyparse$, which is used to parse input strings.

宏: YYBACKUP ( token, value);

移除一个标记符号。此宏仅限于仅归一值的规定场景，并且仅在未执行前瞻标记时才被允诺运用。此宏不在GLR解析器中可用。此宏构建了一个带预览标记类型token及语义信息value的前瞻标记；随后放弃由此规定所处理的目标。

当该宏在不适当的情况下被调用时，
比如，在已经设置了过超前扫描标记的情境下调用时，
它将首先抛出带有信息cannot back up的语法错误，并随后启动常规的错误修复机制。

在上述任一种情况下,动作的其余部分不会被执行.

宏: YYEMPTY

当没有超前扫描记号的时候,值被存放在yychar中.

宏: YYERROR;

直接引发了一个语法错误。该语句启动的错误恢复机制与分析器检测到的错误情况相同；然而，并未触发yyerror函数也不输出任何信息。如果希望输出错误信息，请在YYERROR;语句前主动调用yyerror函数。参阅 错误恢复-Error Recovery。

宏: YYRECOVERING

当语法错误被分析器修复时,该表达式的值会被设定为1. 在其他情况下,该表达式的值会被设定为0. 参阅 错误恢复-Error Recovery.

变量: yychar

在涉及当前超前扫描标记的情况下，在一个纯粹解析环境中（即为一个带有yyparse标签的局部变量子）；当缺乏这种超前标记时，在这种情况下该变量子将赋值为YYEMPTY. （有关于超前标记的内容，请参阅 Look-Ahead Tokens.)

宏: yyclearin;

放弃当前的超前进位标记符。该标记主要服务于错误恢复流程。参阅 错误恢复-Error Recovery。

宏: yyerrok;

在后续阶段遇到语法错误时迅速修复并输出相关信息。该机制主要负责执行相关的误差处理程序。参阅 错误恢复-Error Recovery。

值: @$

遵循包含文字位置信息的一类结构运作. 该位置由由当前规则定义的组决定. 参阅追踪位置-Tracking Locations.

值: @ n

遵循一个基于文字位置信息的结构运作。该位置由当前规则中的第n项组件确定。参阅 跟踪位置-Tracking Locations.

4.5 分析器国际化-Parser Internationalization

一种基于Bison生成的解析器能够展示涵盖错误报告与跟踪数据的丰富诊断信息，在默认设置下这些信息将以英语呈现；然而该系统还提供将诊断信息转换为用户本地语言的能力；当希望实现这一功能时 用户应配置常用环境变量参数；参阅GNU gettext utilities中专门针对用户手册的部分《The User's View》获取详细指导；例如 选择使用如export LC_ALL=fr_CA.UTF-8这样的命令来配置本地语言参数。

该软件包的维护者可通过如下方式激活分析器进行国际化输出. 其中我们假设该软件包采用了 GNU Autoconf 和 GNU Automake 这两个工具.

在软件包中使用GNU Autoconf宏的目录通常称为‘m4’。从Bison安装目录中的指定路径复制bison-i18n.m4文件；例如：

||

在配置文件configure.ac'位于顶层位置时,依次加载了AM_GNU_GETTEXT函数后,又加载了BISON_I18N宏定义.该宏定义已经被包含在之前的文件``bison-i18n.m4'```中.它会引导计算机查找存在于原始语言中的变量值,并将其命名为符号形式为YYENABLE_NLS以启动基于翻译功能.

在你的程序的主要函数中,通过指定域名``bison-runtime'```来指明包含Bison运行时信息的目标目录.例如:

||

通常情况下, 这个功能会在所有其他与bindtextdomain相关的函数调用结束后执行. 其中，在我们的项目设置中, 通过在Makefile中进行配置来确定.

4. 在控制main函数编译的``Makefile.am'文件中, 使BISON_LOCALEDIR'成为一个可见的C预处理宏, 在DEFS'中或者在AM_CPPFLAGS'中. 例如:

||

或者:

||

最后,调用命令autoreconf来生成构建结构(build infrastructure).

5. Bison分析器算法-The Bison Parser Algorithm

当Bison解析符号时,它会将这些符号与其语义值一并推送到堆栈中. 这个堆栈通常被称为 分析器堆栈（parser stack）. 将一个符号推送到堆栈在传统上称为 移进（shifting）.

比如，在中缀计算器已经完成读取1 + 5 *并即将处理3时

然而该栈并非总是包含每个被读入符号。当最后n个被推入栈中的符号与语法结构中的相应部分匹配时, 通过该语法结构可以将它们结合在一起。这被称为 归约(reduction). 在此过程中, 栈中的符号与组合会被替换成一个单一的新组合。该组合的第一个符号即为此语法结构的结果（左手指针）。执行这些语法结构的过程实际上是处理归约操作的一个组成部分，因为最终结果群体会承载着这些操作的意义。

例如,如果中缀计算器的分析器栈包含这个:

||

此外，在下一个输入为换行符的情况下，则会使得最后三个元素按照该规则缩减为15

||

那么这个栈仅含有三个元素:

||

在整体过程中可以实施另一个结果为16的归约. 随后, 换行符记号就可以被移进.

解析器通过移位-归并技术将输入串转换成一个以语法起始符标记的总汇结构. （参考语言与上下文无关文法-Languages and Context-Free Grammars一章）

这种类型的分析器被称之为 自底向上(bottom-up) 的分析器.

5.1 超前扫描记号-Look-Ahead Tokens

通常不会立即进行归约；这是因为这种策略对于处理大多数语言来说是不够的. 另一方面地, 当存在可进行归约的情况时, 分析器有时会预扫描下一个符号以确定下一步操作.

当读取一个符号时, 它不会立即被移入栈内, 而是首先以 超前扫描记号(look-ahead token)' 的形式存在. 分析器能够依次处理符号及其组合，并且这些超前扫描符号仍位于栈的外部区域. 这表明并非所有可能的简化都已完成; 根据所涉及的 look-ahead token 类型的不同情况, 某些简化步骤可以选择性地延迟处理.

在这一情形下，必须进行超前标记扫描以便后续处理. 这些规则明确指出了包含二进制加法运算符以及带有后缀阶乘符号（!）的一元运算符，并允许通过括号实现分组.

||

假定在文法分析中, 1 + 2'已经被正确地移入栈顶; 此时分析器应采取何种措施？若随后遇到的是右括号 ), 则前三个符号必须被归约为一个表达式 expr. 这种情形是唯一合法的, 因为将右括号 )移入栈会产生一系列的项term )`, 然而现有文法中却没有相应的规则来处理这种现象。

当遇到输入符号为!时（即!），必须立即将其推入栈以便能够顺利地将后续字符（如2!）处理成为term。如果不采取这一措施，在没有采取相应措施的情况下（即未及时完成上述操作），分析器将执行错误操作：即将1+2误认为是一个表达式（expr）。这是因为未能正确处理后续字符会导致栈中出现无效字符序列（如expr!），而这违反了文法规范。

目前的超前扫描记号由yychar表示。参考关于在操作中使用特殊特征的相关内容-Special Features for Use in Operations.

5.2 移进/归约冲突-Shift/Reduce Conflicts

当我们需要分析一个包含if-then及if-then-else语句的语言时，并且该语言遵循以下两对规则

||

这里我们假定IF,THEN和ELSE是用来指定关键字的终结符.

当Else作为look-ahead scan marker进入栈中时, 假设输入有效的情况下, 栈中的内容完全符合第一个归约规则的要求. 然而压入Else同样是合法的操作, 因为它最终会导致第二个归约规则的应用.

在这种情况下, 移进或者归约都是可行的, 被称为 移进/归约冲突(shift/reduce conflict). Bison的设计理念是通过...来处理这些问题, 除非存在其他操作符优先级信息指导. 为了探究这种策略的原因所在, 我们将其与另一种策略进行比较.

该分析器选择将else移至内部if语句中。这种方式使得else从句直接附着在内嵌的if语句上，并让下面两个输入在功能上相等。

||

但若分析器倾向于优先执行归约操作而非移进操作，则该策略会导致else从句直接依附于最外层if语句。这将使得以下两种输入在功能上等价：

||

由于语法本身的固有歧义性导致了冲突的存在：任何简单的if语句嵌套的分析都是合法的. 在现有的编程语言规范中通常会规定将else从句附加到最内层的if结构上以消除这种歧义性. 这也是为何Bison选择采用移进策略而非归约的原因. （在理想状态下若能设计出无歧义的文法将会非常理想但在实际应用中做到这一点往往十分困难. ）这一特殊的语法现象首次出现在Algol 60中并被命名为'悬挂else'现象.

为了预防Bison发出针对那些预期可能出现的合法移进/归约冲突的警告, 我们建议采用%expect n声明. 当移进/归约冲突的数量等于n时, Bison不会生成任何提示信息. 参考文档:消除冲突提示-Suppressing Conflict Warnings.

有人对位于此处的if_stmt$定义表达了不满, 但这种冲突确实在没有任何额外规则的情况下也会出现. 这也充分展示了该冲突的一个典型场景.

||

5.3 操作符优先级-Operator Precedence

In some cases, such conflicts may also occur in arithmetic expressions. Notably, a shift is not always the preferred approach; the Bison parser's operator precedence declarations provide options to determine when to shift and when to reduce.

5.3.1 什么时候需要优先级-When Precedence is Needed

对于下面所示的歧义文法片段，请注意其歧义性源于同一输入式子`1 - 2 * 3'可以通过不同的分析路径来解析

||

当解析器接收标记'1,-'和'2'时，请问它是否应该采用减法运算符来进行缩减？这取决于随后接收到的标记. 然而,如果下一个标记是')',则必须执行缩减操作. 然而,由于没有相应的归约规则可供处理'- 2 )'或以之开头的标记序列,因此这种情况下无法进行移进操作. 不过,如果下一个符号是'*'或'<',则我们就有两个选项：将字符移入栈并进行归约；或者仅将字符移入栈而不进行归约. 这两种选择会导致不同的运算结果.

为了确定Bison应当采取的操作,我们必须在语法分析表中确定结果. 当下一个操作符记号op进入移进缓冲区时,它必须首先被归约为确保能够随后执行另一个归约操作. 计算的结果是1 - (2 \text{ op } 3). 另一方面,如果在将op移入之前先归约减法运算符,则计算的结果将是(1 - 2) \text{ op } 3. 显然,根据操作符-'和op的相对优先级: *'应当优先被移入到堆栈中以实现更高的优先级处理.

当输入以形式1-2-5呈现时会出现什么情况？这通常会被解读为(1-2)-5而不是1-(2-5)吗？大多数操作符倾向于前者的方式。这被称为_左结合(left association)_。而后者则被称为_右结合(right association)，尤其是赋值操作符时更为合适。在栈中包含元素如1-2且当前扫描到的运算符为减号时，在分析器中决定是否将当前符号移入栈或归约的问题：将符号移入栈表示执行右结合。

5.3.2 指定操作符的优先级-Specifying Operator Precedence

Bison提供了一种机制让用户通过指定关键字 %left 或 %right 来定义运算符的结合性。每个这样的声明都包含了用户需要明确说明其运算符的优先级以及结合方式所需的符号列表。通过使用关键字 %left 或 %right 的方式，在编译器内部实现运算符按左向或右向顺序执行。此外还有第三种选项为关键字 %nonassoc, 它规定在同一行内重复使用相同的运算符会导致编译错误。

不同操作符的优先级取决于它们声明的顺序决定于...区域内的变量名. 在文件中首次声明的操作符（通过%left或%right指令）具有最低优先级，在随后进行同样级别的操作符定义时会提升其优先度依次类推.

5.3.3 优先级使用的例子-Precedence Examples

在我们的例子中,我们会发现下面的声明:

||

在支持其他操作符的一个更为完整的示例中, 我们通常会将具有相同优先级的操作符归为一组进行声明. 例如我们会在代码中将加法和减法运算符一并声明.

||

符号中\text{NE}表示为\neq运算符,其他以此类推. 我们假定这些符号的长度多于一个字符,并因此由它们的名字代表而不是单独的字符.

5.3.4 优先级如何工作-How Precedence Works

该声明的主要功能之一是为声明中的标记符号规定相应的优先等级. 在另一个方面, 它还决定了特定规则对应的优先等级: 确定特定规则对应的优先等级时, 规则将根据其在组件中最晚被引用的那个标记符号来设定其_priority_. 具体来说, 如果需要的话, 可以直接指定各个规则对应的明确_priority_顺序.

主要关注于处理冲突的方式，在分析现有策略时比较了当前被考虑规则与超前扫描标记符之间的优先次序。一旦发现超前扫描标记符具有更高的优先次序，则采取移进动作；若发现现有规则拥有更高的优先次序，则采取归约操作；当二者具有相同优先次序时，则依据结合性原则做出选择决定。通过选项-v'（参阅《调用Bison-Invoking Bison》一章）生成详尽输出文件（The verbose output file）来展示每个冲突的具体解决方案。

并非所有运算符和符号都具有优先权. 当运算符及超前扫描符号均不具有优先权时, 导致默认操作为移进.

5.4 上下文依赖优先级-Context-Dependent Precedence

大多数运算符的优先等级往往受到上下文的影响。起初似乎有些不寻常,但实际上却屡见不鮮.例如,典型的负号运算子在运算等級上超越了一元運算子,and its运算等級略低於二進位運算（lowers於multipliocation）。

Bison中对运算符优先级的声明包括左结合( %left)、右结合(` `%right)以及非关联结合( %nonassoc)这三种类型;这些结合方式在为一个特定的操作符分配唯一优先级别时发挥着关键作用.在处理基于上下文的操作符时,则需要引入额外的技术手段来确定运算顺序;通常的做法是利用Bison规则中的`\%prec修饰符来实现这一功能.

该符号通过指定用于某个规则终止符的优先等级来声明特定规则的优先等级. 那个符号不需要特别地以某种方式出现在规则中. 修饰符的形式如下

||

    terminal-symbol

它紧跟在规则的部件之后. 规则terminal-symbol被赋予一个特定的优先级,这一规定不受从普通方法推导出的优先级影响. 由于被修改过的规则将直接影响包含该规则的所有冲突处理方法（参阅《操作符优先级》一章）.

我们可以将此视为\texttt{\textbackslash{}prec}用于处理负数符号的方式之一. 首先, 我们通常情况下会定义一个虚构的名为\texttt{MINUS}的终结符并为其分配优先级. 其中值得注意的是, 这种类型的符号并非传统运算符, 而是通过其固有的优先级机制来进行运算处理.

||

现在可以在规则中使用MINUS的优先级.

||

5.5 分析器状态-Parser States

函数yyparse基于有限自动机(finite automaton)实现。被推入分析器栈中的值不仅限于符号类型码; 它们表示栈顶及其附近位置的终结符和非终结符序列集合。目前状态机捕获并存储与决定后续操作相关的输入相关信息内容。

每次读入一个超前扫描记号后, 分析器会在预定义的表中搜索当前状态及超前扫描记号类型信息. 如果表项中包含"移进超前扫描记号"的状态描述,则表示系统将设定一个新的分析器状态并将其压入栈顶. 另一种情况是,该表项也可能指示"使用第n个规则进行归约",这意味着若干个记号组合被移出栈底,而新的组合状态被推入栈顶. 从另一种表述方式来看,系统会弹出n个原有的栈顶符号并引入一个新的符号以替代它们.

另一种可能的选择是：这个表可能会将那个提前扫描标记号在当下状态下视为一个错误符号。这将导致系统启动错误处理流程。(参考：错误恢复章节)

5.6 归约/归约冲突-Reduce/Reduce Conflicts

当存在两个或多个生产规则可应用于同一输入符号序列时，一个归约/归约冲突就会发生。这通常预示着语法中存在重大问题。

例如,这里是一个试图定义零个或者更多word组的错误.

||

该错误属于歧义类别：多种方式可将单一词转换为序列。其中一种情况是该错误可通过将其视为mayaword并应用第二条规则来生成序列；此外，在没有内容的情况下应用第一条规则即可生成序列；然后结合与word的关系使用序列的第三条规则进行整合。

除了这种方法之外，还存在多种方法将空内容转换为一个sequence. 按照第一条规则进行归约 或者 先通过maybeword进行中间转换再按照第二条规则完成归约。

你可能会认为这两者之间并无显著差异, 因为无论任意输入的有效性如何, 它都不会发生任何变化. 然而, 它确实会影响应该执行哪一条规则的决定. 从分析顺序来看, 前者触发了第二个动作指令, 而后者则同时触发了第一条和第三条动作指令. 在这一具体案例中, 程序的输出发生了相应的变化.

Bison通过将规则优先排列在语法中来解决归约/归减冲突；然而采用这种方法存在极大的风险。必须细致地考察每一个归减/回减冲突并通常予以消除。此处提供了一个可靠定义用于实现sequence的功能：

||

这里是另外一个产生归约/归约冲突的普通例子:

||

这里的目的是确定一个可以包含单词或重定向组的序列. sequence、words和redirects各自的定义都是没问题的, 但将它们放在一起会产生微妙的不同解释: 即使输入为空也可以被以无数种不同的方式解析出来.

考虑如下情况:没有任何内容时可以选择一个 \texttt{words} 作为基础。这种情况下有两种主要选择:一是将多个 \texttt{word} 符号连续排版,二是单独使用单个 \texttt{word} 符号作为独立元素。此外，在某些情况下可以选择一个 \texttt{word} 后跟三个 \texttt{redirect} 和另一个 \texttt{word}. 依此类推。

这有两种改正这些规则的方法. 第一,使它成为一个单层序列:

||

第二,防止words或者redirects为空:

||

5.7 神秘的归约/归约冲突-Mysterious Reduce/Reduce Conflicts

在某些情况下,看似不冲突的文法也可能引起归约冲突. 举个例子来说：

||

从这个文法的角度看,可以使用单一的向前扫描标记来进行分析.当解析器试图识别当前输入内容时,遇到的项目是para_spec.如果后续符号是另一个标识符ID,则当前结构属于类型;否则若紧随分号，则属于名称.换句话说,这种文法遵循LR(1)分析规则.

但是如同大多数分析器产生器一样,BISON实际上并不能处理所有的LR(1)文法. 在随后的上下文中极为相似的情况下, 即使是参数指定部分(param_spec)和返回指定部分(return_spec)中的某些结构,BISON也会认为它们是等价的. 由于相同的规则集活跃地用于归约到名称以及类型的行为,BISON在识别特定条件时缺乏足够的信息来区分这两种情况. 因此,BISON会错误地将这两种情形视为同一状态. 当这两种情况被结合时,Impact就会引发潜在冲突. 在分析器术语中, 这种现象表明该文法不属于LALR(1)范畴

一般而言,修补漏洞比将其记录在文档中更为明智. 然而,这一特殊的缺陷难以自我修复; 构建处理LR(1)文法的解析器生成器既复杂又容易导致庞大的解析器规模. 经过实践检验,Bison展现出显著优势.

当问题出现时, 你一般可以通过明确标识出两个容易混淆的分析器状态 并在此基础上引入能够显著区别它们的额外信息 来建立修复机制 在上述案例中 请通过向return_spec字段增加相应的约束条件来实现修复

||

对这个问题进行了修正。因为在return_spec起始处ID后的上下文中引入了一个可能的额外活动规则。这个规则本身并非活跃状态，在param_spec对应的环境中并未激活任何解析器。因此这两个环境分别采用了不同的解析器模式。只要始终不生成特定符号就不会影响解析输入的方法。

在这一特殊案例中,还存在另一种解决方法: 采用ID替代名称以重新制定返回规范. 这种做法也导致了两种混淆情况出现了不同的行为轨迹, 因为返回规范的行为主要作用于其自身的规则而非名称.

||

5.8 通用LR (GLR)分析-Generalized LR (GLR) Parsing

Bison生成了一种_确定性的_(deterministic)解析器。这种解析器依据先前输入及附加超前扫描符号摘要，在唯一的方式下决定何时以及如何进行归约。由此可知，通常情况下，Bison能够处理一种上下文无关文法所定义的语言。当遇到歧义文法时（即包含可采用多种归约路径的情况），无法采用确定性的解析器。同样的情况也适用于那些需要多个超前扫描符号的语言场景。最终，请参阅《神秘冲突-Mystery Conflicts》一章的相关讨论后可知，在某些语言中目前看来Bison在归纳输入方面仍存在不足之处。

当你在你的文法文件中使用`%glr-parser'声明时,Bison会生成一种基于不同算法的一般性通用LR(或GLR)解析器.这种类型的解析器被称为GLR解析器.每个普通的Bison解析器都采用相同的底层机制来进行常规操作;然而,当遇到无法通过优先级规则（参阅《优先级-Precedence》一章）解决的关键字移进/归约冲突,或者出现归约/归约冲突等情况时,该解析器会表现出与普通Bison解析器不同的行为.每当遇到此类复杂情况时,GLR解析器会高效地拆分成多个子解析器,每个子解析器分别对应于可能的移进动作或归约动作.这些子解析体通常会独立运行并采用同步处理的方式进行符号消费.某些情况下,这些子栈也会经历额外冲突进而进一步拆分.最终形成的一个Bison GLR解析栈相当于状态序列的一种高效替代结构.

实际上,每个栈都代表着一种关于正确分析的理解或假设. 当剩余输入出现时,可能暗示着某个猜想存在问题，在这种情况下那些不正确的思路会自然消亡. 此外，在处理过程中特定的行为会被暂时保留而不立即执行. 然而，在某个特定步骤中如果某项操作使两个堆达到等价状态那么它们各自的操作集合以及由此产生的结果都会被永久记录下来. 我们称这两个堆为等价关系的原因在于它们不仅代表着相同的运行状态序列，并且每一个对应的状态都能够生成相同的输入流片段

当一个分析器从具有多个分析状态转变为单一状态时，在完成之前保存的动作后（即动作集），该分析器将切换至常规LALR(1)解析算法。在这一转换过程中（即上述动作切换期间），栈上某些状态包含了一系列（实际上是多个）语义值的操作集；而解析器则试图从中选择一条已被%prec'声明指定并具有最高动态优先级的操作进行执行；如果可选操作未被明确排序，则当两个规则均使用%merge'声明相同的合并函数时（即采用相同合并策略），Bison会评估并解决这些操作后再调用合并函数以得到结果；否则系统将报告这种歧义情况。

通过在GLR分析树上采用这种数据结构是可行的。

希望了解关于GLR分析器的更多技术细节，请参考文献如下：Elizabeth Scott, Adrian Johnstone and Shamsa Sadaf Hussain, Tomita-Style Generalised LR Parsers, Royal Holloway, University of London, Department of Computer Science, TR-00-12, http://www.cs.rhul.ac.uk/research/languages/publications/tomita_style_1.ps, (2000-12-24).

5.9 内存管理以及防止溢出-Memory Management and Preventing Memory Overflow

如果过多的符号未被归并而导致无法移除，则会导致Bison解析栈溢出。当这种情况发生时, 解析器函数yyparse将返回一个非零值以暂停执行并调用yyerror函数来报告错误。

因为Bison分析器支持栈式的扩展。栈满通常主要源于采用右递归来代替左递归。参阅 递归规则-Recursive Rules.

通过设定宏YYMAXDEPTH变量,你可以调节在栈溢出前的最大深度. 建议我们采用正值来设定该变量. 该数值表示在未完成缩减（归约）前移入系统中的符号数量.

栈空间不需要一次性全部分配完成. 当指定一个较大的YYMAXDEPTH值时, 分析器会在初始化时预留一个较小内存块的空间. 随着阶段性的需求增加, 分析器会自动扩展栈容量. 增加内存块的空间分配是自动且无明显操作反馈的过程. 因此,对于普通情况下的内存管理需求来说, 无需特意将YYMAXDEPTH设置得很小即可满足要求.

然而, 我们同样应避免将YYMAXDEPTH设定为过大值以防止在计算栈容量时产生算术溢出. 同时我们必须确保不会将YYMAXDEPTH设为低于YYINITDEPTH的数值.

如果你没有定义YYMAXDEPTH,那么它的默认值是10000.

建议可靠地定义宏YYINITDEPTH为一个正值以控制栈初始分配的空间。只有当您使用支持变长数组的语言及其编译器时才需要考虑这一参数对于C语言LALR(1)解析器而言必须是一个静态常量。其默认设置为200。

避免使 YYINITDEPTH 过大从而在计算栈空间时出现溢出。同样需要注意的是,为了避免使 YYINITDEPTH 超过最大允许值 YYMAXDEPTH。

由于存在与现代编程语言之间的差异,C++语义下生成的基于现代编程语言构建工具无法自然地支持LALR(1)解析器的增长。注释:指栈无法自然增长。在此情况下（当我们选择使用现代编程语言编写解析器时），我们建议您增大YYINITDEPTH变量的值。在不远将来, 我们将推出解决此问题的相关内容。

6. 错误恢复-Error Recovery

对于大多数编程环境来说，无法容忍程序在遇到语法错误时突然退出运行.

对于那些将每条指令作为独立输入的一类交互式解析器来说，在遇到解析失误时应设计使其返回特定状态，并暂不处理后续指令（随后再进行解析）。
然而这对编译器而言并不足够完善, 因为其无法记住导致该错误的所有相关上下文信息。
因此，在处理编程语言代码时, 若在一个函数体内出现语法错误，则不应让编译器将后续代码视为从头开始解读。

为了恢复从语法错误中恢复, 你可以编写一个规则来识别特殊符号error. 这个术语通常已经被预先定义（无需显式声明）并用于错误处理中的术语. 每当出现语法错误时,Bison分析器都会生成一个带有标记符的异常信息. 如果你在当前语境中提供了针对此异常信息的处理逻辑, 分析过程将能够继续正常运行.

例如:

||

第四条规则指出了错误紧跟换行的情况，并对所有stmnts$实现了有效的添加。

当错误出现在某个表达式（exp）内部时会遇到什么情况？该恢复机制被准确描述为作用于单个语句（stmnts）、单个错误（error）以及精确的一行分隔符序列。当在一个表达式（exp）内部出现了一个错误时，栈中最后一个语句（stmnts）之后通常会包含一些额外标记或自我表达式；即，在下一个换行前可能有其他符号被读取。因此，该机制并非按照常规方法运作。

但是Bison能够通过舍弃部分语义背景以及一部分输入信息来强行适用这一规则（注：错误恢复规则）。首先，在栈上弹出状态以及对象直至重新达到可接受error的状态。（这表示已被解析过的子表达式被弹出，并且最终停留在最后一个完整的stmnts上。）此时将此错误标记移入工作区。随后，在旧超前扫描标记无法接纳接收到的新标记时（类似于读取记录那样），分析器会舍弃这些标记直至找到可接纳的第一个新标记。在这样的情况中，请注意删除的部分符号通常会导致内存泄漏问题，请参阅《释放已被删除符号》一节以获取更多相关信息。

在语法学领域中,错误恢复规则与策略之间的关系是等同的. 识别到一个错误后省略当前输入行的剩余内容是一个简单有效的策略：

||

用于已识别的一个左括号恢复匹配其相应的右括号也非常实用。
如果不进行配对,右括号未正确配对地出现可能会导致可能出现更为严重的问题信息提示。

||