第 1章 习题
T4,6.
补充习题：
1）简述程序设计语言的发展简史。
2）解释算法、数据结构的含义。
3）程序语言的使用代价有哪几种量度。
4）程序语言一般有哪几种计算模型，各有和特点。
T4
分析：该题的意思说明一种具体的程序设计语言中规定了一定的语法规则和基本的语句（指令），那么利用这种语言编写程序，必须符合该语言的语法规则，
并且只能使用它的基本指令集。
(a ),1
x = a
L,x = x - 1
b = b - 1
if b > 0 th e n g o to L
h a lt
(a ),2
x = a
c = a
L 1,b = b - 1
L 2,x = x + 1
c = c – 1
if c > 0 th e n g o to L2
if b > 0 th e n g o to L1
h a lt
(a ),3
x = a
m = a
L 1,b = b - 1
L 2,x = x + 1
m = m – 1
if m > 0 th e n g o to L 2
if b > 0 th e n g o to L 1
y = c
n = c
L 4,d = d - 1
L 3,y = y + 1
n = n - 1
if n > 0 th e n g o to L 3
if d > 0 th e n g o to L 4
h a lt
简单的扩充：
如 dim a[10]
a[0] = 1
b = a + c
b = a + 1
b = ‘a’
sub(x,y)
call sub(a,b)
T6
如 ++x; x++; x = x+1; x+=1;
优点,增加了程序开发的灵活性。
缺点,1）降低了程序的可读性；
2）多种语义，使得翻译较为复杂；
3）容易出错，如 y=x++; 与 y=++x;
1）简述程序设计语言的发展简史。
从语言的角度考虑：程序设计语言经历了：机器语言 — >汇编语言 — >高级语言的发展。
其中：机器语言是一种二进制代码语言，它能够被计算机直接识别和运行，无须翻译。但它的缺点是：可读性极差；容易出错；可维护性差。
汇编语言：是一种助记符语言，其源程序计算机不能直接识别和运行，需要经过汇编生成机器语言程序后才能运行。它的优点是：相对于机器语言而言，可读性，可维护性，可写性都有所提高。
它的特点是：一条汇编语言指令对应着一条机器语言指令。
高级语言：是一种类似于自然语言的程序设计语言。其源程序也不能在计算机上直接运行，
需要经过翻译成目标代码程序（或中间代码程序经解释）而执行。它的优点是：相对于汇编语言而言，可读性，可维护性，可写性都有很大的提高。
机器语言高级语言汇编语言
} 低级语言执行语言翻译
从对程序的要求角度而言经历了,简单性,
到,复杂性,；编程强调,技巧性,到,可读性,；追求实现的,高效性,到,可维护性,
和强调,可移植性,的演变与发展。
2）解释算法、数据结构的含义。
程序 = 算法 + 数据结构。其中：
算法：应用问题的处理需要一定的求解过程，
对求解过程的描述称之为算法，它通常包含一些操作。
数据结构：是指操作所需要的相关数据的组织和在存储器中的存储形式。
4）程序语言的使用代价有哪几种量度？
– 程序执行代价：运行时占用系统资源代价。
如今，不是关心的主要问题。
– 翻译的代价：翻译的速度和占用系统资源代价，对于教学性的语言较为强调。
– 程序创建、测试和使用的代价：程序员设计、
编码、调试、修改、集成、测试和使用时投入的总时间与工作量。这是目前最关心的代价之一。
– 程序维护的代价：在程序的使用过程中对程序反复修改、修复和升级扩充所花费的代价。
这是目前最关心的代价之一。
5）程序语言一般有哪几种计算模型，各有何特点？
– 命令式语言（过程式语言）：是命令驱动和面向语句的语言。程序由一系列的语句组成。
每条语句执行的结果使得计算机改变一个或多个存储单元的值，即进入一个新的状态。
该计算模型的优点是：效率较高。主要的应用领域为：科学计算、系统设计、商业应用、
工业控制等领域。
应用式语言（函数式语言）：以数据为驱动，
强调程序（函数）执行的初始状态和处理（输出）结果。不是将计算看成连续的机器状态的转换，而是看成为了得到答案而应用于数据的连续的函数转换。该计算模型可看成是一个以原始数据作为输入，对内存进行操作以产生答案的透镜。该模型的优点是：较好的灵活性和可靠性。主要应用领域是：人工智能。
基于规则语言（逻辑编程语言）：以条件作为驱动而执行相应动作的语言。规则 =
条件 +动作。类似于命令式语言，但语句不是连续的，启用条件决定语句的执行顺序。该计算模型可看作是应用于数据的一个过滤器集合。通过使用过滤器来改变状态。该模型的优点是：较好的灵活性和决策推理性。主要应用领域是：人工智能和决策支持。
面向对象语言：以对象为程序单元。通过建立复杂的数据对象，并且设计有限的函数集对对象实施操作。该模型的优点：结合命令式和应用式语言的优点。具有较高的效率以及较好的灵活性和可靠性。其主要应用领域：科学计算、
系统设计、商业应用、工业控制等领域 。
第 2章 习题T1,2,5
补充习题：
1）程序设计语言具有那几个基本特征。
2）什么叫固件计算机，虚拟计算机，绑定，绑定时间。
3）编译和解释的实现原理是什么，各有何特点。
4）请画出虚拟计算机系统的典型层次结构。并简述各个层次是由什么支持实现的。
5）绑定时间可分成哪几个类型。
T1
以 C语言为例。
C语言程序的可执行形式是,exe文件（从用户角度看），实际上是 C源程序的目标代码（ *.o
文件）与库函数等程序连接而成的文件。
将各类语句和表达式转换成可执行的代码时时用了编译。具体的说使用了编译器、汇编器、
装入与连接器以及预处理器。
在程序执行过程中需要支持库函数运行的软件模拟，通过解释执行。
该解释器可以通过软件模拟。
对于一些构造的数据类型，如结构、指针、动态链表、外部文件结构、时间日期功能等的原始操作需要软件模拟。
T2
以网络操作系统 Win2000为例。
该虚拟机于实际计算机的区别是：实际计算机只能处理硬件所支持的基本操作，只能执行机器语言程序。而该虚拟计算机可以通过软件模拟解释执行网络应用程序
（如用 java开发的 Applet小程序）。网络应用程序可以通过解释执行。
实际硬件计算机
（由物理设备实现）
固件虚拟计算机
（由微程序指令控制实现）
机器语言虚拟计算机
（由微程序解释实现）
操作系统虚拟计算机
（由机器语言程序实现）
汇编语言虚拟计算机高级语言虚拟计算机网络虚拟计算机网络应用虚拟计算机网络操作系统的虚拟机层次结构
存在硬件允许但被操作系统限制的特征：如对存储器直接分配和管理功能、输入输出、关机等。
操作系统定义的虚拟机提供了 HTML格式的数据结构,Applet小程序中的数据结构以及对该数据结构的操作等需要通过复杂的软件才能实现。
T5
以 C语言语句 X= fun(y) +10为例。
1) 变量 y的类型集,y的类型通常在语言定义时确定，如只有整型类型是允许类型 。
2）变量 y的类型,变量 y的具体类型一般在编译时确定,即变量 y的类型 绑定时间是编译时 。
通常通过在程序中使用显式声明 语句，如 int y。
3) 变量 x的类型集：与 1）相同,x的类型通常在语言定义时确定 。
4）变量 x的类型,与 2）相同，变量 x的类型 绑定时间是编译时 。
5) 变量 y可能的值：如果 y的类型是整型，则 y
的值就是整数集合中的一个元素，该集合的大小由 C语言的虚拟计算机可以表示和操作的整数 (-32768~32767)确定，所以，变量 y可能的值的绑定时间是语言定义时。
6)变量 y的值：在程序执行的任何一点，变量 y
都有一个值。如果在定义变量 y时进行了初始化，则编译时就将实际的值与变量 y绑定。如果，没有进行初始化，在编译时将分配给变量
y的存储单元中的值与 y绑定。
7) 变量 x可能的值：与 5）相同，变量 x可能的值的绑定时间是语言定义时。
8)变量 x的值：在程序执行的任何一点，变量 y
都有一个值。如果在定义变量 x时进行了初始化，则编译时就将实际的值与变量 x绑定。如果，没有进行初始化，在编译时将分配给变量
x的存储单元中的值与 x绑定。在程序运行过程中，根据赋值语句重新改变变量 X与其值的绑定关系。此时，变量 X与其值的绑定时间是运行时。
9) 标识符 fun的类型集：与 1）相同,fun的类型通常在语言定义时确定 。
10）标识符 fun的类型：与 2）相同，变量 fun
的类型绑定时间是编译时。
11) fun ()可能的值,fun()可能的值的绑定时间是语言定义时。例如，如果 fun()的类型是整型，
则 fun()的可能值的大小由 C语言的虚拟计算机可以表示和操作的整数 (-32768~32767)确定,
12) fun ()的值：在程序运行过程中，根据参数
y的值，进行计算改变 fun()与其值的绑定关系。
此时,fun()与其值的绑定时间是运行时。
13）常数 10的表示：在程序文本中，整数 10是使用字符串,10”表示的，而在执行时表示为一个位串序列。在程序文本中，选择 10进制表示法通常是在语言定义时确定的，而在运行时如何表示为一个位串序列是由语言实现时确定的。即常数 10在语言定义时进行了一个绑定，
而在语言实现时，重新进行绑定。
14）操作符,+”的性质：操作符,+”可以是加法操作，也可能是字符串连接操作。这种可能的性质是由语言定义时确定的。即操作符,+”
可能的操作性质的绑定时间是语言定义时。但操作符,+”的具体操作性质的绑定时间是编译时。编译程序可以通过操作数的类型来确定
,+”的具体操作性质。
第三章 习题
T1,2,3,6,11
补充习题：
1）解释名词可读性、可写性、易验证性和易翻译性的含义。
2）什么叫二义性，解决方法通常有哪些。
3）简述词法分析、语法分析的原理和过程。
4）简述语义分析的主要功能。
5）简述优化的原理。
T1
该题的关键是分析出语法树，然后通过语法树构造表达式。
<pop>
<bop>
<boop>
Z
(a)
<pop>
<boop>
x
(b)
( <pop> )
<bop>
<bop>
[ <bop>,<pop> ]
<pop>
<boop>
y
(c)无法实现
<pop>
<boop>
x
(d)
( <pop> )
<bop>
<bop>
[ <bop>,<pop> ]
<boop>
y
<pop>
(e)
( <pop> )
<bop>
<bop>
[ <bop>,<pop> ]
<boop>
x
<bop>
<boop>
y
<pop>
(f)
( <pop> )
<bop>
<bop>
[ <bop>,<pop> ]
<boop>
x
<bop><boop>
y
[ <bop>,<pop> ]
<boop>
x
T2
S-->SS|(S)|( )存在二义性，如下图所示。
可改写为：
S--> S( )|(S)|( )(S)| ( )
S
S
S
( )
SS
( )( )
S
S
( )
S
SS
( )( )
T3
如果文法具有二义性，则相同的字符系列存在两颗不同的语法分析树。
如果文法无二义性，则一个字符系列仅存在唯一的一颗语法分析树。
T6
通过符号系列进行反推
<sen>
<sen> # word
<syl> <word> <syl>
a<plo>
a b
<syl>
<plo><stop>
<stop>a
b a b
a<plo>
a b a
<stop>a
a
<stop>a
<sen> # word
<sen> # word
<word>
<syl>
<plo>
<stop>a
b a #
Ap
e讲话语法图
(1)
<sen> # word
<syl> <word> <syl>
<stop>a
<syl>
<plo><stop>
b a d
<sen> # word
#
<plo><stop>
d a b
<stop>a
<syl>
<plo>
b a
<stop>a
<plo>
d a
<stop>a
#
Ape讲话语法图 (2)
<sen>
<sen> # word
<word>
<syl> <word> <syl>
a<stop>
a b
<syl> <word> <syl>
<plo>
<stop>a
d a
<syl>
<plo>
<stop>a
b a
a<stop>
a d
a<stop>
a b
<stop>a
d a
<syl>
a<plo>
# a
Chimp讲话语法图
<sen>
<sen> # <word>
<word> <syl> <word> <syl>
<sen> # < word>
<sen> # <word>
<syl>
<plo> <stop>
<stop>a
d a d #
<syl>
a<stop>
a d #
<stop>a
b aa
<syl>
a<stop>a<stop>
a d a d
a <plo>
Baboon讲话语法图 (1)
<plo>
<syl> <word> <syl>
<stop>a
b a
<syl> <word> <syl>
<plo> <stop>
<stop>a
d a d
<syl>
<stop>a
b a
a<stop>
a d
<sen> # <word>
#
badadbaad
Baboon讲话语法图 (2)
1）解释名词可读性、可写性、易验证性和易翻译性的含义。
可读性,如果一个程序的算法和数据结构能够明显的从程序文本中观察出来，则这个程序是可读的。可读的程序称之为自引证的。
可写性是指程序易于编写。语法结构简单的 语言程序可写性好。
易检验性,证明程序的正确性。这不仅涉及到语法，主要涉及到语义的正确性验证。
易翻译性：源程序容易翻译成可执行的目标程序。易翻译性与翻译器密切关联。
2）什么叫二义性，解决方法通常有哪些。
所谓二义性是指：相同的语法结构存在两种或更多种理解。二义性问题通常不是出现在单个的程序元素中，而是在不同结构的相互作用下表现出来的。
解决方法 1：插入定界符。
解决方法 2：在多种语义中选择一个作为合理的解释。
3）简述词法分析、语法分析的原理和过程。
词法分析原理：利用词法分析器将源程序中的字符串划分成基本要素单元。划分的结果称为语法项。
分析过程：将源程序代码逐字采用假读（超前搜索）的方式阅读到一个缓冲器中；根据具体语言提供的字符集、关键字、保留字集合等加以判断；分离出基本语法要素单元。
语法分析原理：按照具体语言的语法规则，从词法分析的结果（语法项）中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。
分析过程：利用语法分析器，以语法项为输入数据 ;通过采用自顶向下分析方法：递归子程序法和 LL(1)分析法或自低向上的分析方法：
LR分析法或高效的基于形式语法的技术识别出各类语法成分；然后进行语法检查。
4）简述语义分析的主要功能。
语义分析的主要功能是：处理语法分析而识别出来的语法结构，生成中间代码。语义分析任务由语义分析器完成。此外，还完成其它的辅助性功能，如符号表的维护、隐含信息的插入、
错误检测、宏扩展等。
5）简述优化的原理。
语义分析器的输出结构是中间代码。中间代码一般是一种内部表达方式。代码生成器将根据这些中间代码生成目标代码。但在代码生成之前，可对中间代码进行一些优化处理。
代码优化的原理是：分析中间代码，将中间代码中生成的一些临时中间变量的存储、读取等操作删除，将一些复杂的算法过程进行简化。
从而获得较高的执行效率的目的代码。
T4,6.
补充习题：
1）简述程序设计语言的发展简史。
2）解释算法、数据结构的含义。
3）程序语言的使用代价有哪几种量度。
4）程序语言一般有哪几种计算模型，各有和特点。
T4
分析：该题的意思说明一种具体的程序设计语言中规定了一定的语法规则和基本的语句（指令），那么利用这种语言编写程序，必须符合该语言的语法规则，
并且只能使用它的基本指令集。
(a ),1
x = a
L,x = x - 1
b = b - 1
if b > 0 th e n g o to L
h a lt
(a ),2
x = a
c = a
L 1,b = b - 1
L 2,x = x + 1
c = c – 1
if c > 0 th e n g o to L2
if b > 0 th e n g o to L1
h a lt
(a ),3
x = a
m = a
L 1,b = b - 1
L 2,x = x + 1
m = m – 1
if m > 0 th e n g o to L 2
if b > 0 th e n g o to L 1
y = c
n = c
L 4,d = d - 1
L 3,y = y + 1
n = n - 1
if n > 0 th e n g o to L 3
if d > 0 th e n g o to L 4
h a lt
简单的扩充：
如 dim a[10]
a[0] = 1
b = a + c
b = a + 1
b = ‘a’
sub(x,y)
call sub(a,b)
T6
如 ++x; x++; x = x+1; x+=1;
优点,增加了程序开发的灵活性。
缺点,1）降低了程序的可读性；
2）多种语义，使得翻译较为复杂；
3）容易出错，如 y=x++; 与 y=++x;
1）简述程序设计语言的发展简史。
从语言的角度考虑：程序设计语言经历了：机器语言 — >汇编语言 — >高级语言的发展。
其中：机器语言是一种二进制代码语言，它能够被计算机直接识别和运行，无须翻译。但它的缺点是：可读性极差；容易出错；可维护性差。
汇编语言：是一种助记符语言，其源程序计算机不能直接识别和运行，需要经过汇编生成机器语言程序后才能运行。它的优点是：相对于机器语言而言，可读性，可维护性，可写性都有所提高。
它的特点是：一条汇编语言指令对应着一条机器语言指令。
高级语言：是一种类似于自然语言的程序设计语言。其源程序也不能在计算机上直接运行，
需要经过翻译成目标代码程序（或中间代码程序经解释）而执行。它的优点是：相对于汇编语言而言，可读性，可维护性，可写性都有很大的提高。
机器语言高级语言汇编语言
} 低级语言执行语言翻译
从对程序的要求角度而言经历了,简单性,
到,复杂性,；编程强调,技巧性,到,可读性,；追求实现的,高效性,到,可维护性,
和强调,可移植性,的演变与发展。
2）解释算法、数据结构的含义。
程序 = 算法 + 数据结构。其中：
算法：应用问题的处理需要一定的求解过程，
对求解过程的描述称之为算法，它通常包含一些操作。
数据结构：是指操作所需要的相关数据的组织和在存储器中的存储形式。
4）程序语言的使用代价有哪几种量度？
– 程序执行代价：运行时占用系统资源代价。
如今，不是关心的主要问题。
– 翻译的代价：翻译的速度和占用系统资源代价，对于教学性的语言较为强调。
– 程序创建、测试和使用的代价：程序员设计、
编码、调试、修改、集成、测试和使用时投入的总时间与工作量。这是目前最关心的代价之一。
– 程序维护的代价：在程序的使用过程中对程序反复修改、修复和升级扩充所花费的代价。
这是目前最关心的代价之一。
5）程序语言一般有哪几种计算模型，各有何特点？
– 命令式语言（过程式语言）：是命令驱动和面向语句的语言。程序由一系列的语句组成。
每条语句执行的结果使得计算机改变一个或多个存储单元的值，即进入一个新的状态。
该计算模型的优点是：效率较高。主要的应用领域为：科学计算、系统设计、商业应用、
工业控制等领域。
应用式语言（函数式语言）：以数据为驱动，
强调程序（函数）执行的初始状态和处理（输出）结果。不是将计算看成连续的机器状态的转换，而是看成为了得到答案而应用于数据的连续的函数转换。该计算模型可看成是一个以原始数据作为输入，对内存进行操作以产生答案的透镜。该模型的优点是：较好的灵活性和可靠性。主要应用领域是：人工智能。
基于规则语言（逻辑编程语言）：以条件作为驱动而执行相应动作的语言。规则 =
条件 +动作。类似于命令式语言，但语句不是连续的，启用条件决定语句的执行顺序。该计算模型可看作是应用于数据的一个过滤器集合。通过使用过滤器来改变状态。该模型的优点是：较好的灵活性和决策推理性。主要应用领域是：人工智能和决策支持。
面向对象语言：以对象为程序单元。通过建立复杂的数据对象，并且设计有限的函数集对对象实施操作。该模型的优点：结合命令式和应用式语言的优点。具有较高的效率以及较好的灵活性和可靠性。其主要应用领域：科学计算、
系统设计、商业应用、工业控制等领域 。
第 2章 习题T1,2,5
补充习题：
1）程序设计语言具有那几个基本特征。
2）什么叫固件计算机，虚拟计算机，绑定，绑定时间。
3）编译和解释的实现原理是什么，各有何特点。
4）请画出虚拟计算机系统的典型层次结构。并简述各个层次是由什么支持实现的。
5）绑定时间可分成哪几个类型。
T1
以 C语言为例。
C语言程序的可执行形式是,exe文件（从用户角度看），实际上是 C源程序的目标代码（ *.o
文件）与库函数等程序连接而成的文件。
将各类语句和表达式转换成可执行的代码时时用了编译。具体的说使用了编译器、汇编器、
装入与连接器以及预处理器。
在程序执行过程中需要支持库函数运行的软件模拟，通过解释执行。
该解释器可以通过软件模拟。
对于一些构造的数据类型，如结构、指针、动态链表、外部文件结构、时间日期功能等的原始操作需要软件模拟。
T2
以网络操作系统 Win2000为例。
该虚拟机于实际计算机的区别是：实际计算机只能处理硬件所支持的基本操作，只能执行机器语言程序。而该虚拟计算机可以通过软件模拟解释执行网络应用程序
（如用 java开发的 Applet小程序）。网络应用程序可以通过解释执行。
实际硬件计算机
（由物理设备实现）
固件虚拟计算机
（由微程序指令控制实现）
机器语言虚拟计算机
（由微程序解释实现）
操作系统虚拟计算机
（由机器语言程序实现）
汇编语言虚拟计算机高级语言虚拟计算机网络虚拟计算机网络应用虚拟计算机网络操作系统的虚拟机层次结构
存在硬件允许但被操作系统限制的特征：如对存储器直接分配和管理功能、输入输出、关机等。
操作系统定义的虚拟机提供了 HTML格式的数据结构,Applet小程序中的数据结构以及对该数据结构的操作等需要通过复杂的软件才能实现。
T5
以 C语言语句 X= fun(y) +10为例。
1) 变量 y的类型集,y的类型通常在语言定义时确定，如只有整型类型是允许类型 。
2）变量 y的类型,变量 y的具体类型一般在编译时确定,即变量 y的类型 绑定时间是编译时 。
通常通过在程序中使用显式声明 语句，如 int y。
3) 变量 x的类型集：与 1）相同,x的类型通常在语言定义时确定 。
4）变量 x的类型,与 2）相同，变量 x的类型 绑定时间是编译时 。
5) 变量 y可能的值：如果 y的类型是整型，则 y
的值就是整数集合中的一个元素，该集合的大小由 C语言的虚拟计算机可以表示和操作的整数 (-32768~32767)确定，所以，变量 y可能的值的绑定时间是语言定义时。
6)变量 y的值：在程序执行的任何一点，变量 y
都有一个值。如果在定义变量 y时进行了初始化，则编译时就将实际的值与变量 y绑定。如果，没有进行初始化，在编译时将分配给变量
y的存储单元中的值与 y绑定。
7) 变量 x可能的值：与 5）相同，变量 x可能的值的绑定时间是语言定义时。
8)变量 x的值：在程序执行的任何一点，变量 y
都有一个值。如果在定义变量 x时进行了初始化，则编译时就将实际的值与变量 x绑定。如果，没有进行初始化，在编译时将分配给变量
x的存储单元中的值与 x绑定。在程序运行过程中，根据赋值语句重新改变变量 X与其值的绑定关系。此时，变量 X与其值的绑定时间是运行时。
9) 标识符 fun的类型集：与 1）相同,fun的类型通常在语言定义时确定 。
10）标识符 fun的类型：与 2）相同，变量 fun
的类型绑定时间是编译时。
11) fun ()可能的值,fun()可能的值的绑定时间是语言定义时。例如，如果 fun()的类型是整型，
则 fun()的可能值的大小由 C语言的虚拟计算机可以表示和操作的整数 (-32768~32767)确定,
12) fun ()的值：在程序运行过程中，根据参数
y的值，进行计算改变 fun()与其值的绑定关系。
此时,fun()与其值的绑定时间是运行时。
13）常数 10的表示：在程序文本中，整数 10是使用字符串,10”表示的，而在执行时表示为一个位串序列。在程序文本中，选择 10进制表示法通常是在语言定义时确定的，而在运行时如何表示为一个位串序列是由语言实现时确定的。即常数 10在语言定义时进行了一个绑定，
而在语言实现时，重新进行绑定。
14）操作符,+”的性质：操作符,+”可以是加法操作，也可能是字符串连接操作。这种可能的性质是由语言定义时确定的。即操作符,+”
可能的操作性质的绑定时间是语言定义时。但操作符,+”的具体操作性质的绑定时间是编译时。编译程序可以通过操作数的类型来确定
,+”的具体操作性质。
第三章 习题
T1,2,3,6,11
补充习题：
1）解释名词可读性、可写性、易验证性和易翻译性的含义。
2）什么叫二义性，解决方法通常有哪些。
3）简述词法分析、语法分析的原理和过程。
4）简述语义分析的主要功能。
5）简述优化的原理。
T1
该题的关键是分析出语法树，然后通过语法树构造表达式。
<pop>
<bop>
<boop>
Z
(a)
<pop>
<boop>
x
(b)
( <pop> )
<bop>
<bop>
[ <bop>,<pop> ]
<pop>
<boop>
y
(c)无法实现
<pop>
<boop>
x
(d)
( <pop> )
<bop>
<bop>
[ <bop>,<pop> ]
<boop>
y
<pop>
(e)
( <pop> )
<bop>
<bop>
[ <bop>,<pop> ]
<boop>
x
<bop>
<boop>
y
<pop>
(f)
( <pop> )
<bop>
<bop>
[ <bop>,<pop> ]
<boop>
x
<bop><boop>
y
[ <bop>,<pop> ]
<boop>
x
T2
S-->SS|(S)|( )存在二义性，如下图所示。
可改写为：
S--> S( )|(S)|( )(S)| ( )
S
S
S
( )
SS
( )( )
S
S
( )
S
SS
( )( )
T3
如果文法具有二义性，则相同的字符系列存在两颗不同的语法分析树。
如果文法无二义性，则一个字符系列仅存在唯一的一颗语法分析树。
T6
通过符号系列进行反推
<sen>
<sen> # word
<syl> <word> <syl>
a<plo>
a b
<syl>
<plo><stop>
<stop>a
b a b
a<plo>
a b a
<stop>a
a
<stop>a
<sen> # word
<sen> # word
<word>
<syl>
<plo>
<stop>a
b a #
Ap
e讲话语法图
(1)
<sen> # word
<syl> <word> <syl>
<stop>a
<syl>
<plo><stop>
b a d
<sen> # word
#
<plo><stop>
d a b
<stop>a
<syl>
<plo>
b a
<stop>a
<plo>
d a
<stop>a
#
Ape讲话语法图 (2)
<sen>
<sen> # word
<word>
<syl> <word> <syl>
a<stop>
a b
<syl> <word> <syl>
<plo>
<stop>a
d a
<syl>
<plo>
<stop>a
b a
a<stop>
a d
a<stop>
a b
<stop>a
d a
<syl>
a<plo>
# a
Chimp讲话语法图
<sen>
<sen> # <word>
<word> <syl> <word> <syl>
<sen> # < word>
<sen> # <word>
<syl>
<plo> <stop>
<stop>a
d a d #
<syl>
a<stop>
a d #
<stop>a
b aa
<syl>
a<stop>a<stop>
a d a d
a <plo>
Baboon讲话语法图 (1)
<plo>
<syl> <word> <syl>
<stop>a
b a
<syl> <word> <syl>
<plo> <stop>
<stop>a
d a d
<syl>
<stop>a
b a
a<stop>
a d
<sen> # <word>
#
badadbaad
Baboon讲话语法图 (2)
1）解释名词可读性、可写性、易验证性和易翻译性的含义。
可读性,如果一个程序的算法和数据结构能够明显的从程序文本中观察出来，则这个程序是可读的。可读的程序称之为自引证的。
可写性是指程序易于编写。语法结构简单的 语言程序可写性好。
易检验性,证明程序的正确性。这不仅涉及到语法，主要涉及到语义的正确性验证。
易翻译性：源程序容易翻译成可执行的目标程序。易翻译性与翻译器密切关联。
2）什么叫二义性，解决方法通常有哪些。
所谓二义性是指：相同的语法结构存在两种或更多种理解。二义性问题通常不是出现在单个的程序元素中，而是在不同结构的相互作用下表现出来的。
解决方法 1：插入定界符。
解决方法 2：在多种语义中选择一个作为合理的解释。
3）简述词法分析、语法分析的原理和过程。
词法分析原理：利用词法分析器将源程序中的字符串划分成基本要素单元。划分的结果称为语法项。
分析过程：将源程序代码逐字采用假读（超前搜索）的方式阅读到一个缓冲器中；根据具体语言提供的字符集、关键字、保留字集合等加以判断；分离出基本语法要素单元。
语法分析原理：按照具体语言的语法规则，从词法分析的结果（语法项）中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。
分析过程：利用语法分析器，以语法项为输入数据 ;通过采用自顶向下分析方法：递归子程序法和 LL(1)分析法或自低向上的分析方法：
LR分析法或高效的基于形式语法的技术识别出各类语法成分；然后进行语法检查。
4）简述语义分析的主要功能。
语义分析的主要功能是：处理语法分析而识别出来的语法结构，生成中间代码。语义分析任务由语义分析器完成。此外，还完成其它的辅助性功能，如符号表的维护、隐含信息的插入、
错误检测、宏扩展等。
5）简述优化的原理。
语义分析器的输出结构是中间代码。中间代码一般是一种内部表达方式。代码生成器将根据这些中间代码生成目标代码。但在代码生成之前，可对中间代码进行一些优化处理。
代码优化的原理是：分析中间代码，将中间代码中生成的一些临时中间变量的存储、读取等操作删除，将一些复杂的算法过程进行简化。
从而获得较高的执行效率的目的代码。
