GNU Bison 2.3：Yacc兼容的解析器生成器手册

4星 · 超过85%的资源需积分: 9 152 浏览量更新于2024-08-02 收藏 763KB PDF 举报

"GNU Bison 手册，一本关于 Bison（一个 Yacc 兼容的解析器生成器）的好书。" GNU Bison 是一个强大的工具，它允许开发者根据上下文无关文法（Context-Free Grammar, CFG）生成解析器。这个手册详细介绍了 Bison 的使用方法和原理，适合对编译原理和解析技术感兴趣的开发者。手册由 Charles Donnelly 和 Richard Stallman 编写，版本为 2.3，发布于2006年5月30日。 Bison 是 GNU 项目的一部分，其设计灵感来源于 AT&T 的 Yacc（Yet Another Compiler-Compiler）。Yacc 是一种经典的解析器生成器，而 Bison 则是它的开源实现，提供了更多的功能和更灵活的选项。Bison 支持 C 和 C++ 语言，生成的解析器可以用于处理各种语言的语法分析，例如编程语言、配置文件格式或者数据交换格式等。手册内容可能包括以下几个主要部分： 1. **基础概念**：介绍什么是解析器、上下文无关文法的基本概念以及它们在编译器和解释器中的作用。解析器是将源代码或输入数据转换为抽象语法树（AST）的关键组件。 2. **Bison 语法**：详细阐述 Bison 文件的结构，包括 `%token`、`%nonterminal`、`%start`、`%%` 分隔符的用法，以及如何定义规则来描述文法规则。 3. **动作和语义值**：讲解如何在 Bison 规则中添加 C 或 C++ 代码来处理文法符号的结合性和优先级，以及如何通过语义值（yyval 和 yylval）传递解析结果。 4. **错误处理**：解释如何处理解析错误，包括自定义错误消息和错误恢复机制。 5. **预定义的符号和函数**：列出 Bison 提供的预定义符号和函数，如 `yyerror()` 用于报告语法错误，`yylex()` 用于词法分析。 6. **调试和测试**：指导如何使用 Bison 的调试选项和工具，如 `-d` 选项生成解析器的辅助文件，以及如何使用 `yydebug` 进行调试。 7. **性能优化**：讨论如何优化生成的解析器，减少内存消耗和提高解析速度。 8. **高级特性**：涵盖如条件语法制导文法、多语法制导文法、用户自定义的文法属性等高级话题。 9. **与其他 GNU 工具的集成**：介绍如何将 Bison 生成的解析器与 Flex（词法分析器生成器）配合使用，以及如何与 GNU Autoconf 和 Automake 等构建系统工具协同工作。 10. **附录和参考**：包含 Bison 的完整命令行选项列表、文法语法的详细规范，以及 GNU Free Documentation License 的副本。通过学习这本手册，开发者不仅可以掌握 Bison 的使用，还能深入理解解析理论和编译器构造。这对于那些想要编写自己的编程语言、解析复杂数据格式或者优化已有解析器的人来说是非常宝贵的资源。

10 Bison 2.3

Appendix: How to Apply These Terms to Your New

Programs

If you develop a new program, and you want it to be of the greatest possible use to the public,

the bes t way to achieve this is to make it free software which everyone can redistribute and

change under these terms.

To do so, attach the following notices to the program. It is safest to attach them to the

start of e ach source ﬁle to most eﬀectively convey the exclusion of warranty; and each ﬁle

should have at least the “copyright” line and a pointer to where the full notice is found.

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

This program is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation; either version 2 of the License, or

(at your option) any later version.

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

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

If the program is interactive, make it output a short notice like this when it starts in an

interactive m ode:

Gnomovision version 69, Copyright (C) 19yy name of author

Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type ‘show w’.

This is free software, and you are welcome to redistribute it

under certain conditions; type ‘show c’ for details.

The hypothetical commands ‘show w’ and ‘show c’ should show the appropriate parts of

the General Public License. Of course, the commands you use may be called something

other than ‘show w’ and ‘show c’; they could even be mouse-clicks or menu items—whatever

suits your program.

You should also get your employer (if you work as a programmer) or your school, if any,

