编译原理4[1].4-递归下降分析程序构造.ppt

1、第四章,4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL(1)分析法 4.4 递归下降分析程序构造 4.5 预测分析程序 4.6 LL(1)分析中的错误处理,4.4 递归下降分析程序构造,前提: 文法满足LL(1)文法 实现思想: 每个非终结符对应一个递归过程,约定的数据结构和函数,IP: 输入串指示器 SYM: IP当前所指的输入符号 ADVANCE: 使IP指向下一输入符号 getsym , NextCh ERROR: 出错诊察处理程序,p74,文法 (4.2) E TE E +TE| T FT T *FT| F (E) | i,E TE,PROCEDURE E; B

2、EGIN T;E END,T FT,PROCEDURE T; BEGIN F;T END,E +TE|,PROCEDURE E; IF SYM=+ THEN BEGIN ADVANCE; T;E END,T *FT|,PROCEDURE T; IF SYM=* THEN BEGIN ADVANCE; F;T END,F (E) | i,PROCEDURE F; IF SYM= i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE; ELSE ERROR END ELSE ERROR,基本架构(1)Uu

3、1 | u2 | un,U( ) if (sym SELECT(Uu1) ) 处理u1 else if (sym SELECT(Uu2) ) 处理u2 else ERROR ,补充,基本架构(2)对于U的每个右部ui=x1x2xn,处理ui 处理x1的程序； 处理x2的程序； 处理xn的程序； 如果右部为, 则不处理,基本架构(3)对于右部中的每个符号xi,xiVT if(xi = =sym) ADVANCE; return; elseERROR xiVN xi( )/直接调用相应的过程,基本架构(4) sx*,while symselect (sx) do x,补充例: 用递归下降分析程序进

4、行句型分析,G: SbA ABaA| Bab 输入串 baba#,SELECT(SbA) = b SELECT(ABaA)= a SELECT(A)= # SELECT(Bab) = a,G: SbA ABaA| Bab 输入串 baba#,S,主程序,program parser begin getsym; S; If sym= # Success else fail end,SbA,procedure S begin if sym in SELECT(SbA) /b if sym = b getsym; A else error else error end,ABaA|,procedure A begin if sym in SELECT(ABaA) /a B if sym = a getsym; A; else error else if sym in SELECT(A) /# else error end,Bab,procedure B begin if sym in SELECT(Bab) /a if sym = a getsym