kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

LINUX汇编

一, IA-32 硬件特性

寄存器:

1, 通用寄存器, 用于存放正在处理的数据
1
2
3
4
5
6
7
8
EAX 用于操作数和结果数的累加器
EBX 指向数据内存断中的数据的指针
ECX 字符串和循环操作的计数器
EDX IO指针
EDI 用于字符串操作的目标的数据指针
ESI 用于字符串操作的源的数据指针
ESP 堆栈指针
EBP 堆栈数据指针

其中寄存器EAX, EBX, ECX, EDX又可以通过16位和8位寄存器名称引用 如EAX, AX 引用EAX低16位, AL 引用EAX低8位, AH 引用AL之后的高8位

2, 段寄存器:

IA-32平台允许使用3中内存模型: 平坦内存模式 分段内存模式 实地址模式

平坦内存: 把全部的系统内存表示为连续的地址空间, 通过线性地址的特定地址访问内存位置.

分段内存: 把系统内存划分为独立的段组, 通过位于寄存器中的指针进行引用. 每个段用于包含特定类型的数据。 一个段用于包含指令码, 另一个段包含数据元素, 第三个段包含数据堆栈。段中的内存位置是通过逻辑地址引用的, 逻辑地址是由段地址加上偏移量构成, 处理器把逻辑地址转换为相应的线性地址以便访问。

1
2
3
4
5
6
7
段寄存器:
CS 代码段
DS 数据段
SS 堆栈段
ES 附加段指针
FS 附加段指针
GS 附加段指针

每个段寄存器都是16位的, 包含指向内存特定段起始位置的指针,程序不能显示加载或改变CS寄存器, DS, ES, FS, GS都用于指向数据段, 通过4个独立的段, 程序可以分隔数据元素, 确保他们不会重叠, 程序必须加载带有段的正确指针值的数据段寄存器, 并且使用偏移值引用各个内存的位置。SS段寄存器用于指向堆栈段, 堆栈包含传递给函数和过程的数据值。

实地址: 如果实地址模式, 所有段寄存器都指向线性0地址, 并且都不会被程序改动,所有的指令码 数据元素 堆栈元素 都是通过他们的线性地址直接访问的。

3, 指令指针寄存器

是EIP寄存器, 它跟踪要执行程序的下一条指令代码, 应用程序不能修改指令指针本身,不能指定内存地址把它拖放EIP寄存器中,相反必须通过一般的跳转指令来改变预存取缓存的下一条指令。

在平坦内存模型中, 指令指针包含下一条指令码的线性地址, 在分段模型中指令指针包含逻辑地址指针, 通过CS寄存器的内存引用。

4, 控制寄存器
1
2
3
4
5
CRO 控制操作模式 和 处理器当前状态的系统标志
CR1 当前没有使用
CR2 内存页面错误信息
CR3 内存页面目录信息
CR4 支持处理器特性和说明处理器特性能力的标志

不能直接访问控制寄存器, 但是能把控制寄存器中的值传递给通用寄存器,如果必须改动控制寄存器的标志, 可以改动通用寄存器的值, 然后把内容传递给控制寄存器。

标志:

IA-32使用单一的寄存器来包含一组状态控制和系统标志, EFLAGS寄存器包含32位标志信息

1, 状态标志
1
2
3
4
5
6
7
8
标志 位 说明
CF 0 进位标志, 如果无符号数的数学操作产生最高有效位的进位或者借位, 此时值为1
PF 2 奇偶校验标志, 用于表明数学操作的结果寄存器中的是否包含错误数据
AF 4 辅助进位标志, 用于二进制编码的10进制(BCD)的数学操作中, 如果用于运算的
寄存器的第三位发生进位或借位, 该值为1
ZF 6 0标志, 如果操作为0, 则该值为1
SF 7 符号标志, 设置为结果的最高有效位, 这一位是符号位表明结果是正值还是负值
OF 11 溢出标志
2, 控制标志

当前只定义了一个控制标志DF即方向标志, 用于控制处理器处理字符串的方式 如果设置为1, 字符串指令自动递减内存地址以便到达字符串中的下一字节。 反之。

3, 系统标志
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
标志 位 说明
TF 8 陷阱标志, 设置为1时启用单步模式, 在单步模式下处理器每次只执行一条命令。
IF 9 中断使能标志, 控制处理器如响应从外部源接收到的信号。
IOPL 12和13 IO特权级别标志, 表明当前正在运行任务的IO特权级别, 它定义IO地址空间的
特权访问级别, 该值必须小于或者等于访问I/O地址空间的级别; 否则任何访问
IO空间的请求都会被拒绝!
NT 14 嵌套任务标志控制当前运行的任务是否连接到前一个任务, 它用于连接被中断
和被调用的任务.
RF 16 恢复标志用于控制在调试模式中如何响应异常。
VM 17 虚拟8086模式, 表明处理器在虚拟8086模式中而不是保护模式或者实模式。
AC 18 对准检查标志, 用于启用内存引用的对准检查
VIF 19 虚拟中断标志, 当处理器在虚拟模式中操作时, 该标志起IF标志的作用.
VIP 20 虚拟中断挂起标志, 在虚拟模式操作时用于表示一个中断正在被挂起。
ID 21 表示CPU是否支持cpuid指令, 如果处理器能够设置或者清零这个标志, 表示
处理器支持该指令。

二,GNU汇编工具系列

