第四章语法分析4.1语法分析程序的功能4.1语法分析程序的功能4.1语法分析程序的功能4.1语法分析程序的功能4.2自上而下语法分析法4.2.1非确定的自上而下分析法的思想4.2.1非确定的自上而下分析法的思想4.2.1非确定的自上而下分析法的思想4.2.1非确定的自上而下分析法的思想4.2.1非确定的自上而下分析法的思想4.2.1非确定的自上而下分析法的思想4.2.2文法的左递归性和回溯的消除法符号串α的首符号集合。A→α是文法G的任一条规则，其中或者说，为输入串寻找一个最左推导。例设有文法G[S]：例设有文法G[A]:2文法的左递归性和回溯的消除SELECT(B→bBA)=FIRST(bBA)={b}第一种情况:文法中相同左部的规则，其右部左端第一个符号相同而引起回溯。从文法的开始符号出发，根据文法规则正向推导出给定句子的一种方法；A→bdA'|eA'不难验证改写后的文法为LL(1)文法。{$,d,a}将A的两条规则代入非终结符S的规则中2文法的左递归性和回溯的消除例4设有文法G[S]:由LL(1)文法定义可知,若文法中含有左递归或含有公共左因子，则该文法不是LL(1)文法，因此，对某些非LL(1)文法而言,可通过消除左递归和反复提取公共左因子对文法进行等价变换，可能将其改造为LL(1)文法。(b)使用方括号[α]表示α的出现可有可或者说，从树根开始，往下构造语法树，直到建立每个叶的分析方法。4.2.2文法的左递归性和回溯的消除2自上而下语法分析法SELECT(A→dA)=FIRST(dA)={d}对A的规则可改写成如下右递归形式：2文法的左递归性和回溯的消除A∈VN,α∈(VN∪VT)*，定义2文法的左递归性和回溯的消除SELECT(A→dA)∩SELECT(A→ε)=ΦFIRST(Ap)=改写后的文法是LL(1)文法。A→Aα1|Aα2|…|Aαm|β1|β2|…|βnLL(1)中的第一个L表明自上而下的分析是从左到右扫描输入串，第二个L表明分析过程中使用最左推导，1表示分析时每一步只需向前看一个符号即可决定所选用的规则，而且这种选择是准确无误的。文法左递归是指文法中的某个非终结符A存在推导这里我们用$作为输入串的结束符，例如，$输入串$。例设有文法G[A]:FIRST(aB)=F→(E)|id4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除4.2.2文法的左递归性和回溯的消除对文法的某个非终结符A,当它有多个侯选式时:这也就是说，在自上而下分析过程中，为了避免回溯，要求描述语言的文法是LL(1)文法。LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件LL(1)文法的判断条件4.2.3某些非LL(1)文法到LL(1)文法的改写方法由LL(1)文法定义可知,若文法中含有左递归或含有公共左因子，则该文法不是LL(1)文法，因此，对某些非LL(1)文法而言,可通过消除左递归和反复提取公共左因子对文法进行等价变换，可能将其改造为LL(1)文法。消除文法左递归的方法见4.2.2。提取公共左因子提取公共左因子将文法改写成:例1设有文法G[S]:不难验证改写后的文法为LL(1)文法。例2设有文法G[S]:对S提取公共左因子得应当指出的是并非一切非LL(1)文法都能改写为LL(1)文法。对S提取公共左因子后，得显然，它仍不是一个LL(1)文法，且不难看出无论将上述步骤重复多少次,都无法将它改写为LL(1)文法。谢谢观看