编译原理教材配套---哈尔滨工业大学独立博客服务PPT课件

.1，schoollocomputersciencea abb ，aba，bfirst op(b)，aba，a，25，运算符优先关系矩阵构造，A x1x2.xn xixi 1TT的话：XiXi 1如果Xixi 1Xi 2TVT的话：XiXi 2 Xixi 1TV的话：aI op(Xi 1)，Xi，26，示例5.6表达式语法中的运算符优先关系881ACC，88115；15；15；5 . 2 . 3运算符优先分析算法，原理识别句柄和返回各种优先级关系运算符优先分析表中使用的识别句柄结束，识别句柄头使用识别句柄头识别，对堆栈的标识部分进行分析，比较堆栈顶部与下一输入符号之间的关系，在句柄结束时沿着堆栈顶部向下查找句柄头，找到后，弹出句柄将分类为非终结器。2020/6/6，28，示例5.7ee t | e-t | TTt * f | t/f | ff(e)| id，使用运算符优先分析尝试解析id，2020/6/6，29，问题，有时真正的句柄(f)不是严格的最左边的reton的符号字符串也与生成的右侧部分不同，为什么正确识别句子OPG没有定义符号之间的优先关系，由单个非终止符组成的句柄定义运算符优先分析过程识别的“句柄”是最左边的语法leftmostprimephase(lpp)，30，素语法和最左边的语法，短语是什么？现在我们在找什么短语？如果具有至少一个运算符s * a anda ，至少包含一个终结器，且不包含较小终结器的语法，则具有一个相对于句型 的变量a的子句模式的终结器，且没有其他子句的球体，2020/6/6，31，是，E e | TT t * f | ff (e) | id句子t * f I的词组是TT * FiT * FT * F I。其中素语句是T*FiT*F最左边的语句，这是合同对象问题。e e | e | (e) | id，I E*i I的球体和子球体，EETTEFT * F I，2020/6/6，32，语法：e e | e * ee (e) | id语句型I E*i的词组，问题：缩小过程中如何发现“中间句子”的最左边词组？iie * iii e * ii e * I其中，素词组为iii，2020/6/6，33，素词组和最左边素词组，# n1 a1 n2a 2.nnan #(ni ，ai vt)最左边的素短语是满足以下条件的最左边的字符串niaini 1ai 1.nja jjy1。其中，Ai-1Ai，AiAi 1aj-1aj，aj aj1，2020/6/6，34，实现运算符优先分析，系统组件减少分析器优先关系表分析算法参考输入字符串，优先级关系表，完成一系列减少，生成解析树输出，2020/6/6，35，运算符优先分析算法，算法5.3运算符优先分析算法。输入：输入语法G=(V，T，P，S)、字符串w和优先级表。输出：如果w是句子，则输出分析树搁板，否则指示错误。步骤：beginS1:= # ；I :=1；Repeat将以下输入符号转换为r；ifsItthe NJ :=iel sej :=I-1；whilesj8815；rdobeginrepeat q :=sj；ifsj-1tthe NJ :=j-1 elsej 3360=j-2 untilj88144；q；S j 1.s I约为n；I :=j 1；sI:=Nend；ifsj8814；rorsj8801；rthenbegini :=I 1；sI:=renelseerroruntil=2andr= # end；2020/6/6，36，id id*id的分析进程，id id*id#，运算符优先于分析控制器，e id，e id，e e * e，37，5.2.4优先级函数，节省存储空间(n22n)，为了便于比较操作，使用两个优先级函数f和g，它们从结束符号映射为整数。为终结器a和b选择f和g，以匹配a b的f(a)g(b)。减少丢失错误检测(例如，id id不存在，f(id)g(id)可比较，2020/6/6，38，表5.2中对应的优先级函数：1)构成优先级函数的算法不是唯一的。2)有优先函数集，就有无限优先函数集。2020/6/6，39，构建优先级函数，构建算法5.4优先级函数。输入：运算符优先级矩阵；输出：表示输入矩阵的优先级函数，或表示不存在。步骤：1。为at # 创建标记为fa和ga的顶点。2.如果a、Bt # 、a b或a b，则直接从fa到GB绘制弧。如果是ab或ab，则直接从GB到fa绘制圆弧。3.如果配置的直接图包含循环，则表示没有优先级函数。如果没有循环，则对于at # ，将f(a)设置为从fa开始的最长走刀长度，将g(a)设置为从ga开始的最长走刀长度。2020/6/6，40，示例5.10Ges:EE T|TTT*F|FFid，根据Ges的优先级矩阵设置的直接图形和优先级函数，Ges的优先级矩阵，2020/6/6，41，5.2.5运算符优先分析的错误处理，堆栈顶部的结束符号和当前输入符号之间没有优先级关系。发现了“合同对象”，但“合同对象”未满足合同要求。对于方案，必须修改堆栈、输入或两者，才能恢复错误。必须为优先级矩阵中的每个空白项指定错误处理程序，同一程序可以在多个位置使用。在第一个方案中，由于找不到与缩小目标匹配的生成右侧，分析器可以继续将这些符号弹出到堆栈中，没有任何意义的行为。2020/6/6，42，运算符优先分析摘要，简单高效的优点部分2-I语法缺点语法写作限制强调运算符之间的优先关系唯一性占用内存空间不规范，无法确定的语法错误算法在发现最左侧语法结束时对应的头部，2020/6/6，43，5.3LR分析5.3.1LR分析算法，LR(k)分析分析LR(k)语法生成的语言。l:从左到右，输入符号扫描分析器自动生成的前提和基础分析器基于当前状态向前查看最多k个输入符号时，是否找到了句柄，如果找到了句柄，则将其重新分类为相应的生成标准，如果没有句柄，则转至输入符号，进入相应的状态，2020/6/6，44，LR解析器的整体结构，a1.ai.an #，lr分析程序，动作表action，传输表goto，生成序列，状态/符号堆栈，输入缓冲区，smsm-1.S10，xmxmxmxmxm-1.x1 #，2020/6/6，45，lr分析表格：action s，a；gotos，x、lr (0)、SLR(1)、LR(1)、LALR(1)根据不同的原则构造此分析表。sn:将符号a，状态n按在堆栈rn:上，返回到第n次生成，2020/6/6，46，LR分析器的工作流程，书本的下级(模式)(s0s 1.sm，x1x 2.XM，Aiai 1.an #)，其中s0s1.sm # x1.xmaiai 1.an #、2020/6/6、47，lr分析器工作流程，1 .初始化s0 # a1a2.an #表示“句型”a1a 2.an、2 .一般情况下，分析器的模式为s0s1.sm # x1.xmaiai 1.an #表示“句型”x1.xmaiai 1.an， if action sm，ai=si (shifti) then模式为s0s1.SMI # x1.xmaiai 1.an #、2020/6/6、48，S0s1.sm # x1.xmaiai 1.an #， if action sm，ai=accthen分析成功Ifactionsm，ai=errthen语法错误， if action sm，ai.sm-k # x1.XM-kaaiai 1.检查an #，goto表格，gotosm-k，A=ithen阵列为s0s1.sm-ki # x1.XM.XM-kaaiai 1.an #、2020/6/6、49，lr分析算法，算法5.5LR分析算法。输入：语法g LR分析表和输入字符串w；输出：如果是wl (g)，则输出w的自上而下分析；否则报告错误；步骤：1。将#和初始状态S0按到堆栈上，并将w#放入输入缓冲区。使输入指针IP指向w#的第一个字符。s位于堆栈顶部，a是交点指向的符号。4.repeat 5 .if action s，a=si then/* si表示转至状态I */6.begin7。继续按堆叠符号a和状态I。8.pi为以下输入符号9.end，2020/6/6，指向50，10.else if action s，a=rkthen/* ri意味着按k生成A返回*/11 . beg in 12。堆栈顶部的2*|符号；使s成为当前堆栈顶部状态。14.将A和gotoS，A依次推入堆栈。15.输出生成式a 16.end 17.else if action s，a=accthen 18 . return 19 . else 20 . error()；2020/6/6，51，例5.12，语法1)SBB2)BaB3)Bb，按照分析表，说明，快速抄写右边的表！2020/6/6，52，bab的分析流程：1) s bb2) b ab3) b b，0236 # Bab # action (6，#)=r202 # bb # b)=202 # Bab # action (2，a)=s3023 # Bab # action (3，b)=s40214 # Bab # action (4 ，53，标准句型操作前缀，分析堆栈中的其馀输入符号=规范句型分析堆栈中的内容为一句的前缀分析堆栈中的活动前缀(ActivePrefix)句柄右侧没有任何字符的规范句子前缀示例：id id*id的分析中的句型E id。*id和E E*。id、活动前缀、活动前缀、S * RM awrm 1 2w、2020/6/6、54，标准句型活动前缀，由规范减少生成的标准句型(CanonicalSententialForm)的活动前缀是出现在分析堆栈中的符号字符串，因此句柄后面的字符不出现，其后缀是输入字符串中尚未处理的结束符号字符串。活动前缀与句柄的关系包含句柄a 句柄的部分符号a 没有1.2句柄的任何符号a 。2020/6/6，55，5.3.2 lr (0)分析表的配置，lr (0)项目生成的返回方法右侧一个位置上标记为公园点的生成式对应语法的LR(0)项目(Item)示例bbbs bb.bs b.bbs“移动”(Shift)主题：s abb。BBB暂挂项目：Sb.BBSbB。b，2020/6/6，56，项目的意义，使用项目表示分析过程(句柄的识别状态)的方法：在结果右侧添加一个点，分割获得的内容和要导入的内容。配置句柄，Bab，b，b，s，s b.bb ab，2020/6/6，57，需要表示扩展语法，“返回S”(只有一种允许状态)语法G=(V，T，P，S)的扩展语法G:G=(V S ，T，Ps s，s) SV匹配SS(开始分析)和SS .(分析成功)示例5.130) s S1) s bb2) b ab3) b b，58，G中构成识别所有规范句活字前缀的DFA的问题：指示分析器的操作，根据当前状态(堆栈顶部)确定句柄分类为合同对象的头的设备，2020/6/6，59，项目集I的闭包(I)=I b| a。bI，bp 算法j :=I；repeatj=j b| a.b-j，b-p until j不再扩展，项目集闭包的计算，2020/6/6，60，闭包之间的前，后项a 。x 的后续项是AX.闭包之间的上一个go(I，X)=closure (a x. | a .xI ，2020/6/6，61，状态转移计算，状态发现语法符号后状态转移对象functionGO(I，X)；beginj :=；ForI中的a 。每个项目(例如x)do