1, 二进制工具系列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
addr2line 把地址转换成文件名或者行号
ar 创建 修改或者展开文件存档
as 把汇编语言代码汇编成目标代码
c++filt 还原c++符号的过滤器
gprof 显示程序简档信息的程序
ld 把目标代码文件转换成可执行文件的转换器
nm 列出目标文件中的符号
objcopy 复制或翻译目标文件
objdump 显示来自目标文件的信息
ranlib 生成存档文件内容的索引
readelf 按照elf格式显示目标文件信息
size 列出目标文件或者存档文件的段长度
strings 显示目标文件中可打印字符串
strip 丢弃符号
windres 编译Microsoft Windows资源文件

2, GNU编译器

gcc

3, GNU调试程序

gdb

三, GNU汇编语言结构

主要包括三个常用的段: data 数据段 声明带有初始值的元素
bss 数据段 声明使用0或者null初始化的元素
text 正文段 包含的指令, 每个汇编程序都必须包含此段

使用.section 指令定义段, 如:

1
2
3
.section .data
.section .bss
.section .text

起始点:

gnu汇编器使用start标签表示默认的起始点, 此外如果想要汇编内部的标签能够被外部程序访问, 需要使用.globl 指令, 如:.globl start

使用通用库函数时可以使用:
ld -dynamic-linker /lib/ld-linux.so.2

四, 数据传递

1, 数据段

使用.data声明数据段, 这个段中声明的任何数据元素都保留在内存中并可以被汇编程序的指令读取, 此外还可以使用.rodata声明只读的数据段, 在声明一个数据元素时, 需要使用标签和命令:

标签:用做引用数据元素所使用的标记, 它和c语言的变量很相似, 它对于处理器是没有意义的, 它 只是用做汇编器试图访问内存位置时用做引用指针的一个位置。

指令:这个名字指示汇编器为通过标签引用的数据元素保留特定数量的内存, 声明命令之后必须给出 一个或多个默认值。

声明指令:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
.ascii 文本字符串
.asciz 以空字符结尾的字符串
.byte 字节值
.double 双精度浮点值
.float 单精度浮点值
.int 32位整数
.long 32位整数, 和int相同
.octa 16字节整数
.quad 8字节整数
.short 16位整数
.single 单精度浮点数(和float相同)


例子:
output:
.ascii "hello world."

pi:
.float 2.14

声明可以在一行中定义多个值, 如:
ages:
.int 20, 10, 30, 40

定义静态符号:
使用.equ命令把常量值定义为可以在文本段中使用的符号,如:

1
2
3
4
.section .data
.equ LINUX_SYS_CALL, 0x80
.section .text
movl $LINUX_SYS_CALL, %eax

2, bss段

和data段不同, 无需声明特定的数据类型, 只需声明为所需目的保留的原始内存部分即可。 GNU汇编器使用以下两个命令声明内存区域:

1
2
.comm 声明为未初始化的通用内存区域
.lcomm 声明为未初始化的本地内存区域

两种声明很相似, 但.lcomm是为不会从本地汇编代码之外进行访问的数据保留的, 格式为:

1
.comm/.lcomm symbol, length

例子:

1
2
.section .bss
.lcomm buffer, 1000

该语句把1000字节的内存地址赋予标签buffer, 在声明本地通用内存区域的程序之外的函数是 不能访问他们的.(不能在.globl命令中使用他们)

在bss段声明的好处是, 数据不包含在可执行文件中。在数据段中定义数据时, 它必须被包含在 可执行程序中, 因为必须使用特定值初始化它。 因为不使用数据初始化bss段中声明的数据区域, 所以内存区域被保留在运行时使用, 并且不必包含在最终的程序中

3, 传送数据

move 指令: 格式 movex 源操作数, 目的操作数。 其中x为要传送数据的长度, 取值有: l 用于32位的长字节
w 用于16位的字
b 用于8位的字节值

立即数前面要加一个$符号, 寄存器前面要加%符号。
8个通用的寄存器是用于保存数据的最常用的寄存器, 这些寄存器的内容可以传递 给其他的任何可用的寄存器。 和通用寄存器不同, 专用寄存器(控制, 调试, 段) 的内容只能传送给通用寄存器, 或者接收从通用寄存器传过来的内容。

在对标签进行引用时: 例:

1
2
3
4
5
6
7
8
.section .data
value:
.int 100
_start:
movl value, %eax
movl $value, %eax
movl %ebx, (%edi)
movl %ebx, 4(%edi)

其中:
movl value, %eax 只是把标签value当前引用的内存值传递给eax
movl $value, %eax 把标签value当前引用的内存地址指针传递给eax
movl %ebx, (%edi) 如果edi外面没有括号那么这个指令只是把ebx中的
值加载到edi中, 如果有了括号就表示把ebx中的内容
传送给edi中包含的内存位置。
movl %ebx, 4(%edi) 表示把edi中的值放在edi指向的位置之后的4字节内存位置中
movl %ebx, -4(%edi) 表示把edi中的值放在edi指向的位置之前的4字节内存位置中

cmove 指令(条件转移): cmovex 源操作数, 目的操作数. x的取值为:
无符号数:

1
2
3
4
5
6
7
8
9
10
a/nbe 大于/不小于或者等于
ae/nb 大于或者等于/不小于
nc 无进位
b/nae 小于/不大于等于
c 进位
be/na 小于或等于/不大于
e/z 等于/零
ne/nz 不等于/不为零
p/pe 奇偶校验/偶校验
np/po 非奇偶校验/奇校验