to sign a “copyright disclaimer” for the program, if necessary. Here is a sample; alter the

names:

Yoyodyne, Inc., hereby disclaims all copyright interest in the program

‘Gnomovision’ (which makes passes at compilers) written by James Hacker.

signature of Ty Coon, 1 April 1989

Ty Coon, President of Vice

This General Public License does not permit incorporating your program into proprietary

programs. If your program is a subroutine library, you may consider it more useful to permit

linking proprietary applications with the library. If this is what you want to do, use the

GNU Library General Public License instead of this License.

Chapter 1: The Concepts of Bison 11

1 The Concepts of Bison

This chapter introduces many of the basic concepts without which the details of Bison will

not make sense. If you do not already know how to use Bison or Yacc, we suggest you start

by reading this chapter carefully.

1.1 Languages and Context-Free Grammars

In order for Bison to parse a language, it must be des cribed by a context-free grammar.

This means that you specify one or more syntactic groupings and give rules for constructing

them from their parts. For example, in the C language, one kind of grouping is called an

‘expression’. One rule for making an expression might be, “An expression can be made of a

minus sign and another expression”. Another would be, “An expression can be an integer”.

As you can see, rules are often recursive, but there must be at least one rule which leads

out of the recursion.

The most common formal system for presenting such rules for humans to read is Backus-

Naur Form or “BNF”, which was developed in order to specify the language Algol 60. Any

grammar expressed in BNF is a context-free grammar. The input to Bison is essentially

machine-readable BNF.

There are various important subclasses of context-free grammar. Although it can handle

almost all context-free grammars, Bison is optimized for what are called LALR(1) grammars.

In brief, in these grammars, it must be possible to tell how to parse any portion of an input

string with just a single token of look-ahead. Strictly speaking, that is a description of

an LR(1) grammar, and LALR(1) involves additional restrictions that are hard to explain

simply; but it is rare in actual practice to ﬁnd an LR(1) grammar that fails to be LALR(1).

See Section 5.7 [Mysterious Reduce/Re duce Conﬂicts], page 77, for more information on

this.

Parsers for LALR(1) grammars are deterministic, meaning roughly that the next gram-

mar rule to apply at any point in the input is uniquely determined by the preceding input

and a ﬁxed, ﬁnite portion (called a look-ahead) of the remaining input. A context-free gram-

mar can be ambiguous, meaning that there are multiple ways to apply the grammar rules to

get the same inputs. Even unambiguous grammars can be nondeterministic, meaning that

no ﬁxed look-ahead always suﬃces to determine the next grammar rule to apply. With the

proper declarations, Bison is also able to parse these more general context-free grammars,

using a technique known as GLR parsing (for Generalized LR). Bison’s GLR parsers are able

to handle any context-free grammar for which the number of possible parses of any given

string is ﬁnite.

In the formal grammatical rules for a language, each kind of syntactic unit or grouping

is named by a symbol. Those which are built by grouping smaller constructs according

to grammatical rules are called nonterminal symbols; those which can’t be subdivided

are called terminal symbols or token types. We call a piece of input corresponding to a

single terminal symbol a token, and a piece corresponding to a single nonterminal symbol

a grouping.

We can use the C language as an example of what symbols, terminal and nonterminal,

mean. The tokens of C are identiﬁers, constants (numeric and string), and the various key-

words, arithmetic operators and punctuation marks. So the terminal symbols of a grammar

12 Bison 2.3

for C include ‘identiﬁer’, ‘number’, ‘string’, plus one symbol for each keyword, operator

or punctuation mark: ‘if’, ‘return’, ‘const’, ‘static’, ‘int’, ‘char’, ‘plus-sign’, ‘open-brace’,

‘close-brace’, ‘comma’ and many more. (These tokens can be subdivided into characters,

but that is a matter of lexicography, not grammar.)

Here is a simple C function subdivided into tokens:

int /* keyword ‘int’ */

square (int x) /* identiﬁer, open-paren, keyword ‘int’, identiﬁer, close-paren */

{ /* open-brace */

return x * x; /* keyword ‘return’, identiﬁer, asterisk, identiﬁer, semicolon */

} /* close-brace */

