词法分析与有限自动机.pptxVIP

词法分析与有限自动机;教学内容;3、1 词法分析器得设计思想;1、词法分析器得任务与输出形式;1、词法分析器得任务与输出形式;1、词法分析器得任务与输出形式;1、词法分析器得任务与输出形式;1、词法分析器得任务与输出形式;2、将词法分析工作分离得考虑;2、将词法分析工作分离得考虑;3、2 词法分析器得设计;大家有疑问的，可以询问和交流;1、输入缓冲区与预处理程序 ;2、扫描器得工作原理 ;2、扫描器得工作原理 ;3、状态转换图与单词得识别 ;3、状态转换图与单词得识别 ;3、状态转换图与单词得识别 ;3、状态转换图与单词得识别 ;3、状态转换图与单词得识别 ;4、状态转换图得代码实现 ;4、状态转换图得代码实现 ;4、状态转换图得代码实现 ;4、状态转换图得代码实现 ;4、状态转换图得代码实现 ;4、状态转换图得代码实现 ;4、状态转换图得代码实现 ;4、状态转换图得代码实现 ;4、状态转换图得代码实现 ;4、状态转换图得代码实现 ;实验一 词法分析器得设计 ;实验一 词法分析器得设计 ;实验一 词法分析器得设计 ;3、3 单词得描述工具;1、正规文法 ;2、正规式与正规集 ;2、正规式与正规集 ;2、正规式与正规集 ;2、正规式与正规集 ;2、正规式与正规集 ;2、正规式与正规集 ;作业3、1;3、4 有限自动机;1、确定有限自动机(DFA) ;1、确定有限自动机(DFA) ;1、确定有限自动机(DFA) ;1、确定有限自动机(DFA) ;2、非确定有限自动机(NFA) ;2、非确定有限自动机(NFA) ;2、非确定有限自动机(NFA) ;3、将 NFA 转换为 DFA ;3、将 NFA 转换为 DFA ;3、将 NFA 转换为 DFA ;3、将 NFA 转换为 DFA ;3、将 NFA 转换为 DFA ;3、将 NFA 转换为 DFA ;3、将 NFA 转换为 DFA ;3、将 NFA 转换为 DFA ;3、将 NFA 转换为 DFA ;3、将 NFA 转换为 DFA ;3、将 NFA 转换为 DFA ;4、确定有限自动机得化简 ;4、确定有限自动机得化简 ;4、确定有限自动机得化简 ;(5)DFA最小化算法(子集分割算法) 具体步骤 初始分割:把状态集S划分为终态集与非终态集,记为 其中, 属于终态集, 属于非终态集。 k次分割:假定经过k次划分后, 得到m个子集, 记为 ,并且属于不同子集中得状态都就是可区别得。检查 中得每个子 集 ,瞧其能否进一步分割。令 ,若存在一个输入字符a(a∈Σ),使得 不全包含在现行分割 得某一子集 中,就将 一分为二。;分割办法: 假设当前子集 ,若状态q1与q2经a弧分别到达状态t1与t2,而t1与t2又分属于当前已划分出得两个不同子集 与 中,则此时应将 分为两半,使得一半含有q1,另一半含有q2。;(5)DFA最小化算法(子集分割算法) 具体步骤 循环分割:重复上一步,直到子集个数不再增加为止(即每个子集已就是不可再分得了)。所谓不能划分,就是指该子集或者仅有一个状态,或者虽有多个状态但这些状态均不可区别(即等价)。 选代表,删除等价状态:对于最后分划 中得每一个子集,选取该子集中得一个状态代表其它等价状态。例如,状态子集I={q1,q2,…,qk},挑选q1作为子集I得代表,则凡导入到q2,…,qk得弧都改成导入到q1中,然后将q2,…,qk及其所射出得弧从原来得DFA中删除。 决定初态与终态:设删除等价状态之后得DFA为M′ ,凡那些包含M得初态得状态子集所对应得代表状态均作为M′得初态;凡那些包含M得终态得状态子集所对应得代表状态均作为M′ 得终态。则有L(M′ )=L(M)。;4、确定有限自动机得化简 ;4、确定有限自动机得化简;4、确定有限自动机得化简;4、确定有限自动机得化简;作业3、2;3、5 正规文法、正规式与有限自动机得等价特性;1、正规文法与正规式得等价性 ;1、正规文法与正规式得等价性 ;1、正规文法与正规式得等价性 ;1、正规文法与正规式得等价性 ;1、正规文法与正规式得等价性 ;2、正规文法与有限自动机得等价性 ;2、正规文法与有限自动机得等价性 ;2、正规文法与有限自动机得等价性 ;2、正规文法与有限自动机得