有符号数:

1
2
3
4
5
6
7
ge/nl 大于或者等于/不小于
l/nge 小于/不大于或者等于
le/ng 小于或者等于/不大于
o 溢出
no 未溢出
s 带符号(负)
ns 无符号(非负)

交换数据: xchg 在两个寄存器之间或者寄存器和内存间交换值。如:
xchg 操作数, 操作数, 要求两个操作数必须长度相同且不能同时都是内存位置
其中寄存器可以是32,16,8位的

bswap 反转一个32位寄存器的字节顺序
如: bswap %ebx

xadd 交换两个值 并把两个值只和存储在目标操作数中
如: xadd 源操作数,目标操作数
其中源操作数必须是寄存器, 目标操作数可以是内存位置也可以是寄存器
其中寄存器可以是32,16,8位的

cmpxchg
cmpxchg source, destination
其中source必须是寄存器, destination可以是内存或者寄存器, 用来比较 两者的值, 如果相等,就把源操作数的值加载到目标操作数中, 如果不等就把 目标操作数加载到源操作数中,其中寄存器可以是32,16,8位的, 其中源操作 数是EAX,AX或者AL寄存器中的值

cmpxchg8b 同cmpxchg, 但是它处理8字节值, 同时它只有一个操作数
cmpxchg8b destination
其中destination引用一个内存位置, 其中的8字节值会与EDX和EAX寄存器中 包含的值(EDX高位寄存器, EAX低位寄存器)进行比较, 如果目标值和EDX:EAX 对中的值相等, 就把EDX:EAX对中的64位值传递给内存位置, 如果不匹配就把 内存地址中的值加载到EDX:EAX对中

4, 堆栈

ESP 寄存器保存了当前堆栈的起始位置, 当一个数据压入栈时, 它就会自动递减,反之其自动递增
压入堆栈操作:

1
2
3
pushx source, x取值为:
l 32位长字
w 16位字

*出堆栈操作:

1
popx source

其中source必须是16或32位寄存器或者内存位置, 当pop最后一个元素时ESP值应该和以前的相等

5,压入和*出所有寄存器

1
2
3
4
pusha/popa 压入或者*出所有16位通用寄存器
pushad/popad 压入或者*出所有32位通用寄存器
pushf/popf 压入或者*出EFLAGS寄存器的低16位
pushfd/popfd 压入或者*出EFLAGS寄存器的全部32位

6,数据地址对齐

gas 汇编器支持.align 命令, 它用于在特定的内存边界对准定义的数据元素, 在数据段中.align命令紧贴在数据定义的前面

五,控制流程

无条件跳转:

1, 跳转

jmp location 其中location为要跳转到的内存地址, 在汇编中为定义的标签

2,调用

调用指令分为两个部分:
1, 调用call address 跳转到指定位置
2, 返回指令ret, 它没有参数紧跟在call指令后面的位置

执行call指令时,它把EIP的值放到堆栈中, 然后修改EIP以指向被调用的函数地址, 当被调用函数完成后, 它从堆栈获取过去的EIP的值, 并把控制权返还给原始程序。

3,中断

由硬件设备生成中断。 程序生成软件中断 当一个程序产生中断调用时, 发出调用的程序暂停, 被调用的程序接替它运行, 指令指针被转移到被调用的函数地址, 当调用完成时使用中断返回指令可以返回调原始程序。

条件跳转:

条件跳转按照EFLAGS中的值来判断是否该跳转, 格式为:

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
jxx address, 其中xx是1-3个字符的条件代码, 取值如下:
a 大于时跳转
ae 大于等于
b 小于
be 小于等于
c 进位
cxz 如果CX寄存器为0
ecxz 如果ECS寄存器为0
e 相等
na 不大于
nae 不大于或者等于
nb 不小于
nbe 不小于或等于
nc 无进位
ne 不等于
g 大于(有符号)
ge 大于等于(有符号)
l 小于(有符号)
le 小于等于(有符号)
ng 不大于(有符号)
nge 不大于等于(有符号)
nl 不小于
nle 不小于等于
no 不溢出
np 不奇偶校验
ns 无符号
nz 非零
o 溢出
p 奇偶校验
pe 如果偶校验
po 如果奇校验
s 如果带符号
z 如果为零

条件跳转不支持分段内存模型下的远跳转, 如果在该模式下进行程序设计必须使用程序逻辑确定条件是否存在, 然后实现无条件跳转, 跳转前必须设置EFLAGS寄存器

比较:
cmp operend1, operend2

进位标志修改指令:
CLC 清空进位标志(设置为0)
CMC 对进位标志求反(把它改变为相反的值)
STC 设置进位标志(设置为1)

循环:
loop 循环直到ECX寄存器为0
loope/loopz 循环直到ecx寄存器为0 或者没有设置ZF标志
loopne/loopnz 循环直到ecx为0或者设置了ZF标志

指令格式为: loopxx address 注意循环指令只支持8位偏移地址

六,数字

IA-32平台中存储超过一字节的数都被存储为小尾数的形式但是把数字传递给寄存器时, 寄存器里面保存是按照大尾数的形式存储

把无符号数转换成位数更大的值时, 必须确保所有的高位部分都被设置为零

