有穷⾃动机的最⼩化c语⾔代码，程序语⾔基础
1编译原理
1.1Lex Yacc
lex：提取语⾔中各种保留字、操作符等语⾔的元素。
yacc：语法分析器
lex和yacc能帮助我们做事情是：⽤c语⾔来实现另外⼀种语⾔。
1.2编译器⼯作原理
对于编译器的各个阶段，在逻辑上可以把它们划分为前端和后端两部分.前端包括从词法分析到中间代码⽣成各阶段的⼯作，后端包括中间代码优化和⽬标代码的⽣成、优化等。
这样以中间代码为分⽔岭，把编译器分成了与机器有关的部分和与机器⽆关的部分。
2形式语⾔与⾃动机
2.1乔姆斯基体系
四⼤⽂法之间的关系：
1，⽂法的构造。
例3-1，L(G)：{ a^n b^n|n,m>0}
S->aSb|ab    (n,m>=0时，S->aSb|ε  )
例3-2，L(G):  {a^n b^n a^m b^m|n,m>=0} S->AB  A->aAb|ε    B->aBb|ε
2，(1)确定的有穷状态⾃动机DFA。
特点：1)，初态唯⼀，终态可有多个。
2)，任意状态任意射出弧上的元素均不相等
3)，识别对象为空时，初态为终态。
构造：例4-1，L={x000y|x,y ∈{0,1}* }
最⼩化：
扫描所有的状态对，出所有的可区分的状态对，不可取分的状态对⼀定是等价的。
(2)不确定的有穷状态⾃动机NFA。
特点：1)，初态不唯⼀。
2)，同⼀状态射出弧上的标记可以相同
3)，初态可以为终态。
(3)ε-NFA
是在NFA的基础上，允许直接根据当前状态变换到新的状态⽽不考虑输⼊带上的符号
(4)等价性
1)， NFA与DFA等价、ε-NFA与NFA等价(NFA与DFA等价，ε-NFA与NFA等价，统称它们为FA)
2)，FA与正则⽂法等价(FA和左线性⽂法、右线性⽂法等价)
对于⼀个输⼊字符，NFA与DFA的差异是前者可以进⼊若⼲个状态，⽽后者只能进⼊⼀个惟⼀的状态。虽然从DFA看待问题的⾓度来说，NFA在某⼀时刻同时进⼊若⼲个状态，但是，这若⼲个状态合在⼀起的“总效果”相当于它处于这些状态对应的⼀个“综合状态”
3，正则表达式RE-----FA的转换规则
(1)
(2)
(3)
4，正则语⾔RL
(1)封闭性
1)正则语⾔的并、交、补是正则语⾔。
2)正则语⾔的乘积(连接)是正则语⾔。
3)正则语⾔的差是正则语⾔。
4)正则语⾔的闭包是正则语⾔。
5)正则语⾔的商是正则语⾔。
6)正则语⾔的同态是正则语⾔。
7)正则语⾔的逆转是正则语⾔。
附：上下⽂⽆关语⾔CFL的封闭性
1)并、乘积、闭包是封闭的
2)交、补不封闭
(2)泵引理
DFA在处理⼀个⾜够长的句⼦的过程中，必定会重复地经过某⼀个状态。换句话说，在DFA的状态转移图中，必定存在⼀条含有回路的从启动状态到某个终⽌状态的路。由于是回路，所以，DFA可以根据实际需要沿着这个回路循环运⾏，相当于这个回路中弧上的标记构成的⾮空⼦串可以重复任意多次。
(3)等价模型
5，上下⽂⽆关语⾔CFL
(1)语法树
1)每个句型⾄少存在⼀颗语法树，每颗语法树⾄少存在⼀个推导。
2)每颗树的叶⼦组成句型(句型就是我们的结果)。
3)每颗简单⼦树的叶⼦组成简单短语。
基础c语言代码
4)最左简单⼦树的叶⼦组成句柄。
(2)CFG的化简
1)去⽆⽤符号。
⾸先删除不可终⽌的，再删除不可到达的
2)去空产⽣式
先求可空变量，再看空产⽣式会对哪些产⽣式有影响
3)去单⼀产⽣式
可能会产⽣新的⽆⽤符号或单⼀产⽣式
6，图灵机与计算机
(1)⽤计算机模拟图灵机，不是任何的图灵机都能被计算机来模拟
模拟步骤： 1)，在计算机上开辟较⼤的⼀维数组来模拟输⼊带
2)，将输⼊带存⼊数组
3)，转换函数⽤什么数据结构存储
4)，⽤有穷的编制计算机程序，在输⼊带上模拟图灵机运⾏
(2)图灵机⽐计算机速度慢
(3)运⾏时间
2.2⼏种不同的转换
⼀：DFA的最⼩化。
DFA最⼩化，最简单的理解就是“劈枝斩叶留主⼲”，最⼩化的DFA⽐原状态等价且状态数少。
劈枝斩叶留住⼲，在化简时候就是对等价的状态进⾏合并。
那么怎么等价状态呢？所有的终结符号都是等价的。这也是之后等价符号的基础。详情看下⾯例⼦。
化简步骤：
1，画出状态矩阵图
2，终结符(等价的)。
3，根据到的等价的终结符，在继续其他的等价符号。
解：由于q2，q3等价，q0，q1 1到达q2，(q0,q1)==(q1,q0)  所以 q0,q1等价。

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