Bison生成文件分析

Bison功能很强大，可以加参数-v可以生成可阅读的.output文件，还可以生成dot转换图

本文以lex yacc 创建一个桌面计算器为例子研究bison生成代码

所有介绍都以bison生成为准，通过-v生成*.output文件，通过设置#define YYDEBUG 1以及yydebug=1进行调制

文法

0 ACCEPT : OVER

1 OVER : E '\n'

2 E : E + T

3 E : T

4 T : T * F

5 T : F

6 F : ( E )

7 F : NUM

状态图

NUM

+

*

(

)

$

\n

E

F

T

OUT

def

0

ACC->.OVER

s1

s2

4

6

5

3

1

F->NUM.

r7

2

F->(.E)

s1

s2

7

6

5

3

ACC->OVER.

acc

4

OUT->e.'\n' E->E.+T

s10

s9

5

E->T. T->T.*F

s11

r3

6

T->F.

r5

7

E->E.+T F->(E.)

s10

s12

8

ACC->OVER end.

acc

9

OVER->E'\n'.

r1

10

E->E+.T

s1

s2

6

13

11

T->T*.F

s1

s2

14

12

F->(E).

r6

13

E->E+T. T->T.*F

s11

r2

14

T->T*F.

r4

3+2*5规约过程

	栈	符号	输入	动作
0	0	$	3+2*5\n$	shift1
1	0 1	$3	+2*5\n$	r7
2	0 6	$F	+2*5\n$	r5
3	0 5	$T	+2*5\n$	read->r3
4	0 4	$E	+2*5\n$	shift10
5	0 4 10	$E+	2*5\n$	shift1
6	0 4 10 1	$E+2	*5\n$	r7
7	0 4 10 6	$E+F	*5\n$	r5
8	0 4 10 13	$E+T	*5\n$	shift11
9	0 4 10 13 11	$E+T*	5\n$	shift1
10	0 4 10 13 11 1	$E+T*5	\n$	r7
11	0 4 10 13 11 14	$E+T*F	\n$	r4
12	0 4 10 13	$E+T	\n$	r2
13	0 4	$E	\n$	shift9
14	0 4 9	$E\n	$	r1
15	0 3	$OVER	$	over

源代码分析

yyprhs[] { } 产生式右端文法串在yyrhs中的开始位置

yyrhs[] { } 以-1隔开的产生式右端串

yyrline[] { 0, 8, 8, 9 } .y文件中产生式定义所在的行号，调试信息用

yyname[] {{0:$end}, {1:error}, {2:$undefined}, {3:NUM}, {4:'\n'}, {5:+}, {6:*}, {7:(}, {8:)}, {9:acc}, {10:OUT}, {11:E}, {12:T}, {13:F}, '\0' }

yytoknum[] { 0, 256, 257, 258, 10, 43, 42, 40, 41 }功能与yytranslate相同，token转化为标示符

yy1[] {}产生式左端符号的编号，阅读Bison生成的.output文件开头即可明白

yyr2[] { } 产生式右端长度，阅读Bison生成的.output文件开头即可明白，规约的时候从栈中弹出多少个状态用到

yydefact[] { } 对于每个状态的缺省规约表达式，对应于状态图中def这一列+1

yydefgoto[] { } 对于每个非终结符号，状态0情况下GOTO状态

yypact[] { } 如果某个状态只有默认动作，则为设置默认操作值，这儿是-6， 没有向前看token的情况下执行判断

yypgoto[] { }

yytable[] { }

yycheck[] { }

yystos[] { }

如果yypact值不为默认值，则yypact、yytoken、yytable、yycheck来确定状态转移，应该是用了某种压缩算法

规约以后状态转移根据yypgoto，判断采用yytable还是yydefgoto计算新的state

参考资源

以下是网上找到的资源，太不容易了

bison的实现中用到的表格：

1. yyrhs 和yyprhs一起表示产生式右端文法串，是一个用-1隔开的索引串大数组，串的内容是文法符号的编号
2. yyr1 产生式左端文法符号的编号
3. yyr2 产生式右端长度
4. yyrline 产生式的定义行
5. yyprhs 和yyrhs一起表示产生式右端文法串，内容为右端在yyrhs中的起始位置
6. yytname 文法符号的名称，必须用YYDEBUG条件编译
7. yytranslate 把flex返回的token编号翻译成bison的文法编号
8. yytoknum flex返回的token编号翻译成bison的token编号
9. yytable DFA状态转移表
10. yycheck 和yycheck等长的数组
11. yypgoto 非终结符号上的goto下个状态
12. yypact Index in YYTABLE of the portion describing STATE-NUM.
13. yydefact 缺省动作，长度为DFA的状态个数
14. yydefgoto 缺省goto，长度为非终结符号

