第一章
1. 程序设计语言是人与计算机联系的工具，通过程序设计语言指挥计算机按照自己的意志
进行运算和操作显示信息和输出运算结果。
2. 最早的计算机程序设计语言是机器语言(指令系统)。机器语言中的指令都是用二进制代码
直接表示的。
3. 机器语言和符号语言以及汇编语言都是低级程序设计语言。
4. 1954年FORTRAN I语言的问世标志计算机高级程序设计语言的诞生。
5. 计算机高级程序设计语言独立于机器，比较接近于自然语言，容易学习掌握，编写程序效
率高，编写的程序易读易理解易移植。
6. 翻译程序：将高级语言编写的程序翻译成机器语言。
7. 编译程序的工作过程：编译程序这要功能是将源程序翻译成等价的目标程序，这个翻译
过程分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。
8. 编译程序的重要意义在于它使高级语言独立于机器语言，使程序员用高级语言编写程序
时不必考虑那些直接与机器有关的琐碎的环节，这些细节由编译程序区处理。
9. 编译程序包括：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序和目标代码生成程序以及表格处理程序和出错处理程序。
10.编译程序的组织方式：编译过程分为六个阶段，改划分是编译程序的逻辑组织方式。编译
过程分为前端和后端。前端包括词法分析、语法分析、语义分析、中间代码生成、代码优化。后端包括目标代码生成，依赖于计算机的硬件系统和机器指令系统。这种组织方式便于编译程序的移植，如果移植到不同类型的机器上只需修改编译程序的后端即可。
11.翻译方式：编译方式和解释方式。
12.源程序：用高级语言编写的程序。源程序是编译程序加工的对象。
13.编译方式：先将源程序翻译成汇编语言程序或机器语言程序（目标程序），然后再执行。
这个翻译程序为编译程序.
14.编译方式中源程序的编译和目标程序的运行时分成两个阶段完成的。编译所的目标程序计算机暂时不能执行，必须由连接装配程序将目标程序和编译程序及系统子程序连接成一个可执行程序，这个可执行程序可直接被计算机执行。例如FORTRAN,ALGOL,PASCAL,C,C++等等。
15.解释方式：对源程序边翻译边执行，按解释方式进行翻译的翻译程序为解释程序。优点
在于便于对源程序调试和修改，加工处理过程慢。
16.解释程序：按解释方式进行翻译的翻译程序.
17.词法分析：词法分析是编译过程的基础，任务是扫描源程序，根据语言的词法规则分解
和识别出每个单词，并把单词翻译成相应的机内表示。在识别单词的过程中同时也做词法检查。
18.语法分析：语法分析师在词法分析的基础上进行的。任务是根据语言的语法规则把单词
符号串分解成格内语法单位，如表达式、语句等。通过语法分析确定整个输入符号串是否构成一个语法正确的程序。
19.语义分析：任务是对源程序进行语义检查，其目的是保证标识符和常数的正确使用，把
必要的信息收集保存到符表或中间代码程序中，并进行相应的处理。
20.中间代码生成：是必不可少的阶段，任务是在语法分析和语义分析基础上把语法成分的
语义对其继续翻译，翻译的结果是某种中间代码形式，这种中间代码的结果简单，接近计算机的指令形式，能够很容易被翻译成计算机指令，常用的中间代码有三元式，四元式和逆波兰式。
21.目标代码生成：任务：将中间代码或优化之后的中间代码转换为等价的目标代码，即机器指
令或汇编语言。由中间代码很容易生成目标程序（地址指令序列）。这部分工作与机器关系密切，所以要根据机器进行。在做这部分工作时（要注意充分利用累加器），也可以进行优化处理。
22.编译程序的自展、移植与自动化：高级语言的自编译性是指可以用这个语言来编写自己
的编译程序。对于具有自编译性的高级语言，可运用自展技术构造其编译程序。即先对语言的核心部分构造一个小小的编译程序(可用低级语言实现)，再以它为工具构造一个能够编译更多语言成分的较大编译程序，如此扩展下去，最后形成整个编译程序。
23.高级语言的自编译性：是指可以用这个语言来编写自己的编译程序。一个具有自编译性
的高级语言该机其他高级语言的编译程序。
24.编译程序的移植：将一个机器(宿主机)上的具有自编译性的高级语言编译程序移植到另一
个机器上(目标机)。
25.编译程序的自动化：在编译程序自动化中开发早和应用广泛的是分析程序生成器和语法
分析程序生成器。LEX是一个有代表的性的词法分析生成器。输入的是正规表达式，输出的是词法分析器。LEX的基本思想是由正规表达式构造有穷自动机。YACC是一种基于LALR(1)文法的语法分析生成器。他接受LALR(1)文法生成一个相应的LALR(1)分析表以及一个LALR(1)分析器，而且YACC得语法分析程序可以和扫描器连接。在YACC源程序中除2型语言的规则之外，还可以包括一段语义程序指定相应的语义操作(填写，查符号表，语义检查，生成语法树，代码生成)。LEX和YACC是关于编译程序前端的生成器。编译程序后端(代码生成，代码优化)。
26.编译程序编写系统(TWS)：将有助于减轻编写翻译程序(编译程序汇编程序解释程序)工作
的任何软件系统或工具包统称为翻译程序编写系统。包括产生式语言的编译程序和自动分析算法的改构造程序，以及翻译程序所必须执行的各种基本操作(建立，查符号表操作，生成目标代码，处错处理操作等)。
27.TWS分为三类：
第一类为自动产生编译程序的“编译程序的编译程序”，只要给出一个高级语言的语法规则和语义描述这类程序就能自动产生相应语言的编译程序。第二类为面向语法的符号加工程序。比较通用，例如表达式符号化简，数据格式转换，高级语言之间的相互转换等。当输入对象可用巴科斯范式BNF表示法加以描述时该TWS适用。第三类为由可扩充语言组成的集合。允许程序员用已有的数据类型和语句自定义新的数据类型和语句。
28.规格说明：以某种方式告知计算机所需要的是什么样的程序，要求这一程序干什么。
29.目标语言：是自动程序设计系统用以表示最后生成的程序的语言。
30.问题范围：是指希望生成的程序的应用范围，问题范围与规格说明有关，对系统采用的方法有很大影响。
31.采用方法：程序转换，知识工程等。
32.串行编译程序：适合于SISD结构计算机的编译程序。
33.并行编译程序：适合于SIMD和MIMD结构计算机，具有并行处理功能的编译程序。
34.并行编译程序的功能：把串行的源程序和尚未充分并行化的并行源程序自动转换成并行
计算机上运行的并行目标程序或它所能接受的并行源程序。
35.并行编译程序的任务：实现对并行语言的翻译，受到并行语言的约束和并行计算机体系
结构以及和操作系统提供的基本手段的限制。
36.并行语言分为扩充式语言和全新设计语言。
37.扩充式语言流行原因：
向上兼容串行语言。用扩充式语言编译程序可以使串行源程序不必修改或者极少的修改就可以转换成并行程序。当前全新式并行语言不能够全面的支持并行语言。兼容性不高，
不容易掌握。
38.实现扩充语言编译程序的方式有：
直接法：直接接受扩充式语言，并按语言的语义规则处理。
间接法：接受串行源程序(或带并行指示标志的串行源程序)，并行编译程序对源程序进行并行性检查，将检测到的并行成分转换成并行语句。或者立即进行并行编译处理。39.并行粒度是对并行执行任务或者事务大小的度量。分为作业级，用户级，程序级，指令级(语句级)。作业级粒度最大，指令级粒度最小。并行编译程序应该选择适当的并行粒度。40.加速比Sp可认为是应用程序在单处理机上串行执行时间Ts和p个处理器并行执行的时
间Tp之比，即Sp=Ts/Tp。分析比较并行编译程序所生成的目标程序的执行速度是可用此指标。
41.并行硬件上实现神经模型和连接机制模型途径：
用大量的专门的神经元器件连接成特定的模型。用通用并行计算机支持各种连接模型。第二章
1. 字母表：字母表是元素的非空有穷集合。字母表中的元素称为符号。
2. 符号串：符号的有穷序列成为符号串。什么符号也不包含的符号称为空符号串。符号串
中符号的个数称为符号的长度。
3. 符号串相等若xy是集合上的两个符号串。且符号串的每个元素和元素的位置均相等时编程语言翻译
符号串相等。
4. 符号串的正闭包：A+ 为集合A上所有符号串的集合。
5. 符号串的自反闭包：A* 自反闭包不包含A本身A+=AA*=A*A
6. 文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文
法”（或称为“语法”）。对于we妇女发要研究它的句型、句子和语言。
7. 语法规则：我们通过建立一组规则，来描述句子的语法结构。规定用“::=”表示“由……
组成”或“定义为……”。
8. 产生式的定义；设VN、VT分别是非空有限的非终结符号集和终结符号集，V=VN∪VT ,VN∩VT=Φ。一个产生式是一个有序偶对（α,β），其中α∈V+,β∈V*，通常表示为α→β或α::=β。称α为产生式的左部，称β为产生式的右部。产生式又称为重写规则，它意味着能将一个符号串用另一个符号串替换。
9. 文法的定义：文法G =（VN，VT，P，S）。VN：非终结符号集。VT：终结符号集。P：
产生式或规则的集合。S：开始符号（识别符号）S∈VN.
10.文法和语言分类Chomsky将文法分为四类：0型、1型、2型、3型。这几类文法的差别在于对产生式施加不同的限制。
11.0型文法：P：α::=β
其中α∈(VN∪VT)＋，β∈(VN∪VT)*
0型文法称为短语结构文法。规则的左部和右部都可
以是符号串，一个短语可以产生另一个短语。
0型语言：L0 这种语言可以用图灵机(Turing)接受。
12.1型文法：
P：γ1Aγ2::= γ1δγ2
其中γ1,γ2∈(VN∪VT)*, A∈VN,
δ∈(VN∪VT)+
称为上下文有关文法或上下文敏感文法。也即只有在
γ1,γ2这样的上下文中才能把A改写为δ
1型语言：L1 这种语言可以由一种线性界限自动机接受.
13.2型文法：
P：A::= δ
其中A∈VN，
δ∈(VN∪VT)+
称为上下文无关文法。也即把A改写为δ时，不必考虑上下文。
注意：2型文法与BNF表示相等价。
2型语言：L2 这种语言可以由下推自动机接受.
14.3型文法：
（右线性）P：A::=a 或A::=aB
其中A、B∈VN。a∈VT。
3型文法称为正则文法。它是对2型文法进行进一步限制。
3型语言：L3 又称正则语言、正则集合这种语言可以由有穷自动机接受.
根据上述分析，L0 L1 L2 L3
0型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1。
从0型文法到3型文法，各文法描述语言的能力依次减弱。
15.直接推导
设文法G＝(VN, VT, P, S)(α, β)∈P ，γ,δ∈(VN∪VT)*则称符号串γβδ为符号串γαδ应用产生式α::=β所得到的直接推导，记为γαδ=>γβδ
特别有，当γ＝δ＝ε时，有α=>β即每个产生式得右部都是它左部的直接推导。
16.最左直接推导
在xUy=》xuy直接推导中，若x属于Vt*，U属于Vn，即U是符号串最左非终结符，即最左直接推导，若每一步都是最左直接推导，称为最左推导。
17.最右直接推导
在xUy=》xuy直接推导中，若y属于Vt*，U属于Vn，即U是符号串最右非终结符，即最右直接推导，若每一步都是最右直接推导（规范直接推导），称为最右推导（规范推导）。
18.句型：S是文法G的识别符号，若S*=>u，则称u为文法G的句型。S也是。
19.句子：S是文法G的识别符号，若S*=>u，u属于Vt*，则U为文法G的句子。
20.语言：S是文法G的识别符号,G语言L(G)={u|S*=>u，u属于V*t}，即文法的语言是文法所有句子构成的集合。
21.语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。
（1）：树中每个结点都有一个标记，该标记是Vn并上Vt并上空中的一个符号。
（2）：树的根节结标记是文法的标志符号S
（3）：若书的一个节点至少有一个叶子结点，则该结点的标记一点是一个非终结22二义性：若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法。（包含二义性的句子）
23.无用非终结符号：如果文法的某个非终结符不出现的任何一个句型中，并且不能从它推
导出非终结号串，则称该非终结符称为无用非终结符号。
24.不可达文法符号：如果一个非终结符不出现在we妇女发的任何一条产生式的右部，则称
该非终结符为不可达文法符号。
25. 自上而下分析方法：从文法的识别符号出发，看是否能推导出待检查的符号串，如果能
推导出这个符号串，则表明此符号串是该文法的一个句型或句子，否则便不是。或者说，以文法的识别符号作为根节点，看其是否能构造一个语法树，而且此语法树所有叶子节点从左到右所构成的符号串恰好是待检查的符号串。如果能生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则便不是。
26：带回溯的自上而下分析方法：又称为不确定的自上而下分析方法。这种方法显然花费时间多，效率低。
27：确定的自上而下分析方法：是指在分析的过程中，选择某个非终结符的产生式，是根据待检查符号串的当前符号以及各产生式右部首符号而进行的，因此是确定的。
28.自下而上分析方法：基本思想：从待检查的符号串出发，看最终是否能归约（推导的逆
过程）到文法的识别符号。如果能归约到文法的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。从待检查符号串出发，在其中寻一个称为句柄的子串，此句柄如果与文法中的某一产生式右部相匹配，那么就用此产生式左部（一个非终结符）去替换待检查符号串中的句柄，替换之后得一新符号串，然后对这新符号串作同样处理。这便是一个归约的过程。
29.文法分类：为0型、1型、2型、3型文法。程序设计语言的语法规则属于3型文法（正
规文法）。程序设计语言的语法和语义部分，一般属于1型文法（上下文有关文法），但实际上都是采用二型文法（上下文无关文法）。
30.语法分析：语法分析方法有两类，一类是自上而下分析法，另一类是自下而上分析法。
为了语法分析，需讲文法的产生式存储在计算机，可以为文法建立一个产生表，为了方便还可建立一个目录表。
第三章
1.有穷自动机(FA)分为确定有穷自动机(DFA)和非确定有穷自动机(NFA)。
2.一个确定的有穷自动机DFA是一个五元组DFA=(Q，∑，t，q0，F)其中，Q是非空有穷
状态集，∑是有穷输入字母表，t是一个映射Q*∑→Q，q0∈Q是开始状态，F包含于Q 是非空终止状态集。
3.一个状态转换图实际上是一个有穷自动机。
4.一个不有穷自动机NFA是一个五元组DFA=(Q，∑，t，Q0，F)其中，Q是非空有穷状
态集，∑是有穷输入字母表，映射t为Q*∑→Q的子集所成的集合(即t是一个多值映射)，Q0∈Q是开始状态，F包含于Q是终止状态集。
5.非确定有穷自动机与确定有穷自动机的主要区别有二：一是NFA有一个开始状态集，
而DFA只有一个开始状态；二是NFA的映射是Q*∑→Q的子集所成的集合，是一个多值映射，而DFA的映射Q*∑→Q，是一个单值映射。
6.如果自动机的弧上允许标记ε，则称此自动机为ε自动机，记为εNDFA或εDFA。
7.ε自动机的状态转换图中会出现由若干条ε弧组成的空移环路或空移。
8.NDFA确定化方法
子集法
设NDFA A=(∑,Q ,t ,Q0,F)是一个非确定的有穷自动机，那么可以通过子集法构造一个和它等价的确定有穷自动机DFA A‘=(∑,Q‘, t‘, q0, F‘)。构造方法如下：
⑴输入字母表∑不变
⑵把NDFA A的每一个状态子集都作为DFA A‘的一个状态
⑶DFA A‘的映射定义t‘({r1,r2,…,rm} , a) = q‘ = t (r1,a)∪t (r2,a)∪…∪t (rm,a)
⑷DFA A‘的开始状态q0＝{s1 , s2 , … , sk}，其中，si∈Q0( i =1,2,…,k)
⑸DFA A‘的终态集为包含原终止状态的子集组成
造表法
造表法中DFA A‘的输入字母表∑、开始状态q0和终态集F‘的确定都与子集法的构造方法一致。
状态集Q‘与映射函数t‘则是随着造表的过程而动态生成。
首先求出开始状态q0在接受各输入字母后状态变迁的结果，将其填入表中。然后把得到

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。