编译原理四元式第四章语法分析—自上而下分析上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTVN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VTVN)*开始符S至少必须在某个产生式的左部出现一次。例，定义只含+，*的算术表达式的文法G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列产生式组成：EiEE+EEE*EE(E)定义：称A直接推出，即A仅当A是一个产生式，且，(VTVN)*。如果12n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。例：对文法(1)E(E)(E+E)(i+E)(i+i)通常，用表示：从1出发，经过一步或若干步，可以推出n。4.1语法分析器的功能源程序语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约G(E)：Ei|E+E|E-E|E*E|E/E|(E)i*i+iE*i+iE*E+iE+iE+EE语法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。4.2自上而下分析面临的问题例3.4.1假定有文法G(S):(1)S→xAy(2)A→**|*分析输入串x*y(记为)。当某个非终结符有多个产生式候选时，可能带来如下问题:1.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P4.3LL(1)分析法4.3.1左递归的消除一般而言，假定P关于的全部产生式是P→P1|P2|…|Pm|1|2|…|n其中，每个都不等于，每个都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P→1P|2P|…|nPP→1P|2P|…|mP|例文法G(E):E→E＋T|TT→T*F|FF→(E)|i经消去直接左递归后变成：E→TEE→+TE|T→FTT→*FT|F→(E)|i例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a(4.3)虽没有直接左递归，但S、Q、R都是左递归的SQcRbcSabc消除左递归的算法:1.把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行；2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如Pi→Pj的规则改写成Pi→1|2|…|k;(其中Pj→1|2|…|k是关于Pj的所有规则)消除关于Pi规则的直接左递归性END3.化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。例考虑文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q的有关候选后，把Q的规则变为Q→Sab|ab|b例考虑文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非终结符的排序为R、Q、S。Q的规则变为Q→Sab|ab|b现在的Q不含直接左递归，把它代入到S的有关候选后，S变成S→Sabc|abc|bc|c例考虑文法G(S)S→Qc|cQ→Rb|bR→Sa|aS变成S→Sabc|abc|bc|c消除S的直接左递归后：S→abcS|bcS|cSS→abcS|Q→Sab|ab|bR→Sa|a例考虑文法G(S)S→Qc|cQ→Rb|bR→Sa|a消除S的直接左递归后：S→abcS|bcS|cSS→abcS|Q→Sab|ab|bR→Sa|a关于Q和R的规则已是多余的，化简为：