程序代码中的括号匹配_c语言基础代码大全

编译原理 (5) NFA 到 DFA的转化 　　练习题： 　　1 词法分析器的输出结果是( D )。A. 单词自身值B. 单词在符号表中的位置C. 单词的种别编码D. 单词的种别编码和自身值 　　2 表示正规语言L={
}的正规式是（A）A.
B.
C.
D.
　　3 词法分析器不能( D )。A. 识别出数值常量B. 过滤源程序中的注释C. 扫描源程序并识别单词符号D. 发现括号不匹配 　　4 正规表达式R1和 R2等价是指(C)A. R1 和 R2都是定义在一个字母表上的正规表达式B. R1 和 R2使用的运算符相同C. R1 和 R2代表同一正规集D. R1 和 R2 长度相同 　　5 词法分析器用于识别（B）。A. 句子B. 单词C. 句型D. 产生式 　　6 与
等价的正规式是( C )A.
B.
C.
D.
　　7 词法分析器的加工对象是( B)。A. 中间代码B. 源程序C. 单词D. 文法 　　8 如果一个正规式所代表的集合是无穷的，则它必含有的运算是( C )。A. 连接运算“·”B. 或运算“|”C. 闭包运算“*”D. 左右括号“（”和“）” 　　接着上次的进行讲解：GAN就行了：编译原理 (4) 词法分析 　　NFA到DFA的转换 　　子集构造法 　　对任意一个NFA，构造一个与之等价的DFA 　　将 NFA 中一个状态面临一个输入符号转换到的状态集合(子集)作为 DFA 中的一个状态 　　(DFA的一个状态是NFA的一个状态集合) 　　读了输入
后，NFA能到达的所有状态：
，则DFA到达状态{
} 　　ε-闭包(ε-closure) 　　如果t是一个状态，则ε-closure(t)是从状态t只经过ε转换可以到达的状态集 　　如果T是一个状态集，则ε-closure(T)是从T中的任一状态只经过ε转换可以到达的状态集 　　（遍历T 中的所有素，然后调用状态函数转化就行） 　　T中的所有状态属于ε-closure(T) 　　move(t, a): 从状态t经过a边所能到达的状态集 　　move(T, a): 从T中的状态经过非空的a转换可以到达的状态集 　　
　　ε 闭包就是经过多次的ε 可以到达的状态(可以确定的是通过ε 可以到达自己本身的状态)ε-closure(
) = {
}ε-closure(
) = {
}ε-closure(
) = {
}move({
}, a)={
}move({
}, b) ={
}

转移图 　　子集构造法 　　DFA的开始状态是ε-closure(
)，其中
是NFA的初态 　　（从开始状态出发，通过空串可以得到什么） 　　其余状态由ε-closure(move(T, a))生成，其中T是由NFA的状态构成的状态集(也就是DFA的状态) 　　（由于在经过a 边后，还有可能有ε 边，所以需要再添加一层ε-closure ） 　　DFA move(T, a) = ε-closure(move(T, a)) 　　DFA 的终态是那些包含原来的终态的状态集 　　（NFA识别合法串 ： 从开始到结尾找到一条路径就可以） 　　代码描述 　　Dstates数组保存DFA的状态，t1是NFA的初态，Dstates[1]是DFA的初态j表示当前处理的状态集，p表示总的状态集数在当前的状态集states[j]中，对于输入a，NFA可能到达的状态集ε-closure(edge(states[j], a)); 如果该状态已经存在列表中，则找到该状态序号，直接设置转换函数值，即δ(j, a)=i否则，新增一个状态集，并设置转换函数 　　中文描述算法 (本质是 DFS)： 　　举例 　　（move 和 edge 是一样的） 　　算法中的Dstates数组，表示DFA的状态(NFA的状态子集)

NFA 转移图 　　初态： A=ε-closure({0}) ： 0 1 2 4 7 　　edge(A, a)={3, 8} 　　edge(A, b)={5} 　　ε-closure({3,8}) 　　ε-closure({5}) 　　edge(B, a)={3, 8} 　　edge(B, b)={5,9} 　　ε-closure({3,8}) 　　ε-closure({5, 9}) 　　edge(C, a)={3, 8} 　　edge(C, b)={5} 　　edge(D, a)={3, 8} 　　edge(D, b)={5,10} 　　edge(E, a)={3, 8} 　　edge(E, b)={5} 　　下面是NFA 转化成的DFA

