《编译原理与技术讲义》课件_编译原理与技术讲义－第5章.pptVIP

编译原理与技术*5.4LALR分析器的生成工具yacc这个yacc源程序的辅助部分包含了三个子程序说明。第一个是main的定义，把它包括进来可以使yacc的输出直接编译成可执行代码。main调用yyparse，它是yacc产生的语法分析的过程名。Yyparse又调用名字为yylex的词法扫描器，以便与Lex扫描器生成器（见第2章）保持一致。所以，yacc文件里也包含了yylex的定义。本例的yylex只需返回下一个非空的字符，除非这个字符是数字，在这种情况下，它必须识别出构成NUMBER的数字串并且返回在yylval中的数值。最后，yacc定义了一个打印错误信息的过程yyerror，以便在语法分析出现错误是调用。编译原理与技术*5.4LALR分析器的生成工具yacc对于二义性的算术表达式文法E→E+E|E*E||E/E|－E|(E)|iyacc允许用户规定运算符的优先级和结合性，就可以消除上述文法的二义性。?用yacc表示如下：％tokenNAME

???? ％left+－

???? ％left*

???? ％％exp ：exp+exp??????? |exp－exp??????? |exp*exp |exp/exp |－exp％prec* |NAME;编译原理与技术*5.4LALR分析器的生成工具yaccyacc提供了下面两条消除二义性的规则A1．出现移进－归约冲突时，进行移进；A2.出现归约－归约冲突时，按照产生式在yacc源程序中出现的次序，用先出现的产生式归约。根据终结符和产生式的优先级和结合性，yacc又有两个解决冲突的规则：P1.当出现移进－归约冲突或归约－归约冲突，而且当时输入符号和语法规则均没有优先级和结合性，就用A1和A2来解决这些冲突。P2．当出现移进－归约冲突时，如果输入符号和语法规则都有优先级和结合性，那么如果输入符号的优先级大于产生式的优先级就移进如果输入符号的优先级小于产生式的优先级就归约。如果二者优先级相等，则由结合性决定动作，左结合则归约，右结合则移进，无结合性则出错。编译原理与技术*5.3.4规范LR分析表的构造最后，看它是否是LR(1)文法。按照LR(1)方法构造的LR(1)自动机如图5.10。初始项集只包含了一个预测符$，在I3的项集中第一次出现了不同的预测符b，在那里关的第一个项中关于A的预测规则产生了[A→·aAb,b]和[A→·B,b]，它们都有一个预测符b，这是由于FIRST(b$)={b}。可以看到在状态3中的处突不存在了：移进项在输入为b时起作用，当面临$时才执行归约。uBauI0：[S’→·S,$][S→·A,$][S→·ub,$][A→·aAb,$][A→·B,$][B→·u,$]SI1：[S’→S·,$]I3：[S→u·b,$][B→u·,$]I4：[A→a·Ab,$][A→·aAb,b][A→·B,b][B→·u,b]I5：[A→B·,$]BI8：[A→B·,b]bI6：[S→ub·,$]AI7：[A→aA·b,$]bI9：[A→aAb·,$]aaI11：[A→a·Ab,b][A→·aAb,b][A→·B,b][B→·u,b]BuI10：[B→u·,b]AI12：[A→aA·b,b]bI13：[A→aAb·,b]AI2：[S→A·,$]编译原理与技术*5.3.4规范LR分析表的构造状态ACTIONGOTOuab$SAB0s3s41251acc2r13s64s10s11785r16r27s98r19r310r511s10s1112812s1313r3表5.15文法G5.8的LR(1)分析表编译原理与技术*5.3.4规范LR分析表的构造可以看到LR(1)的DFA比SLR(1)的DFA具备更强的识别能力。实际上，如果我们可以在线性时间用一个预测符号自左至右分析任何一个语言，那么，我们也能用LR(1)分析。也就是说，LR(1)时最强的自左至右的新型分析方法。这是因为LR项集对于句柄实现了最佳可能的宽度优先查找。然而，LR(1)技术的更强分析能力也不是没有代价：本例子中LR(1)的状态数比SLR(1)的要多仅30％。一般来说，LR(1)的状态及其分析表比SLR(1)的都要大到一个数量级。当一个