实 际上BISON就是给我们造表，至于怎么用这个表是我们的事，这些好比是个瓤子，在这个瓤子外头套个毛衣，一个翻译程序就出来了。当然一般来说都是直接用 嵌在BISON里头的毛衣，这样就得到一个LALR(1)分析程序，BISON程序多半支持一个``-S''参数可以用来切换毛衣。

想 了想，明白为什么昨天搞的那个parse tree那么庞大了，因为那个语法是从c99手册扒出来的一点都没有改造过。c99为了严谨用的是优先级级联的无二义性的文法(所以c99里头用不着说明 什么优先级了)，这个文法的毛病就是实现太不方便，太多的单一产生式(右端只有一个文法符号的产生式)，所以parse tree打印出来就成了一个个很大的锯齿。反观gcc的语法文件就很不一样，引入优先级说明之后，文法变的很简单，所以分析树也得到了简化。

http://www.docin.com/p-483435351.html

介绍了gcc语法分析

yyprhs[] { 0, 0, 3, 7 } 产生式右端文法串在yyrhs中的开始位置，表示从第3、7项开始

yyrhs[] { 6, 0, -1, 6, 4, 3, -1, 3, -1 } 以-1隔开的产生式右端串

yydefact[] { 0, 3, 0, 1, 0, 2 } 对于每个状态的缺省规约表达式，0表示默认出错

yydefgoto[] { -1, 2 } 对于每个非终结符号的缺省GOTO

yypact[] { -2, -3, 0, -3, -1, -3 } -3:默认 没有向前看token的情况下执行判断

yypgoto[] { -3, -3 }

yytable[] { 3, 1, 5, 0, 4 }

yycheck[] { 0, 3, 3, -1, 4 }

yystos[] { 0, 3, 6, 0, 4, 3 }

Bison功能很强大，可以加参数-v可以生成可阅读的.output文件，还可以生成dot转换图

本文以lex yacc 创建一个桌面计算器为例子研究bison生成代码

所有介绍都以bison生成为准，通过-v生成*.output文件，通过设置#define YYDEBUG 1以及yydebug=1进行调制

文法

0 ACCEPT : OVER

1 OVER : E '\n'

2 E : E + T

3 E : T

4 T : T * F

5 T : F

6 F : ( E )

7 F : NUM

状态图

NUM

+

*

(

)

$

\n

E

F

T

OUT

def

0

ACC->.OVER

s1

s2

4

6

5

3

1

F->NUM.

r7

2

F->(.E)

s1

s2

7

6

5

3

ACC->OVER.

acc

4

OUT->e.'\n' E->E.+T

s10

s9

5

E->T. T->T.*F

s11

r3

6

T->F.

r5

7

E->E.+T F->(E.)

s10

s12

8

ACC->OVER end.

acc

9

OVER->E'\n'.

r1

10

E->E+.T

s1

s2

6

13

11

T->T*.F

s1

s2

14

12

F->(E).

r6

13

E->E+T. T->T.*F

s11

r2

14

T->T*F.

r4

3+2*5规约过程

	栈	符号	输入	动作
0	0	$	3+2*5\n$	shift1
1	0 1	$3	+2*5\n$	r7
2	0 6	$F	+2*5\n$	r5
3	0 5	$T	+2*5\n$	read->r3
4	0 4	$E	+2*5\n$	shift10
5	0 4 10	$E+	2*5\n$	shift1
6	0 4 10 1	$E+2	*5\n$	r7
7	0 4 10 6	$E+F	*5\n$	r5
8	0 4 10 13	$E+T	*5\n$	shift11
9	0 4 10 13 11	$E+T*	5\n$	shift1
10	0 4 10 13 11 1	$E+T*5	\n$	r7
11	0 4 10 13 11 14	$E+T*F	\n$	r4
12	0 4 10 13	$E+T	\n$	r2
13	0 4	$E	\n$	shift9
14	0 4 9	$E\n	$	r1
15	0 3	$OVER	$	over