DFA 转移图 　　正规式与有限自动机的等价性 　　从正规表达式到NFA (McNaughton-Yamada-Thompson算法) 　　首先构造识别 ε 和字母表中一个符号的NFA

最小的机器就是单个的符号 ε 或者 a 　　并运算

并运算 　　交运算

交运算

* 闭包 　　识别(s)的NFA和识别s的NFA是一样的 （括号没有多大的影响） 　　用上述方法得到的NFA有以下性质 　　N(r)的状态数最多是r中符号和算符总数的两倍。N(r)只有一个开始状态和一个接受状态，接受状态没有向外的转换。N(r)的每个状态有一个用Σ的符号标记的指向其它结点的转换，或者最多两个指向其它结点的ε转换。 　　例: 将(a|b)*abb转换为NFA 　　（简单点说，就是一个搭积木的过程，从小零件到大部件进行构造）

并运算

添加一个* 闭包

添加一个交运算

继续添加交运算 　　DFA的化简(最小化) 　　(数字电路时序逻辑电路的状态图的化简)对于同一个语言，存在着许许多多识别它的DFA小的DFA(状态少)更加高效(存储、速度) 　　化简: 为 DFA 寻找一个状态数比较少的等价 DFA任何 DFA(或NFA)都存在(唯一)一个状态数最少的 DFA 与之等价 该最少状态的DFA可以从任意一个识别该语言的DFA转换而来 　　DFA的最小化(求同法) 　　基本思想: 寻找等价状态，合并之 　　等价状态必须满足两个条件:一致性条件 — 状态 s 和 t 必须同时为接受状态或非接受状态蔓延性条件 — 对于所有的输入符号，状态 s 和 t 必须转移到等价的状态中 　　两个状态不等价，则称它们两个是可区分的（找不等价的） 　　DFA的最小化例子 　　1.通过一个表来寻找等价状态 　　根据一致性条件判断，一般状态和终结状态之间是不等价的。

原始状态转移图 　　



　　

　　2.合并等价的状态 　　初态：含有原DFA初态的状态终态：含有原DFA终态的状态集

合并等价的状态 　　DFA的最小化(求异法) 　　基本思想 　　首先将状态划分为接受状态与非接受状态两组，然后逐步将这个划分精细化最后得到一个不可再细化的状态集的划分，每个状态子集作为一个状态。 　　1.首先把DFA M的状态集划分为非接受状态组和接受状态组，作为初始划分П。 　　2.执行以下过程 　　令
; 　　3. 如果
，则令
并执行4；否则用
替换П并重复执行 2. 　　4. 划分
=中的每个组内的状态均是等价的，作为一个新状态 　　划分П: {
}, {
} 　　求异法例子 　　

原始图 　　（对于某个组内的状态，输入所有可能的状态，如果没有转移到其它的组中，就是等价的，不需要将组别拆开） 　　首先:把M的状态分为2组:终结状态组{q4, q5, q6, q7}, 非终结状态组{q1, q2, q3} 　　划分П: {q4, q5, q6, q7}, {q1, q2, q3} 　　考察划分П中的组{q4, q5, q6, q7}，当输入a或b的时候，该组可到达的状态集包含于{q4, q5, q6, q7}，因此该组可不再划分 　　划分
: {q4, q5, q6, q7}, {q1, q3}, {q2} 　　再考察组 {q1, q2, q3}，由于该组在输入a时可到达的状态集合是{q2, q4}，不是П中的某个组，因此需要继续划分。由于q1, 经过a弧到状态q4, 而q1, q3均到达q2, 因为把q2单独划分出来 　　划分
{q4, q5, q6, q7}, {q1}, {q3}, {q2} 　　由于Пnew≠П，将П更新为Пnew ，重复算法第2步。考察组 {q1, q3}，由于该组在输入b时可到达的状态集合是{q3, q6}，不是П中的某个组，因此需要继续划分。由于q3, 经过b弧到状态q6, 而q1到达q3, 因为把q3单独划分出来 　　至此，整个划分包括4组状态集，每个状态集均不可再分，令状态f代表{q4, q5, q6, q7}，把原来到达{q4, q5, q6, q7}的弧全部导入到f。

