kk Blog —— 通用基础


date [-d @int|str] [+%s|"+%F %T"]
netstat -ltunp
sar -n DEV 1

构造LR(1)项目集，生成LR(1)分析表、进行相应的语法分析

贴自这里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

引言...........................................................  2
第一章 概述...................................................  3
  1.1设计内容............................................  3
  1.2设计要求............................................  3
第二章 设计的基本原理.........................................  3
  2.1 CLOSURE(I)的构造...................................  3
  2.2 GO(I,X)的构造......................................  3
  2.3 FIRST集合的构造....................................  3
  2.4 LR（1）分析表的构造........................ .......  3
第三章 程序设计..............................................  4
  3.1总体方案设计........................................  4
  3.2各模块设计...........................................  5
      3.2.1读入模块：Read_G().........................  5
      3.2.2 计算FIRST模块：get_first() ..............  5
      3.2.3 判断项目数否在项目集里：is_in(proj temp,int T)...  5
      3.2.4 获得计算closure(I)时需要的First(βa)：gete_expc(proj temp)...  5
      3.2.5 项目集的CLOSURE计算：e_closure(int T) .... 5
      3.2.6 检查项目集是否已经在项目集族里：is_contained()... 6
      3.2.7 GO()函数的实现：go(). ..................  6
      3.2.8 LR(1)分析表的构造：get_action().........  6
      3.2.9　对输入串的语法分析：在main()中实现 ..... 6
第四章 程序测试............................................... 6
  4.1 课本115页文法的LR(1) 分析器的构造和语法分析.......... 6
  4.2 表达式文法的LR(1)分析器的构造和语法分析.............. 7
第五章 结论.................................................... 9
参考文献........................................................ 9
附录    程序清单................................................ 10

引言

《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计思想。通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。

我选择的是老师给的第31题，并予以扩充。即对任意给定的文法G构造LR(1)项目集规范族，其中要实现CLOSURE(I)、GO(I,X)、FIRST集合等。在此基础上，构造了LR（1）分析表。然后对输入的句子进行语法分析，给出接受或出错报告。程序采用文件输入输出方式。其中包括两个输入文件：文法grammar.txt，以及输入串input.txt；两个输出文件：项目集items.txt和文法的LR(1)分析表action_table.txt。由于语法分析的结果只给出接受或错误报告，比较简单。所以直接在屏幕上输出，也便于用户查看。

在具体编写程序过程中，对文法操作的各个功能模块独立成为一个子程序，而对具体输入串的分析则放在main()函数中进行。各个变量及函数的意义和用法我将在叙述程序设计的总体方案中详细给出。

程序的总体算法思想来自《编译原理》课程。具体实现由我独立完成。程序用C/C++语言编写。在Microsoft Visual C++ 2005环境下调试通过。

第一章 概述

1.1 设计内容

对任意给定的上下文无关文法G，构造其LR（1）项目集族，并且在此基础上进一步构造其LR（1）分析表。然后分析输入的“句子”。

1.2 设计要求

对输入的文法G（要求是上下文无关文法）,在程序中实现CLOSURE(I)、GO(I,X)、FIRST等的构造，并利用这些功能函数构造出LR(1)项目集族。并且输出结果。在此基础上构造出G的LR(1)分析表（这个表也输出给用户），并对输入的“句子”进行语法分析，给出分析结果。

第二章 设计的基本原理

2.1 CLOSURE(I)的构造

CLOSURE(I)表示和I中项目可以识别同样活前缀的所有项目的集合。它可以由以下方法得到：
⑴ I中的所有项目都属于CLOSURE(I)；
⑵ 若项目[A→α·Bβ,a]属于CLOSURE(I)，B→ξ是一个产生式，那么，对于FIRST（βa）中的每一个终结符b，如果[B→·ξ，b]原来不在CLOSURE(I)中，则把它加进去；
⑶ 重复执行步骤⑵，直到CLOSURE(I)不再增大为止。

2.2 GO(I,X)的构造

GO(I,X) = CLOSURE(J)
其中 J={任何形如[A→αX·β,a]的项目|[A→α·Xβ,a]属于I}

2.3 FIRST集合的构造

在这个程序中使用的是FIRST（βa），这基于每一个非终结符的FIRST集合（终结符的FIRST就是它本身）。所以需要对每一个非终结符构造其FIRST集合。方法如下：
连续使用下面的规则，直到每个集合FIRST不再增大为止。
⑴ 若X属于VT，则FIRST（X）= {X}。
⑵ 若X属于VN，且有产生式X→a…，则把a加入到FIRST（X）中；若X→ε也是一条产生式，则把ε也加入到FIRST（X）中。
⑶　若X→Y…是一个产生式且Y属于VN，则把FIRST（Y）中的所有非ε元素都加入到FIRST（X）中；若X→Y1Y2…Yk是一个产生式，Y1，…,Yｉ－１都是非终结符，而且，对于任何j,１<= j <= i-1，FIRST(YJ)都含有ε（即Y1…Yｉ－１=­­­>ε）,则把FIRST(Yi)中的所有非ε元素都加入到FIRST(X)中；特别的，若所有的FIRST(YJ)都含有ε,j=1,2,3…k,则把ε加入到FIRST(X)中。

2.4 LR（1）分析表的构造

在实现GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后，再扫描所有的项目集，找到其中包含归约项目的那些项目集，根据其中的项目，得到分析表中那些归约的部分。

第三章 程序设计

3.1总体方案设计

在main()函数中读入文法。并对文法进行扩展，同时记录下文法的所有终结符和非终结符。对每一个非终结符计算它的FIRST集合。以备在计算CLOSURE(I)时使用。然后，调用GO（）函数。完成LR（1）项目集族的计算。计算的结果记录到items.txt中。并且记录下状态之间的转换关系。接下来，调用get_action()根据上面的项目集族和记录的状态转换数组获得LR（1）分析表。然后就可以对输入的句子进行语法检查。程序中主要变量以及函数的说明如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