把有符号数转换成位数更大的数时:
intel 提供了movsx指令它允许扩展带符号数并保留符号, 它与movzx相似, 但是它假设要传送的字节是带符号数形式

浮点数:

fld 指令用于把浮点数字传送入和传送出FPU寄存器, 格式:

1
fld source

其中source可以为32 64或者80位整数值

IA-32使用FLD指令用于把存储在内存中的单精度和双精度浮点值FPU寄存器堆栈中, 为了区分这两种长度GNU汇编器使用FLDS加载单精度浮点数, FLDL加载双精度浮点数

类似FST用于获取FPU寄存器堆栈中顶部的值, 并且把这个值放到内存位置中, 对于单精度使用FSTS, 对于双精度使用FSTL

七,基本数学运算

1, 加法

ADD source, destination 把两个整数相加
其中source可以是立即数内存或者寄存器, destination可以是内存或者寄存器, 但是两者不能同时都是内存位置

ADC 和ADD相似进行加法运算, 但是它把前一个ADD指令的产生进位标志的值包含在其中, 在处理位数大于32(如64)位的整数时, 该指令非常有用

2, 减法

SUB source, destination 把两个整数相减 NEG 它生成值的补码
SBB 指令, 和加法操作一样, 可以使用进位情况帮助执行大的无符号数值的减法运算. SBB在多字节减法操作中利用
进位和溢出标志实现跨数据边界的的借位特性

3,递增和递减

dec destination 递减
inc destination 递增
其中dec和inc指令都不会影响进位标志, 所以递增或递减计数器的值都不会影响程序中涉及进位标志的其他任何运算

4, 乘法

mul source 进行无符号数相乘 它使用隐含的目标操作数, 目标位置总是使用eax的某种形式, 这取决与源操作数的长度, 因此根据源操作数的长度, 目标操作数必须放在AL, AX, EAX中。 此外由于乘法可能产生很大的值, 目标位置必须是源操作数的两倍位置, 源为 8时, 应该是16, 源为16时, 应该为32, 但是当源为16位时intel为了向下兼容, 目标操作数不是存放在eax中, 而 是分别存放在DX:AX中, 结果高位存储在DX中, 地位存储在AX中。对于32位的源, 目标操作数存储在EDX:EAX中, 其中 EDX存储的是高32位, EAX存储的是低32位

imul source 进行有符号数乘法运算, 其中的目标操作数和mul的一样

imul source, destination 也可以执行有符号乘法运算, 但是此时可以把目标放在指定的位置, 使用这种格式的缺陷 在与乘法的操作结果被限制为单一目标寄存器的长度.

imul multiplier, source, destination 其中multiplier是一个立即数, 这种方式允许一个值与给定的源操作数进行快速的乘法运算, 然后把结果存储在通用 寄存器中

5, 除法

div divisor 执行无符号数除法运算 除数的最大值取决与被除数的长度, 对于16位被除数 ,除数只能为8位, 32或64位同上 被除数 被除数长度 商 余数
AX 16位 AL AH
DX:AX 32位 AX DX
EDX:EAX 64位 EAX EDX

idiv divisor 执行有符号数的除法运算, 方式和div一样

6, 移位

左移位:
sal 向左移位
sal destination 把destination向左移动1位
sal %cl, destination 把destination的值向左移动CL寄存器中指定的位数
sal shifter, destination 把destination的值向左移动shifter值指定的位数
向左移位可以对带符号数和无符号数执行向左移位的操作, 移位造成的空位用零填充, 移位造成的超过数据长度的任何位 都被存放在进位标志中, 然后在下一次移位操作中被丢弃

右移位:
shr向右移位
sar向右移位
SHR指令清空移位造成的空位, 所以它只能对无符号数进行移位操作
SAR指令根据整数的符号位, 要么清空, 要么设置移位造成的空位, 对于负数, 空位被设置为1

循环移位:
和移位指令类似, 只不过溢出的位被存放回值的另一端, 而不是丢弃
ROL 向左循环移位
ROR 向右循环移位
RCL 向左循环移位, 并且包含进位标志
RCR 向右循环移位, 并且包含进位标志

7, 逻辑运算

AND OR XOR
这些指令使用相同的格式:
and source, destination
其中source可以是8位 16 位或者32位的立即值 寄存器或内存中的值, destination可以是8位 16 位或者 32位寄存器或内存中的值, 不能同时使用内存值作为源和目标。 布尔逻辑功能对源和目标执行按位操作。 也就是说使用指定的逻辑功能按照顺序对数据的元素的每个位进行单独比较。

NOT指令使用单一操作数, 它即是源值也是目标结果的位置 清空寄存器的最高效方式是使用OR指令对寄存器和它本身进行异或操作.当和本身进行XOR操作时, 每个设置为 1的位就变为0, 每个设置为0的位也变位0。

位测试可以使用以上的逻辑运算指令, 但这些指令会修改destination的值, 因此intel提供了test指令, 它不 会修改目标值而是设置相应的标志

八,字符串处理

1, 传送字符串
1
2
3
4
movs 有三种格式
movsb 传送单一字节
movsw 传送一个字
movsl 传送双字

