编译原理---第4章-语法分析和语法分析程序.pptx

第4章语法分析和语法分析程序计算机与软件学院陆克kzlu@szu.edu.cn12021/4/6

第4章语法分析和语法分析程序2编译程序的逻辑结构词法分析程序语法分析程序语义分析程序中间代码生成代码优化程序目标代码生成信息表管理程序错误检查和处理程序源程序目标代码2021/4/6

第4章语法分析和语法分析程序3编译程序的组织语法分析程序语义分析及代码生成程序词法分析程序整理目标程序源程序目标程序停机开始2021/4/6

第4章语法分析和语法分析程序4语法树（分析树、推导树）每个结点均有标记?VN∪VT根的标记为开始符号S内部结点标记?VN若以A为标记的结点有k个孩子分别标记为X1,X2,…,Xk,则A?X1X2…Xk必然是G的一个产生式。文法的二义性：一个句子对应多个语法树。对无二义文法，一个句子只对应一个语法树。2021/4/6

第4章语法分析和语法分析程序5按产生语法树的方向分类自顶向下分析递归下降法LL自底向上分析算符优先法LR2021/4/6

4.1自顶向下的语法分析6例文法G[E]:E?T|EATT?F|TMFF?(E)|iA?+|-M?*|/建立从E到i+i*i的最左推导。左递归与死循环：E?EAT，必须消除左递归。2021/4/6

4.1.1消除文法的左递归7直接左递归的消除前提：掌握算法2.1-2.6消除无用符号和无用产生式、?产生式和单产生式。直接左递归的形式：A?A?，??V+方法一：将A?A?|?改写为A??{?}方法二：引入A，改写为A??A和A??A|?一般化：将A?A?1|A?2|…|A?n|?1|?2|…|?m改写为A??1A|?2A|…|?mA和A??1A|?2A|…|?nA|?2021/4/6

4.1.1消除文法的左递归8左递归的消除从线性方程组到矩阵方程从3类文法到2类文法只关心产生式右部各符号串的首字符对n个非终结符X1…Xn，得到矩阵方程 或表示为:X=XA+B，方程的解为:X=BA* 由于A*=A0+A1+A2+…=I+AA* (r*=?|rr*) 若令A*=Z，则对X=BA*可得X=BZ和Z=I+AZX会不会产生左递归？Z会不会产生左递归？2021/4/6

4.1.1消除文法的左递归9左递归的消除从线性方程组到矩阵方程例消除文法S?Sa|Ab|a,A?Sc的左递归。 S=Sa+Ab+a A=Sc+AΦ+Φ 2021/4/6

4.1.1消除文法的左递归10课堂练习消除文法S?AS|b,A?SA|a的左递归。2021/4/6

4.1.1消除文法的左递归11课堂练习消除文法S?AS|b,A?SA|a的左递归。S=SΦ+AS+bA=SA+AΦ+aS?bz11|az21A?bz12|az22z11??|Az21z12?Az22z21?Sz11z22??|Sz122021/4/6

4.1.4预测分析法12FIRST集的定义对符号串?，FIRST(?)={a|??*a?,且a?VT,??V*}(当??*?，约定??FIRST(?))，即FIRST(?)由?推导出的每个符号串的首个终结符组成。若?以终结符a打头，则FIRST(?)=FIRST(a)={a}。若?以非终结符X打头，则FIRST(?)=FIRST(X)？(若X?*?，等式不成立)Xai?X2021/4/6

4.1.4预测分析法13构造FIRST集的方法令X?VN，a?VT，X的产生式具有下述3种形式X?a或X?a?{a}FIRST(A)Xa…X??{?}FIRST(A)?XX?Y1Y2…YkFIRST(Y1)-{?}FIRST(X)若?∈FIRST(Y1)，则FIRST(Y2…Yk}FIRST(X)Y1Y2Yk…X2021/4/6

4.1.4预测分析法14构造FIRST集的方法遍历所有左部为X的产生式setFIRST(X){ft=?;if(X?VT)return{X};if(X???P)ft+={?};foreach(X?Y1Y2…Yk?P){foreach(Yi){if(??FIRST(Yi)){ft+=(FIRST(Yi)-{?});if(i==k)ft+={?};}else{ft+=FIRST(Yi);break;}}}returnft;}2021/4/6

4.1.4预测分析法15构造FIRST集的方法例对文法G[E]: E?TE′ E′?ATE′|? T?FT′ T′?MFT′|? F?(E)|i A?+|- M?*