源代码分析

yyprhs[] { } 产生式右端文法串在yyrhs中的开始位置

yyrhs[] { } 以-1隔开的产生式右端串

yyrline[] { 0, 8, 8, 9 } .y文件中产生式定义所在的行号，调试信息用

yyname[] {{0:$end}, {1:error}, {2:$undefined}, {3:NUM}, {4:'\n'}, {5:+}, {6:*}, {7:(}, {8:)}, {9:acc}, {10:OUT}, {11:E}, {12:T}, {13:F}, '\0' }

yytoknum[] { 0, 256, 257, 258, 10, 43, 42, 40, 41 }功能与yytranslate相同，token转化为标示符

yy1[] {}产生式左端符号的编号，阅读Bison生成的.output文件开头即可明白

yyr2[] { } 产生式右端长度，阅读Bison生成的.output文件开头即可明白，规约的时候从栈中弹出多少个状态用到

yydefact[] { } 对于每个状态的缺省规约表达式，对应于状态图中def这一列+1

yydefgoto[] { } 对于每个非终结符号，状态0情况下GOTO状态

yypact[] { } 如果某个状态只有默认动作，则为设置默认操作值，这儿是-6， 没有向前看token的情况下执行判断

yypgoto[] { }

yytable[] { }

yycheck[] { }

yystos[] { }

如果yypact值不为默认值，则yypact、yytoken、yytable、yycheck来确定状态转移，应该是用了某种压缩算法

规约以后状态转移根据yypgoto，判断采用yytable还是yydefgoto计算新的state

参考资源

以下是网上找到的资源，太不容易了

bison的实现中用到的表格：

1. yyrhs 和yyprhs一起表示产生式右端文法串，是一个用-1隔开的索引串大数组，串的内容是文法符号的编号
2. yyr1 产生式左端文法符号的编号
3. yyr2 产生式右端长度
4. yyrline 产生式的定义行
5. yyprhs 和yyrhs一起表示产生式右端文法串，内容为右端在yyrhs中的起始位置
6. yytname 文法符号的名称，必须用YYDEBUG条件编译
7. yytranslate 把flex返回的token编号翻译成bison的文法编号
8. yytoknum flex返回的token编号翻译成bison的token编号
9. yytable DFA状态转移表
10. yycheck 和yycheck等长的数组
11. yypgoto 非终结符号上的goto下个状态
12. yypact Index in YYTABLE of the portion describing STATE-NUM.
13. yydefact 缺省动作，长度为DFA的状态个数
14. yydefgoto 缺省goto，长度为非终结符号

实 际上BISON就是给我们造表，至于怎么用这个表是我们的事，这些好比是个瓤子，在这个瓤子外头套个毛衣，一个翻译程序就出来了。当然一般来说都是直接用 嵌在BISON里头的毛衣，这样就得到一个LALR(1)分析程序，BISON程序多半支持一个``-S''参数可以用来切换毛衣。

想 了想，明白为什么昨天搞的那个parse tree那么庞大了，因为那个语法是从c99手册扒出来的一点都没有改造过。c99为了严谨用的是优先级级联的无二义性的文法(所以c99里头用不着说明 什么优先级了)，这个文法的毛病就是实现太不方便，太多的单一产生式(右端只有一个文法符号的产生式)，所以parse tree打印出来就成了一个个很大的锯齿。反观gcc的语法文件就很不一样，引入优先级说明之后，文法变的很简单，所以分析树也得到了简化。

http://www.docin.com/p-483435351.html

介绍了gcc语法分析

yyprhs[] { 0, 0, 3, 7 } 产生式右端文法串在yyrhs中的开始位置，表示从第3、7项开始

yyrhs[] { 6, 0, -1, 6, 4, 3, -1, 3, -1 } 以-1隔开的产生式右端串

yydefact[] { 0, 3, 0, 1, 0, 2 } 对于每个状态的缺省规约表达式，0表示默认出错

yydefgoto[] { -1, 2 } 对于每个非终结符号的缺省GOTO

yypact[] { -2, -3, 0, -3, -1, -3 } -3:默认 没有向前看token的情况下执行判断

yypgoto[] { -3, -3 }

yytable[] { 3, 1, 5, 0, 4 }

yycheck[] { 0, 3, 3, -1, 4 }

yystos[] { 0, 3, 6, 0, 4, 3 }