movs指令使用隐含的源和目的操作数, 隐含的源操作数是ESI, 隐含的目的操作数是EDI, 有两种方式加载内存地址到 ESI和EDI, 第一种是使用标签间接寻址 movl $output, %ESI, 第二种是使用lea指令, lea指令加载对象的地址到指定 的目的操作数如lea output, %esi, 每次执行movs指令后, 数据传送后ESI和EDI寄存器会自动改变,为另一次传送做 准备, ESI和EDI可能随着标志DF的不同自动递增或者自动递减, 如果DF标志为0则movs指令后ESI和EDI会递增, 反之会 递减, 为了设置DF标志, 可以使用一下指令:
CLD 将DF标志清零
STD 设置DF标志

2,rep前缀

REP 指令的特殊之处在与它不执行什么操作, 这条指令用于按照特定次数重复执行字符串指令, 有ECX寄存器控制, 但不需要额外的loop指令, 如rep movsl
rep的其他格式:
repe 等于时重复
repne 不等于时重复
repnz 不为零时重复
repz 为零时重复

3, 存储和加载字符串

LODS 加载字符串, ESI为源, 当一次执行完lods时会递增或递减ESI寄存器, 然后把字符串值存放到EAX中

STOS 使用lods把字符串值加载到EAX后, 可以使用它把EAX中的值存储到内存中去: stos使用EDI作为目的操作数, 执行stos指令后, 会根据DF的值自动递增或者递减EDI中的值

4, 比较字符串

cmps 和其他的操作字符串的指令一样, 隐含的源和目标操作数都为ESI和EDI, 每次执行时都会根据DF的值把 ESI和EDI递增或者递减, cmps指令从目标字符串中减去源字符串, 执行后会设置EFLAGS寄存器的状态.

5,扫描字符串

scas 把EDI作为目标, 它把EDI中的字符串和EAX中的字符串进行比较 ,然后根据DF的值递增或者递减EDI

九,使用函数

GNU汇编语言定义函数的语法:
.type 标签(也就是函数名), @function
ret 返回到调用处

十,linux系统调用

linux系统调用的中断向量为0x80

1, 系统调用标识存放在%eax中
2, 系统调用输入值:

1
2
3
4
5
EBX 第一个参数
ECX 第二个参数
EDX 第三个参数
ESI 第四个参数
EDI 第五个参数

需要输入超过6个输入参数的系统调用, EBX指针用于保存指向输入参数内存位置的指针, 输入参数按照连续的的顺序 存储, 系统调用的返回值存放在EAX中

十一,汇编语言的高级功能

1,gnu内联汇编的语法:

asm__asm__(“汇编代码”); 指令必须包含在引号里 如果包含的指令超过一行 必须使用新行分隔符分隔

使用c全局变量, 不能在内联汇编中使用局部变量, 注意在汇编语言代码中值被用做内存位置, 而不是立即数值

如果不希望优化内联汇编, 则可以volatile修饰符如:__asm__ volatile("code");

2,GCC内联汇编的扩展语法

__asm__("assembly code":output locations:input operands:changed registers); 第一部分是汇编代码 第二部分是输出位置, 包含内联汇编代码的输出值的寄存器和内存位置列表 第三部分是输入操作数,包含内联汇编代码输入值的寄存器和内存位置的列表 第四部分是改动的寄存器, 内联汇编改变的任何其他寄存器的列表 这几个部分可以不全有, 但是没有的还必须使用:分隔

1, 指定输入值和输出值, 输入值和输出值的列表格式为:

“constraint”(variable), 其中variable是程序中声明的c变量, 在扩展asm格式中, 局部和全局变量都可以使用, 使用constrant(约束)定义把变量存放到哪(输入)或从哪里传送变量(输出) 约束使用单一的字符, 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
约束 描述
a 使用%eax, %ax, %al寄存器
b 使用%ebx, %bx, %bl寄存器
c 使用%ecx, %cx, %cl寄存器
d 使用%edx, %dx, %dl寄存器
S 使用%esi, %si寄存器
D 使用%edi, %di寄存器
r 使用任何可用的通用寄存器
q 使用%eax, %ebx, %ecx,%edx之一
A 对于64位值使用%eax, %edx寄存器
f 使用浮点寄存器
t 使用第一个(顶部)的浮点寄存器
u 使用第二个浮点寄存器
m 使用变量的内存位置
o 使用偏移内存位置
V 只使用直接内存位置
i 使用立即整数值
n 使用值已知的立即整数值
g 使用任何可用的寄存器和内存位置

除了这些约束之外, 输出值还包含一个约束修饰符:

1
2
3
4
5
输出修饰符 描述
+ 可以读取和写入操作数
= 只能写入操作数
% 如果有必要操作数可以和下一个操作数切换
& 在内联函数完成之前, 可以删除和重新使用操作数

如:
__asm__("assembly code": "=a"(result):"d"(data1),"c"(data2)); 把c变量data1存放在edx寄存器中, 把c变量data2存放到ecx寄存器中, 内联汇编的结果 将存放在eax寄存器中, 然后传送给变量result

在扩展的asm语句块中如果要使用寄存器必须使用两个百分号符号

不一定总要在内联汇编代码中指定输出值, 一些汇编指令假定输入值包含输出值, 如movs指令

其他扩展内联汇编知识:
1, 使用占位符

输入值存放在内联汇编段中声明的特定寄存器中, 并且在汇编指令中专门使用这些寄存器. 虽然这种方式能够很好的处理只有几个输入值的情况, 但对于需要很多输入值的情况, 这 中方式显的有点繁琐. 为了帮助解决这个问题, 扩展asm格式提供了占位符, 可以在内联 汇编代码中使用它引用输入和输出值.

