第一章1.程序设计语言是人与计算机联系的工具，通过程序设计语言指挥计算机按照自己的意志进行运算和操作显示信息和输出运算结果。
2.最早的计算机程序设计语言是机器语言(指令系统)。
机器语言中的指令都是用二进制代码直接表示的。
3.机器语言和符号语言以及汇编语言都是低级程序设计语言。
4.1954年FORTRANI语言的问世标志计算机高级程序设计语言的诞生。
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.并行粒度是对并行执行任务或者事务大小的度量。
分为作业级,用户级,程序级,指令级(语句级)。
作业级粒度最大，指令级粒度最小。
并行编译程序应该选择适当的并行粒度。
分析比较并行编译程序所生成的目标程序的执行速度是可用此指标。
41.并行硬件上实现神经模型和连接机制模型途径：用大量的专门的神经元器件连接成特定的模型。
用通用并行计算机支持各种连接模型。
第二章1.字母表：字母表是元素的非空有穷集合。
字母表中的元素称为符号。
2.符号串：符号的有穷序列成为符号串。
什么符号也不包含的符号称为空符号串。
符号串中符号的个数称为符号的长度。
3.符号串相等若xy是集合上的两个符号串。
且符号串的每个元素和元素的位置均相等时符号串相等。
4.符号串的正闭包：A+为集合A上所有符号串的集合。
5.符号串的自反闭包：A*自反闭包不包含A本身A+=AA*=A*A6.文法：文法是对语言结构的定义与描述。
即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。
对于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又称正则语言、正则集合这种语言可以由有穷自动机接受.根据上述分析，L0L1L2L30型文法可以产生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确定化方法子集法设NDFAA=(∑,Q,t,Q0,F)是一个非确定的有穷自动机，那么可以通过子集法构造一个和它等价的确定有穷自动机DFAA‘=(∑,Q‘,t‘,q0,F‘)。
构造方法如下：⑴输入字母表∑不变⑵把NDFAA的每一个状态子集都作为DFAA‘的一个状态⑶DFAA‘的映射定义t‘({r1,r2,…,rm},a)=q‘=t(r1,a)∪t(r2,a)∪…∪t(rm,a)⑷DFAA‘的开始状态q0＝{s1,s2,…,sk}，其中，si∈Q0(i=1,2,…,k)⑸DFAA‘的终态集为包含原终止状态的子集组成造表法造表法中DFAA‘的输入字母表∑、开始状态q0和终态集F‘的确定都与子集法的构造方法一致。
状态集Q‘与映射函数t‘则是随着造表的过程而动态生成。
首先求出开始状态q0在接受各输入字母后状态变迁的结果，将其填入表中。
然后把得到的结果作为新的状态，再求其接受各输入字母后状态变迁的结果，填入表中，如此过程不断重复，直到最后无新结果（状态）出现为止，此时造表结束。
9.造表法:在子集法中，如果NFA的状态个数n比较大，那么，确定化后的DFA的状态个数2n-1将更大，其中不少状态时不可达状态。
10.I包含Q，状态子集I的ε-闭包，记为ε-closuer(I)，定义如下：①若q∈I，则q∈ε-closuer(I)；②若q∈ε-closuer(I)，q‘是由q出发经多条ε弧所到达的状态，则q‘∈ε-closuer(I)。
显然ε-closuer(I)包含Q。
11.I包含Q，a∈∑，映射t(I,a)={q‘|t(q,a=q‘,q∈I)=J包含QIa=ε-closuer(J)12.不可达状态:动机中，从开始状态出发没有任何一条路径能达到的状态称为不可达状态。
13.DFA的化简对于任一个DFA，存在一个唯一的状态最少的等价的DFA一个有穷自动机是化简的它没有多余状态并且它的状态中没有两个是互相等价的。
②文法G的每一个非终结符都作为自动机A的一个状态，特别是文法G的开始符号作为自动机A的开始状态。
③在自动机A中增加一个新状态Z作为自动机的终止状态。
④对于文法G的形如U→aV的产生式，在自动机A中构造形如t(U,a)=V的映射。
⑤对于文法G的形如U→a的产生式，在自动机A中构造形如t(U,a)=Z的映射。
17.有穷自动机A正则文法G①自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的标记作为正规文法的开始符号。
自动机的输入字母表中的所有符号，作为正规文法的终结符。
②对于自动机的映射t（U,a）=V，构造文法的一条产生式U→aV③对于自动机的终止状态Z，在正规文法中增加一条产生式Z→ε18.正规表达式的定义：有字母表∑,定义在∑上的正规表达式和正规集合递归定义如下:1.ε和φ都是∑上的正规表达式,它们所表示的正规集合分别为:{ε}和φ;2.任何a∈∑,a是∑上的正规表达式,它所表示的正规集合为:{a};3.假定U和V都是∑上的正则表达式,它们所表示的正则集合分别记为L(U)和L(V),那么U|V,UV和U*也都是∑上的正则表达式,它们所表示的正则集合分别为L(U)L(V)、L(U)L(V)和L(U)*4.任何∑上的正规表达式和正规集合均由1、2和3产生。
词法分析器负责对源程序进行扫描，从中识别出一个个的单词符号，因此，词法分析器又称为扫描器。
单词符号是程序设计语言的基本语法单位和最小语义单位。
单词的种类1.关键字：if、then、else、while、do等2.标识符：表示变量名、过程名等3.常数：无符号数、布尔常数、字符串常数等4.运算符：+、－、*、/等5.分界符：逗号、分号、括号等词法分析程序的输出形式-----单词的内部形式8、单词类别单词自身值几种常用的单词内部形式：1、按单词种类分类2、关键字、运算符和分界符采用一符一类3、标识符和常数的单词值又为指示字（指针值）预处理包括删除无用的空格、跳格、回车和换行等编辑性字符以及注解部分。
文法：1.<标识符>::=字母|<标识符>字母|<标识符>数字2.<无符号整数>::=数字|<无符号整数>数字3.<单字符分界符>::=:|+|*|,|(|)4.<双单字符分界符>::=<冒号>=5.<冒号>::=:9、标识符的处理标识符的类型在机内可用向量形式表示。
标识符赋予语义后，可以用来标识变量、数组、函数、过程等。
符号表用来存放在程序中出现的各种标识符及其语义特征。
定义性标识符、使用性标识符第五章1.语法分析阶段的主要任务是对词法分析的输出结果─单词序列进行分析，识别合法的语法单位。
语法分析分为自上而下和自下而上两类方法2.自上而下分析法的基本思想是从文法的识别符号出发，试图推导出输入符号串；或试图为输入串从上而下构造一颗语法树。
3.自上而下语法分析面临的问题：左递归：造成死循环回溯现象：降低分析效率4.文法的左递归性是指文法具有以下形式的直接左递归：U→Ux|y或间接左递归：U+=>Ux5.用扩展的BNF表示法消除左递归对巴科斯范式进行扩展，增加以下元符号：①花括号{}{x}：表示符号串x出现零次或多次。
{x}：n表示符号串x能重复出现的最大次数，m表示符号串x能重复出现的最小次数。
②方括号[]：用来表示可选项。
[x]=x或ε，表示符号串x可出现一次或不出现。
③圆括号()：利用圆括号可提出一个非终结符的多个产生式右部的公共因子。
6.直接改写法设产生式U∷＝Ux|y直接左递归形式可将其改写为一个等价的非直接左递归形式U∷＝yU’U’∷＝xU’|ε7.LL(K)文法是一种自上而下的语法分析方法。
它是从文法的识别符号出发，生成句子的最左推导。
它从左到右扫描源程序，每次向前查看k(k>1)个字符，便能确定当前应该选择的产生式。
如果每次只向前查看一个字符，则称为LL(1)文法。
8.集合FIRST、FOLLOW与SELECT的构造⑴设X∈(VN∪VT)，FIRST(X)的构造①若X∈VT，则FIRST(X)={X};②若X∈VN，其产生式为X→a…，a∈VT,则a∈FIRST(X)；若它有产生式为X→ε，则ε∈FIRST(X)；③如果它有产生式X→Y…，Y∈VN则FIRST(Y)-{ε}∈FIRST(X)；如果它有产生式X→Y1Y2…YK(其中，Y1,Y2,…Yi-1都是非终结符，且Y1,Y2,…,Yi-1*=>ε)，则FIRST(Yi)-{ε}∈FIRST(X)；。