编译原理例题与习题解答PPT课件

.1，示例和练习解题第2章，2，复习，编程语言的定义程序语言是符号体系，主要是语法意义，语法，语义，3，语法=词汇规则语法规则，词汇规则：单词符号形成规则。单词符号是语言中具有独立意义的最基本的结构。通常包括常数、识别码、基本单字、运算子、边界文字等。说明工具：一般和有限机器人理论语法规则：语法单元的形成规则。语法单位通常是表达式、语句、子程序、过程、函数、程序等。说明工具：上下文无关语法、审阅、4、标识符和名称、标识符：以字母开头的字母数字字符串。标识符和名称之间的根本区别如下：标识符具有语法概念名称的确切含义和属性。复习，5，上下文无关语法的定义：上下文无关语法G是基于四元的G=(VT，VN，s，p)。其中VT:终结器集合(非空)VN:非终结器集合(非空)和VT如果是s，则称为句型。只有结束符号的句型是句子。语法g生成的句子的全部是一种语言，其中l (g) l (g)=| s中间部分可以出现任意数目的数字0到9，每个数字都用字符表示，而不是用终结符d表示；最低位只有1，3，5，7，9，用a表示。中间部分可以是任意位，因此需要额外的包含最高位和中间部分的非终结器m。14，15，解决方案：奇数集语法GN为：g=(0，1，9，n，a，m，b，d，n，)95:na | mamb | MDA1 | 3 | 5 | 7 |命令语法为e t | e | e-TT f | t/ff e，解决方案：i*(i I)例如，最左边的是ett * ff * fi * fi * (ee t | e t | e-TT f | t * f | t/ff (e) | I，i-i-i-I的语法树，(2) I，I II I语法树、I i*i语法树、注意：分支和符号不能随机增加或减少！18，9，证明语法：SiSeS|iS|i是二进制。2的意思：语法中存在对应于两个或两个以上不同语法树的句子，或引出两个或两个以上其他最左/右，则该语法称为2的意思。第一：查找与此语法对应的句子iiiei，第二：构造与此语法对应的两个语法树，结论：由于此语法对应于两个不同的语法树，因此语法被解释为两个含义。19，10。用无疑问法替代以下语法：S-SS|(S)|()答案：s-ts | TT-(s) |()，20，L2=AIB ncn | n 1，其馀两部分为：S1S0，中间部分为0m1m:A0a 1 |，因此G4S表示：S1S0|AA0A1|，|A，22，示例和练习疑难解答第三章，23，1。假设NFAM=，将m的状态转换图表转换为：1)在新的初始状态节点x和最终状态节点y、x、ys、x中，从S0的所有状态节点连接到箭头弧，从f的所有状态节点连接到箭头弧1、y。2)进一步替换m的状态转换贴图。其中k是新引入的状态。，非确定性有限自动机状态图的变形，24，相反，根据以下三个规则将v划分为：逐步将此图转换为每个圆弧的单个字符或最后一个NFAM ，显然L(M)=L(M)，25，有限自动机的确定-closure (I)=I s |如果可以通过任何si中的任意圆弧到达s (s)，则设置a是定义Ia= 15-closure(J)的字符。其中j是从I的一个状态经过a号到达的状态集合。假设识别过程：没有失去一般性，字母表只包含两个a和b。我们构造表：27，对一个DFAM的最小基本思想：分为不相交于m的状态集的子集，两个不同子集的状态是区分的，同一子集的两个状态是相等的。最后，为每个子集选择一个代表，并确保删除其他状态。将DFAM最小化，28，具体地说， m的状态集划分为两个子集，首先将s划分为两个子集，形成基本划分。(I (1)，I(2)，I(m)如果有m个子集，请确定的每个子集是否可以将：进一步分割为特定的I(i)=S1，S2，29例如，假设状态S1和S2通过a弧分别到达t1和T2，t1和T2现在属于两个不同的子集，那么t1在读取后到达最终状态，T2在读取后到达最终状态，或者相反，在读取a的情况下，S1在读取a后到达最终状态，S2在读取a后到达最终状态，或者S1和S2不相等。S1，t1，a，S2，T2，a，I，j，30，示例3.1，可除以以下面所述正则表达式01结尾的二进制数字字符串5的十进制整数包括奇数1或奇数0的二进制字符串，31，示例3.2，下一步根据正则表达式创建相应的状态转换图；基于状态转换图的相应状态转换矩阵；根据状态转换矩阵得到重命名的状态转换矩阵。最终DFA。32，1(0|1)*101，。状态转换贴图，a，b，a，d，b，1 (0 | 1) * 101，a，1，(0 | 1) *，101，d d，f、c，d、c，e、c，e、c，e，e、c，e，e、c，e、c，e 设置DFA，35，示例3.3，M=(x，y，a，b，f，x，y)。其中f的定义如下：A)=x，y f (x，b)=y f (y，a)= f (y，b)=x，y配置相应的晶体有限自动机根据f的定义可以知道F(x，a)，f(y，b)是多值函数，因此m是非晶有限机器人。首先绘制NFAM相应的状态图，37，使用子集方法构造状态转换矩阵，38，重命名的状态转换矩阵，39，40，1 (1010 * | 1 (010) * 0，a，b，状态转换图，41，状态转换矩阵，42，。状态转换矩阵，。DFA，43，8，提供下面的正则表达式，(4)所有由字母组成的符号必须按字母顺序排列。(a | a) * (b | b) * (c | c) *.(z | z) *，(5)不带重复数字的数字符号字符串的完整。，ri=I |，I=0，1，2，9 r0 | R1 | R2 | | | r9至P(0，1，2.9)表示为0，1，2.9的完整数组，44，(6)最多具有1个重复数字的完整数字符号字符串，(7)不包含a和b的完整符号字符串，b*(a|ab)*，45，12，图3.18 (a)，(a)，。状态转换矩阵，0，0，1，1，0，1，0，1，1，0， 0 ，。重命名的状态转换矩阵，0，1，2，1，1，2，0，a，2，b，a，a，。DFA，。最小化， 0=(0，1，2)，0，1 a=1) 1b=2，因此不能再分割，2，配置接受满足以下条件的所有字符串的DFA:每个1的0直接在右边。想法：首先写满足条件的正则表达式，用正则表达式构建NFA，然后确定并最小化NFA。48，(1)首先满足条件的正则表达式：(10|0)*(2)NFA:为：DFA :49，DFA 3360，DFA :DFA :50，示例和练习疑难解答第4章，51，编译过程中解析器的状态，52，自上而下分析，基本思路：从语法的起始符号开始，反复使用各种生成模式来查找“匹配”的派生。递归降分析：为每个语法变量(不是终结器)构建相应的子程序，每个子程序标识特定的语法单元，并通过子程序之间的信息反馈和组合功能标识输入字符串。预测分析程序的优点：直观、简单、适合手动实施。53，困难和困难：在分析过程中，如果非终结符通过候选匹配成功，则此匹配可能是暂时的。如果发生错误，必须“回溯”。语法左边递归问题。一个语法包含左递归，如果终结符p包含左递归的语法，自上而下分析就会陷入无限循环。54，左侧递归移除，直接移除在生成中看到的左侧递归：假定非终结器p的规则为p p |。其中不是以p开头。p的规则 PP p |，从左递归到右递归，55，间接从左递归到语法G(S):SQc|cQRb|bRSa|a，直接从左递归，但S，q例如：N-N，56，消除左递归的算法：1。语法g的所有非终结符按任意顺序运行，P1，p2，P2按任意顺序运行；2.fori :=1 tondobe ginforj :=1 toi-1do通过使用Pi的生成(如果可以替代)替换Pj，直接为Pi规则向左重复END3。简化2生成的语法。从起始符号中移除永远无法到达的终止元的建立规则。57，要消除回溯，回溯，必须保证回溯。在匹配语法的所有非终结符时，可以根据输入字符串中的输入符号，准确地分配一个候选人来执行任务，该候选人的工作结果必须是确定的。58，g是没有左递归的语法，对于g的所有非终结器每个候选项，将相应的终结器集first()定义为：具体来说，第一个()是：在所有非终结器a的候选第一集中，如果两者不相交，即a的两个其他候选I和j first(I)first(j)=a与输入字符串匹配，则a可以分配一个候选，以便根据第一输入符号a执行操作。这位候选人是最后一位符文尤汉a。59、如何选择除终止语法外的所有侯，第一套字符集两者相交？在公用左系数3360中，假设a的规则是a 1 | 2 | | n | 1 | 2 | | m(其中每个规则都不是以开头)，则这些规则是a a | 1 | 2 | | ma 1 | 2 | | n，60，构造没有回溯的自上而下分析的语法条件1。语法没有左递归，2 .对于语法中每个非终结符a的每个生成的候选第一组，两者不相交。也就是说，如果a 1 | 2 | | n，则first(I)first(j)=(ij)3。对于语法中的每个非终结器a，如果它包含在候选的第一组中，则first(I)follow(a)=I=1，2，如果n个语法g满足上述条件，则称为LL(1)语法。假设LL(1)语法，61，s是语法g的开始符号，为g的所有非结束符a定义，特别是# follow (a)，Follow，提示：62，以了解如何组织First和Follow集合这