编译原理题目总结

2023-06-20 07:43| 来源: 网络整理| 查看: 265

目录 NFA转换DFA化简DFA识别单词的DFA词法分析阶段的错误处理 **回溯的消除****提取左因子****消除左递归**消除间接左递归第三章用状态转换图识别字符串relop的状态转换图的概要实现作业3前缀、后缀、真前缀、子串和子序列语言上的运算正则表达式与语言P53 第五章

NFA转换DFA

在这里插入图片描述

eg：将下图NFA M确定化。在这里插入图片描述

生成DFA M的初态ε-Closure({0})={0，2，3}。重新命名生成的各个状态：{0，2，3}为0，{1}为1，{2，3}为2，{3}为3。由于{0，2，3}、{2，3}和{3}中均包含M中的终态3，因此0、2、3为M’的终态。在这里插入图片描述

化简DFA

eg：化简DFA。在这里插入图片描述根据终态和非终态划分为两个子集：Π1={A，B，F}，Π2={C，D，E，G}。对Π1，输入b，状态A、B经过b可到达终态，而F经过b不能到达终态。因此Π1划分为两个子集Π11={A，B}和Π12={F}。对Π11，输入bb，A经过bb可到达终态，而B不能，所以A和B是可区别的两个状态。故Π1划分为{A}、{B}、{F}三个子集。对Π2，输入b，划分成两个子集Π21={C，E}和Π¬22={D，G}。对Π21，输入a，划分成两个子集{C}和{E}。故Π2划分成{C}、{E}、{D，G}。最终状态集合划分成：{A}、{B}、{F}、{C}、{E}、{D，G}。在这里插入图片描述

识别单词的DFA 识别标识符的DFA

在这里插入图片描述

无符号数

在这里插入图片描述

无符号整数

注释

识别token

词法分析阶段的错误处理词法分析阶段可检测错误的类型单词拼写错误例：int i = 0x3G; float j =1.05e;非法字符例：~ @

词法错误检测如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序

错误处理查找已扫描字符串中最后一个对应于某终态的字符

如果找到了，将该字符与其前面的字符识别成一个单词。然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词如果没找到，则确定出错，采用错误恢复策略错误恢复策略最简单的错误恢复策略：“恐慌模式 (panic mode)”恢复：从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止回溯的消除提取左因子

若有A→αβ1|αβ2|…|αβ1|γ，其中γ不是以α开头的候选式，则A的产生式规则可替换为A→αA‘|γ，A’→β1|β2|…|βn。A’是一个新的非终结符号。在这里插入图片描述

消除左递归左递归缺点：容易产生死循环消除直接左递归若某个文法中非终结符A的产生式规则是直接左递归规则：A→Aα|β，其中α,β∈(VN∪VT)。若β不以A打头，则将A的产生式规则改写为：A→βA’，A’→αA’|ε。A’是新增加的非中介符号。在这里插入图片描述

eg：设有文法G[Z]： E→E+T|E-T|T T→TF|T/F|F F→(E)|i 消除非终结符E,T的直接左递归后，文法G[Z’]改写为： E→TE’ E’→+TE’|-TE’|ε T→FT’ T’→*FT’|/FT’|ε F→(E)|i 消除间接左递归

1）对文法G的非终结符号按任一种顺序排列成A1，A2，…，An。 2）依次对各非终结符号对应的产生式进行左递归的消除： for(j=1;j

【本文地址】

编译原理题目总结

编译原理题目总结

今日新闻

推荐新闻