占位符是前面加上百分号的数字, 按照内联汇编中列出的每个输入和输出值在列表中的位置, 每个值被赋予从0开始的地方. 然后就可以在汇编代码中引用占位符来表示值。

如果内联汇编代码中的输入和输出值共享程序中相同的c变量, 则可以指定使用占位符作为 约束值, 如:

1
2
3
__asm__("imull %1, %0"
: "=r"(data2)
: "r"(data1), "0"(data2));

如输入输出值**享相同的变量data2, 而在输入变量中则可以使用标记0作为输入参数的约束

2, 替换占位符

如果处理很多输入和输出值, 数字型的占位符很快就会变的很混乱, 为了使条理清晰 ,GNU汇编 器(从版本3.1开始)允许声明替换的名称作为占位符.替换的名称在声明输入值和输出值的段中 定义, 格式如下:

1
2
3
4
5
%[name]"constraint"(variable)
定义的值name成为内联汇编代码中变量的新的占位符号标识, 如下面的例子:
__asm__("imull %[value1], %[value2]"
: [value2] "=r"(data2)
: [value1] "r"(data1), "0"(data2));
3, 改动寄存器列表

编译器假设输入值和输出值使用的寄存器会被改动, 并且相应的作出处理。程序员不需要在改动的 寄存器列表中包含这些值, 如果这样做了, 就会产生错误消息. 注意改动的寄存器列表中的寄存器 使用完整的寄存器名称, 而不像输入和输出寄存器定义的那样仅仅是单一字母。 在寄存器名称前面 使用百分号符号是可选的。

改动寄存器列表的正确使用方法是, 如果内联汇编代码使用了没有被初始化地声明为输入或者输出 值的其他任何寄存器 , 则要通知编译器。编译器必须知道这些寄存器, 以避免使用他们。如:

1
2
3
4
5
6
7
8
9
10
11
12
int main(void) {
int data1 = 10;
int result = 20;

__asm__("movl %1, %%eax\n\t"
"addl %%eax, %0"
: "=r"(result)
: "r"(data1), "0"(result)
: "%eax");
printf("The result is %d\n", result);
return 0;
}
4, 使用内存位置

虽然在内联汇编代码中使用寄存器比较快, 但是也可以直接使用c变量的内存位置。 约束m用于引用输入值 和输出值中的内存位置。 记住, 对于要求使用寄存器的汇编指令, 仍然必须使用寄存器, 所以不得不定义 保存数据的中间寄存器。如:

1
2
3
4
5
6
7
8
9
10
11
12
int main(void) {
int dividentd = 20;
int divisor = 5;
int result;

__asm__("divb %2\n\t"
"movl %%eax, %0"
: "=m"(result)
: "a"(dividend), "m"(divisor));
printf("The result is %d\n", result);
return 0;
}
5, 处理跳转

内联汇编语言代码也可以包含定义其中位置的标签。 可以实现一般的汇编条件分支和无条件分支, 如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(void) {
int a = 10;
int b = 20;
int result;

__asm__("cmp %1, %2\n\t"
"jge greater\n\t"
"movl %1, %0\n\t"
"jmp end\n"
"greater:\n\t"
"movl %2, %0\n"
"end:"
:"=r"(result)
:"r"(a), "r"(b));
printf("The larger value is %d\n", result);
return 0;
}

在内联汇编代码中使用标签时有两个限制。 第一个限制是只能跳转到相同的asm段内的标签, 不能从-个asm段跳转到另一个asm段中的标签。第二个限制更加复杂一点。 以上程序使用 标签greater和end。 但是, 这样有个潜在的问题, 查看汇编后的代码清单, 可以发现内联 汇编标签也被编码到了最终汇编后的代码中。 这意味着如果在c代码中还有另一个asm段, 就 不能再次使用相同的标签, 否则会因为标签重复使用而导致错误消息。还有如果试图整合使用 c关键字(比如函数名称或者全局变量)的标签也会导致错误。

Linux 汇编基础

绝顶好书Professional_Assembly_Language

一、简介

作为最基本的编程语言之一,汇编语言虽然应用的范围不算很广,但重要性却勿庸置疑,因为它能够完成许多其它语言所无法完成的功能。就拿 Linux 内核来讲,虽然绝大部分代码是用 C 语言编写的,但仍然不可避免地在某些关键地方使用了汇编代码,其中主要是在 Linux 的启动部分。由于这部分代码与硬件的关系非常密切,即使是 C 语言也会有些力不从心,而汇编语言则能够很好扬长避短,最大限度地发挥硬件的性能。

大多数情况下 Linux 程序员不需要使用汇编语言,因为即便是硬件驱动这样的底层程序在 Linux 操作系统中也可以用完全用 C 语言来实现,再加上 GCC 这一优秀的编译器目前已经能够对最终生成的代码进行很好的优化,的确有足够的理由让我们可以暂时将汇编语言抛在一边了。但实现情况是 Linux 程序员有时还是需要使用汇编,或者不得不使用汇编,理由很简单:精简、高效和 libc 无关性。假设要移植 Linux 到某一特定的嵌入式硬件环境下,首先必然面临如何减少系统大小、提高执行效率等问题,此时或许只有汇编语言能帮上忙了。

