1
第 5章 LL(1)文法及其分析程序
5.1 自上而下的语法分析
5.2 预测分析程序递归下降子程序表驱动的预测分析程序
5.3 LL(1)分析程序的生成
LL(1)文法
FIRST和 FOLLOW集 定义和计算
5.4 非 LL(1)文法的改造
2
5.1自上而下的语法分析
1语法分析概念
2自上而下的语法分析的一般过程
3自上而下的语法分析面临的问题
3
（ 上下文无关文法） 句型的分析句型分析 就是 识别 一个符号串是否为某文法的 句型的 过程，或者说是某个 推导 的构造过程。
4
语法树－推导的几何表示
句型 aabbaa的可能 推导 序列和语法树例,G[S]:
S→ aAS
A→ SbA
A→ SS
S→ a
A→ ba
S
a A S
S b A a
a b a
S?aAS?aAa?aSbAa?aSbbaa?aabbaa
S?aAS?aSbAS?aabAS?aabbaS?aabbaa
S?aAS?aSbAS?aSbAa?aabAa?aabbaa
5
语法分析在语言的编译实现中，把 句子分析 的过程称为 语法分析，即 完成这个任务的程序称为语法分析 程序或称为 识别程序 。 分析算法又称识别算法。
从左到右的分析算法,即 总是从 左 到 右 地 识别输入符号串,首先识别符号串中的 最左符号，进而 依次识别右边 的一个符号,直到分析结束 。
6
分析算法分类分析算法可分为：
自上而下分析法,
从文法的开始符号出发,寻找 与 输入符号串 匹配 的 推导,或者说，为输入串寻找一个最左推导。
自下而上分析法,
从 输入符号串 开始,逐步进行 归约,直至归约 到 文法的 开始符号 。
7
两种方法反映了语法树的两种构造过程。
自上而下方法 是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法 则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树
8
自上而下分析对任何输入串，试图用一切可能的办法，
从文法开始符号着手，自上而下地为输入串构造一棵语法树，或者说，为输入串寻找一个最左推导。本质上是一个试探过程，
反复使用不同地产生式谋求匹配输入串的过程。
9
自上而下的语法分析的一般过程例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否为该文法的 句子
S S S
c A d c A d
a b
推导过程,S? cAd cAd? cabd
10
自上而下的语法分析的一般过程
(1)S → cAd (2) A → ab (3) A → a
识别输入串 w=cad是否为该文法的 句子
1.S? cAd
2.后选择 (2)扩展 A，得到推导 S?
cAd? cabd
这时
w的第二个符号可以与叶子结点 a
得以匹配，但第三个符号 d却不能与下一叶子结点 b匹配怎么办？ -查看 A有无另一个选择，
有！ 回溯,把 A为根的子树剪掉，
扫描过的输入串中的 a吐出来,再试探用产生式（ 3）构造推导 S?
cAd? cad
识别输入串 w=caa的 过程,
1.S? cAd
2.选择 (2)扩展 A，得到推导 S? cAd
cabd
3.回溯回 到推导 S? cAd
4.选择 (3)扩展 A，得到推导 S? cAd
cad
5,A没有选择了！ 回溯 到推导 S?
cAd
6.再 回溯 S有无另一个选择？没有！
宣告分析失败。
（请思考 若有
(4) S → cB
(5) B → aa 会怎样?）
11
自上而下的语法分析面临的问题 -实现考虑
回朔
文法的左递归性
S→ Sa
12
自上而下分析对文法的要求例文法 G0[S]:
(1) S→ Sa
(2) S→ b
分析 baa是不是文法的句子按照自上而下的分析思想选用产生式 (1)来推导 S?Sa
语法树末端结点最左符号为非终结符，所以选用（ 1）继续推导 S?Sa?Saa
此时语法树末端结点最左符号仍为非终结符，所以选用（ 1）继续推导 S?Sa?Saa?Saaa
问题 ——试图用 S匹配输入串时，出现：在没有读入任何输入符号的情况下，又得重新要求 S去进行新的匹配原因 ——文法含有左递归，
13
自上而下的语法分析－－左递归规则
G[S],S→Sa
S→b L={ba n | n≥1}
W=baaa S
b
S
S a
S a
14
左递归 －关于非终结符 P的规则直接左递归 若 P → P α | β
α,β ∈V *且 α,β 不以 P开头一般 左递归 若 P =>* P α
S→Aa
A→Sb
…
15
自上而下 分析 的进一步讨论自上而下分析 也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子，若能构造出推导则表明输入串是给定文法的句子，否则表明该输入不是给定文法的句子。
自上而下分析对文法的要求－ 文法不能含有左递归规则。
自上而下分析 又可分为 确定的 和 不确定的 两种不确定的 分析方法称为带回溯的分析方法，这种方法实际上是一种穷举的试探方法确定的分析方法 需对文法有一定的限制
16
消除文法中左递归规则消除直接左递归形如,P → P α | β
α 非?,α,β 不以 P打头改写为,P → β Q
Q → α Q|?
其中 Q为新增加的非终结符
17
消除文法中左递归规则例,E → E+T|T
T →T*F|F
F →(E)| a
G[ E],(1) E → TE’ (2) E’ → +TE’
(3) E’ →? (4) T → FT’
(5) T’ → *FT’ (6) T’ →?
(7) F → (E) (8) F → a
18
消除一般左递归 要求文法,
1.无回路 (A(=>+(A) 2.无空产生式
（ 1）,以某种顺序将文法非终结符排列 A1,A2 …An
（ 2） for i:=1 to n do
begin
for j:=1 to i-1 do
用 Ai-->?1|?2r…|? k r替代形如 Ai--> Ajr的规则,其中
Aj-->?1|?2…|?k是关于 Aj的全部产生式 ;
消除 Ai规则的直接左递归 ;
end;
（ 3） 化简由 2得到的文法
19
回溯的原因例 G[S],
S→ xAy
A→ ab｜ a
若当前输入串为 xay，首先构造的推导 S?xAy
匹配?
进一步推导对 A可选择 A→ ab替换，得 S?xAy?xaby
xay xaby
匹配?
xa都已匹配，当前面临输入符为 y与 b不能匹配，所以将输入串指针退回到 a，对 A的替换重新选用下一个产生式 A→ a进行试探,S?xAy?xay输入串中当前符 a得到匹配，指针向前移动到 y，与语法树中 y匹配，匹配成功。
由于相同左部的产生式的右部开始符号相同而引起回溯。
20
在自上而下的分析方法中 如何 选择 使用 哪个 产生式进行推导？
假定要被代换的最左非终结符号是 B，且有 n条规则,B→ A1|A2|…|An,那么如何确定用哪个右部去替代 B？ -------什么信息用于 Parser做正确选择?(输入串,文法特点 )
21
可预测的试探 推导过程例 文法 G’[S]:
S → pA |qB
A → cAd|a
B → d B |c
识别输入串 w= pccadd是否是 G1[S]的句子可预测的试探 推导过程：
S?pA? pcAd? pccAdd?pccadd
试探 成功。
22
PL/0语言的 EBNF
〈 程序 〉 ∷= 〈 分程序 〉,
〈 分程序 〉 ∷=[ 〈 常量说明部分 〉 ][〈 变量说明部分 〉 ][〈 过程说明部分 〉 ]〈 语句 〉
〈 常量说明部分 〉 ∷=CONST 〈 常量定义部分 〉 {,〈 常量 定义 〉 }；
〈 变量说明部分 〉 ∷=VAR 〈 标识符 〉 {,〈 标识符 〉 }；
〈 过程说明部分 〉 ∷= PROCEDURE 〈 标识符 〉〈 分程序 〉
{； 〈 过程说明部分 〉 }；
〈 语句 〉 ∷= 〈 标识符 〉,=〈 表达式 〉 |IF 〈 条件 〉
then〈 语句 〉 |CALL… |READ… |BEGIN 〈 语句 〉 {； 〈 语句 〉 } END|WHILE… |…
23
PL/0分析,语句,的子程序片断
begin(*statement*)
if sym=ident
then (*parsing ass.st.*)
begin
getsym;
if sym=becomes
then getsym
else error(13);
expression(fsys);
end
else
if sym=readsym
then
(* parsing read st.*)
begin
getsym;
if sym<>lparen
then error(34)
else
repeat
getsym;
if sym <> ident
then error(35)
else getsym
until sym<>comma;
if sym<>rparen
then error(33);
end
24
例：递归子程序实现表达式的语法分析表达式的 EBNF
〈 表达式 〉 ∷=[+| -]〈 项 〉 {（ +|-） 〈 项 〉 }
〈 项 〉 ∷= 〈 因子 〉 {（ *|/） 〈 因子 〉 }
〈 因子 〉 ∷= ident|number|‘（ ’ 〈 表达式 〉
‘） ’
25
〈 表达式 〉 ∷= [+|-]〈 项 〉 {（ +|-） 〈 项 〉 }
int expression(bool* fsys,int* ptx,int lev)
{
if(sym==plus || sym==minus) /* 开头的正负号 */
{ …
getsym;
…
term(nxtlev,ptx,lev); /* 处理项 */
…
}
else /* 此时表达式被看作项的加减 */
{ …
term(nxtlev,ptx,lev); /* 处理项 */
}
while (sym==plus || sym==minus)
{
…
getsym;
…
term(nxtlev,ptx,lev); /* 处理项 */
…
}
}
26
〈 项 〉 ∷= 〈 因子 〉 {（ *|/） 〈 因子 〉 }
int term(bool* fsys,int* ptx,int lev)
{ …
factor (nxtlev,ptx,lev);/* 处理因子 */
while(sym==times || sym==slash)
{ …
getsym;
factor (nxtlev,ptx,lev);
…
}
}
27
〈 因子 〉 ∷= 〈 标识符 〉 |〈 无符号整数 〉 |‘（ ’ 〈 表达式 〉
‘） ’
int factor(bool* fsys,int* ptx,int lev)
{ if(sym == ident) /* 因子为常量或变量 */
getsym else
{if(sym == number) /* 因子为数 */
getsym else
{if (sym == lparen) /* 因子为表达式 */
{ expression(nxtlev,ptx,lev);
if (sym == rparen)
getsym;
else error(22); /* 缺少右括号 */
}
else error( )
}
}
28
5.2 预测分析程序（ Predictive
parser） 无 回溯 的自顶向下分析程序特征 ——根据下一个 (几个）输入符号为当前要处理的非终结符选择产生式要求 ——文法是 LL(1)的第一个 L 从左到右扫描输入串第二个 L 生成的是最左推导
1 向前看一个输入符号（ lookahead)
预测分析程序的实现技术
1 递归（下降）子程序
2 表驱动分析程序
29
例,递归下降子程序 ParseFunction()
BNF描述
program –> function_list
function_list –> function function_list |?
function –> FUNC identifier ( parameter_list ) statement
…
void ParseFunction()
{
MatchToken(T_FUNC);
ParseIdentifier();
MatchToken(T_LPAREN);
ParseParameterList();
MatchToken(T_RPAREN);
ParseStatement();
}
30
例,递归下降子程序 ParseFunction()（续）
void MatchToken(int expected)
{
if (lookahead != expected) {
printf("syntax error \n");
exit(0);
} else // if match,consume token and move
on
lookahead = yylex();
}
31
予测分析程序的实现表驱动 予测分析程序模型
Input
#
总控程序预测分析表
stack
32
带 a0 a1 a2 a3 a4 a5 a6 a7 a8 … an-1 an
有限控制器磁头识别程序的数学模型 下推自动机
33
上下文无关语言句型分析（识别）程序的数学模型下推自动机 Pda=(K,Σ,f,H,h0,S,Z)
K,有穷状态集 S：开始状态 Z：接受状态的集合
Σ,有穷输入字母集
H,有穷 堆 栈 字母表
h0,H中的初始符号
f,K?（ Σ?{?})? H –> K? H*
Pda的一个组态是 K?Σ *? H 中的一个 （ k,w,?) k:当前状态,w:余留输入串,?：栈中符号，最左边的符号在栈顶。
Pda的一次移动用组态表示终止和接受的条件,
1.到达输入串结尾时，处在 Z中的一个状态或 2.某个动作序列导致栈空时
34
例,Pda P=({A,B,C),{a,b,c),f,{h,i},i
A,{ })
f(A,a,i) = (B,h) f(B,a,h) = (B,hh)
f(C,b,h) = (C,?) f(A,c,i) = (A,?)
f(B,c,h) = (C,h)
接受输入串 aacbb的过程
(A,aacbb,i) 读 a,pop i,push h,goto B
(B,acbb,h) 读 a,pop h,push hh,goto B
(B,cbb,hh) 读 c,pop h,push h,goto C
(C,bb,hh) 读 b,pop h,push?,goto C
(C,b,h) 读 b,pop h,push?,goto C
(C,?,? )
35
例：表驱动 予测分析程序
G[ E],(1) E –> TE’
(2) E’ –> +TE’
(3) E’ –>?
(4) T –> FT’
(5) T’ –> *FT’
(6) T’ –>?
(7) F –> (E)
(8) F –> a
36
a + * ( ) #
E (1) (1)
E’ (2) (3) (3)
T (4) (4)
T’ (6) (5) (6) (6)
F (8) (7)
G[ E],(1) E –> TE’ (2) E’ –> +TE’ (3) E’ –>?
(4) T –> FT’ (5) T’ –> *FT’ (6) T’ –>?
(7) F –> (E) (8) F –> a
预测分析表
37
表驱动 予测分析程序分析算法首先把 ’ #‘然后把文法开始符号推入栈；把第一个输入符号读进 b;
FLAG,=TRUE；
WHILE FLAG DO
BEGIN
把栈顶符号上托出去并放在Ｘ 中；
IF X? Vt THEN IF X=b THEN
把下一 个输入符号读进 b
ELSE ERROR
ELSE IF X=‘#’ THEN
IF b=‘#’ THEN FLAG:=FALSE
ELSE ERROR
ELSE IF?[X,b]={X –> X1X2..XK}
THEN 把 XK,X K-1,..,X1一一推进栈
ELSE ERROR
END OF WHILE;
STOP/*分析成功，过程完毕 *／
38
分析输入串 #a+a#的步骤栈内容 栈顶符号 当前输入 余留串 M[X,b ]
1 #E E a +a# E –> TE’
2 #E’T T a +a# T –> FT’
3 #E’T’F F a +a# F –> a
4 #E’T’a a a +a#
5 # E’T’ T’ + a# T’ –>?
6 #E’ E’ + a# E’ –> +TE’
7 #E’T+ + + a#
8 # E’T T a # T –> FT’
9 #E’T’F F a # F –> a
10 #E’T’a a a #
11 #E’T’ T’ # T’ –>?
12 #E’ E’ # E ’ –>?
13 # # #
39
回溯的原因例 G[S],
S→ xAy
A→ ab｜ a
若当前输入串为 xay，首先构造的推导 S?xAy
匹配?
进一步推导对 A可选择 A→ ab替换，得 S?xAy?xaby
xay xaby
匹配?
xa都已匹配，当前面临输入符为 y与 b不能匹配，所以将输入串指针退回到 a，对 A的替换重新选用下一个产生式 A→ a进行试探,S?xAy?xay输入串中当前符 a得到匹配，指针向前移动到 y，与语法树中 y匹配，匹配成功。
由于相同左部的产生式的右部开始符号相同而引起回溯。
40
例 G”[S]:
(1) S→ aAS
(2) S→ b
(3) A→ bAS
(4) A→ ε
对输入串 ab的试探推导,S?aAS
用产生式 (1)推导,a得到匹配，输入串指针移到 b，再将 A向下推导，而对 A的产生式可选 (3)或 (4)，先试选 (3),S?aAS? abAS
…
由于相同左部非终结符 A的右部存在能?*ε的情况且 跟在 它 后面的符号会 含有 b
41
5.3 LL（ 1）分析程序的生成
LL（ 1）文法一个文法 G是 LL（ 1）的，当且仅当对于 G的每一个非终结符
Ａ的任何两个不同产生式Ａ? α?β,下面的条件成立：
１,FIRST（ α ） ∩ FIRST(β )=?,也就是 α?和 β 推导不出以同一个终结符 a为首的符号串；它们不应该都能推出空字
．
２,假若 β =>*?，那么，
FIRST（ α )∩FOLLOW （ A）＝?,也就是，
若 β =>*?.则 α 所能推出的串的首符号不应在 FOLLOW(A）
中．
．
42
FIRST集和 FOLLOW集的定义设 G=(VT,VN,P,S)是上下文无关文法
FIRST（?） ={a|? =>* a?,a∈ VT,?,?∈V *}
若? =>* ε 则规定 ε ∈FRIST （?）
FOLLOW（ A） ={a?S =>*? A?且 a ∈ FRIST
（?）,? ∈ V*,?∈ V+ }
若 S =>* u A?,且? =>* ε,则
#∈F OLLOW(A)
LL (1) 文法
43
计算 FIRST集
1.若 X?V?,则 FIRST(X)={X}
2.若 X?VN,且有产生式 X?a…，则把 a加入到 FIRST(X)
中 ;若 X也是一条产生式,则把?也加到 FIRST(X)中,
3.若 X?Y…是一个产生式且 Y?VN,则把 FIRST(Y)中的所有非?元 素都加到 FIRST(X)中 ;若 X? Y1Y2…YK 是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何 j,1≤ j ≤i -1,FIRST(Yj)都含有? (即
Y1..Y(i-1) =>*? ),则把 FIRST(Yj)中的所有非?元素和 FIRST(Yi)中的所有元素都加到 FIRST(X)中 ;特别是,若所有的 FIRST(Yj,j=1,2,…,K)均含有?,则把?
加到 FRIST(X)中,
44
计算 FOLLOW集
1.对于文法的开始符号 S,置 #于 FOLLOW(S) 中 ;
2.若Ａ? α B β 是一个产生式,则把
FIRST(β )\{?}加至 FOLLOW(B)中 ;
3.若Ａ? α B是一个产生式,或Ａ? α Bβ 是
一个产生式而 β =>*?(即FIRST(β )），
则把 FOLLOW（ A）加至 FOLLOW（ B）中．
45
G[ E],(1) E –> TE’ (2) E’ –> +TE’ (3) E’ –>?
(4) T –> FT’ (5) T’ –> *FT’ (6) T’ –>?
(7) F –> (E) (8) F –> a
·各非终结符的 FIRST集合如下：
FIRST(E)=｛ (,a｝
FIRST(E′)= ｛ +,ε ｝
FIRST(T)=｛ (,a｝
FIRST(T′)= ｛ *,ε ｝
FIRST(F)=｛ (,a｝
·各非终结符的 FOLLOW集合为：
FOLLOW(E)=｛ ),＃｝
FOLLOW(E′)= ｛ )，＃｝
FOLLOW(T)=｛＋,)，＃｝
FOLLOW(T′)= ｛＋,),#}
FOLLOW(F)=｛ *,＋,),#}
46
G[ E],(1) E –> TE’ (2) E’ –> +TE’ (3) E’ –>?
(4) T –> FT’ (5) T’ –> *FT’ (6) T’ –>?
(7) F –> (E) (8) F –> a
E’ –> +TE’ |? FIRST(+TE’)=｛ +｝
FOLLOW(E′)= ｛ )，＃｝
T’ –> *FT’ |? FIRST(*FT’)=｛ *｝
FOLLOW(T′)= ｛ +,)，＃｝
F –> (E) | a FIRST( (E))=｛ (｝
FIRST( a)=｛ a｝
所以 G[E]是 LL（ 1）的
47
予测分析表构造算法
1.对文法 G的每个产生式Ａ执行第二步
和第三步；
2.对每个终结符 a?FIRST(?)，把Ａ加
至?[A,a]中，
3.若 FIRST(?),则对任何 b?FOLLOW(A)
把Ａ加至?[A,b]中，
4.把所有无定义的?[A,a]标上,出错标志,。
可以证明，一个文法 G的予测分析表不含多重入口，当且仅当该文法是 LL(1)的
48
LL(1)文法的性质,
LL(1)文法是无二义的
LL(1)文法不含左递归
49
5.4非 LL(1)文法的改造消除左递归提左公因子将产生式Ａβ | 变换为：
ＡB
B? β |?
50
E→E+T ｜ T
T→T*F ｜ F
F→i ｜ (E)
FIRST(E)=｛ (,i｝
FIRST(T)=｛ (,i｝
FIRST(F)=｛ (,i｝
消左递归
E –> TE’
E’ –> +TE’
E’ –>?
E→T+E ｜ T
T→F*T ｜ F
F→i ｜ (E)
FIRST(E)
=FIRST(T)
=FIRST(F)
=｛ (,i｝
提左公因子
E→T(+E ｜?)
T→F(*T ｜?)
51
消除左递归和提左公因子并不一定都能将 非 LL(1)文法改造 为 LL(1)的
S → if C t S |
if C t S e S
C →b
提左因子
S → if C t S A
A→ e S |?
First集 Follow集
S if #,e
A e,? #,e
C b t
M[A,e]={A→ e S
A→? }
52
LL(1)分析中的一种错误处理办法发现错误
1栈顶的终结符与当前输入符不匹配
2非终结符 A于栈顶，面临的输入符为 a，但分析表 M的 M[A,a]为空
“应急”恢复策略跳过输入串中的一些符号直至遇到“同步符号”为止。
同步符号的选择
1把 FOLLOW(A)中的所有符号作为 A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把 A从栈中弹出，可使分析继续
2把 FIRST(A)中的符号加到 A的同步符号集，当 FIRST(A)中的符号在输入中出现时，可根据 A恢复分析
53
a + * ( ) #
E (1) (1)
E’ (2) (3) (3)
T (4) (4)
T’ (6) (5) (6) (6)
F (8) (7)
G[ E],(1) E –> TE’ (2) E’ –> +TE’ (3) E’ –>?
(4) T –> FT’ (5) T’ –> *FT’ (6) T’ –>?
(7) F –> (E) (8) F –> a
syn
syn
54
练习
1,对文法 G［ S］
S→a| ∧ |(T)
T→T,S|S
（ 1）给出 (a,(a,a)) 和 (((a,a),∧,(a)),a)的最左推导。
（ 2）对文法 G进行改写，改写后的文法 G’是否 LL(1)?
若是，给出它的递归下降分析程序和预测分析表，
并描述对输入串 (a,a)#的分析过程。
2,已知文法 G[S]：
S→MH|a
H→LSo|ε
K→dML|ε
L→eHf
M→K|bLM 判断 G是否是 LL(1)文法，如果是，构造 LL(1)分析表。
55
3,对于一个文法若消除了左递归，提取了左公共因子后是否一定为 LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。
(1) A→aABe|a
B→Bb|d
(3) S→Aa|b
A→SB
B→ab
56
review---parsing
The syntax analysis phase of a compiler verifies that the
sequence of tokens returned from the scanner
represent valid sentences in the grammar of the
programming language,
There are two major parsing approaches,top-down and
bottom-up,
In top-down parsing,you start with the start symbol and
apply the productions until you arrive at the desired
string,
In bottom-up parsing,you start with the string and
reduce it to the start symbol by applying the
productions backwards,
57
In the top-down parsing,we
begin with the start symbol
and at each step,expand one
of the remaining nonterminals
by replacing it with the right
side of one its productions.
We repeat until only terminals
remain,The top-down parse
prints a leftmost derivation of
the sentence.
A bottom-up parse works in
reverse,We begin with the
sentence of terminals and each
step applies a production in
reverse,replacing a substring
that matches the right side with
the nonterminal on the left,
We continue until we have
substituted our way back to the
start symbol,If you read from
the bottom to top,the bottom-up
parse prints out a rightmost
derivation of the sentence.
58
lookahead symbol,The lookahead symbol is the next
symbol coming up in the input,
backtracking,Based on the information the parser
currently has about the input,a decision is made to
go with one particular production,If this choice leads
to a dead end,the parser would have to backtrack to
that decision point,moving backwards through the
input,and start again making a different choice and
so on until it either found the production that was the
appropriate one or ran out of choices.
59
predictive parser and LL(1)grammar
Predictive parser is a non-backtracking top-down
parser,A predictive parser is characterized by its
ability to choose the production to apply solely on the
basis of the next input symbol and the current
nonterminal being processed,
To enable this,the grammar must take a particular form,
We call such a grammar LL(1),The first,L” means
we scan the input from left to right; the second,L”
means we create a leftmost derivation; and the 1
means one input symbol of lookahead.
60
recursive-descent
The first technique for implementing a predictive parser
is called recursive-descent,
A recursive descent parser consists of several small
functions(procedures),one for each nonterminal in
the grammar,As we parse a sentence,we call the
functions (procedures) that correspond to the left side
nonterminal of the productions we are applying,If
these productions are recursive,we end up calling the
functions recursively.
61
Table-driven LL(1) parsing
In a recursive-descent parser,the production
information is embedded in the individual parse
functions for each nonterminal and the run-time
execution stack is keeping track of our progress
through the parse,There is another method for
implementing a predictive parser that uses a table
to store that production along with an explicit stack
to keep track of where we are in the parse.
62
How a table-driven predictive parser works
We push the start symbol on the stack and read the first
input token,As the parser works through the input,there
are the following possibilities for the top stack symbol X
and the input token nonterminal a:
1,If X = a and a = end of input (#),parser halts and parse
completed successfully
2,If X = a and a != #,successful match,pop X and advance
to next input token,This is called a match action.
3,If X != a and X is a nonterminal,pop X and consult table
at [X,a] to see which production applies,push right side of
production on stack,This is called a predict action.
4,If none of the preceding cases applies or the table entry
from step 3 is blank,there has been a parse error
63
The first set of a sequence of symbols u,written
as First(u ) is the set of terminals which
start all the sequences of symbols derivable from
u,A bit more formally,consider all
strings derivable from u by a leftmost derivation,
If u =>* v,where v begins with some
terminal,that terminal is in First(u),If u =>*?,
then? is in First(u ).
64
The follow set of a nonterminal A is the set of
terminal symbols that can appear immediately
to the right of A in a valid sentential form,A
bit more formally,for every valid sentential
form S =>*uAv,where v begins with some
terminal,that terminal is in Follow(A).
65
Calculating first set
To calculate First(u) where u has the form
X1X2...Xn,do the following:
1,If X1 is a terminal,then add X1 to First(u),
otherwise add First(X1) -? to First(u ),
2,If X1 is a nullable nonterminal,i.e.,X1 =>*?,
add First(X2) -? to First(u),Furthermore,
if X2 can also go to?,then add First(X3) -?
and so on,through all Xn until the first
nonnullable one.
3,If X1X2...Xn =>*?,add? to the first set.
66
Calculating follow sets,For each nonterminal in the
grammar,do the following:
1,Place# in Follow(S) where S is the start symbol and # is
the input's right endmarker.The endmarker might be end of
file,it might be newline,it might be a special symbol,
whatever is the expected end of input indication for this
grammar,We will typically use # as the endmarker.
2,For every production A –> uBv where u and v are any
string of grammar symbols and B is a nonterminal,
everything in First(v) except? is placed in Follow(B).
3,For every production A –> uB,or a production A –> u Bv
where First(v ) contains? (i.e,v is nullable),then
everything in Follow(A) is added to Follow(B).
67
Constructing the parse table
1,For each production A –> u of the grammar,do steps 2
and 3
2,For each terminal a in First(u),add A –> u to M[A,a]
3,If? in First(u),(i.e,A is nullable) add A –> u to
M[A,b] for each terminal b in Follow(A),
If? in First(u),and # is in Follow(A),add A –> u to
M[A,#]
4,All undefined entries are errors
68
LL(1) grammar
A grammar G is LL(1) iff whenever A –> u | v are two
distinct productions of G,the following conditions
hold:
- for no terminal a do both u and v derive strings
beginning with a (i.e,first sets are disjoint)
- at most one of u and v can derive the empty string
- if v =>*? then u does not derive any string beginning
with a terminal in Follow(A)
69
Error-reporting and recovery
An error is detected in predictive parsing when
the terminal on top of the stack does not match
the next input symbol or
when nonterminal A is on top of the stack,a is
the next input symbol and the parsing table
entry M[A,a] is empty.
70
Panic-mode error recovery
Panic-mode error recovery is a simple technique
that just bails out of the current construct,
looking for a safe symbol at which to restart
parsing,The parser just discards input tokens
until it finds what is called a synchronizing
token,The set of synchronizing tokens are
those that we believe confirm the end of the
invalid statement and allow us to pick up at
the next piece of code.
第 5章 LL(1)文法及其分析程序
5.1 自上而下的语法分析
5.2 预测分析程序递归下降子程序表驱动的预测分析程序
5.3 LL(1)分析程序的生成
LL(1)文法
FIRST和 FOLLOW集 定义和计算
5.4 非 LL(1)文法的改造
2
5.1自上而下的语法分析
1语法分析概念
2自上而下的语法分析的一般过程
3自上而下的语法分析面临的问题
3
（ 上下文无关文法） 句型的分析句型分析 就是 识别 一个符号串是否为某文法的 句型的 过程，或者说是某个 推导 的构造过程。
4
语法树－推导的几何表示
句型 aabbaa的可能 推导 序列和语法树例,G[S]:
S→ aAS
A→ SbA
A→ SS
S→ a
A→ ba
S
a A S
S b A a
a b a
S?aAS?aAa?aSbAa?aSbbaa?aabbaa
S?aAS?aSbAS?aabAS?aabbaS?aabbaa
S?aAS?aSbAS?aSbAa?aabAa?aabbaa
5
语法分析在语言的编译实现中，把 句子分析 的过程称为 语法分析，即 完成这个任务的程序称为语法分析 程序或称为 识别程序 。 分析算法又称识别算法。
从左到右的分析算法,即 总是从 左 到 右 地 识别输入符号串,首先识别符号串中的 最左符号，进而 依次识别右边 的一个符号,直到分析结束 。
6
分析算法分类分析算法可分为：
自上而下分析法,
从文法的开始符号出发,寻找 与 输入符号串 匹配 的 推导,或者说，为输入串寻找一个最左推导。
自下而上分析法,
从 输入符号串 开始,逐步进行 归约,直至归约 到 文法的 开始符号 。
7
两种方法反映了语法树的两种构造过程。
自上而下方法 是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法 则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树
8
自上而下分析对任何输入串，试图用一切可能的办法，
从文法开始符号着手，自上而下地为输入串构造一棵语法树，或者说，为输入串寻找一个最左推导。本质上是一个试探过程，
反复使用不同地产生式谋求匹配输入串的过程。
9
自上而下的语法分析的一般过程例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否为该文法的 句子
S S S
c A d c A d
a b
推导过程,S? cAd cAd? cabd
10
自上而下的语法分析的一般过程
(1)S → cAd (2) A → ab (3) A → a
识别输入串 w=cad是否为该文法的 句子
1.S? cAd
2.后选择 (2)扩展 A，得到推导 S?
cAd? cabd
这时
w的第二个符号可以与叶子结点 a
得以匹配，但第三个符号 d却不能与下一叶子结点 b匹配怎么办？ -查看 A有无另一个选择，
有！ 回溯,把 A为根的子树剪掉，
扫描过的输入串中的 a吐出来,再试探用产生式（ 3）构造推导 S?
cAd? cad
识别输入串 w=caa的 过程,
1.S? cAd
2.选择 (2)扩展 A，得到推导 S? cAd
cabd
3.回溯回 到推导 S? cAd
4.选择 (3)扩展 A，得到推导 S? cAd
cad
5,A没有选择了！ 回溯 到推导 S?
cAd
6.再 回溯 S有无另一个选择？没有！
宣告分析失败。
（请思考 若有
(4) S → cB
(5) B → aa 会怎样?）
11
自上而下的语法分析面临的问题 -实现考虑
回朔
文法的左递归性
S→ Sa
12
自上而下分析对文法的要求例文法 G0[S]:
(1) S→ Sa
(2) S→ b
分析 baa是不是文法的句子按照自上而下的分析思想选用产生式 (1)来推导 S?Sa
语法树末端结点最左符号为非终结符，所以选用（ 1）继续推导 S?Sa?Saa
此时语法树末端结点最左符号仍为非终结符，所以选用（ 1）继续推导 S?Sa?Saa?Saaa
问题 ——试图用 S匹配输入串时，出现：在没有读入任何输入符号的情况下，又得重新要求 S去进行新的匹配原因 ——文法含有左递归，
13
自上而下的语法分析－－左递归规则
G[S],S→Sa
S→b L={ba n | n≥1}
W=baaa S
b
S
S a
S a
14
左递归 －关于非终结符 P的规则直接左递归 若 P → P α | β
α,β ∈V *且 α,β 不以 P开头一般 左递归 若 P =>* P α
S→Aa
A→Sb
…
15
自上而下 分析 的进一步讨论自上而下分析 也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子，若能构造出推导则表明输入串是给定文法的句子，否则表明该输入不是给定文法的句子。
自上而下分析对文法的要求－ 文法不能含有左递归规则。
自上而下分析 又可分为 确定的 和 不确定的 两种不确定的 分析方法称为带回溯的分析方法，这种方法实际上是一种穷举的试探方法确定的分析方法 需对文法有一定的限制
16
消除文法中左递归规则消除直接左递归形如,P → P α | β
α 非?,α,β 不以 P打头改写为,P → β Q
Q → α Q|?
其中 Q为新增加的非终结符
17
消除文法中左递归规则例,E → E+T|T
T →T*F|F
F →(E)| a
G[ E],(1) E → TE’ (2) E’ → +TE’
(3) E’ →? (4) T → FT’
(5) T’ → *FT’ (6) T’ →?
(7) F → (E) (8) F → a
18
消除一般左递归 要求文法,
1.无回路 (A(=>+(A) 2.无空产生式
（ 1）,以某种顺序将文法非终结符排列 A1,A2 …An
（ 2） for i:=1 to n do
begin
for j:=1 to i-1 do
用 Ai-->?1|?2r…|? k r替代形如 Ai--> Ajr的规则,其中
Aj-->?1|?2…|?k是关于 Aj的全部产生式 ;
消除 Ai规则的直接左递归 ;
end;
（ 3） 化简由 2得到的文法
19
回溯的原因例 G[S],
S→ xAy
A→ ab｜ a
若当前输入串为 xay，首先构造的推导 S?xAy
匹配?
进一步推导对 A可选择 A→ ab替换，得 S?xAy?xaby
xay xaby
匹配?
xa都已匹配，当前面临输入符为 y与 b不能匹配，所以将输入串指针退回到 a，对 A的替换重新选用下一个产生式 A→ a进行试探,S?xAy?xay输入串中当前符 a得到匹配，指针向前移动到 y，与语法树中 y匹配，匹配成功。
由于相同左部的产生式的右部开始符号相同而引起回溯。
20
在自上而下的分析方法中 如何 选择 使用 哪个 产生式进行推导？
假定要被代换的最左非终结符号是 B，且有 n条规则,B→ A1|A2|…|An,那么如何确定用哪个右部去替代 B？ -------什么信息用于 Parser做正确选择?(输入串,文法特点 )
21
可预测的试探 推导过程例 文法 G’[S]:
S → pA |qB
A → cAd|a
B → d B |c
识别输入串 w= pccadd是否是 G1[S]的句子可预测的试探 推导过程：
S?pA? pcAd? pccAdd?pccadd
试探 成功。
22
PL/0语言的 EBNF
〈 程序 〉 ∷= 〈 分程序 〉,
〈 分程序 〉 ∷=[ 〈 常量说明部分 〉 ][〈 变量说明部分 〉 ][〈 过程说明部分 〉 ]〈 语句 〉
〈 常量说明部分 〉 ∷=CONST 〈 常量定义部分 〉 {,〈 常量 定义 〉 }；
〈 变量说明部分 〉 ∷=VAR 〈 标识符 〉 {,〈 标识符 〉 }；
〈 过程说明部分 〉 ∷= PROCEDURE 〈 标识符 〉〈 分程序 〉
{； 〈 过程说明部分 〉 }；
〈 语句 〉 ∷= 〈 标识符 〉,=〈 表达式 〉 |IF 〈 条件 〉
then〈 语句 〉 |CALL… |READ… |BEGIN 〈 语句 〉 {； 〈 语句 〉 } END|WHILE… |…
23
PL/0分析,语句,的子程序片断
begin(*statement*)
if sym=ident
then (*parsing ass.st.*)
begin
getsym;
if sym=becomes
then getsym
else error(13);
expression(fsys);
end
else
if sym=readsym
then
(* parsing read st.*)
begin
getsym;
if sym<>lparen
then error(34)
else
repeat
getsym;
if sym <> ident
then error(35)
else getsym
until sym<>comma;
if sym<>rparen
then error(33);
end
24
例：递归子程序实现表达式的语法分析表达式的 EBNF
〈 表达式 〉 ∷=[+| -]〈 项 〉 {（ +|-） 〈 项 〉 }
〈 项 〉 ∷= 〈 因子 〉 {（ *|/） 〈 因子 〉 }
〈 因子 〉 ∷= ident|number|‘（ ’ 〈 表达式 〉
‘） ’
25
〈 表达式 〉 ∷= [+|-]〈 项 〉 {（ +|-） 〈 项 〉 }
int expression(bool* fsys,int* ptx,int lev)
{
if(sym==plus || sym==minus) /* 开头的正负号 */
{ …
getsym;
…
term(nxtlev,ptx,lev); /* 处理项 */
…
}
else /* 此时表达式被看作项的加减 */
{ …
term(nxtlev,ptx,lev); /* 处理项 */
}
while (sym==plus || sym==minus)
{
…
getsym;
…
term(nxtlev,ptx,lev); /* 处理项 */
…
}
}
26
〈 项 〉 ∷= 〈 因子 〉 {（ *|/） 〈 因子 〉 }
int term(bool* fsys,int* ptx,int lev)
{ …
factor (nxtlev,ptx,lev);/* 处理因子 */
while(sym==times || sym==slash)
{ …
getsym;
factor (nxtlev,ptx,lev);
…
}
}
27
〈 因子 〉 ∷= 〈 标识符 〉 |〈 无符号整数 〉 |‘（ ’ 〈 表达式 〉
‘） ’
int factor(bool* fsys,int* ptx,int lev)
{ if(sym == ident) /* 因子为常量或变量 */
getsym else
{if(sym == number) /* 因子为数 */
getsym else
{if (sym == lparen) /* 因子为表达式 */
{ expression(nxtlev,ptx,lev);
if (sym == rparen)
getsym;
else error(22); /* 缺少右括号 */
}
else error( )
}
}
28
5.2 预测分析程序（ Predictive
parser） 无 回溯 的自顶向下分析程序特征 ——根据下一个 (几个）输入符号为当前要处理的非终结符选择产生式要求 ——文法是 LL(1)的第一个 L 从左到右扫描输入串第二个 L 生成的是最左推导
1 向前看一个输入符号（ lookahead)
预测分析程序的实现技术
1 递归（下降）子程序
2 表驱动分析程序
29
例,递归下降子程序 ParseFunction()
BNF描述
program –> function_list
function_list –> function function_list |?
function –> FUNC identifier ( parameter_list ) statement
…
void ParseFunction()
{
MatchToken(T_FUNC);
ParseIdentifier();
MatchToken(T_LPAREN);
ParseParameterList();
MatchToken(T_RPAREN);
ParseStatement();
}
30
例,递归下降子程序 ParseFunction()（续）
void MatchToken(int expected)
{
if (lookahead != expected) {
printf("syntax error \n");
exit(0);
} else // if match,consume token and move
on
lookahead = yylex();
}
31
予测分析程序的实现表驱动 予测分析程序模型
Input
#
总控程序预测分析表
stack
32
带 a0 a1 a2 a3 a4 a5 a6 a7 a8 … an-1 an
有限控制器磁头识别程序的数学模型 下推自动机
33
上下文无关语言句型分析（识别）程序的数学模型下推自动机 Pda=(K,Σ,f,H,h0,S,Z)
K,有穷状态集 S：开始状态 Z：接受状态的集合
Σ,有穷输入字母集
H,有穷 堆 栈 字母表
h0,H中的初始符号
f,K?（ Σ?{?})? H –> K? H*
Pda的一个组态是 K?Σ *? H 中的一个 （ k,w,?) k:当前状态,w:余留输入串,?：栈中符号，最左边的符号在栈顶。
Pda的一次移动用组态表示终止和接受的条件,
1.到达输入串结尾时，处在 Z中的一个状态或 2.某个动作序列导致栈空时
34
例,Pda P=({A,B,C),{a,b,c),f,{h,i},i
A,{ })
f(A,a,i) = (B,h) f(B,a,h) = (B,hh)
f(C,b,h) = (C,?) f(A,c,i) = (A,?)
f(B,c,h) = (C,h)
接受输入串 aacbb的过程
(A,aacbb,i) 读 a,pop i,push h,goto B
(B,acbb,h) 读 a,pop h,push hh,goto B
(B,cbb,hh) 读 c,pop h,push h,goto C
(C,bb,hh) 读 b,pop h,push?,goto C
(C,b,h) 读 b,pop h,push?,goto C
(C,?,? )
35
例：表驱动 予测分析程序
G[ E],(1) E –> TE’
(2) E’ –> +TE’
(3) E’ –>?
(4) T –> FT’
(5) T’ –> *FT’
(6) T’ –>?
(7) F –> (E)
(8) F –> a
36
a + * ( ) #
E (1) (1)
E’ (2) (3) (3)
T (4) (4)
T’ (6) (5) (6) (6)
F (8) (7)
G[ E],(1) E –> TE’ (2) E’ –> +TE’ (3) E’ –>?
(4) T –> FT’ (5) T’ –> *FT’ (6) T’ –>?
(7) F –> (E) (8) F –> a
预测分析表
37
表驱动 予测分析程序分析算法首先把 ’ #‘然后把文法开始符号推入栈；把第一个输入符号读进 b;
FLAG,=TRUE；
WHILE FLAG DO
BEGIN
把栈顶符号上托出去并放在Ｘ 中；
IF X? Vt THEN IF X=b THEN
把下一 个输入符号读进 b
ELSE ERROR
ELSE IF X=‘#’ THEN
IF b=‘#’ THEN FLAG:=FALSE
ELSE ERROR
ELSE IF?[X,b]={X –> X1X2..XK}
THEN 把 XK,X K-1,..,X1一一推进栈
ELSE ERROR
END OF WHILE;
STOP/*分析成功，过程完毕 *／
38
分析输入串 #a+a#的步骤栈内容 栈顶符号 当前输入 余留串 M[X,b ]
1 #E E a +a# E –> TE’
2 #E’T T a +a# T –> FT’
3 #E’T’F F a +a# F –> a
4 #E’T’a a a +a#
5 # E’T’ T’ + a# T’ –>?
6 #E’ E’ + a# E’ –> +TE’
7 #E’T+ + + a#
8 # E’T T a # T –> FT’
9 #E’T’F F a # F –> a
10 #E’T’a a a #
11 #E’T’ T’ # T’ –>?
12 #E’ E’ # E ’ –>?
13 # # #
39
回溯的原因例 G[S],
S→ xAy
A→ ab｜ a
若当前输入串为 xay，首先构造的推导 S?xAy
匹配?
进一步推导对 A可选择 A→ ab替换，得 S?xAy?xaby
xay xaby
匹配?
xa都已匹配，当前面临输入符为 y与 b不能匹配，所以将输入串指针退回到 a，对 A的替换重新选用下一个产生式 A→ a进行试探,S?xAy?xay输入串中当前符 a得到匹配，指针向前移动到 y，与语法树中 y匹配，匹配成功。
由于相同左部的产生式的右部开始符号相同而引起回溯。
40
例 G”[S]:
(1) S→ aAS
(2) S→ b
(3) A→ bAS
(4) A→ ε
对输入串 ab的试探推导,S?aAS
用产生式 (1)推导,a得到匹配，输入串指针移到 b，再将 A向下推导，而对 A的产生式可选 (3)或 (4)，先试选 (3),S?aAS? abAS
…
由于相同左部非终结符 A的右部存在能?*ε的情况且 跟在 它 后面的符号会 含有 b
41
5.3 LL（ 1）分析程序的生成
LL（ 1）文法一个文法 G是 LL（ 1）的，当且仅当对于 G的每一个非终结符
Ａ的任何两个不同产生式Ａ? α?β,下面的条件成立：
１,FIRST（ α ） ∩ FIRST(β )=?,也就是 α?和 β 推导不出以同一个终结符 a为首的符号串；它们不应该都能推出空字
．
２,假若 β =>*?，那么，
FIRST（ α )∩FOLLOW （ A）＝?,也就是，
若 β =>*?.则 α 所能推出的串的首符号不应在 FOLLOW(A）
中．
．
42
FIRST集和 FOLLOW集的定义设 G=(VT,VN,P,S)是上下文无关文法
FIRST（?） ={a|? =>* a?,a∈ VT,?,?∈V *}
若? =>* ε 则规定 ε ∈FRIST （?）
FOLLOW（ A） ={a?S =>*? A?且 a ∈ FRIST
（?）,? ∈ V*,?∈ V+ }
若 S =>* u A?,且? =>* ε,则
#∈F OLLOW(A)
LL (1) 文法
43
计算 FIRST集
1.若 X?V?,则 FIRST(X)={X}
2.若 X?VN,且有产生式 X?a…，则把 a加入到 FIRST(X)
中 ;若 X也是一条产生式,则把?也加到 FIRST(X)中,
3.若 X?Y…是一个产生式且 Y?VN,则把 FIRST(Y)中的所有非?元 素都加到 FIRST(X)中 ;若 X? Y1Y2…YK 是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何 j,1≤ j ≤i -1,FIRST(Yj)都含有? (即
Y1..Y(i-1) =>*? ),则把 FIRST(Yj)中的所有非?元素和 FIRST(Yi)中的所有元素都加到 FIRST(X)中 ;特别是,若所有的 FIRST(Yj,j=1,2,…,K)均含有?,则把?
加到 FRIST(X)中,
44
计算 FOLLOW集
1.对于文法的开始符号 S,置 #于 FOLLOW(S) 中 ;
2.若Ａ? α B β 是一个产生式,则把
FIRST(β )\{?}加至 FOLLOW(B)中 ;
3.若Ａ? α B是一个产生式,或Ａ? α Bβ 是
一个产生式而 β =>*?(即FIRST(β )），
则把 FOLLOW（ A）加至 FOLLOW（ B）中．
45
G[ E],(1) E –> TE’ (2) E’ –> +TE’ (3) E’ –>?
(4) T –> FT’ (5) T’ –> *FT’ (6) T’ –>?
(7) F –> (E) (8) F –> a
·各非终结符的 FIRST集合如下：
FIRST(E)=｛ (,a｝
FIRST(E′)= ｛ +,ε ｝
FIRST(T)=｛ (,a｝
FIRST(T′)= ｛ *,ε ｝
FIRST(F)=｛ (,a｝
·各非终结符的 FOLLOW集合为：
FOLLOW(E)=｛ ),＃｝
FOLLOW(E′)= ｛ )，＃｝
FOLLOW(T)=｛＋,)，＃｝
FOLLOW(T′)= ｛＋,),#}
FOLLOW(F)=｛ *,＋,),#}
46
G[ E],(1) E –> TE’ (2) E’ –> +TE’ (3) E’ –>?
(4) T –> FT’ (5) T’ –> *FT’ (6) T’ –>?
(7) F –> (E) (8) F –> a
E’ –> +TE’ |? FIRST(+TE’)=｛ +｝
FOLLOW(E′)= ｛ )，＃｝
T’ –> *FT’ |? FIRST(*FT’)=｛ *｝
FOLLOW(T′)= ｛ +,)，＃｝
F –> (E) | a FIRST( (E))=｛ (｝
FIRST( a)=｛ a｝
所以 G[E]是 LL（ 1）的
47
予测分析表构造算法
1.对文法 G的每个产生式Ａ执行第二步
和第三步；
2.对每个终结符 a?FIRST(?)，把Ａ加
至?[A,a]中，
3.若 FIRST(?),则对任何 b?FOLLOW(A)
把Ａ加至?[A,b]中，
4.把所有无定义的?[A,a]标上,出错标志,。
可以证明，一个文法 G的予测分析表不含多重入口，当且仅当该文法是 LL(1)的
48
LL(1)文法的性质,
LL(1)文法是无二义的
LL(1)文法不含左递归
49
5.4非 LL(1)文法的改造消除左递归提左公因子将产生式Ａβ | 变换为：
ＡB
B? β |?
50
E→E+T ｜ T
T→T*F ｜ F
F→i ｜ (E)
FIRST(E)=｛ (,i｝
FIRST(T)=｛ (,i｝
FIRST(F)=｛ (,i｝
消左递归
E –> TE’
E’ –> +TE’
E’ –>?
E→T+E ｜ T
T→F*T ｜ F
F→i ｜ (E)
FIRST(E)
=FIRST(T)
=FIRST(F)
=｛ (,i｝
提左公因子
E→T(+E ｜?)
T→F(*T ｜?)
51
消除左递归和提左公因子并不一定都能将 非 LL(1)文法改造 为 LL(1)的
S → if C t S |
if C t S e S
C →b
提左因子
S → if C t S A
A→ e S |?
First集 Follow集
S if #,e
A e,? #,e
C b t
M[A,e]={A→ e S
A→? }
52
LL(1)分析中的一种错误处理办法发现错误
1栈顶的终结符与当前输入符不匹配
2非终结符 A于栈顶，面临的输入符为 a，但分析表 M的 M[A,a]为空
“应急”恢复策略跳过输入串中的一些符号直至遇到“同步符号”为止。
同步符号的选择
1把 FOLLOW(A)中的所有符号作为 A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把 A从栈中弹出，可使分析继续
2把 FIRST(A)中的符号加到 A的同步符号集，当 FIRST(A)中的符号在输入中出现时，可根据 A恢复分析
53
a + * ( ) #
E (1) (1)
E’ (2) (3) (3)
T (4) (4)
T’ (6) (5) (6) (6)
F (8) (7)
G[ E],(1) E –> TE’ (2) E’ –> +TE’ (3) E’ –>?
(4) T –> FT’ (5) T’ –> *FT’ (6) T’ –>?
(7) F –> (E) (8) F –> a
syn
syn
54
练习
1,对文法 G［ S］
S→a| ∧ |(T)
T→T,S|S
（ 1）给出 (a,(a,a)) 和 (((a,a),∧,(a)),a)的最左推导。
（ 2）对文法 G进行改写，改写后的文法 G’是否 LL(1)?
若是，给出它的递归下降分析程序和预测分析表，
并描述对输入串 (a,a)#的分析过程。
2,已知文法 G[S]：
S→MH|a
H→LSo|ε
K→dML|ε
L→eHf
M→K|bLM 判断 G是否是 LL(1)文法，如果是，构造 LL(1)分析表。
55
3,对于一个文法若消除了左递归，提取了左公共因子后是否一定为 LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。
(1) A→aABe|a
B→Bb|d
(3) S→Aa|b
A→SB
B→ab
56
review---parsing
The syntax analysis phase of a compiler verifies that the
sequence of tokens returned from the scanner
represent valid sentences in the grammar of the
programming language,
There are two major parsing approaches,top-down and
bottom-up,
In top-down parsing,you start with the start symbol and
apply the productions until you arrive at the desired
string,
In bottom-up parsing,you start with the string and
reduce it to the start symbol by applying the
productions backwards,
57
In the top-down parsing,we
begin with the start symbol
and at each step,expand one
of the remaining nonterminals
by replacing it with the right
side of one its productions.
We repeat until only terminals
remain,The top-down parse
prints a leftmost derivation of
the sentence.
A bottom-up parse works in
reverse,We begin with the
sentence of terminals and each
step applies a production in
reverse,replacing a substring
that matches the right side with
the nonterminal on the left,
We continue until we have
substituted our way back to the
start symbol,If you read from
the bottom to top,the bottom-up
parse prints out a rightmost
derivation of the sentence.
58
lookahead symbol,The lookahead symbol is the next
symbol coming up in the input,
backtracking,Based on the information the parser
currently has about the input,a decision is made to
go with one particular production,If this choice leads
to a dead end,the parser would have to backtrack to
that decision point,moving backwards through the
input,and start again making a different choice and
so on until it either found the production that was the
appropriate one or ran out of choices.
59
predictive parser and LL(1)grammar
Predictive parser is a non-backtracking top-down
parser,A predictive parser is characterized by its
ability to choose the production to apply solely on the
basis of the next input symbol and the current
nonterminal being processed,
To enable this,the grammar must take a particular form,
We call such a grammar LL(1),The first,L” means
we scan the input from left to right; the second,L”
means we create a leftmost derivation; and the 1
means one input symbol of lookahead.
60
recursive-descent
The first technique for implementing a predictive parser
is called recursive-descent,
A recursive descent parser consists of several small
functions(procedures),one for each nonterminal in
the grammar,As we parse a sentence,we call the
functions (procedures) that correspond to the left side
nonterminal of the productions we are applying,If
these productions are recursive,we end up calling the
functions recursively.
61
Table-driven LL(1) parsing
In a recursive-descent parser,the production
information is embedded in the individual parse
functions for each nonterminal and the run-time
execution stack is keeping track of our progress
through the parse,There is another method for
implementing a predictive parser that uses a table
to store that production along with an explicit stack
to keep track of where we are in the parse.
62
How a table-driven predictive parser works
We push the start symbol on the stack and read the first
input token,As the parser works through the input,there
are the following possibilities for the top stack symbol X
and the input token nonterminal a:
1,If X = a and a = end of input (#),parser halts and parse
completed successfully
2,If X = a and a != #,successful match,pop X and advance
to next input token,This is called a match action.
3,If X != a and X is a nonterminal,pop X and consult table
at [X,a] to see which production applies,push right side of
production on stack,This is called a predict action.
4,If none of the preceding cases applies or the table entry
from step 3 is blank,there has been a parse error
63
The first set of a sequence of symbols u,written
as First(u ) is the set of terminals which
start all the sequences of symbols derivable from
u,A bit more formally,consider all
strings derivable from u by a leftmost derivation,
If u =>* v,where v begins with some
terminal,that terminal is in First(u),If u =>*?,
then? is in First(u ).
64
The follow set of a nonterminal A is the set of
terminal symbols that can appear immediately
to the right of A in a valid sentential form,A
bit more formally,for every valid sentential
form S =>*uAv,where v begins with some
terminal,that terminal is in Follow(A).
65
Calculating first set
To calculate First(u) where u has the form
X1X2...Xn,do the following:
1,If X1 is a terminal,then add X1 to First(u),
otherwise add First(X1) -? to First(u ),
2,If X1 is a nullable nonterminal,i.e.,X1 =>*?,
add First(X2) -? to First(u),Furthermore,
if X2 can also go to?,then add First(X3) -?
and so on,through all Xn until the first
nonnullable one.
3,If X1X2...Xn =>*?,add? to the first set.
66
Calculating follow sets,For each nonterminal in the
grammar,do the following:
1,Place# in Follow(S) where S is the start symbol and # is
the input's right endmarker.The endmarker might be end of
file,it might be newline,it might be a special symbol,
whatever is the expected end of input indication for this
grammar,We will typically use # as the endmarker.
2,For every production A –> uBv where u and v are any
string of grammar symbols and B is a nonterminal,
everything in First(v) except? is placed in Follow(B).
3,For every production A –> uB,or a production A –> u Bv
where First(v ) contains? (i.e,v is nullable),then
everything in Follow(A) is added to Follow(B).
67
Constructing the parse table
1,For each production A –> u of the grammar,do steps 2
and 3
2,For each terminal a in First(u),add A –> u to M[A,a]
3,If? in First(u),(i.e,A is nullable) add A –> u to
M[A,b] for each terminal b in Follow(A),
If? in First(u),and # is in Follow(A),add A –> u to
M[A,#]
4,All undefined entries are errors
68
LL(1) grammar
A grammar G is LL(1) iff whenever A –> u | v are two
distinct productions of G,the following conditions
hold:
- for no terminal a do both u and v derive strings
beginning with a (i.e,first sets are disjoint)
- at most one of u and v can derive the empty string
- if v =>*? then u does not derive any string beginning
with a terminal in Follow(A)
69
Error-reporting and recovery
An error is detected in predictive parsing when
the terminal on top of the stack does not match
the next input symbol or
when nonterminal A is on top of the stack,a is
the next input symbol and the parsing table
entry M[A,a] is empty.
70
Panic-mode error recovery
Panic-mode error recovery is a simple technique
that just bails out of the current construct,
looking for a safe symbol at which to restart
parsing,The parser just discards input tokens
until it finds what is called a synchronizing
token,The set of synchronizing tokens are
those that we believe confirm the end of the
invalid statement and allow us to pick up at
the next piece of code.
