这个文法的特点：
1、每个产生式的右部都由终结符号开始
2、如果两个产生式有相同的左部，那么它们 的右部由不同的终结符开始
编译原理
2020年5月23日
【例】 G2[S]:
S → Ap |Bq
A →a|cA
B →b|dB 识别输入串w= ccap是否是G2[S]的句子
❖试探推导过程：
➢S Ap cAp ➢试探成功
编译原理
2020年5月23日
自顶向下分析方法分类 确定的
回溯 不确定的
编译原理
2020年5月23日
【例】 G1[S]:
S → pA |qB
A →cAd|a
B →d B |c 识别输入串w= pccadd是否是G1[S]的句子
❖试探推导过程：
➢S pA pcAd pccAdd pccadd
➢试探3日
【例】 G2[S]:
S → Ap |Bq
A →a|cA
B →b|dB 识别输入串w= ccap是否是G2[S]的句子
❖试探推导过程：
➢S Ap cAp ccAp ccap
➢试探成功
✓FIRST（Ap）＝｛a，c｝ ✓FIRST（Bq）＝｛b，d｝
编译原理
2020年5月23日
2. FOLLOW集
对于文法G的非终结符的后继符号集称为 FOLLOW集，定义如下：
FOLLOW(A) ={a|S …Aa…，a ∈VT} 若S …A，则规定#∈FOLLOW(A) FOLLOW(A)：是所有句型中紧接A之后的终结符号或#
E→TE'
E'→+TE'|
E
T→FT'
T'→*FT'|
编译原理
2020年5月23日
自顶向下分析算法的基本思想为：
若xG+[SS]
则xL(G[S]) 否则xL(G[S])
存在主要问题: 回溯问题,左递归问题
主要方法：递归子程序法、 LL分析法
自底向上分析算法的基本思想为：
若xG+[S]S
则xL(G[S]) 否则xL(G[S])
存在主要问题:“可归约串”的识别问题
（2）若α=Xβ ，X∈VN，且有产生式X→b…，则 把b加入到FIRST(α)中；
例： FIRST(FT')={ ( , i } ??
编译原理
2020年5月23日
E→TE'
（13≤）i若≤nα；=X1X2 … Xn，其中Xi∈VN , 例：FIRST(FT')= FIRST(F)-{ε}={(,i}
FIRST()={a| a …，a∈VT 若 ，则规定∈FIRST()
FIRST(α)：从α可能推导出的所有开头终结符号或ε
【例】 S→aAb A→cd|c
FIRST(aAb) ={a} FIRST(cd) ={c} FIRST(c) ={c}
【例】
S→Aa A→a|
FIRST(a) ={a} FIRST() = {} FIRST(Aa) ={a}
FIRST(S) ={a} FIRST(A) ={c}
编译原理
FIRST(S) ={a} FIRST(A) ={a, }
2020年5月23日
构造FIRST集的算法
（1）若α=aβ ，且a∈VT ，则 a∈FIRST(α)； 例： FIRST(i)={ i } FIRST(+TE')={ + }
E→TE' E'→+TE'| T→FT' T'→*FT'| F→(E)|i
S.P 词法分析程序
符 号 表 管 理
语法分析程序
语义分析、生成中间代码 代码优化
错 误 处 理
生成目标程序 O.P
编译原理
2020年5月23日
知 识 结 构
编译原理
2020年5月23日
语法分析的任务
任务：根据文法规则，从源程序单词符号串中识别出语法 成分，并进行语法检查。
两大类分析方法：
自顶向下分析 自底向上分析
主要方法：算符优先分析法、 LR分析法
编译原理
2020年5月23日
5.1 自顶向下分析法
自顶向下分析的一般过程 从S出发采用最左推导，试图逐步推出输入串α,αL(G[S])?
S作为语法树的根，试图自上而下地为α构造一棵语法树 o 若叶结点从左向右排列恰好α，则表示α是文法的句子，而 这棵语法树就是句子α的语法结构 o 若构造不出语法树，则α不是文法的句子
F→(E)|i
编译原理
T+TE ' ，则+∈FOLLOW(T)
2020年5月23日
构造集合FOLLOW的算法
E→TE' E'→+TE'|
（1）若A为开始符号，则把“#”加入FOLLOW(A)中；T→FT'
#∈FOLLOW(E)
T'→*FT'|
F→(E)|i
（2）若B→A (≠)，则把FIRST()-{}加入FOLLOW(A)中；
ccAp ccap 这个文法的特点：
1、产生式的右部不全是由终结符开始
2、如果两个产生式有相同的左部，它们的 右部是由不同的终结符或非终结符开始
编 译 原 理3、文法中无空产生式2020年5月23日
1. FIRST集
对于文法G的所有非终结符的每个候选式，其终 结首符号集称为FIRST集，定义如下：
2020年5月23日
【例】 G[E] E→TE' E'→+TE'| T→FT' T'→*FT'| F→(E)|i
计算文法中非终结符的First集合
FIRST(F)={(,i} FIRST(T’)={*,ε} FIRST(T)=FIRST(F)-{ε}={(,i} FIRST(E’)={+,ε} FIRST(E)= FIRST(T)-{ε}={(,i}
E'→+TE'| T→FT' T'→*FT'|
①F将IRFSITR(SαT)(；X1)中的一切非ε的终结符加进 F→(E)|i ②终若结ε∈符F加IR进SFTI(RXS1)T,(则α将)；FIRST(X2)中的一切非ε的 ③中若的ε∈一F切IR非SεT的(X终1)结且符ε∈加F进IRFSITR(SXT2()α,则)；将FIRST(X3) ④则依将此ε类加推进，FI若RS对T(于α注一)意。切：1要≤顺i≤序n往,ε下∈做F，IR一S旦T(不X满i)，足条件，
编译原理
2020年5月23日
【例】 G3[S]: S → aA|d A →bAS|ε 识别输入串w= abd是否是G3[S]的句子
❖试探推导过程： ➢S aA abAS abS ➢试探成功
编译原理
ab这d 个文法的特点： 1、含有空产生式 2、非空产生式右部首符号集合两两 不相交 3、紧跟该非终结符右边可能出现的 终结符集合也不相交