汇编语言直接同计算机的底层软件甚至硬件进行交互,它具有如下一些优点: 能够直接访问与硬件相关的存储器或 I/O 端口; 能够不受编译器的限制,对生成的二进制代码进行完全的控制; 能够对关键代码进行更准确的控制,避免因线程共同访问或者硬件设备共享引起的死锁; 能够根据特定的应用对代码做最佳的优化,提高运行速度; 能够最大限度地发挥硬件的功能。

同时还应该认识到,汇编语言是一种层次非常低的语言,它仅仅高于直接手工编写二进制的机器指令码,因此不可避免地存在一些缺点: 编写的代码非常难懂,不好维护; 很容易产生 bug,难于调试; 只能针对特定的体系结构和处理器进行优化; 开发效率很低,时间长且单调。

Linux 下用汇编语言编写的代码具有两种不同的形式。第一种是完全的汇编代码,指的是整个程序全部用汇编语言编写。尽管是完全的汇编代码,Linux 平台下的汇编工具也吸收了 C 语言的长处,使得程序员可以使用 #include、#ifdef 等预处理指令,并能够通过宏定义来简化代码。第二种是内嵌的汇编代码,指的是可以嵌入到C语言程序中的汇编代码片段。虽然 ANSI 的 C 语言标准中没有关于内嵌汇编代码的相应规定,但各种实际使用的 C 编译器都做了这方面的扩充,这其中当然就包括 Linux 平台下的 GCC。

C 语言文法 ( C Language Grammar )

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
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
%token IDENTIFIER CONSTANT STRING_LITERAL SIZEOF
%token TYPE_NAME

%token TYPEDEF EXTERN STATIC AUTO REGISTER
%token CHAR SHORT INT LONG SIGNED UNSIGNED FLOAT DOUBLE CONST VOLATILE VOID
%token STRUCT UNION ENUM

%token CASE DEFAULT IF ELSE SWITCH WHILE DO FOR GOTO CONTINUE BREAK RETURN

%start translation_unit
%%
translation_unit
	: external_declaration
	| translation_unit external_declaration
	;

external_declaration
	: function_definition
	| declaration
	;

function_definition
	: declaration_specifiers declarator declaration_list compound_statement
	| declaration_specifiers declarator compound_statement
	| declarator declaration_list compound_statement
	| declarator compound_statement
	;

declaration_list
	: declaration
	| declaration_list declaration
	;

declaration
	: declaration_specifiers ';'
	| declaration_specifiers init_declarator_list ';'
	;
	
declaration_specifiers
	: storage_class_specifier
	| storage_class_specifier declaration_specifiers
	| type_specifier
	| type_specifier declaration_specifiers
	| type_qualifier
	| type_qualifier declaration_specifiers
	;
	
specifier_qualifier_list
	: type_specifier specifier_qualifier_list
	| type_specifier
	| type_qualifier specifier_qualifier_list
	| type_qualifier
	        
type_qualifier_list
	: type_qualifier
	| type_qualifier_list type_qualifier
	;

type_qualifier
	: CONST
	| VOLATILE
	;
 
storage_class_specifier
	: TYPEDEF
	| EXTERN
	| STATIC
	| AUTO
	| REGISTER
	;

type_specifier
	: VOID
	| CHAR
	| SHORT
	| INT
	| LONG
	| FLOAT
	| DOUBLE
	| SIGNED
	| UNSIGNED
	| struct_or_union_specifier
	| enum_specifier
	| TYPE_NAME
	;

struct_or_union_specifier
	: struct_or_union IDENTIFIER '{' struct_declaration_list '}'
	| struct_or_union '{' struct_declaration_list '}'
	| struct_or_union IDENTIFIER
	;

struct_or_union
	: STRUCT
	| UNION
	;

struct_declaration_list
	: struct_declaration
	| struct_declaration_list struct_declaration
	;

struct_declaration
	: specifier_qualifier_list struct_declarator_list ';'
	;

struct_declarator_list
	: struct_declarator
	| struct_declarator_list ',' struct_declarator
	;

struct_declarator
	: declarator
	| ':' constant_expression
	| declarator ':' constant_expression
	;

enum_specifier
	: ENUM '{' enumerator_list '}'
	| ENUM IDENTIFIER '{' enumerator_list '}'
	| ENUM IDENTIFIER
	;

enumerator_list
	: enumerator
	| enumerator_list ',' enumerator
	;

enumerator
	: IDENTIFIER
	| IDENTIFIER '=' constant_expression
	;       
	
init_declarator_list
	: init_declarator
	| init_declarator_list ',' init_declarator
	;       

init_declarator
	: declarator
	| declarator '=' initializer
	;
	
initializer_list
	: initializer
	| initializer_list ',' initializer
	;        

initializer
	: assignment_expression
	| '{' initializer_list '}'
	| '{' initializer_list ',' '}'
	;

parameter_type_list
	: parameter_list
	| parameter_list ',' '...'
	;

parameter_list
	: parameter_declaration
	| parameter_list ',' parameter_declaration

parameter_declaration
	: declaration_specifiers declarator
	| declaration_specifiers abstract_declarator
	| declaration_specifiers
	;

identifier_list
	: IDENTIFIER
	| identifier_list ',' IDENTIFIER
	;

type_name
	: specifier_qualifier_list
	| specifier_qualifier_list abstract_declarator
	;

abstract_declarator
	: pointer
	| direct_abstract_declarator
	| pointer direct_abstract_declarator
	;

