柚子@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： 正规式/正规集->正规文法？？貌似不要求