《程序设计语言与编译》课程PPT教学课件（高职）第十四讲 预测分析程序

三.预测分析程序 构成下推栈预测分析表控制程序输入串 1.预测分析表 ●形式M[A,a矩阵,A∈Va∈V{$} 内容A◇或出错标志(空白)

三. 预测分析程序 构成:下推栈,预测分析表,控制程序,输入串 1. 预测分析表 •形式:M[A,a]矩阵, AVN,a VT{$} •内容:A→α或出错标志(空白)

预测分析表 EE→TE E→TE E E”→+TE E→E E→E T T→FT T→FT T T→E T→*FT T→8 F F→→1 F→→(E)

预测分析表 E E’ T T’ F i + * ( ) $ E→TE’ E→TE’ E’→+TE’ T→FT’ T→FT’ T’→*FT’ F→i F→(E) E’→ε E’→ε T’→ε T’→ε T’→ε

2.分析方法 初始时$和开始符入栈,输入指针指 向第一个符号然后根据下推栈栈顶 符x和当前输入符a进行工作 ①x=a=$,成功 ②x-a≠$,匹配 ③x∈V查表

2. 分析方法 初始时,$和开始符入栈,输入指针指 向第一个符号,然后根据下推栈栈顶 符x和当前输入符a进行工作: ①x=a=$, 成功 ②x=a$, 匹配 ③xVN, 查表

例计i*i的分析过程 下推栈 输入串查分析表 SE i+*i$E→TE SET i+i*i$T→FT SETF i+i*i$F→i SETi i+i*iS SET +i*i$ T→E SE +i*i$E,→+TE SET+ +i*i$ SET i*i$T→FT

例:i+i*i的分析过程 下推栈 输入串 查分析表 $E i+i*i$ $E’T $E’T’F $E’T’ $E’T’i $E’ $E’T $E’T+ i+i*i$ +i*i$ i+i*i$ i+i*i$ +i*i$ +i*i$ i*i$ E→TE’ T→FT’ T→FT’ F→i T’→ε E’→+TE’

SETF *iS F SETi SET *i$T→*FT SETF* SETF F→→1 SET SET SE E→E 结束

$E’T’F $E’T’i i*i$ $E’T’ $E’T’F* $E’T’i $E’T’F $E’T’ $ $E’ *i$ i$ *i$ i$$$$ T’→*FT’ 结束F→i T’→ε i*i$ F→i E’→ε

四LL(1)文法 1. FIRST集 (1)定义对a∈(V八V)*有 FIRST (a)=(a@=a.,, ae VT) 若a→>E,则∈ FIRST(a) (2对文法符号X∈VN (3)当0=X1X2X时

四. LL(1)文法 1．FIRST集 (1)定义:对α(VTVN)*,有 FIRST（α）＝{a|αa. . . , aVT} 若αε,则εFIRST(α) (2)对文法符号XVTVN (3)当α=X1X2…Xn时 * *

X∈V则 FIRST(X){X} X∈V,分三种情形 Ⅹ→>a. Ⅹ→Y →Y1Y2..Yk

XVT , 则FIRST(X)={X}; XVN, 分三种情形: X→a… X→Y… X→Y1Y2…Yk

2. FOLLOW集 (1)定义对A∈V有 FOLLOW(Aa s3.Aa.,aEVT) 若S→.A,则$∈ FOLLOW(A)其中S为开始符号

2. FOLLOW集 (1)定义:对AVN ,有 FOLLOW(A)={a│S . . .Aa. . . ,aVT} 若S  ...A, 则$FOLLOW(A),其中S为开始符号 * *

(2)求法 $∈ FOLLOW(S) A→OBβ将 FIRST(β)-{}加入 FOLLOW(B) A→0B或者AB且B将 FOLLOW(A加入 FOLLOW(B) 注意:求 FOLLOW(B实际上是考察B在产生式右 端的每一次出现

(2)求法 $  FOLLOW(S) A→αBβ: 将FIRST()-{}加入FOLLOW(B) A→αB 或 者 A→αBβ 且 βε: 将 FOLLOW(A) 加 入 FOLLOW(B) 注意: 求FOLLOW(B)实际上是考察B在产生式右 端的每一次出现 *

例:G(EE→TE E→+TE T→FT T*FTe F→(E)i

例: G(E) E→TE’ E’→+TE’│ε T→FT’ T’→*FT’ │ε F→(E)│i