direct_abstract_declarator
	: '(' abstract_declarator ')'
	| '[' ']'
	| '[' constant_expression ']'
	| direct_abstract_declarator '[' ']'
	| direct_abstract_declarator '[' constant_expression ']'
	| '(' ')'
	| '(' parameter_type_list ')'
	| direct_abstract_declarator '(' ')'
	| direct_abstract_declarator '(' parameter_type_list ')'
	;

declarator
	: pointer direct_declarator
	| direct_declarator
	;

direct_declarator
	: IDENTIFIER
	| '(' declarator ')'
	| direct_declarator '[' constant_expression ']'
	| direct_declarator '[' ']'
	| direct_declarator '(' parameter_type_list ')'
	| direct_declarator '(' identifier_list ')'
	| direct_declarator '(' ')'
	;

pointer
	: '*'
	| '*' type_qualifier_list
	| '*' pointer
	| '*' type_qualifier_list pointer
	;        
	
statement
	: labeled_statement
	| compound_statement
	| expression_statement
	| selection_statement
	| iteration_statement
	| jump_statement
	;
	       
labeled_statement
	: IDENTIFIER ':' statement
	| CASE constant_expression ':' statement
	| DEFAULT ':' statement
	;

compound_statement
	: '{' '}'
	| '{' statement_list '}'
	| '{' declaration_list '}'
	| '{' declaration_list statement_list '}'
	;        
	     
statement_list
	: statement
	| statement_list statement
	;
     
expression_statement
	: ';'
	| expression ';'
	;

selection_statement
	: IF '(' expression ')' statement
	| IF '(' expression ')' statement ELSE statement
	| SWITCH '(' expression ')' statement
	;

iteration_statement
	: WHILE '(' expression ')' statement
	| DO statement WHILE '(' expression ')' ';'
	| FOR '(' expression_statement expression_statement ')' statement
	| FOR '(' expression_statement expression_statement expression ')' statement
	;

jump_statement
	: GOTO IDENTIFIER ';'
	| CONTINUE ';'
	| BREAK ';'
	| RETURN ';'
	| RETURN expression ';'
	;        

expression
	: assignment_expression
	| expression ',' assignment_expression
	;
	
assignment_expression
	: conditional_expression
	| unary_expression assignment_operator assignment_expression
	;
	
assignment_operator
	: '='
	| '*='
	| '/='
	| '%='
	| '+='
	| '-='
	| '<<='
	| '>>='
	| '&='
	| '^='
	| '|='
	;

constant_expression
	: conditional_expression
	;

conditional_expression
	: logical_or_expression
	| logical_or_expression '?' expression ':' conditional_expression
	;

logical_or_expression
	: logical_and_expression
	| logical_or_expression '||' logical_and_expression
	;

logical_and_expression
	: inclusive_or_expression
	| logical_and_expression '&&' inclusive_or_expression
	;

inclusive_or_expression
	: exclusive_or_expression
	| inclusive_or_expression '|' exclusive_or_expression
	;

exclusive_or_expression
	: and_expression
	| exclusive_or_expression '^' and_expression
	;

and_expression
	: equality_expression
	| and_expression '&' equality_expression
	;

equality_expression
	: relational_expression
	| equality_expression '==' relational_expression
	| equality_expression '!=' relational_expression
	;

relational_expression
	: shift_expression
	| relational_expression '<' shift_expression
	| relational_expression '>' shift_expression
	| relational_expression '<=' shift_expression
	| relational_expression '>=' shift_expression
	;

shift_expression
	: additive_expression
	| shift_expression '<<' additive_expression
	| shift_expression '>>' additive_expression
	;

additive_expression
	: multiplicative_expression
	| additive_expression '+' multiplicative_expression
	| additive_expression '-' multiplicative_expression
	;

multiplicative_expression
	: cast_expression
	| multiplicative_expression '*' cast_expression
	| multiplicative_expression '/' cast_expression
	| multiplicative_expression '%' cast_expression
	;

cast_expression
	: unary_expression
	| '(' type_name ')' cast_expression
	;
	
unary_expression
	: postfix_expression
	| '++' unary_expression
	| '--' unary_expression
	| unary_operator cast_expression
	| SIZEOF unary_expression
	| SIZEOF '(' type_name ')'
	;
	
unary_operator
	: '&'
	| '*'
	| '+'
	| '-'
	| '~'
	| '!'
	;
	
argument_expression_list
	: assignment_expression
	| argument_expression_list ',' assignment_expression
	;

postfix_expression
	: primary_expression
	| postfix_expression '[' expression ']'
	| postfix_expression '(' ')'
	| postfix_expression '(' argument_expression_list ')'
	| postfix_expression '.' IDENTIFIER
	| postfix_expression '->' IDENTIFIER
	| postfix_expression '++'
	| postfix_expression '--'
	;
	
primary_expression
	: IDENTIFIER
	| CONSTANT
	| STRING_LITERAL
	| '(' expression ')'
	;
%%

构造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,…,Yi-1都是非终结符,而且,对于任何j,1<= j <= i-1,FIRST(YJ)都含有ε(即Y1…Yi-1=­­­>ε),则把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中放入(0,#),然后,用当前栈顶状态和当前输入字符查找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)+i
i#
输出截图

第五章 结论

通过以上章节的分析与说明,可以看到,本程序在功能上完全实现了课程设计的要求。并且扩展了一些功能。即对任意给定的上下文无关文法都可以构造出相应的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;
}