char G[20][20];                  存放输入的文法；为简单起见，设文法的产生式条数不  多于20条，每个产生式不多与20个字符，用@表示ε，且产生式输入的时候要以$结束
int  length[20];              每条产生式的长度
int  number = 0;              产生式的条数
bool tempofinput[150];            记录哪些ASCII字符在文法中，以求得所有的VN和VT
char str_vn[20];              记录所有的非终结符
int  size_vn = 0;             记录非终结符的个数
char str_vt[150];             记录所有的终结符
int  size_vt = 0;             记录终结符的个数
bool first_vn[30][150];           记录每个非终结符的first集合
char buffer[50];              用来存放CLOSURE(I)时需要的first_set 也用来读入用户的输入串
int  bsize = 0;                   buffer的有效长度
struct thri{
  int  beg;
  int  nex;
  char ch;
};                                定义状态转换数组中的元素格式
thri trans[200];              用来在GO（）函数中记录状态间的转换
int  size_trans = 0;          trans数组的大小
struct proj{
  int formula_numb;
  int part;
  char expc;
};                                定义项目集的格式
proj items[100][100];         项目集数组，假设项目集的个数不超过100个，且每个项目集中的项目个数不超过100个
int  Ccount = 0;              项目集的个数
int  size_item[100];          每个项目集中项目的个数
struct action{
  char  ch;
  int   nxt_sta;
};                                定义状态转换表的格式
action    action_table[100][100]; 状态转换表
int   size_act_table[100];        状态转换表的大小
ifstream G_ifile;             输入文法的文件指针
ifstream input_ifile;         输入句子的文件指针
ofstream items_ofile;         输出项目集族的文件指针
ofstream act_ofile;               输出转换表的文件指针
void Read_G()                 读入文法的子程序模块
void get_first()              计算每一个非终结符的first集合
bool is_in(proj temp,int T)       判断项目temp是否已经在项目集族items[T]中
void gete_expc(proj temp)     计算在生成CLOSURE(I)时用到的FIRST（βa）
void e_closure(int T)         计算items[T]的closure闭包
int is_contained()                判断新生成的项目集是否已经在项目集族中
void go()                     实现GO（I，X）的功能
void get_action()             生成LR(1)表
int main()                        调用各个字模块，并在其中对输入串进行语法分析

3.2各模块设计

3.2.1 读入模块：Read_G()

文法要为上下文无关文法。输入文件的格式为：首先输入产生式的条数；每条产生式的第一个字符为非终结符。以$结尾。输入的同时用tempofinput[temp] = true来记录字符temp。为统计有哪些非终结符和终结符作准备。这些都通过ASCLL码对应位是否为true来判断。

3.2.2 计算FIRST模块：get_first()

先设置flag1表示本轮扫描first_vn中有没有新增加的内容。要是有，还要进行下一次扫描。每一轮扫描所有的产生式，在扫描每一个产生式的时候，设置一个下标指针t用来保证不会扫过本产生式，还设置flag2表示t的位置是否是一个可以推导出ε的非终结符。是的话，还要进行下一个t位置的检查。如果t走到产生式的最后位置的下一个位置，则表明ε属于此产生式左边非终结符的FIRST集合；

3.2.3 判断项目数否在项目集里：is_in(proj temp,int T)

Scan项目集原有的每一个项目，和新生成的项目作比较。若有相同的就返回true,否则返回false

3.2.4 获得计算closure(I)时需要的First(βa)：gete_expc(proj temp)

设置flag表示是否还要进行下一轮计算（即此次处理的为非终结符且它的FIRST中有ε），若处理的位置已经超过了产生式的长度，则直接把项目中的那个搜索字符添加进去。这个模块的返回结果放在buffer数组中。

3.2.5 项目集的CLOSURE计算：e_closure(int T)

在Go()函数中会生成items[T]的一些基本项目。对items[T]中已经有的每一个项目检查在”·”之后的是否为非终结符；若是，则计算FIRST（βa），把每一个buffer中的元素和相应的产生式构成一个项目，加入到项目集中。（注意，此时的项目集的大小是随着项目的不断加入而变大的，所以可以用for循环保证项目集中不会有遗漏。）

3.2.6 检查项目集是否已经在项目集族里：is_contained()

把已经有的项目集和新生成的项目集进行比较，要是有相等的话则表示已经存在相同的项目集合，此时返回相同的那个项目集的编号。否则，返回0。

3.2.7 GO()函数的实现：go()

第一步制作一个初始项目（即拓展文法的第一条产生式），然后用e_closure构造项目集0。在程序中Ccount 作为项目集的计数从0开始到n(包括n)，所以在for循环中是<= Ccount。即扫描每一个项目集，对每一个项目在”·”之后的终结符，向后移动一位“·”的位置生成新的项目，暂存在buf数组中。然后，预生成项目集，并且求其CLOSURE，再判断新的项目集是否已经存在，若存在了，就撤销这个项目集，并设置相应的trans。否则就生成新的项目集，也设置相应的trans。在以上过程中，每次确定生成一个项目集的时候都把它输出到items.txt中。

3.2.8 LR(1)分析表的构造：get_action()

Scan每一个项目集，若其中有规约项目，则转换表增加一个归约项（用负值表示）。然后，根据trans数组中的元素，构造转换表中的移进项（用正值表示）。 接受项目也是一个归约项，用0表示。生成的转换表输出到action_table.txt中。

3.2.9　对输入串的语法分析：在main()中实现

用stack模拟语法分析的过程，先在stack中放入（０，＃），然后，用当前栈顶状态和当前输入字符查找action_table。根据action_table中的值的情况做相应处理（即执行移进和归约动作）。若遇到接受项目则给出接受提示，程序结束。若遇到出错的情况给出出错提示，也结束程序。

