柚子@2010

词法分析的任务是：从左至右逐个字符的对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。
单词符号有：关键字、标识符、常数、运算符和界符这几种类型。
输出的单词符号常常用二元式表示：（单词种别，单词符号的属性值）
单词种别通常用整数编码；对于一个种别内有多个单词的符号，那么还需要给出单词的符号属性信息。
—————————————————————————————————————
输入和预处理
通常将输入的字符存入缓冲器中，常常还需要将它们进行预处理，去除多余的白字符。
用双缓冲技术可以避免缓冲器的边界打断单词的识别。
单词符号的识别，超前搜索
有的时候需要用超前搜索的技术才能识别某一符号的具体类别。
状态转换图
状态转换图是一张有向图，结点代表状态，状态之间用箭弧链接，上标记可能出现的输入字符。
—————————————————————————————————————
设计词法分析器的步骤
1. 设计表格（单词符号/种别编码<单词种别>/助记符/内码值<单词符号的属性值>）
2. 画状态转换图
3. 编码
正规式和正规集
假定有字母表Σ
(1)ε和Φ都是Σ上的正规式，它们对应的正规集是{ε}和{Φ}。
(2) 任何a属于Σ都是Σ上的正规式，对应的正规集是{a}。
(3) 如果u和v都是Σ上的正规式，它们所表示的正规集为L(u)和L(v)。那么(u|v)、(u.v)、(u)*也都是正规式，他们所表示的正规集为L(u) U L(v)、L(u)L(v)（连接积）、(L(u))*（闭包）。
也就是说，正规式形如ab*，ab(a|b)，a*b*等等，他们所能代表的字符串的集合就是对应的正规集。
正规式的运算顺序为先有*后.再而|。
—————————————————————————————————————
DFA（确定优先自动机）和NFA（非确定优先自动机）
两者都是一个五元式(S,Σ,δ,S0,F)
S：有限状态集
Σ：有穷字母表，每一个元素称为一个输入字符
δ：一个映射关系，对于DFA这是一个从S*Σ到S的单值部分映射，对于NFA这是一个从S*Σ*到2S（S的子集的幂集）的映射。
S0是初态，是S的一个元素
F是终态集合，是S的一个子集
—————————————————————————————————————
表示方法：状态转换表和状态转换图
DFA的确定性表现在单值映射S*Σ->S
若S中有M个元素，Σ中有N个元素，则状态转换图中最多有M个状态结点，且其中有一个初态结点，有0个或者多个终态结点（用双圈表示）。对于DFA，每一个结点最多连接N条弧，且每条弧的标记各不相同，对于NFA则可以相同。
对于Σ*上的任何字α，若存在一条从初态到某一终态的通路，且这条通路上所有弧的标记符连接成的字符等于α，则称α被DFA/NFA M识别。DFA/NFA M所能识别字的全体记为L(M)。
Σ上的一个子集是正规的，当且仅当它等于Σ上的某一个DFA M所能识别字的全体L(M)。
—————————————————————————————————————
对于任何一个NFA M，一定存在一个DFA M’，使得L(M)=L(M’)
NFA到DFA的转换步骤如下：
1. 改造状态转换图
a. 增加X初态结点和Y终态结点，用ε和原结点相连。
b. 替换输入字符为ab/，a|b和a*形式的弧，分别代之以两条弧相连，两条弧可选和一个自环回路。
2. 子集法转换到DFA
先定义两个概念
I是状态集S的子集，定义ε_CLOSURE(I)是这样的集合，它包括所有I中的状态结点和I中的状态结点经过任意多个ε弧可以到达的状态结点；定义Ia是这样的集合，它等于ε_CLOSURE(I经过一个a弧到达的状态结点集合)。
a. 根据状态转换图填写下表

其中第一个格子计算X的ε_CLOSURE，右边的格子都以左边第一列的元素为I进行计算。计算完一行后，看看当前得到的格子中的内容有哪些还未在第一列出现，将这些尚未出现的内容填入第一列，继续计算，直至全部得到的内容都在第一列出现。
b. 对表格内容进行重新编号，根据表格第一列进行0,1,2,…编号。

含原初态的结点为新初态，含原终态的结点为新终态
3. DFA化简
寻找一个状态数比M少的DFA M’，使得L(M)=L(M’)
状态s和状态t等价：从s出发的能识别出的某个字w而停止于终态，则t出发也能识别出同样的字而停止于终态，反之亦然。若不满足，则称为s状态和t状态是可区别的。
DFA化简的目标是将M的状态集划分成一些不相交的子集，并且任意两个子集的任意两个状态都是可区别的，同一个子集的任意两个状态都等价。最后在每个子集中取一个代表元素即可。
a. 把状态集S划分为I1和I2，I1为非终态集，I2为终态集，显然这两个集合的元素与元素之间是相互区别的。
b. 取当前得到的子集I，让每个元素都经过弧a，根据得到状态属于不同组的子集，进行子集的划分。不断重复此步，直至所有子集都不能再分。
c. 每个子集任取一个代表字母，代替该子集内的其他字母。
含原初态的集合的代表元素为新初态，含原终态的集合的代表元素为新终态
—————————————————————————————————————
计算题型4：用文字描述正规式表示的正规集
注意：不要看表面，要概括出深层次的含义；可以尝试几个例子证实自己的判断
((ε|0)1*)*：任意的01串
(0|1)*0(0|1)(0|1)：任意长度大于等于3的01串，且倒数第三位是0
0*10*10*10*：01串，但只包含3个1
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*：01串，且0和1的个数均为偶数。靠举例子，如0，1，00，01，10，11等等。归纳判断
—————————————————————————————————————
计算题型5： 写出文字描述的正规集所对应的正规式
字母表{a,b,c}上的串，且第一个a先于第一个b：c*a(a|b|c)*或(a|c)*a(a|b|c)*均可。
—————————————————————————————————————
计算题型6：DFA到NFA的转化并化简
a. NFA转化成DFA并化简；注意新加节点X和Y，改造NFA；小心计算；注意新初态、终态的选择。
b. 根据正规式构造最小化DFA
注意：遇到*，采用环即可搞定（两个半环上写*），如果*对应的只是几个字符相或，则直接用一个结点，自环即可（环上标字符）。
如构造1(0|1)*101的最小化DFA
如构造1(1010*|1(010)*1)*0的最小化DFA
c. 根据描述构造最小化DFA
同上。
如构造一个最小化DFA，输入字母表为{0,1}，接受0开始1结尾的串。
—————————————————————————————————————
计算题型7： 正规式/正规集->正规文法？？貌似不要求

