《程序设计语言与编译》课程PPT教学课件（高职）第十三讲 自顶向下语法分析

第二节自顶向下语法分析 语法分柝:自上而下(自顶而下) 自下而上自底而上) 自顶向下语法分析法或从开始符号出发, 找最左推导;或从根开始构造推导树

第二节 自顶向下语法分析 语法分析: 自上而下(自顶而下) 自下而上(自底而上) 自顶向下语法分析法:或从开始符号出发, 找最左推导;或从根开始,构造推导树

回溯分析法 1一个实例 S→xA A→aba 输入串为xa说明分析过程

一. 回溯分析法 1.一个实例 S→xAy A→ab│a 输入串为xay,说明分析过程

A y xA A

S x A y S x A y a b S x A y a

2存在的问题 (1)回溯公共左因子的存在 A→→QB1O阝2 (2)左递归 A→Aa或A→Aa

2.存在的问题 (1)回溯——公共左因子的存在 A→1 | 2 (2)左递归 A→Aα 或 AAα +

二.无回溯的递归下降分析法 1.提取公共左因子 A→→∞B1B2….|oBn8 改写为:A_→αB6 B→β1β2….Bn

二. 无回溯的递归下降分析法 1. 提取公共左因子 A→1 | 2 | ... |n | δ 改写为:A→αB|δ B→ 1 | 2 | ... |n

2左递归的消除 (1)直接左递归的消除 Paβ 改写为P→βP P 8 般地A→Ax12.AamB1324.Bn (≠E,β不以A开头) 改写为P→B1P|β2P P→1P|axP1||anP|e

2.左递归的消除 (1)直接左递归的消除 P→Pα│β 改写为:P→P＇ P＇ →αP＇│ε 一般地 A→A1 |A2 |…|Am|1 |2 |…|n （iε，j不以A开头） 改写为:P→1P’│ 2P’│. . .│ nP’ P’→1P’│2P’│. . .│mP’│ε

(2间接左递归的消除 P→Pa (a)将文法G的所有非终结符按任一给定的顺序排列设为 ala2. An

(2)间接左递归的消除 PPα (a)将文法G的所有非终结符按任一给定的顺序排列,设为 A1,A2,…An; +

(b)消除可能的左递归 for i =1 to n do begin for j: =1 to i-1 do 把一个形如A→>Aq的产生式改写为 A1→>81Q62(|62a 其中A>61621…16是A的所有产生式 消除A产生式的直接左递归 ene (c)化简

(b)消除可能的左递归; for i:=1 to n do begin for j:=1 to i-1 do 把一个形如Ai→Aj的产生式改写为 Ai→1|2|…|k 其中Aj→1 |2 |…|k是Aj的所有产生式; 消除Ai产生式的直接左递归 end (c)化简

以S→Ql|c Q→Rb|b R→Saa 为例按S,QR排列,或RQS排列

以 S→Qc│c Q→Rb│b R→Sa│a 为例,按S,Q,R排列,或R,Q,S排列

按S、Q、R排列,代入后 SQc c Q→Rb|b R→ Rbca bca ca a 消除R中的直接左递归 R→ bcar|caR'laR R→baR|e 文法产生的语言( bcalcala)(bca)* ccbcc

按S、Q、R排列, 代入后 S→Qc│c Q→Rb│b R→ Rbca│bca│ca│a 消除R中的直接左递归 R→ bcaR’│caR’│aR’ R’→ bcaR’│ 文法产生的语言:(bca|ca|a)(bca)*bc|bc|c