第四章 程序测试

本程序在Dev-C++和Microsoft Visual C++ 2005中调试通过。下面给出两个调试实例：

4.1 课本115页文法的LR(1) 分析器的构造和语法分析

输入文法：

1

3    EBB$    BaB$    Bb$

生成的项目集族：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

I0:
0 , 1 , #
1 , 1 , #
2 , 1 , a
2 , 1 , b
3 , 1 , a
3 , 1 , b
I5:
2 , 3 , a
2 , 3 , b
I2:
3 , 2 , a
3 , 2 , b
I7:
3 , 2 , #
I4:
0 , 2 , #
I9:
2 , 3 , #
I3:
1 , 2 , #
2 , 1 , #
3 , 1 , #
I8:
1 , 3 , #
I1:
2 , 2 , a
2 , 2 , b
2 , 1 , a
3 , 1 , a
2 , 1 , b
3 , 1 , b
I6:
2 , 2 , #
2 , 1 , #
3 , 1 , #

生成的转换表：

1
2
3

(0,a,1) (0,b,2)　(0,B,3)　(0,E,4)　(1,a,1)　(1,b,2)　(1,B,5)
(2,a,-3)　(2,b,-3)　(3,a,6)　(3,b,7)　(3,B,8)　(4,#,0)　(5,a,-2)
(5,b,-2)　(6,a,6)　(6,b,7)　(6,B,9)　(7,#,-3)　(8,#,-1)

输入句子测试：
输入句子：aaaabab#
输出截图：
输入句子：abbab#
输出截图：

4.2 表达式文法的LR(1)分析器的构造和语法分析

输入文法：

1

6    EE+T$   ET$ TT*F$   TF$ F(E)$   Fi$

生成的项目集族：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

I0:
0 , 1 , #
1 , 1 , #
2 , 1 , #
1 , 1 , +
2 , 1 , +
3 , 1 , #
4 , 1 , #
3 , 1 , +
4 , 1 , +
3 , 1 , *
4 , 1 , *
5 , 1 , #
6 , 1 , #
5 , 1 , +
6 , 1 , +
5 , 1 , *
6 , 1 , *
I1:
5 , 2 , #
5 , 2 , +
5 , 2 , *
1 , 1 , )
2 , 1 , )
1 , 1 , +
2 , 1 , +
3 , 1 , )
4 , 1 , )
3 , 1 , +
4 , 1 , +
3 , 1 , *
4 , 1 , *
5 , 1 , )
6 , 1 , )
5 , 1 , +
6 , 1 , +
5 , 1 , *
6 , 1 , *
I2:
6 , 2 , #
6 , 2 , +
6 , 2 , *
I3:
0 , 2 , #
1 , 2 , #
1 , 2 , +
I4:
4 , 2 , #
4 , 2 , +
4 , 2 , *
I7:
6 , 2 , )
6 , 2 , +
6 , 2 , *
I6:
5 , 2 , )
5 , 2 , +
5 , 2 , *
1 , 1 , )
2 , 1 , )
1 , 1 , +
2 , 1 , +
3 , 1 , )
4 , 1 , )
3 , 1 , +
4 , 1 , +
3 , 1 , *
4 , 1 , *
5 , 1 , )
6 , 1 , )
5 , 1 , +
6 , 1 , +
5 , 1 , *
6 , 1 , *
I5:
2 , 2 , #
2 , 2 , +
3 , 2 , #
3 , 2 , +
3 , 2 , *
I10:
2 , 2 , )
2 , 2 , +
3 , 2 , )
3 , 2 , +
3 , 2 , *
I8:
5 , 3 , #
5 , 3 , +
5 , 3 , *
1 , 2 , )
1 , 2 , +
I9:
4 , 2 , )
4 , 2 , +
4 , 2 , *
I11:
1 , 3 , #
1 , 3 , +
3 , 1 , #
4 , 1 , #
3 , 1 , +
4 , 1 , +
3 , 1 , *
4 , 1 , *
5 , 1 , #
6 , 1 , #
5 , 1 , +
6 , 1 , +
5 , 1 , *
6 , 1 , *
I12:
3 , 3 , #
3 , 3 , +
3 , 3 , *
5 , 1 , #
6 , 1 , #
5 , 1 , +
6 , 1 , +
5 , 1 , *
6 , 1 , *
I14:
5 , 4 , #
5 , 4 , +
5 , 4 , *
I13:
5 , 3 , )
5 , 3 , +
5 , 3 , *
1 , 2 , )
1 , 2 , +
I15:
1 , 3 , )
1 , 3 , +
3 , 1 , )
4 , 1 , )
3 , 1 , +
4 , 1 , +
3 , 1 , *
4 , 1 , *
5 , 1 , )
6 , 1 , )
5 , 1 , +
6 , 1 , +
5 , 1 , *
6 , 1 , *
I16:
3 , 3 , )
3 , 3 , +
3 , 3 , *
5 , 1 , )
6 , 1 , )
5 , 1 , +
6 , 1 , +
5 , 1 , *
6 , 1 , *
I17:
1 , 4 , #
1 , 4 , +
3 , 2 , #
3 , 2 , +
3 , 2 , *
I18:
3 , 4 , #
3 , 4 , +
3 , 4 , *
I19:
5 , 4 , )
5 , 4 , +
5 , 4 , *
I20:
1 , 4 , )
1 , 4 , +
3 , 2 , )
3 , 2 , +
3 , 2 , *
I21:
3 , 4 , )
3 , 4 , +
3 , 4 , *

生成的转换表：

1
2
3
4
5
6
7
8
9
10

