编译原理：第四章1-2

1
第四章 语法分析和语法分析程序
?对象,单词流形式的源程序
?任务,根据语法规则，分析源程序的语法结
构，同时进行语法检查
?输出,语法树
?假定,先不考虑语义问题
?分析方法,自顶向下和自底向上
?以前最常用的两种方法：递归下降法和算符
优先分析法
2
两种方法的结合
?递归下降分析方法 ——自顶向下
– 根据文法中各语法变量递归定义的特点，用一组相
互递归的子程序来完成语法分析。
?算符优先分析方法 ——自底向上
– 利用各个算符之间的优先关系与结合规则来指导语
法分析，适合于分析算术表达式。
?优点：简单，便于手工实现；经常结合起来使
用。
?另两种流行方法：预测分析方法（自顶向下）
和 LR分析方法（自底向上），广泛用于语法
分析程序的自动生成工具。
3
本章内容
?自顶向下的语法分析
– 预处理：消除文法的左递归、消除回溯
– 递归下降分析法
– 预测分析法、非 LL(1)文法的改造
?自底向上的语法分析
– 简单优先
– 算符优先、优先函数
– LR分析法
4
4.1 自顶向下 的语法分析
? 自顶向下 的分析,对已给的输入串 w,试图自上而下地
建立一棵语法树 ;或者说,从 S出发,为 w构造一个最左
推导（可以一边输入，一边分析）,若成功,则
w?L(G),否则拒绝,
? 一般说来,在为 w寻求最左推导的每一步,都涉及使用
何产生式进行替换的问题,最简单的方法是,逐一 试探,
? 遗憾的是,逐一试探也不能完全解决问题,例如,在含
有 左递归 的文法中,就会出现不能终止的替换现象,
5
左递归 的文法示例
? 例,E?T|EAT; T?F|TMF; F?(E)|i; A?+|-; M?* | /
? 设 w=i+i*i,每个产生式从左至右尝试,从 E出发,
E?T?F?(E)
?i
?TMF?FMF?(E)MF
?iMF ?i*F
?i/F
?TMFMF ?…
?TMFMFMF..,
E?EAT?TAT?FAT?iAT?i+T?i+TMF?i+FMF
?i+iMF ? i+i*F?i +i*i
6
自顶向下 分析方法的特点
1,若 G有左递归,则分析不能正常进行,因此,自顶向下 分
析 必须先消除文法的左递归 ;
2,分析过程是反复进行试探的过程,因此,难免会出现大
量的 回溯,特别是当 w?L(G)时,只有在穷举完所有的
试探后才能拒绝 w,
由于回溯,就需将从出错点到迄今为止已做过的大量
工作废弃,显然会大大 降低分析的效率,特别是在语法
分析阶段还往往要进行同步的语义分析和处理,这些
工作也就白做了,因此,消除回溯 是 自顶向下 分析 的另
一目标,
3,当拒绝 w时,只能知道 w不是句子,不知出错的性质及
位置。
7
4.1.1 消除文法的左递归
? 设文法是已简化的,若文法含直接左递归式,
A?A? | ? (??V+),?不以 A打头，则类似正规
式求解方法,有 A? ?{?} (??*),{?} 表示中 { }的符号
串 ?可以出现 0次或多次。
? 引入新的非终结符 A’,令其产生 ?*,则有,
A? ?A’； A’? ?A’|? 消除直接左递归,
? 对文法,E?T|EAT; T?F|TMF; F?(E)|i; A?+|-;
M?* | /
可改写为,E?TE’； E’?ATE’|?； T?FT’
T’?MFT’|?； F?(E)|i； A?+|-； M? *|/
8
消除文法的左递归
? 一般地,设文法中全部 A-产生式为
A?A?1|A?2|…|A ?n| ?1|…| ?m,其中,?i不以 A打头,
则消除直接左递归后的产生式为
A??1A’|…| ?mA’； A’? ?1A’|…| ?nA’| ?
? 消除文法的 间接左递归,
– 将原文法进行 代入变换 后，再应用上述方法
– 例如,S ? Ab|c； A?Sa,可将其变换为 S ?Sab|c,再
使用上述方法,得 S ?cS’； S’ ?abS’ | ?
? 消除过程：找出具有左递归（包括间接左递归）的所
有非终结符，对相关的产生式进行代入变换，逐步转
变为直接左递归的产生式，最后统一进行消除。
9
消除文法左递归 的矩阵方法
? 设文法的非终结符为 X1,X2,…,X n,其中,Xi的产生式
可分为以 非终结 符 和 终结符 打头的两类,类似正规式
方法,将‘ |’改写为‘ +’,有
Xi=X1?1i+X2?2i+…+X n?ni+?i
其中,?i 是以终结 符打头的产生式之和,?ki (?ki?V+)
可以为 ?, 这样,文法 G可表示为
),,,(),,,(),,,(
21
21
22221
11211
2121 n
nnnn
n
n
nn
XXXXXX ????
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
? ?
?
????
?
?
??
或写成向量和矩阵形式, X=XA+B
10
矩阵求解
该方程有解, X=BA*。 而
则有, X=BZ; Z=I+AZ
其中 X的产生式以 终结符 打头，因此无直接左递归和
间接左递归；而 Z的产生式以 ?ki?V+打头,因此不含直
接左递归，又因 B以 终结符 打头,也不含间接左递归,
由此所得的文法含有无用符号和无用产生式,需化简
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
???????
nnn
n
ZZ
ZZ
ZAI
AAIAAAIA
?
???
?
?
?
1
111
32
*,,
**
令其中
??
??
11
消除 文法左递归 的例子
例 4.1 S?Sa|Ab|a； A?Sc
相应的矩阵为
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
2221
1211
2221
1211
2221
1211
2221
1211
*
),(),(
,
),(),(),(
ZZ
ZZ
b
ca
ZZ
ZZ
ZZ
ZZ
aAS
ZZ
ZZ
b
ca
Z
a
b
ca
ASAS
则令
展开矩阵,得
S =aZ11； A=aZ12
Z11=aZ11 + cZ21 + ?
Z12 = aZ12 + cZ22
Z21 = bZ11
Z22 = bZ12 + ?
12
消除 文法左递归 的例子（续）
写成产生式，有
S ?aZ11 A ?aZ12
Z11?aZ11 |cZ21|? Z12? aZ12 |cZ22
Z21 ? bZ11 Z22 ? ? | bZ12
文法中含有无用产生式,消除之,最后,有
S ?aZ11 Z11?aZ11 |cZ21|?
Z21 ?bZ11
? 将 A?Sc 代入 S?Sa|Ab|a可得,S?Sa|Scb|a
消除直接作递归，有 S?aS’ S’ ? aS’|cbS’| ? 更简
单
13
4.1.2 回溯的消除及 LL(1)文法
? 设 G=(VN,VT,P,S) 为一 CFG,w=a1a2…a n是 VT上的符
号串,现需判明 w是否是 L(G)中的句子,为此,从 S开始
进行最左推导,设经若干步推导后我们得到
niaaaw
VVAAwS
i
N
???
???
? 1,
)17.4(
1211
*
1
*
?且
??
由假设可知,到目前为止,w的前缀 w1已匹配,现在需对
A?进行推导，以匹配 w的剩余部分 aiai+1…a n,
14
回溯的消除
即若 P中产生式能满足下面条件,则 回溯可消除,
w?L(G)?选 A??j进行推导能完成匹配 ;
w?L(G)?选 ?j?或 ?k?进行推导都不能完成匹配
对于当前输入符号 ai,若只有一个 候选项 ?j使得从 ?j?出发
可以推导出一个以 ai打头的符号串，即
, 而对于其它的 ?k(k?j),?k?都推导不出以
ai打头的符号串,则产生式 A??j是唯一可行的推导。
?ij a*???
mA ???? ||| 21 ?
考虑 A的所有候选项,
15
消除 回溯 的条件
? 为导出 无回溯 语法 分析条件,我们定义候选式的 终结
首符集,FIRST(?)={a | ??* a?,a?VT,??V*}
并约定 ??*?时,??FIRST(?)
? 若对于 A-产生式的每个 候选式 ?i(i=1,2,…,m) 都推不出
?,且 FIRST(?i) 互不相交,则当正扫描的当前输入符号
为 ai?FIRST(?j)时,唯一可用于推导的产生式只能是
A? ?j,这样得到了一个无回溯的条件, FIRST(?i)
?FIRST(?j)=?
? 例如,文法 G1[S],S?AA； A?aAb | *,A-产生式有两
个候选式,且 FIRST(aAb)={a}； FIRST(*)={*},两集不
相交,设输入串为 aa*bb*#,其最左推导为
S#?AA #(a)?aAbA #(a)#?aaAbbA #(*)?aa*bbA #
(*) ?aa*bb* #
16
消除 回溯 的条件
? 若某个候选式 ?i ?*?,即 ??FIRST(?i),此时,为匹配当前
扫描的符号 a就可以有 两种选择,一是使用某 ?j,使 ?j推导
出以 a打头的符号串,另一种选择是让 A推导出 ?i,并让跟
随在 A后的符号串推导出以 a打头的符号串,
? 若这两种选择都可行,则回溯不可避免, 因此,若要消除
回溯,就必须要求当 ?i ?* ?时,跟在 A后的符号串的终结
首符集与 ?j的终结首符集不能同时含有 a。 为此,定义 紧
跟在 A后的所有终结符之集
FOLLOW(A)={a|S# ?* ?Aa?,a?VT?{#},?,??V*}
其中,当 A为一句型的尾符号时,#?FOLLOW(A),
17
消除 回溯 的条件
? 当某个 ?i ?*?时, 无回溯的另一个条件为, FOLLOW(A)与
其它 ?j的 FIRST集不相交,FOLLOW(A) ?FIRST(?j)=?。
? 例 S?aA|b； A?cAS|?； FIRST(cAS)={c}； FOLLOW(A)
=FIRST(S)?{#}={a,b,#} 两个集合不相交,故可进行无回
溯的自顶向下分析,设输入串 w=aca#,其推导过程如下,
S#?aA# 当前输入符 a属于 FIRST(aA),用 S?aA推导
?acAS# 当前输入符 c属于 FIRST(cAS),用 A?cAS推导
?acS# 当前输入符 a属于 FOLLOW(A),用 A??推导,
?acaA# 当前输入符 a属于 FIRST(aA),用 S?aA推导
?aca# 当前输入符 #属于 FOLLOW(A),用 A??推导,成功。
18
消除 回溯 的条件（续）
? 最后消除回溯的条件归纳为,对 G中每个产生式
中任何两个候选项 ?i,?j,均满足,
(1)FIRST(?i) ?FIRST(?j)= ? (i?j； 1?i,j?m)
(2)若 ?i ?* ?,则 FIRST(?j)?FOLLOW(A)=?
(j=1,2,…,m ； j?i)
? 满足上述条件的文法称为 LL(1)文法 。 LL表示自左向
右扫描输入字符串，并按最左推导来进行匹配； 1表
示只向前查看一个输入字符就可以确定要选用的产生
式。
? 无回溯的分析方法：递归下降法和预测分析法
mA ???? ||| 21 ?
19
4.1.3 递归下降分析法
? 递归下降分析法 (recursive descent method)的原
理是,对于文法的每个非终结符,根据其各候选式的结
构,为其建立一个递归的子程序 (函数 ),用于识别该非
终结符所表示的语法变量,
? 例如,产生式 E’?+TE’,相应的子程序 (函数 )为
expr_prime( ) {
if(match(PLUS)) {
advance( );
term( );
expr_prime( );
}
}
20
递归下降分析法
? 程序中,函数 match( )的功能是,以其实参与当前正扫描
的符号进行匹配,若成功则返回 1,否则返回 0;
? advance( )是读下一单词函数,将所读单词赋给 变量
lookahead;
? term( )函数是与非终结符 T相对应的子程序,
? 对于文法的每个非终结符,都建立子程序后,这组子程
序组成了所需的自顶向下语法分析程序,
? 注意,由于文法的递归性,子程序一定有 递归,因此,只能
使用允许递归的程序设计语言编写,
? 由于程序有递归,通常,上述方法也称为 递归子程序法
21
递归子程序法 示例
? 例 4.2 文法 G[Statements],
Statements? Expression;Statements | ?
Expression? Term Expression’
Expression’? +Term Expression’ | ?
Term? Factor Term’
Term’? *Factor Term’ | ?
Factor ? num_or_id | (Expression)
? 可以验证,G[Statements]满足 LL(1)文法条件,故可用递
归下降法分析,
? 递归下降分析程序代码见 P112程序 4-1
22
改进的文法及分析程序
? 其中,在文件 lex.h里,将分号、加号、乘号、左右括号、
输入结束符及运算对象分别命名为 SEMI,PLUS、
TIMES,LP,RP,EOI及 NUM_OR_ID,并指定了其内
部码 ;另外,还对外部变量 yytext,yyleng,yylineno进行了
说明,
? 程序 4-1的 缺点：频繁的递归调用降低了算法效率；缺
乏完善的语法检查和出错处理。
? 例 4.2 改写的文法 G’[Statements],
Statements? {Expression;} {}中的符号串可以出现 0次或多次
Expression? Term {+Term}
Term? Factor{*Factor}
Factor ? num_or_id | (Expression)
? 改写后的递归下降分析程序代码见 P114程序 4-2
23
4.1.4 预测分析法
? 预测分析法 的分析
器由一张 预测分析
表 (LL(1)分析表 ),
一个 控制程序 (表
驱动程序 )及一 分
析栈 组成,
? 输入是待分析的符
号串（ 单词流 ），
以 # 结尾。
控制程序
分析表 分
析
栈
a1 a2 … a i … a n #
输入
X Y
Z
#
24
预测分析表
? 分析表是一二维数组,M:VN?(VT?{#}) ?(P?{ERR}),
(目的：描述为完成非终结符与输入符号的匹配所应选
用的产生式 )，对于产生式 A??1|?2|…| ?m （ 假定 LL(1)
文法 ）, M[A,a]的值按下述规则确定,
(1)若 a?FIRST(?i),则置 M[A,a]=“A??i”;
(2)若 ??FIRST(?i)（即 ?i ?*? ）,a?FOLLOW(A),置M[A,a]=“A??
i”,
(3)除上述两种情况外,其它元素均填,ERR”,
? 分析表元素的含义,指明当前应用何产生式进行推导,
或指明输入串出现错误
25
一,分析器 的工作流程
# S a1 a2 … … a n #
2,设分析的某时刻,分析
格局如右，根据 Xm的不同
情况,分别作如下处理,
# X1 X2 …X m-1 Xm ai ai+1 … … a n #
(1) Xm?VT:若 Xm=ai,匹配,将 Xm出栈,输入指针 ++;否则，出错 ;
(2) Xm?VN:查表 M[Xm,ai],若 M[Xm,ai]=“ERR”,出错 ;若 M[Xm,ai]
=“Xm?Y1Y2…Y k”,将 Xm出栈,Y1Y2…Y k 逆序 入栈,得到格局
1,初始化,首先将 #及开始符 S
压入栈,各指针置初值，如右。
# X1 X2 …X m-1YkYk-1...Y1 ai ai+1 … … a n #
(3)若 Xm=ai=#,则表明输入串已完全得到匹配,分析成功,结束,
26
产生式 FIRST FOLLOW
1,E → TE’ {(,i} { ),#}
2,E’ → ATE’|ε {+,-}; {ε} { ),#}
3,T → FT’ {(,i} {+,-,),#}
4,T’ → MFT’ |ε {*,/}; {ε} {+,-,),#}
5,F → (E) | i { ( }; { i } {+,-,*,/,),#}
6,A → +|- { + }; { - } {(,i}
7,M → *|/ { * }; { / }
{(,i}
i + - * / ( ) #
E E?TE’ E?TE’
E’ E’?ATE’ E’?ATE’ E’?? E’??
T T?FT’ T? FT’
T’ T’?? T’?? T’?MFT’ T’?MFT’ T’?? T’??
F F? i F? (E)
A A? + A? -
M M? * M? /
文法, E?TE’;
E’?ATE’|?; T?FT’;
T’?MFT’|?; F?(E)|i;
A?+|-; M?*|/;
FIRST集与 FOLLOW
集如右表（ 计算方法
后面介绍 ）；
预测分析法 实例
其对应的预测分析表如下,
27
对 i+i*i进行预测分析的过程
步骤 分析栈 余留输入串 所用产生式
1,# E i + i * i # E → TE’
2,# E ’ T i + i * i # T → F T’
3,# E ’ T ’ F i + i * i # F → i
4,# E ’ T ’ i i + i * i #
5,# E ’ T ’ + i * i # T’ → ε
6,# E ’ + i * i # E’ → A T E ’
7,# E ’ T A + i * i # A → +
8,# E ’ T + + i * i #
9,# E ’ T i * i # T → F T’
10,# E ’ T ’ F i * i # F → i
11,# E ’ T ’ i i * i #
12,# E ’ T ’ * i # T’ → MF T’
13,# E ’ T ’ F M * i # M → *
14,# E ’ T ’ F * * i #
15,# E ’ T ’ F i # F → i
16,# E ’ T ’ i i #
17,# E ’ T ’ # T’ → ε
18,# E ’ # E’ → ε
19,# E # 成功
28
二、构造 FIRST集的算法
? 对于 G中的 单个文法符号 X?V,为求 FIRST(X),反复应
用如下规则,直到集合不再增大 (递归计算 ),
(1) (X?VT),FIRST(X)={X};
(2) (X?VN),if (X???P),??FIRST(X);
if (X?a??P ? a?VT),a?FIRST(X);
if (X?Y1Y2… Yk?P ? Y1?VN),
FIRST(Y1)-{?} ? FIRST(X);
if (for (1?j?i-1),Yj?VN ? ??FIRST(Yj)),
FIRST(Yi)-{?}?FIRST(X);
if (for(1? j? k),??FIRST(Yj)),
??FIRST(X);
? ???V*,?=X1X2… Xn,求 FIRST(?)类似于求
X?Y1Y2… Yk,略,
29
构造 FOLLOW集的算法
FOLLOW,反复使用如下规则,直到不再增大,
1,# (A??B??P),FIRST(?)-{?}?FOLLOW(B);
3,if ?FOLLOW(S);
2,if ( (A??B?P) ? ( A??B? ? ??FIRST(?) ) ),
{FOLLOW(A)?FOLLOW(B);}
对于 1.,由定义直接得到 ;
对于 2.,由于 A是有用符号,则必存在含 A的句型,
S ?* ?A? ? ??B?? ? ??Ba?? (a ?FIRST(?));
对于 3.,类似地,S ?* ?A? ? ??B[?]?,显然,
FIRST(?)?FOLLOW(A),并且,FIRST(?)?FOLLOW(B),
30
构造 FIRST集和 FOLLOW集的例子
? 以文法 文法, E?TE’; E’?ATE’|?; T?FT’;
T’?MFT’|?; F?(E)|i; A?+|-; M?*|/; 为例,计算相
应的 FIRST集和 FOLLOW集,
1.求所有 VN符的 FIRST集,利用 规则 (2),有
FIRST(M)={*,/},FIRST(A)={+,-},FIRST(F)={(,i};
继续利用 规则 (2),有
FIRST(T’)=FIRST(M)?{?}={*,/,?},
FIRST(T)=FIRST(F)={(,i},
FIRST(E’)=FIRST(A) ?{?}={+,-,?}
FIRST(E)=FIRST(T)={(,i}
31
构造 FIRST集和 FOLLOW集的例子 (续 )
2.求 FOLLOW集
(1)由 规则 (1),#?FOLLOW(E),再由包含 E
的产生式 F?(E),) ?FOLLOW(E),从
而,FOLLOW(E)={),#}
(2)由 规则 (3)及 (包含 E’的 )产生式 E?TE’
可知 FOLLOW(E)?FOLLOW(E’),即有
FOLLOW(E’)={),#}
(3)由 规则 (2)及 (包含 T的 )产生式 E’?ATE’
有 FIRST(E’)-{?}?FOLLOW(T);再由 规
则 (3)及 E?TE’和 E’?*?有
FOLLOW(E)?FOLLOW(T) 即
FOLLOW(T)={+,-}?{),#}={+,-,),#}
文法,
E?TE’;
E’?ATE’|?;
T?FT’;
T’?MFT’|?;
F?(E)|i;
A?+|-;
M?*|/;
32
求 FIRST,FOLLOW集例子 (续 )
(4)由 规则 (3)及 T?FT’有 FOLLOW(T)?FOLLOW(T’),
即 FOLLOW(T’)={+,-,),#}
(5)由 规则 (2)及 T’?MFT’,有 FIRST(T’)-{?}
?FOLLOW(F),再由 规则 (3)及 T?FT’和 T’?*?,
有 FOLLOW(T) ?FOLLOW(F),从而,
FOLLOW(F)={*,/}?{+,-,),#}={+,-,*,/,),#}
(6)由 规则 (2)及 E’?ATE’,有 FIRST(T)-{?}
?FOLLOW(A),即 FOLLOW(A)={(,i}。
(7)由 规则 (2)及 T’?MFT’,有 FIRST(F)-{?}
?FOLLOW(M),故有 FOLLOW(M)={(,i},
最终所得的 FIRST集和 FOLLOW集 结果如前。
文法,
E?TE’;
E’?ATE’|?;
T?FT’;
T’?MFT’|?;
F?(E)|i;
A?+|-;
M?*|/;
33
三,预测分析表 的构造
? 对已给的 LL(1)文法,在得到各文法符号的 FIRST集和
FOLLOW集之后,就可容易地构造出 预测分析表 (也称
LL(1)分析表 ),
? 在 A?VN所在行,a?VT所在列,M[A,a]的填写方法如下,
(1) if ( ?A???P and a?FIRST(?) ),M[A,a] =‘A??’;
(2) if (??*? (??FIRST(?)) and a?FOLLOW(A)),M[A,a]=‘A??’;
(3) Otherwise,M[A,a]=‘ERR’,
? 在实际的表存储结构中,矩阵中每个元素并非真正存储
的是 产生式,而是其 右部的逆序 (也可以是产生式 序
号 ),这样便于分析时使用,并节省了内存空间,
34
4.1.5 某些非 LL(1)文法的改造
? 对于 LL(1)文法而言,总能构造出相应的预测分析表,且
表中不含多重定义的元素；对于 非 LL(1)文法,尽管仍可
建立预测分析表,但表中必然会出现 多重定义 的 元素
? 例如,文法 G[S],S?abB； A?SC|BAA|?； B?AbA；
C?B|c
– FIRST(S)={a}; FIRST(B)={a,b}; FIRST(A)={a,b,?};
FIRST(C)={a,b,c}; FOLLOW(S)= {a,b,c,#};
FOLLOW(B)= FOLLOW(A)= FOLLOW(C)= {a,b,c,#},
– 由造表规则,有 M[A,a]={A?SC,A?BAA,A??},同理,
M[A,b]={A?BAA,A? ?},
? 非 LL(1)文法 所造之表中,必有冲突元素, 是否有冲突元
素也是判别一文法是否是 LL(1)文法 的方法之一,
35
非 LL(1)文法的改造 (续 )
? 对于某些 非 LL(1)文法,通过 消除左递归,反复 提取左
因子 等方法,有时可以将其改造成 LL(1)文法,
? 提取左因子, 当文法中含有形如 A???1|??2|…| ??m
的产生式时,可将其改写为, A??A’; A’??1|?2|…| ?m
? 若诸候选式 ?1,?2,…,?m 中的一部分仍含有左因子,则再
进行提取工作,如此等等,这样,就 可能 得到一个 LL(1)文
法,
? 例如,文法,E?E+T | T； T?(E) | a(E) | a；
经改造后可得文法,E?TE’； E’?+TE’| ?； （消除
左递归） T?aT’ | (E)； T’ ?(E) | ?,可以验证这是一
个 LL(1)文法,
36
非 LL(1)文法 的改造 (续 )
?应当指出,并非 所有的文法都能改造为 LL(1)文法,
?例如,文法 G[S],S?AU | BR； A?aAU | b；
B?aBR | b； U?c； R?d 文法中 S的两个候选
式 AU及 BR的 FIRST集相交,G是非 LL(1)的,
?为提取左因子,先将 S产生式中的 A,B用其右部替
换,得, S?aAUU|bU|aBRR|bR,经提取左因子,得
– S ?aS’|bS” S’?AUU|BRR S” ?U|R A?…
?显然它仍不是 LL(1)文法
37
关于 LL(1)的一些结论
?能由 LL(1)文法产生的语言称为 LL(1)语言,它们已
被证明具有许多重要特性,主要有,
(1) 任何 LL(1)文法都是 无二义性的 ;
(2) 左递归文法 是非 LL(1)的 ;
(3) 存在一种算法,它能 判定任意文法是否为 LL(1)的 ;
(4) 存在一种算法,它能 判定任意两个 LL(1)文法是否等价 ;
(5) CFL是否是 LL(1)语言是 不可判定 的 ;
(6) 非 LL(1)语言是 存在 的,
?LL(k)分析,若在分析过程中,每步向前扫描 k个符
号来确定选用的产生式,此分析方法称为是 LL(k)
分析, LL(k)分析（ K>1）极少用,故从略,