12 程序设计语言

语言处理程序

汇编程序

地址寄存器AR、数据寄存器DR、指令寄存器IR对汇编语言透明的不可见，程序计数器PC可见

算术指令

带符号数左移*2或右移/2

SAL算数左移：把目的操作数的低位向高位移，空出低位补0

SAR算术右移：把目的操作数的高位向低位移，空出高位用最高位（符号位）填补

逻辑指令

用于无符号数*2或/2

SHL逻辑左移：移位后空出位补0

SHR逻辑右移：移位后空出位补0

循环移位指令

蛇咬尾模式

ROL循环左移

ROR循环右移

RCL带进位的循环左移

带进位，所以P进制左移1位即xP

RCR带进位的循环右移

双精度移位指令

SHLD双精度左移

SHRD双精度右移

编译程序

文法，词法，有限自动机。

正规式：正则表达式，表示正规集的工具，对应一个正规文法。

DFA（确定的有限自动机）与NFA（不确定的有限自动机）的转换

编译原理一定会考词法分析，它是后面编译过程的基础。

主要考的内容是正规式与有穷自动机的转换等

自动状态机和正则表达式

过程概述

文法

分类

0型文法（短语文法）：递归、可枚举

1型文法（上下文有关文法）

2型文法（上下文无关文法）

3型文法（正规文法/线性文法）：等价于正规式

描述

文法G=(Vn，Vt，P，S)

Vn非终结符，Vt终结符，Vn∪Vt表示词汇表V，内含文法符号

P产生式的有限集合，S开始符号∈Vn

句型：若G开始符号S，从S能推导出的符号串，称为句型

句子：仅含Vt终结符的句型是一个句子

语言：从G的S出发，能推导出的所有句子的集合，称为G产生的语言

等价L(G1)=L(G2)，即文法G1与G2产生的语言相同

词法分析

正规集：词法规则产生的集合，即字母表ε的字符串子集

正规表达式：一个正规式表示一个正规集

有限自动机：识别正规集装置的抽象概念

NFA不确定的有限自动机（五元组）

DFA确定的有限自动机（五元组）：是NFA的特例

状态转换图、状态转换矩阵P72

NFA到DFA转换、DFA最小化

语法

2型文法(上下文无关文法)应用的语言最广泛

规范推导(最右推导)

短语、直接短语、句柄

自顶向下语法分析：预测分析模型P80

自底向上语法分析：移进——规约分析模型P81

中间代码生成

后缀式(逆波兰式)

x:=(a+b)*(c+d)的后缀式xab+cd+*:=

树形表示

三元式

x:=(a+b)*(c+d)的三元式表示为：

①(+,a,b) ②(+,c,d) ③(*,①,②) ④(:=,③,x)

四元式

x:=(a+b)*(c+d)的三元式表示为：

①(+,a,b,t1) ②(+,c,d,t2) ③(*,t1,t2,t3) ④(:=,t3,_,x)

编译器

过程：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码

编译器不一定生成中间代码并优化，但生成中间代码可以实现前后级分离

解释程序

解释器

过程：词法分析、语法分析、语义分析、执行

解释器参与运行控制，程序执行速度慢

程序设计语言

C语言

指针及指针数组、指针函数等等。

要掌握好三种基本结构、数组、链表、结构体、共用体、参数传递

传值

调用(实参)->被调用(形参)，形参内存内容=实参的值

传引用

调用(实参引用)->被调用(形参)，形参=实参别名

传址

调用(实参地址)->被调用(形参)，形参内存内容=实参地址