编译程序相关的几个概念
翻译程序：把一种语言程序（源语言程序）转换成另一种语言程序（目标语言程序），并且两者在逻辑上等价。
汇编程序：源程序是汇编语言，目标程序是机器语言的翻译程序。
编译程序：源程序是高级语言，目标程序是某种汇编语言或机器语言的翻译程序。
解释程序：将某种高级语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。
编译和解释的根本区别是：是否生成目标代码。
—————————————————————————————————————
诊断编译程序：专门用于帮助程序开发和调试的编译程序
优化编译程序：着重于提高目标代码效率的编译程序
宿主机：运行编译程序的计算机
目标机：运行编译程序产生的目标代码的计算机
可变目标编译程序：不需要重新编译程序中与机器无关的部分就能改变目标机，则这种编译程序称为可变目标编译程序。
—————————————————————————————————————
编译各个阶段任务
词法分析：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（或成为单词符号或符号）。在词法分析中，所依据的是语言的词法规则，描述词法规则的有效工具是正规式和有限自动机。
语法分析：在词法分析基础上，根据语言的语法规则，把词法符号分解成各类语法单位。语法分析所依据的是语言的语法规则，语法规则通常用上下文无关文法描述。
词法分析是一种线性分析，而语法分析是一种层次结构分析。
语义分析与中间代码产生：对于语法分析识别出的各类语法范畴分析其含义，并进行初步翻译生成中间代码。包含两部分工作，首先对各种语法范畴进行静态语义检查；另一方面，进行中间代码的翻译。这一阶段依据的是语言的语义规则，通常用属性文法描述语义规则。
中间代码通常用四元式形式表示。四元式包含算法、左操作数、右操作数和结果四个部分。
优化：对中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。主要包括公共子表达式的提取，循环优化，删除无用代码等等。
目标代码生成：把目标代码（或经过优化处理之后）变换成特定机器上的低级语言代码，目标代码可以是绝对代码或可重定位的指令代码或汇编语言代码。而现今，大部分编译程序产生的目标代码是可重定位的指令代码。
—————————————————————————————————————
编译程序的总体结构
编译程序主要包括：词法分析器、语法分析器、语义分析和中间代码产生器（可选）、优化器（可选）和目标代码生成器五个主要部分和“表格管理”、“出错处理”两个模块。

词法分析器（又称为扫描器），它接收输入的源程序，对源程序进行扫描和分解（词法分析），识别出一个个的单词符号，其输出结果为单词符号。
语法分析器（又称为分析器），对单词符号串进行语法分析（根据语义规则进行推导和规约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
语义分析和中间代码产生器，按照语义规则对语法分析器规约出（或推导出）的语法单位进行语义分析，并把它们翻译成一定形式的中间代码。
优化器对中间代码进行优化处理。
目标代码生成器将中间代码翻译成目标程序。
表格管理模块保持着一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断的和表格打交道。
出错管理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，将有关错误信息报告给用户。编译程序的各个阶段都有可能发生错误，出错处理程序要对发现的错误进行处理、记录并反映给用户。
—————————————————————————————————————
编译前端和编译后端
编译前端主要由与源语言有关但与目标机无关的那些部分组成。通常包括词法分析、语法分析、语义分析和中间代码产生和有部分代码优化工作。
编译后段包括编译程序中与目标代码有关的部分，包括与目标机有关的代码优化，以及目标代码的生成等。
—————————————————————————————————————
遍：对源程序（或其中间形式）从头到尾扫描一次，并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。每遍的工作都由从外存上获前一遍的工作结果开始（或源程序），到完成它所包含的有关阶段程序的工作，并把结果记录于外存上为止。
—————————————————————————————————————
计算题型1：地址的转换
三维数组a[2:5,-2:2,5:7]首地址为100，每个数组元素占4个存储单位，给出a[3,1,6]的地址。
Addr=100+((3-2)*(2+2+1)*(7-5+1)+(1+2)*(7-5+1)+6-5)*4=100+100=200
二维数组A[-4:5,-3:3]，A的首地址为1000，求A[i,j]和A[i+1,j+1]的地址。
Addr1=1000+((i+4)*(3+3+1)+j+3)*6=1186+42i+6j
Addr2=Addr1+48=1234+42i+6j