The syntactic groupings of C include the expression, the statement, the declaration,

and the function deﬁnition. These are represented in the grammar of C by nonterminal

symbols ‘expression’, ‘statement’, ‘declaration’ and ‘function deﬁnition’. The full grammar

uses dozens of additional language constructs, each with its own nonterminal symbol, in

order to express the meanings of these four. The example above is a function deﬁnition;

it contains one declaration, and one statement. In the statement, each ‘x’ is an expression

and so is ‘x * x’.

Each nonterminal symbol must have grammatical rules showing how it is made out of

simpler constructs. For example, one kind of C statement is the return statement; this

would be described with a grammar rule which reads informally as follows:

A ‘statement’ can be made of a ‘return’ keyword, an ‘expression’ and a ‘semi-

colon’.

There would be many other rules for ‘stateme nt’, one for each kind of statement in C.

One nonterminal symbol must be distinguished as the special one which deﬁnes a com-

plete utterance in the language. It is called the start symbol. In a compiler, this means a

complete input program. In the C language, the nonterminal symbol ‘sequence of deﬁnitions

and declarations’ plays this role.

For example, ‘1 + 2’ is a valid C expression—a valid part of a C program—but it is not

valid as an entire C program. In the context-free grammar of C, this follows from the fact

that ‘expression’ is not the start symbol.

The Bison parser reads a sequence of tokens as its input, and groups the tokens using the

grammar rules. If the input is valid, the end result is that the entire token sequence reduces

to a single grouping whose symbol is the grammar’s start symbol. If we use a grammar for

C, the entire input must be a ‘sequence of deﬁnitions and declarations’. If not, the parser

reports a syntax error.

1.2 From Formal Rules to Bison Input

A formal grammar is a mathematical construct. To deﬁne the language for Bison, you must

write a ﬁle expressing the grammar in Bison syntax: a Bison grammar ﬁle. See Chapter 3

[Bison Grammar Files], page 41.

A nonterminal symbol in the formal grammar is represented in Bison input as an iden-

tiﬁer, like an identiﬁer in C. By convention, it should be in lower case, such as expr, stmt

or declaration.

Chapter 1: The Concepts of Bison 13

The Bison representation for a terminal symbol is also called a token type. Token types

as well can be represented as C-like identiﬁers. By convention, these identiﬁers should be

upper case to distinguish them from nonterminals: for example, INTEGER, IDENTIFIER,

IF or RETURN. A terminal symbol that stands for a particular keyword in the language

should be named after that keyword converted to upper case. The terminal symbol error

is reserved for error recovery. See Section 3.2 [Symbols], page 42.

A terminal symbol can also be represented as a character literal, just like a C character

constant. You should do this whenever a token is just a single character (parenthesis,

plus-sign, etc.): use that same character in a literal as the terminal symbol for that token.

A third way to represent a terminal symbol is with a C string constant containing several

characters. See Section 3.2 [Symbols], page 42, for more information.

The grammar rules also have an expression in Bison syntax. For example, here is the

Bison rule for a C return statement. The semicolon in quotes is a literal character token,

representing part of the C syntax for the statement; the naked semicolon, and the colon,

are B ison punctuation used in every rule.

stmt: RETURN expr ’;’

;

See Section 3.3 [Syntax of Grammar Rules], page 44.

1.3 Semantic Values

A formal grammar selects tokens only by their classiﬁcations: for example, if a rule mentions

the terminal symbol ‘integer constant’, it means that any integer constant is grammatically

valid in that position. The precise value of the constant is irrelevant to how to parse the

input: if ‘x+4’ is grammatical then ‘x+1’ or ‘x+3989’ is equally grammatical.

But the precise value is very important for what the input means once it is parsed.

A compiler is useless if it fails to distinguish between 4, 1 and 3989 as constants in the

program! Therefore, each token in a Bison grammar has both a token type and a semantic

value. See Section 3.5 [Deﬁning Language Semantics], page 46, for details.

The token type is a terminal symbol deﬁned in the grammar, such as INTEGER,

IDENTIFIER or ’,’. It tells everything you need to know to decide where the token may

