当前位置：首页 > java >正文

【编译原理】递归下降分析程序的构造

java 2025/8/25 17:36:22

当一个文法满足LL(1)条件（L自左向右扫描输入串，L分析过程采用最左推导，1只需向右看一个符号）时，我们就可以为它构造一个不带回溯的自上而下分析程序（递归过程，每个过程对应文法的一个非终结符）

advance是指把输入串指示器IP调至下一个输入符号

sym是指IP当前所指的那个输入符号

error为出错诊察处理程序

$E\rightarrow TE' \\ E'\rightarrow +TE'|\varepsilon \\ T\rightarrow FT' \\ T'\rightarrow *FT'|\varepsilon \\ F\rightarrow (E)|i$

$E\rightarrow TE'$
procedure E;
beginT;E'
end
$E'\rightarrow +TE'|\varepsilon$
procedure E'
if sym='+' then
beginadvance;T;E'
end
$T\rightarrow FT'$
procedure T
beginF;T'
end
$T'\rightarrow *FT'|\varepsilon$
procedure T'
if sym='*' then
beginadvance;F;T'
end
$F\rightarrow (E)|i$
procedure F
if sym='i' then advance
else if sym='(' thenbeginadvance;E;if sym=')' then advanceelse errorendelse error;

$S\rightarrow a|\wedge |(T) \\ T\rightarrow ST' \\ T'\rightarrow ,ST'|\varepsilon$

不带回溯的递归子程序

procedure S;

begin

if sym='a' or sym='^'

then advance

else if sym='('

then begin

advance;

if sym=')' then advance;

else error;

else error

end

procedure T;

begin

T';

end

procedure T';

begin

if sym=','

then begin

advance;

T';

end

？

递归下降分析程序

（更精确，判断该输入符号是否属于FOLLOW）

procedure E;beginif sym='(' or sym='a' or sym='b' or sym='^' //FIST(E)then begin T; E' endelse errorend
procedure E';
beginif sym='+'                                 //FIRST(E') 有εthen begin advance; 		E;
endelse if sym<>')' and sym<>'#' then error  //FOLLOW(E')
endprocedure T;
beginif sym='(' or sym='a' or sym='b' or sym='^'   //FIRST(T)then begin F; T' endelse error
end	procedure T';
beginif sym='(' or sym='a' or sym='b' or sym='^'  //FIRST(T) 有εthen T else if sym='*' then error                //??
endprocedure F;
beginif sym='(' or sym='a' or sym='b' or sym='^'  //FIRST(F)then begin P; F' endelse error
end	procedure F';
beginif sym='*' then begin advance; F' end
endprocedure P;
beginif sym='a' or sym='b' or sym='^'     //FIST(P)then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advanceelse errorendelse error
end;