　　第二个例子 　　

原始状态转移图

　　





　　正规式与有限自动机的等价性 　　有限自动机也能转换为等价的正规表达式(状态消去法) 　　（将状态减少：从识别串的意义角度理解）

减少状态，减少边 　　正规文法，正规表达式，有限自动机都是等价的. 　　(从语言的等价性来考虑)有限自动机和正规表达式的等价性 　　把正规表达式化为有限自动机 　　把有限自动机化为正规表达式正规文法和有限自动机的等价性 　　把有限自动机化为正规文法 　　把正规文法化为自动机 　　从有限自动机到正规文法 　　任意一个FA 识别的语言都能用正规文法来生成 　　每个状态代表一个非终结符号，如
　　如果状态i是一个接受状态，则设规则
　　如果状态i是一个开始状态，则
是开始符号 　　其他情况为状态转移情况:

转换规则（一条边代表一个规则） 　　例子 ：

　　Σ={a, b},
={A0, A1, A2, A3}, S = A0 　　P={ A0
aA0 | aA1 | bA0 ; 　　A1
bA2 ; 　　A2
bA3 ; 　　A3
ε } 　　词法分析器的自动构造 　　正规文法、正规式、有限自动机都是描述正规语言的工具用正规式表示用正规文法产生用有限自动机识别研究这三个工具，是为了构造程序设计语言的词法分析器，一般过程是首先用正规式表示出单词的结构，再将其转化为有限自动机，在有限自动机的基础上编写程序给每个正规式构造相应的NFA将所有的NFA组合起来当存在多个匹配的时候 ：选择最长的匹配+按出现顺序先后优先

存在多个匹配 　　举例 ： 　　

三种匹配模式

三种转移方式

aaba 举例 　　补充（C 代码实现前置知识，简单过一遍）： 　　（将工程代码模块拆开后的结果，工程上文件的结构组织自行实现） 　　栈数据结构代码 　　定义NFA的数据结构和操作 　　状态转移的基本格式：

状态说明

单字符转移

连接 ab

选择 a|b

a* 星闭包

a? 匹配前面的一次或者0次

加号 a+ 正闭包 　　先不提main 和 post2nfa 　　先来看如何将输入的正则表达式字符串转换成解析树的后续遍历序列 　　Lex:词法分析程序生成器 　　1975年，由AT&T的Mike Lesk和实习生Eric Schmidt编写1987年，Lawrence Berkeley实验室的Vern Paxson改写Lex为flex，意思是快速词法分析器生成程序(Fast Lexical Analyzer Generator)文档：The LEX & YACC Page

Lex 　　LEX规格说明——定义部分 　　变量说明 （单词类型，枚举出来）标识符常量说明 正规定义（对经常用到的正规表达式进行定义）正规定义中的名字可在翻译规则中用作正规表达式的成分C语言的说明必须用分界符“%{”和“}%”括起来。出现在括号中的任何内容都直接抄写到词法分析器mylex.c中，不作为正规定义和翻译规则的一部分。辅助过程也按同样方式处理 　　形式：P1 { 动作1 }P2 { 动作2 }…Pn { 动作n } 　　Pi是一个正规表达式，描述一种记号的模式。 　　动作i是C语言的程序语句，表示当一个串匹配模式Pi时，词法分析器应执行的动作。 　　（词法分析就是输出二组即可） 　　LEX规格说明——辅助过程部分 　　对规则的补充规则部分中某些动作需要调用的过程，如果不是C语言的库函数，则要在此给出具体的定义。这些过程也可以存入另外的程序文件中，单独编译，然后和词法分析器连接装配在一起。 　　LEX生成的词法分析器的执行：最长匹配原则 　　传递单词的属性，是把属性值赋给全局变量yylval 　　正规定义式：if -> ifthen -> thenelse -> elserelop -> < | <= | = | <> | > | >=id -> letter(letter|digit)*num -> digit+(.digit+)?(E(+|-)?digit+)? 　　相应的LEX源程序 　　举例代码： 　　从单词两种定义方式中构造词法分析程序的过程是: 　　

词法分析程序的过程 　　课堂习题 ： 　　有限状态自动机能识别(C)。A. 上下文无关语言B. 上下文有关语言C. 正规语言D. 0型语言 　　2. 如图所示自动机M，请问下列哪个字符串不是M所能识别的( D )。