validly appear and how to group it with other tokens. The grammar rules know nothing

about tokens except their types.

The semantic value has all the rest of the information about the meaning of the token,

such as the value of an integer, or the name of an identiﬁer. (A token such as ’,’ which is

just punctuation doesn’t need to have any semantic value.)

For example, an input token might be classiﬁed as token type INTEGER and have the

semantic value 4. Another input token might have the same token type INTEGER but

value 3989. When a grammar rule says that INTEGER is allowed, either of these tokens is

acceptable because each is an INTEGER. When the parser accepts the token, it keeps track

of the token’s semantic value.

Each grouping can also have a semantic value as well as its nonterminal symbol. For

example, in a calculator, an expression typically has a semantic value that is a number. In

a compiler for a programming language, an expression typically has a semantic value that

is a tree structure describing the meaning of the expression.

14 Bison 2.3

1.4 Semantic Actions

In order to be useful, a program must do more than parse input; it must also produce some

output based on the input. In a Bison grammar, a grammar rule can have an action made

up of C statements. Each time the parser recognizes a match for that rule, the action is

executed. See Section 3.5.3 [Actions], page 47.

Most of the time, the purpose of an action is to compute the semantic value of the whole

construct from the semantic values of its parts. For example, suppose we have a rule which

says an expression can be the sum of two expressions. When the parser recognizes such a

sum, each of the subexpressions has a s em antic value which describes how it was built up.

The action for this rule should create a similar sort of value for the newly recognized larger

expression.

For example, here is a rule that says an expression can be the sum of two subexpressions:

expr: expr ’+’ expr { $$ = $1 + $3; }

;

The action says how to produce the semantic value of the s um expression from the values

of the two subexpressions.

1.5 Writing GLR Parsers

In some grammars, Bison’s standard LALR(1) parsing algorithm cannot decide whether

to apply a certain grammar rule at a given point. That is, it may not be able to decide

(on the basis of the input read so far) which of two possible reductions (applications of a

grammar rule) applies, or whether to apply a reduction or read more of the input and apply

a reduction later in the input. These are known respectively as reduce/reduce conﬂicts

(see Section 5.6 [Reduce/Reduce], page 76), and shift/reduce conﬂicts (see Section 5.2

[Shift/Reduce], page 72).

To use a grammar that is not easily m odiﬁed to be LALR(1), a more general parsing

algorithm is sometimes necessary. If you include %glr-parser among the Bison declarations

in your ﬁle (see

Section 3.1 [Grammar Outline], page 41), the result is a Generalized LR

(GLR) parser. These parsers handle Bison grammars that contain no unresolved conﬂicts

(i.e., after applying precedence declarations) identically to LALR(1) parsers. However, when

faced with unresolved shift/reduce and reduce/reduce conﬂicts, GLR parsers use the simple

expedient of doing both, eﬀectively cloning the parser to follow both possibilities. Each of

the resulting parsers can again split, so that at any given time, there can be any number

of possible parses being explored. The parsers proceed in lockstep; that is, all of them

consume (shift) a given input symbol before any of them proceed to the next. Each of the

cloned parsers eventually meets one of two possible fates: either it runs into a parsing error,

in which c ase it simply vanishes, or it merges with another parser, because the two of them

have reduced the input to an identical set of symbols.

During the time that there are multiple parsers, semantic actions are recorded, but not

performed. When a parser disappears, its recorded semantic actions disappear as well, and

are never performed. When a reduction makes two parsers identical, causing them to merge,

Bison records both sets of semantic actions. Whenever the last two parsers merge, reverting

to the single-parser case, Bison resolves all the outstanding actions either by precedences

given to the grammar rules involved, or by performing both actions, and then calling a

剩余143页未读，继续阅读

zfmxy_public3

粉丝: 0
资源: 1

GNU Bison 2.3：Yacc兼容的解析器生成器手册

GNU Bison 中文手册

GNU Make Manual

词法分析器的实现GNU Bison 中文手册

gnu的maven依赖

gnu emacs lisp reffrence manual

flex/bison 在线编译器

ubuntu安装bison安装失败

手把手 flex bison

centos7如何源码编译bison

flex与bison

最新资源