(0,(,1)　(0,i,2)　(0,E,3)　(0,F,4)　(0,T,5)　(1,(,6)　(1,i,7)　(1,E,8)
(1,F,9)　(1,T,10) (2,#,-6)　(2,+,-6)　(2,*,-6)　(3,#,0)　(3,+,11)
(4,#,-4)　(4,+,-4)　(4,*,-4)　(5,#,-2)　(5,+,-2)　(5,*,12)　(6,(,6)
(6,i,7)　(6,E,13)　(6,F,9)　(6,T,10)　(7,),-6)　(7,+,-6)　(7,*,-6)
(8,),14)　(8,+,15)　(9,),-4)　(9,+,-4)　(9,*,-4)　(10,),-2)　(10,+,-2)
(10,*,16)　(11,(,1)　(11,i,2)　(11,F,4)　(11,T,17)　(12,(,1)　(12,i,2)
(12,F,18)　(13,),19)　(13,+,15)　(14,#,-5)　(14,+,-5)　(14,*,-5)
(15,(,6)　(15,i,7)　(15,F,9)　(15,T,20)　(16,(,6)　(16,i,7)　(16,F,21)
(17,#,-1)　(17,+,-1)　(17,*,12)　(18,#,-3)　(18,+,-3)　(18,*,-3)
(19,),-5)　(19,+,-5)　(19,*,-5)　(20,),-1)　(20,+,-1)　(20,*,16)

输入句子测试：
输入句子：i+i+#
输出截图
输入句子：(i)+ii#
输出截图

第五章 结论

通过以上章节的分析与说明，可以看到，本程序在功能上完全实现了课程设计的要求。并且扩展了一些功能。即对任意给定的上下文无关文法都可以构造出相应的LR(1) 项目集族和LR(1)分析表。并且允许用户使用生成的LR(1)分析表对具体的句子进行分析。

到这里，这次的编译原理课程设计基本上已经完成了，我选择的这道题目较其他的选题有一定的难度。但是，我在克服这些难关的过程中获得了更多的是快乐和信心。同时，通过亲手构造一个简单的LR(1)分析器，我对LR(1)分析方法也有了更深一步的认识和掌握。

参考文献：

  1. 陈火旺　刘春林等 《程序设计语言编译原理》（第三版）国防工业出版社，2000
  2. 陈意云　张昱 《编译原理》　高等教育出版社 2003
  3. 陈意云　张昱 《编译原理习题精选与解析》高等教育出版社 2003

附录 程序清单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384

/*
  Name: LR(1)分析器的构造
  Author: wangrui
  Date: 07-06-07
　Description:对任意给定的文法G构造LR(1)项目集规范族和分析表,并对输入的　　　句子进行语法分析
*/
#include"iostream"
#include"fstream"
#include"stack"
#include"utility"
using namespace std;

char G[20][20];       //use a matrix to store grammar G
int   length[20]; //length use to store each formula's length
int   number = 0;
bool tempofinput[150];    //buffer of input
char str_vn[20];  //put all vn into it
int   size_vn = 0;
char str_vt[150]; //put all vt into it
int   size_vt = 0;
bool first_vn[30][150];
char buffer[50];  //用来存放生成CLOSURE(I)时需要的first_set 也用来读入用户的输入串^_^
int   bsize = 0;
struct thri{
  int beg;
  int nex;
  char ch;
};
thri trans[200];
int   size_trans = 0;

//定义项目集的形式
struct proj{
  int formula_numb;
  int part;
  char expc;
};
/*项目集*/
proj  items[100][100];
int   Ccount = 0;
int   size_item[100];

/*状态转换表*/
struct action{
  char    ch;
  int nxt_sta;
};
action    action_table[100][100];
int       size_act_table[100];

ifstream  G_ifile;
ifstream  input_ifile;
ofstream  items_ofile;
ofstream  act_ofile;

void Read_G()
{
  G_ifile >> number;    //user should give the number of formula first
  for(int i = 1; i <= number; i++){
      char temp;
      int j = 0;
      G_ifile >> temp;
      while(temp != '$'){
          tempofinput[temp] = true;
          G[i][j++] = temp;
          G_ifile >> temp;
      }
      length[i] = j;
  }

  G[0][0] = 'S';
  G[0][1] = G[1][0];
  length[0] = 2;

  for(int i = 0; i < 64; i++)
      if(tempofinput[i])
          str_vt[size_vt++] = i;
  for(int i = 91; i < 128; i++)
      if(tempofinput[i])
          str_vt[size_vt++] = i;
  for(int i = 65; i < 91; i++)
      if(tempofinput[i])
          str_vn[size_vn++] = i;
}

void get_first(){
  bool flag1;
  do{
      flag1 = false;
      for(int i = 1; i <= number; i++){
          int t = 1;
          bool flag2;
          do{
              flag2 = false;
              if (G[i][t] >= 'A' && G[i][t] <= 'Z'){
                  for(int k = 0; k < 64; k++)
                      if(first_vn[G[i][t]-'A'][k]==true&& !first_vn[G[i][0]-'A'][k]){
                          first_vn[G[i][0]-'A'][k] = true;
                          flag1 = true;
                      }
                      for(int k = 91; k < 128; k++)
                      if(first_vn[G[i][t]-'A'][k]==true&& !first_vn[G[i][0]-'A'][k]){
                          first_vn[G[i][0]-'A'][k] = true;
                          flag1 = true;
                      }
                      if(first_vn[G[i][t]-'A'][64] == true){
                          t++;
                          flag2 = true;
                      }
              }
              else if(!first_vn[G[i][0]-'A'][ G[i][t] ]){
                      first_vn[G[i][0]-'A'][ G[i][t] ] = true;
                      flag1 = true;
              }
          }while(flag2 && t < length[i]);
          if(t == length[i])
              first_vn[G[i][0]-'A'][26] = true;
      }
  }while(flag1);
}
/*判断项目数否在项目集里*/
bool is_in(proj temp,int T){
  for(int i = 0; i < size_item[T]; i++)
      if(temp.formula_numb == items[T][i].formula_numb && temp.part == items[T][i].part && temp.expc == items[T][i].expc)
              return true;
  return false;
}

void  gete_expc(proj temp){
  bsize = 0;
  bool flag;
  int tt = temp.part;
  do{
      flag = false;
      if(tt+1 >= length[temp.formula_numb]){
          buffer[bsize++] = temp.expc;
          return;
      }
      else if(G[temp.formula_numb][tt+1] < 'A' || G[temp.formula_numb][tt+1] > 'Z'){
          buffer[bsize++] = G[temp.formula_numb][tt+1];
          return;
      }
      else if(G[temp.formula_numb][tt+1] >= 'A' && G[temp.formula_numb][tt+1] <= 'Z'){
          for(int i = 0; i < 64; i++){
              if(first_vn[ G[temp.formula_numb][tt+1]-'A' ][i])
                  buffer[bsize++] = i;
          }
          for(int i = 91; i < 128; i++){
              if(first_vn[ G[temp.formula_numb][tt+1]-'A' ][i])
                  buffer[bsize++] = i;
          }
          if(first_vn[ G[temp.formula_numb][tt+1]-'A' ][64]){
              tt++;
              flag = true;
          }
      }
  }while(flag);
}

void e_closure(int T){
  for(int i = 0; i < size_item[T]; i++){
      proj temp;
      if(G[items[T][i].formula_numb][items[T][i].part] >= 'A' && G[items[T][i].formula_numb][items[T][i].part] <= 'Z'){
          for(int j = 0; j < 20; j++)
              if(G[j][0] == G[items[T][i].formula_numb][items[T][i].part]){
                  gete_expc(items[T][i]);
                  for(int k = 0; k < bsize; k++){
                      temp.formula_numb = j;
                      temp.part = 1;
                      temp.expc = buffer[k];
                      if(!is_in(temp,T))
                          items[T][size_item[T]++] = temp;
                  }
                  bsize = 0;
              }
      }
  }
  return ;
}

int is_contained()
{
  for(int i = 0; i < Ccount; i++){
      int s = 0;      //记录有多少是匹配的
      if(size_item[i] == size_item[Ccount])
          for(int j = 0; j < size_item[Ccount]; j++){
              for(int k = 0; k < size_item[i]; k++)
                  if((items[Ccount][j].formula_numb==items[i][k].formula_numb)&&(items[Ccount][j].part == items[i][k].part) && (items[Ccount][j].expc == items[i][k].expc)){
                      s++;
                      break;
                  }
          }
      if(s == size_item[Ccount])
          return i;
  }
  return 0;
}

void go(){
  proj init;
  init.expc = '#';
  init.formula_numb = 0;
  init.part = 1;
  items[0][0] = init;
  size_item[0]++;

  e_closure(0);
  items_ofile << "I0:" << endl;
  for(int i = 0; i < size_item[0]; i++)
          items_ofile << items[0][i].formula_numb << " , " << items[0][i].part << " , " << items[0][i].expc << endl;
  items_ofile << "***************************************" << endl;

  for(int index = 0; index <= Ccount ; index++){
      for(int j = 0; j < size_vt; j++){
          proj    buf[50];
          int buf_size = 0;
          proj    tp;
          for(int p = 0; p < size_item[index]; p++){
              if((items[index][p].part<length[items[index][p].formula_numb])&&( G[ items[index][p].formula_numb ][ items[index][p].part ] == str_vt[j]) ){
                  tp.formula_numb = items[index][p].formula_numb;
                  tp.expc = items[index][p].expc;
                  tp.part = items[index][p].part+1;
                  buf[buf_size++] = tp;
              }
          }
          if(buf_size != 0){
              Ccount++;
              for(int t = 0; t < buf_size; t++){
                  items[Ccount][ size_item[Ccount]++ ] = buf[t];
              }
              e_closure(Ccount);
              int next_state = is_contained();        //看生成的项目集是否已经在项目集族中了
              if(next_state != 0){
                  size_item[Ccount] = 0;
                  Ccount--;
                  trans[size_trans].beg = index;
                  trans[size_trans].nex = next_state;
                  trans[size_trans].ch = str_vt[j];
                  size_trans++;
              }
              else{
                  items_ofile << "I" << Ccount << ":" << endl;
                  for(int i = 0; i < size_item[Ccount]; i++)
                      items_ofile << items[Ccount][i].formula_numb << " , " << items[Ccount][i].part << " , " << items[Ccount][i].expc << endl;
                  items_ofile << "***************************************" << endl;
                  trans[size_trans].beg = index;
                  trans[size_trans].nex = Ccount;
                  trans[size_trans].ch = str_vt[j];
                  size_trans++;
              }
          }
      }   //对文法的每一个终结符

      for(int j = 0; j < size_vn; j++){
          proj    buf[50];
          int buf_size = 0;
          proj    tp;
          for(int p = 0; p < size_item[index]; p++){
              if((items[index][p].part<length[items[index][p].formula_numb])&&( G[ items[index][p].formula_numb ][ items[index][p].part ] == str_vn[j]) ){
                  tp.formula_numb = items[index][p].formula_numb;
                  tp.expc = items[index][p].expc;
                  tp.part = items[index][p].part+1;
                  buf[buf_size++] = tp;
              }
          }
          if(buf_size != 0){
              Ccount++;
              for(int t = 0; t < buf_size; t++){
                  items[Ccount][ size_item[Ccount]++ ] = buf[t];
              }
              e_closure(Ccount);
              int next_state = is_contained();    //看生成的项目集是否已经在项目集族中了

              if(next_state != 0){
                  size_item[Ccount] = 0;
                  Ccount--;
                  trans[size_trans].beg = index;
                  trans[size_trans].nex = next_state;
                  trans[size_trans].ch = str_vn[j];
                  size_trans++;
              }
              else{
                  items_ofile << "I" << Ccount << ":" << endl;
                  for(int i = 0; i < size_item[Ccount]; i++)
                      items_ofile << items[Ccount][i].formula_numb << " , " << items[Ccount][i].part << " , " << items[Ccount][i].expc << endl;
                  items_ofile << "***************************************" << endl;
                  trans[size_trans].beg = index;
                  trans[size_trans].nex = Ccount;
                  trans[size_trans].ch = str_vn[j];
                  size_trans++;
              }
          }
      }   //对文法的每一个非终结符
  }
}
//get action table based on item set and trans array
void get_action(){
  for(int i = 0; i < 100; i++)
      size_act_table[i] = 0;

  for(int i = 0; i <= Ccount; i++)     //************* i must <= Ccount !!!!!!!!!!!!!! ***********
      for(int j = 0; j < size_item[i]; j++)
          if(items[i][j].part == length[ items[i][j].formula_numb ] ){
              action_table[i][ size_act_table[i] ].ch = items[i][j].expc;
              action_table[i][ size_act_table[i]++ ].nxt_sta = items[i][j].formula_numb*(-1);
          }
  for(int i = 0; i < size_trans; i++){
      int t1 = trans[i].beg;
      int t2 = trans[i].nex;
      char    tp = trans[i].ch;
      action_table[t1][ size_act_table[t1] ].ch = tp;
      action_table[t1][ size_act_table[t1]++ ].nxt_sta = t2;
  }
}

int main(){
  for(int i = 0; i< 150; i++)
      tempofinput[i] = false;
  for(int i= 0; i < 100; i++)
      size_item[i] = 0;
  for(int i = 0; i < 30; i++)
      for(int j = 0; j < 150; j++)
              first_vn[i][j] = false;

  G_ifile.open("d://grammar.txt");
  input_ifile.open("d://input.txt");
  items_ofile.open("d://items.txt");
  act_ofile.open("d://action_table.txt");

  Read_G();       //read G and put the number of formula into count
  get_first();    //each vn's first_set
  go();
  get_action();
  for(int i = 0; i < Ccount; i++)
      for(int j = 0; j < size_act_table[i]; j++){
          char    tp = action_table[i][j].ch;
          int t   = action_table[i][j].nxt_sta;
          act_ofile << "(" << i << "," << tp << "," << t << ")" << endl;
      }

  bsize = 0;
  do{
      input_ifile >> buffer[bsize];
  }while(buffer[ bsize++ ] != '#');
  stack<pair<int,char> > s;   //语法检查栈
  int work_sta = 0;
  int index_buf = 0;
  bool    err;
  bool    done = false;
  s.push(make_pair(0,'#'));
  do{
      work_sta = s.top().first;
      err =   true;
      for(int i= 0; i < size_act_table[work_sta]; i++)
          if(action_table[work_sta][i].ch == buffer[index_buf]){
              err = false;
              if(action_table[work_sta][i].nxt_sta == 0){
                  cout << "Accept!!!" << endl;
                  done = true;
                  break;
              }
              else if(action_table[work_sta][i].nxt_sta > 0){
                  s.push(make_pair(action_table[work_sta][i].nxt_sta,action_table[work_sta][i].ch));
                  index_buf++;
                  break;
              }
              else{
                  int tp = action_table[work_sta][i].nxt_sta*(-1);    //用来归约的产生式编号
                  for(int k = 0; k < length[tp]-1; k++)
                      s.pop();
                  --index_buf;
                  buffer[index_buf] = G[tp][0];
                  break;
              }
          }
  } while(done == false && err == false);
  if(!done)
      cout << "请检查输入串!!!" << endl;
  G_ifile.close();
  input_ifile.close();
  items_ofile.close();
  act_ofile.close();
  return 0;
}

分段排序网络 Bitonic Sort

分段排序网络 Bitonic Sort

我们之前所有的排序算法都是给定了数据再进行排序，排序的效率很大程度上取决于数据的好坏。我们今天所介绍的是一个完全不同的排序方法，它可以在“暗箱”里对数据进行排序（即你不必知道实际数据是什么），换句话说这种排序方法不依赖于数据(Data-Independent)，所有比较操作都与数据无关。你甚至可以立即忘掉前面的比较结果，因为对于所有可能的数据这类排序算法都能得到正确答案并且排序步骤完全相同。本文结束后再回过头来看这段话你将有更深的认识。

我们设置一个暗箱，暗箱左边有n个输入口，暗箱右边有n个输出口。我们需要设计一个暗箱使得，任意n个数从左边输进去，右边出来的都是有序的。图1显示了有4个输入的暗箱。

暗箱里唯一允许的元件叫做“比较器”(Comparator)，每个比较器连接两个元素，当上面那个比下面那个大时它将交换两个元素的位置。也就是说，每经过一个比较器后，它的两端中较小的一个总是从上面出来，较大的总是到了下面。图2显示了一种包含4个比较器的暗箱系统。当输入数据3,1,4,2通过这个系统时，输出为1,3,2,4，如图3所示。这种暗箱结构叫做比较网络(Comparator Network)。如果对于任意一个输入数据，比较网络的输出都是有序的，那么这个比较网络就叫做排序网络(Sorting Network)。显然，我们例子中的比较网络不是一个排序网络，因为它不能通过3,1,4,2的检验。

现在，我们的第一个问题是，是否存在比较网络。就是说，有没有可能使得任意数据通过同一组比较器都能输出有序的结果。我们最初的想法当然是，把我们已知的什么排序算法改成这种形式。把原来那十种排序又翻出来看一遍，找一找哪些排序的比较操作是无条件的。运气不错，我们所学的第一个算法——冒泡排序，它的比较就是无条件的，不管数据怎样冒泡排序都是不断比较相邻元素并把较小的放到前面。冒泡排序是一个彻头彻尾的排序网络模型，我们可以立即画出冒泡排序所对应的排序网络（图4）。这是我们得到的第一个排序网络。我们通常不认为插入排序是排序网络，因为插入排序的比较次数取决于数据的有序程度。

传统的计算机一次只能处理一个比较。排序网络真正的研究价值在于，假如有机器可以同时处理多个比较器，排序的速度将大幅度提高。我们把比较器的位置稍微移动一下，把那些互不冲突（处理的元素不同）的比较器压缩到一层(Stage)（图5），这样整个排序过程压缩为了2n-3层。实现排序网络的机器可以在单位时间里并行处理同一层中所有的比较。此时，比较次数的多少对排序效率不起决定作用了，即使比较次数多一些但是排序网络的层次更少，效率也会更高一些。我们自然又想，排序网络需要的层数能否少于2n-3。我们想到，图5的左下角和右下角似乎有些空，我们期望能在这些位置加一些比较从而减少层数。图6给出了一个只有n层的排序网络，这叫做奇偶移项排序(Odd-even Transposition Sort)。我们下文将证明它确实是一个排序网络。这次的图很多，排版也很困难，累死我了。我把下面的图7也放到这里来了，不然到处都是图很难看。

给出一个比较网络，怎样判断它是不是一个排序网络？很遗憾，现在还没有找到一种好的算法。事实上，这个问题是一个NPC问题。注：这种说法是不准确的，因为目前还没有迹象表明这个问题是NP问题。准确的说法应该是，“判断某比较网络为排序网络”是Co-NP Complete，而“判断某比较网络不是排序网络”（即找到一个反例）才是NP Complete。

传统的做法是枚举所有n的排列来验证，一共要考虑n!种情况。下面我们介绍排序网络理论里最重要的结论：0-1原理(0-1 Principle)。使用这个原理来验证排序网络只需要考虑2n种情况。0-1原理告诉我们，如果所有的01序列能够通过比较网络排出顺序，那么这足以说明该网络为排序网络。证明过程很简单。为了证明这个结论，我们证明它的逆否命题（逆否命题与原命题同真假）：如果一个比较网络不是排序网络，那么至少存在一个01序列不能被排序。我们给出一种算法，这个算法可以把任何一个不能被排序的输入数据转化为一个不能被排序的01序列。

在最初的例子（图3）中，输入数据3,1,4,2的输出为1,3,2,4，没有成功地排出顺序，从而判断出该网络不是排序网络。这说明，输出结果中存在逆序对（左边某个数大于右边的某个数）。我们从输出结果中找出一个逆序对来。例子中，(3,2)就是我们要找的数。现在，我们把输入中所有小于数字3（左边那个数）的数都变成0，把所有大于等于3的数都变成1。这样，3,1,4,2就变成了1,0,1,0。显然，把得到的这个01序列输入进去，原来曾经发生过交换的地方现在仍然会交换，原来不曾交换的地方现在也同样不会发生交换（当两个0或两个1进行比较时，我们既可以认为它们不交换，也可以看成它们要互相交换，反正都一样）。最后，该01序列输出的结果中，本来3的位置现在还是1，原来2的位置现在仍然是0，逆序对仍然存在。因此，只要一个比较网络不是排序网络，那么总可以找到一个01序列不能被排序。等价地，如果所有的01序列都能被排序了，这个比较网络也就是排序网络了。

我们用0-1原理来证明奇偶移项排序的正确性。我们对n进行数学归纳证明。n=2时（一个“工”字）显然是排序网络。

图中是n=8的情况。我们假设对于所有n<=7，奇偶移项排序网络都是正确的。我们同时假定所有输入数字非0即1，下面我们说明n=8时所有的01序列都能被正确排序。

假设最后一个数是1（图7，在前面的），那么这个1将始终排在最后不参与任何交换操作，对前面7个数没有任何影响。除去无用的灰色部分，剩下的就是n=7这一规模较小的子排序网络，由归纳假设则n=8也是排序网络；

假设最后一个数是0（图8），那么在每一次比较中这个0都会被提到前面去（前面说过，两个0之间交不交换是一回事）。蓝色的箭头表示每个数跑到了什么位置。你会发现除最后一个数以外前7个数之间的比较器又构成了n=7的情况。

接下来，我们提出一些比较器个数为O(nlognlogn)的排序网络。其中一种就是之前提到过的2p3q增量Shell排序。这种增量排序的特点是每一趟排序中的每个数只与前面的数比较一次，因此它可以非常方便地转化为排序网络。图9就是一个n=8的Shell排序网络。Bitonic排序也可以做到O(nlogn*logn)的比较器个数，今天不介绍它。下面详细介绍奇偶归并排序网络。

奇偶归并排序网络也是一种比较器个数为O(nlognlogn)的排序网络。它和归并排序几乎相同，不同的只是合并的过程。普通归并排序的O(n)合并过程显然是依赖于数据的，奇偶归并排序可以把这个合并过程改成非数据依赖型，但复杂度将变高。这个合并过程本身也是递归的。我们假设n是2的幂（不是的话可以在前面添0补足，这对复杂度的计算没有影响），算法首先把n个数中所有的奇数项和偶数项分别递归地合并，然后在排序后的第i个偶数项和第i+1个奇数项之间设立比较器。

假如1,4,6,8和2,3,7,9是两段已经有序的子序列，合并过程首先递归地合并1,6,2,7和4,8,3,9，这样原数列就变成了1,3,2,4,6,8,7,9。然后分别把(3,2),(4,6),(8,7)三对相邻元素中各自较小的那个交换到前面，完成合并操作。使用0-1原理证明这个结论出乎意料的简单：图10显示了n=16的情况，白色的方格代表一个0，灰色方格代表1。奇偶项分别排序后，偶数项1的个数最多比奇数项多出2个，我们设立的比较器可以考虑到所有的情况，不管什么情况都能让它最终变得有序。

由前面说过的结论，合并过程总共需要比较O(nlogn)次。归并排序递归一共有O(logn)层，每一层总的比较器个数不超过O(nlogn)，因此总共O(nlognlogn)。一个n=8的完整的奇偶归并排序网络如图11所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
int M;

void BitonicMerge(int* data, int s, int len, int sta)
{
	if(len < 2) return;
	int k;
	for(k=1;k<len;k=k<<1); k>>=1;
	int i;
	int tmp;
	for(i=s;i<s+len-k;i++)
	    if(sta == data[i]>data[i+k])
	    {
	        tmp = data[i];
	        data[i] = data[i+k];
	        data[i+k] = tmp;
	    }
	BitonicMerge(data, s, k, sta);
	BitonicMerge(data, s+k, len-k, sta);
}

void BitonicSort(int* data, int s, int len, int sta)
{
	if(len>1)
	{
	    int mid=len/2;
	    BitonicSort(data, s, mid, 1-sta);
	    BitonicSort(data, s+mid, len-mid, sta);
	    BitonicMerge(data, s, len, sta);
	}
}

void BitonicSort_(int* data, int n)
{
	int i,j,k,l,len,flag,sta,ll,kk,cou;
	int tmp;

	for(flag = 0, len=1;len<n;len<<=1) flag = 1-flag; // flag == 1 ascending
	for(len=1;len<n;len<<=1)
	{
	    cou = 0;
	    for(i=0;i<n;i+=len*2)
	    {
	        sta = flag; for(ll=0;(1<<ll)<=cou;ll++) if((cou&(1<<ll)) != 0) sta = 1-sta;
	        for(ll=len;ll>=1;ll>>=1)
	        {
	            for(j=i;j+ll<i+len*2; j+=ll*2)
	            {
	                kk = ll*2; if(i+len*2-j < kk) kk = i+len*2-j; if(n-j < kk) kk = n-j;
	                for(k=j;k<j+kk-ll;k++)
	                    if(sta == (data[k] > data[k+ll]))
	                    {
	                        tmp = data[k];
	                        data[k] = data[k+ll];
	                        data[k+ll] = tmp;
	                    }
	            }
	        }
	        cou++;
	    }
	    flag = 1-flag;
	}
}

int main()
{
	for(M = 1;M<=100;M++)
	{
	    int i,j,k,l,tim=1000;

	    int n=M;
	    int m;

	    int a[M],data[M],b[M];
	    int seg_id[M];
	    int seg_start[2]={0,M};

	    int no = 0;

	    while(tim--)
	    {
	        for(i=0;i<n;i++) data[i] = a[i] = b[i] = rand()%100;

	        for(i=0;i<n;i++) seg_id[i] = 0;
	        seg_start[0] = 0;
	        seg_start[1] = M;
	        m = 1;
	        
	        BitonicSort_(data, n);   // 非递归
	        BitonicSort(b, 0, n, 1); // 递归
	        sort(a, a+n);
	        
	        // for(i=0;i<n;i++) printf("%.0f ",b[i]); printf("\n");
	        // for(i=0;i<n;i++) printf("%.0f ",a[i]); printf("\n");
	        
	
	        k = 1;
	        for(i=0;i<n;i++) if(a[i] != data[i] || b[i] != a[i]) k = 0;
	        if(k == 0) no++;
	        // if(k == 1) printf("YES\n"); else  printf("NO\n");
	    }
	    printf(" M = %d  NO = %d\n",M,no);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

#define M 10000

void BitonicMerge(int* data, int s, int len, int sta)
{
	if(len < 2) return;
	int k;
	for(k=1;k<len;k=k<<1); k>>=1;
	int i;
	int tmp;
	for(i=s;i<s+len-k;i++)
	    if(sta == data[i]>data[i+k])
	    {
	        tmp = data[i];
	        data[i] = data[i+k];
	        data[i+k] = tmp;
	    }
	BitonicMerge(data, s, k, sta);
	BitonicMerge(data, s+k, len-k, sta);
}

void BitonicSort(int* data, int s, int len, int sta) // 递归
{
	if(len>1)
	{
	    int mid=len/2;
	    BitonicSort(data, s, mid, 1-sta);
	    BitonicSort(data, s+mid, len-mid, sta);
	    BitonicMerge(data, s, len, sta);
	}
}

void BitonicSort_(int* data, int n) // 非递归
{
	int i,j,k,l,len,flag,sta,ll,kk,cou;
	int tmp;

	for(flag = 0, len=1;len<n;len<<=1) flag = 1-flag; // flag == 1 ascending
	for(len=1;len<n;len<<=1)
	{
	    cou = 0;
	    for(i=0;i<n;i+=len*2)
	    {
	        sta = flag; for(ll=0;(1<<ll)<=cou;ll++) if((cou&(1<<ll)) != 0) sta = 1-sta;
	        for(ll=len;ll>=1;ll>>=1)
	        {
	            for(j=i;j+ll<i+len*2; j+=ll*2)
	            {
	                kk = ll*2; if(i+len*2-j < kk) kk = i+len*2-j; if(n-j < kk) kk = n-j;
	                for(k=j;k<j+kk-ll;k++)
	                    if(sta == (data[k] > data[k+ll]))
	                    {
	                        tmp = data[k];
	                        data[k] = data[k+ll];
	                        data[k+ll] = tmp;
	                    }
	            }
	        }
	        cou++;
	    }
	    flag = 1-flag;
	}
}

int main()
{
	int i, n;
	int data[M];
	int seg_id[M];
	int seg_start[2];

	// 输入
	scanf("%d", &n);
	for(i=0;i<n;i++) scanf("%d", &data[i]);
	
	// 只分一段
	for(i=0;i<n;i++) seg_id[i] = 0;
	seg_start[0] = 0;
	seg_start[1] = n;
	
	//BitonicSort_(data, n);   // 非递归
	BitonicSort(data, 0, n, 1); // 递归

	for(i=0;i<n;i++) printf("%d%c", data[i], i==n-1?'\n':' ');
	return 0;
}