A. bbaaB. abbaC. ababD. aabb 　　3. NFA的初始状态也可以是接受状态 对对错 　　4. 任何一个非确定的有限自动机，都可通过有效算法把其转化为等价的确定的有限自机 对对错 　　5. 对一个状态集中的两个状态 i 和 j ，若对字母表中的某个符号，变换到已划分的不同的状态集中，则i和j这两个状态一定不等价。 对对错 　　6. 有限自动机中的两个接受状态之间一定等价。 错对错 　　7. 自动机A和自动机B的状态数不同，则两者必不等价 错对错 　　8 在一个有限状态自动机中，有且仅有一个接受状态。 错对错 　　9. 对于NFA和DFA模型说法错误的是（C ） 最后经过至少有两个0A. 1(0|1)*0B. 00(0|1)*0C. (0|1)*00D. (0|1)*10

题 9 　　10. 对于NFA和DFA模型说法错误的是（B）。 A. 都有唯一的开始状态B. DFA与NFA的状态转换完全相同C. 都可以有多个接受状态D. DFA是NFA的特殊形式 　　习题 　　部分理论知识参考词法分析这篇文章GAN就行了：编译原理 (4) 词法分析 　　1. 下列选项中哪个不是C语言程序的合法单词？ B 　　A ifB #ifdefC rateD none 　　2. 下列代码中有多少个单词符号？ Cif (x>y) z=0; 　　A 8 B 9 C 10 D 7 　　3. 下列代码中单词符号的个数是？ D printf(“&i=%x i =%d”, &i, i);A 7B 8C 9D 10 　　4.下列{a}上的正规表达式中，正规集表示为偶数个a的是（B）A aa*B (aa)*C aa*aD a(aa)* 　　5. (多选题)考虑由正规表达式
描述的二进制串，下列哪些串是该正规表达式描述的合法串？ 　　ABDA 10011 B 0C 01D E 　　6. 设计一个正规表达式，描述以1结尾的二进制串，且其长度为3的倍数 　　3n=3n-1 +1 =3n-3 +2+1 　　
　　7. 将下图所示的NFA确定化，并最小化。

题7 状态ab{q0} ->1{q0，q1} ->2{q1}->3{q0，q1} ->2{q0，q1}->2{q1}->3{q1} ->3{q0}->1 　　发现就只有三个状态 ： 　　于是可以将其确定化

确定的NFA 　　NFA的确定化：这里指的 NFA 到 DFA的转换，构造一个和 NFA 等价的 DFA 　　观察可以发现，{q0} 和 {q0,q1} 在 输入是a 和 b 的情况下转移到的状态是一样的，所以两个状态是等价的，于是可以化简 ：

化简后的NFA 　　8. 构造与下列正规表达式相应的DFA，并进行最小化化简。b(a|b)*bab

正规表达式对应的NFA状态ab{0} p1{1} p2{1} p2{1} p2{1,2} p3{1,2} p3{1,3} p4{1,2} p3{1,3} p4{1} p2{1,2,4} p5{1,2,4} p5{1,3} p4{1,2} p3 　　于是等价的DFA为 ：

等价的DFA 　　可以发现这个状态转移表无法化简～

状态隐含表 　　9. 有一个语言的合法句子形式如下： {
{0,1}
，且x 以1开头、以 101结尾}，请写出能描述该语言的正规表达式，构造相应的NFA，并将其转换为DFA，如能化简，则进行最小化处理。 　　
， x 可以为101

含有ε-closure的NFA 　　需要先转化为DFA状态10{q0} S{q1,q2,q3} A{q1,q2,q3} A{q1,q2,q3} A{q1,q2,q4} B{q1,q2,q4} B{q1,q2,q3,q5} C{q1,q2} D{q1,q2} D{q1,q2,q3} A{q1,q2} D{q1,q2,q3,q5} C{q1,q2,q3} A{q1,q2,q4} B

等价的DFA 　　发现状态转移图无法化简，所以上面的DFA就是最简的

状态隐含表 　　特别提醒一下： 　　终止状态和其他所有状态都不等价（除非那个状态也是终止状态），所以隐含表可以直接打叉。 　　起始状态也是。