当前位置：文档之家 › 第五章 自顶向下语法分析

第五章 自顶向下语法分析

  • 格式：ppt
  • 大小：646.50 KB
  • 文档页数：49

下载文档原格式

  / 49

合集下载

ch5-自顶向下语法分析方法-v2

ch5-自顶向下语法分析方法-v2

26
4. 计算SELECT集
27
28
5.3 非LL(1)文法到LL(1)文法的等价变换
在确定的自顶向下分析中,要求对给定语言的文法必须 是LL(1)文法,然而不一定每个语言都有LL(1)文法。 如何对一个语言的非LL(1)文法变换为等价的LL(1)形式? 由LL(1)文法的定义知道,当文法中含有直接或间接左递归, 或含有左公共因子时,这样的文法肯定不是LL(1)文法。 因此，首先设法消除文法中的左递归与提取左公共因子 对文法进行等价变换。在某些情况下,使其变换为LL(1)文法。
语法分析就是识别由词法分析给出的单词符号序列是 否是给定文法的正确句子(程序). 语法分析常用的方法:
自顶向下分析
自底向上分析 自底向上分析分为: 算符优先分析 LR分析
2
第五章 自顶向下语法分析
自顶向下分析（面向目标的分析方法） 从文法的开始符号出发企图推导出与输入的单词串完全相 匹配的句子. 自顶向下分析方法分为: 确定的分析方法－对文法有一定的限制。 不确定的分析方法－回溯的分析方法，一种穷举的试 探方法。
18
例题分析： 求文法中符号与符号串的FIRST集。
G[S]: S->AB | bC A->b |ε B->aD |ε C->AD | b
D->aS | c
FIRST(S)=FIRST(A)∪FIRST(B)∪{ε} ∪{b}={b,a, ε} FIRST(A)={b} ∪{ε}={b, ε} FIRST(B)={ε} ∪{a}={a, ε} FIRST(C)={FIRST(A)- {ε}}∪FIRST(D) ∪FIRST(b)={b,a, c} FIRST(D)={a} ∪{c}={a, c}

第5章 自顶向下语法分析方法3

第5章 自顶向下语法分析方法3

③
结论 ： 在推导过程中完全可以根据向前看符号 是属于哪个产生式右部的开始符号集合而决定选 择相应的产生式进行推导，因此，分析过程是完 全确定的。
FIRST定义：设 G = (VT ,VN , S , P) 是2型文法， * FIRST(α) = {a|α aβ,a∈ VT,α,β ∈ V*} * 若α ε，则规定ε∈FIRST(α) 直观定义理解： FIRST(α)={a｜α *a … … ，a∈ＶT } FIRST(α)包含了α对应的串的所有可能的首终结 符号集(选择产生式的依据)
① 若XV,则FIRST(X)={X} ② 若XVN,且有产生式Xa…，则a∈FIRST(X);
若X也是一条产生式,则∈FIRST(X). ③ 若XY…是一个产生式且YVN,则把FIRST(Y)中的 所有非元素都加到FIRST(X)中; 若X Y1Y2…YK 是一个产生式,Y1,Y2,…,Y(k-1)都 是非终结符,而且,对于任何j,1≤j ≤k-1,FIRST(Yj)都 含有(即Y1..Y(k-1) * ),则把FIRST(Yj)中的所有 非元素与FIRST(Yk)都加到FIRST(X)中; 特别是,若所有的FIRST(Yj, j=1,2,…,K)均含有,则 把加到FIRST(X)中. (注意第3点）
③ A→αβ1|αβ2|…|αβn 变换为
语法分析的任务
语法分析是编译过程的核心部分。 2. 语法分析的作用：识别由词法分析输出的单词序列是否 符合该语言的文法（？）正确句子（程序）。 3. 分析方法 ① 自顶向下分析法(确定与不确定 ) 从推导的角度看，从识别符号出发，试图推导出与输入 符号串相同的符号串。一般来讲，推导是最左推导。 构造推导的关键问题: 在构造最左推导的过程中,面对当前读入的单词符号(向 前看符号)和当前被替换的非终结符两者,应该选择这个 非终结符的哪条候选式去替换它(推导)。 ② 自底向上分析法（算符优先、LR分析器）

第5章-自顶向下语法分析方法

第5章-自顶向下语法分析方法
第5章 自顶向下语法分析方法
语法分析的主要工作： 是识别由词法分析给出的单词序列是否是给定的
正确句子（程序）。
பைடு நூலகம்语法分析常用的方法： 自顶向下的语法分析和自底向上的语法分析两大
类。
自顶向下分析思想
自顶向下的方法： 从文法的开始符号（设为〈程序〉）开始进行分析，
逐步推导的往下构造语法树，使其树叶正好构造出所给 定的源程序串(输入串)。
例5.1若有文法G[S]：
S → pA S → qB
A → cAd A→a
若有输入串w = pccadd.
考察自顶向下的推导过程。
解：推导过程为：
S pA pcAd pccAdd pccadd 其相应的语法树见右图：
S pA
cAd c Ad
a
这个文法的特点：
[1]每个产生式的右部都由终结符号开始。 [2]如果两个产生有相同的左部，那么它们的右部由不同的终 结符开始。
FOLLOW(A)的元素。
因此当文法中含有形如： A→α和 A→β的产生式时，其中 A∈VN ,α,β∈V*,当α和β不同时推导出空串时，设α * ε，β\ * ε， 则当FIRST(α) ∩(FIRST(β)∪FOLLOW(A))=φ时，对于非终结符 A的替代仍可唯一地确定候选。
定义5.3：
定义选择符集合SELECT如下： 对于给出上下文无关文法的产生式
自顶向下方法的关键： 是在推导过程中确定的选择候选式的问题。
自顶向下的主要思想： 从开始符出发导出句型并一个符号一个符号地与
给定输入串 (终结符串)进行匹配。如果全部匹配成功， 则表示开始符号可推导出给定的终结符串。因此判定 给定终结符号串是正确句子。
自顶向下的缺点:

软件工程 编译原理 第五章 自顶向下的语法分析方法

软件工程 编译原理 第五章 自顶向下的语法分析方法

P→1P | 2P |… | mP |
（2）消除间接左递归
对于间接左递归的消除需先将间接左递归变为直接左 递归，然后再按a)消除直接左递归。
例：文法G为例： (1) A→aB (2) A→Bb (3) B→Ac (4) B→d 用产生式(1)、(2)的右部 代替产生式(3)中的非终 结符A得到左部为B的产 生式为： (1) B→aBc (2) BG的产生式为： (1) S→aSb (2) S→aS (3) S→ε 请提取文法中的左公因子
对产生式(1)、(2)提取左公因子后得： S→ aS(b|ε) S→ε 进一步变换为文法G′： S→aSA A→b A→ε S→ε
例2：若文法G的产生式为： (1) A→ad (2) A→Bc (3) B→aA (4) B→bB 请提取文法中的隐式左公因子。 对文法G2分别用(3)、(4)的右 部替换(2)中的B，可得： 提取产生式(1)、(2)的左 (1) A→ad 公共因子得： (2) A→aAc A→a(d|Ac) (3) A→bBc A→bBc (4) B→aA B→aA (5) B→bB B→bB
由上面所举例子可以说明以下问题：
① 不一定每个文法的左公共因子都能在有限的步骤内 替换成无左公共因子的文法，上面文法G4就是如此。 ② 一个文法提取了左公共因子后，只解决了相同左部 产生式右部的FIRST集不相交问题，当改写后的文法 不含空产生式，且无左递归时，则改写后的文法是 LL(1)文法，否则还需用LL(1)文法的判别方式进行判 断才能确定是否为LL(1)文法。
例:文法G(E):
E→TE E→+TE | T→FT T→*FT | F→(E) | i
每个非终结符有对应的子程序的定义， 首先在分析过程中，当需要从某个非终 结符出发进行展开(推导)时，就调用这 个非终结符对应的子程序。

第11课 第5章_自顶向下语法分析方法_思想

第11课 第5章_自顶向下语法分析方法_思想




FIRST(A)就是A开头的终结符， 直观的说就是A的开头字母 注意：First集合不仅仅针对非终 结符。 Nullable：可致空的
6
例子
S aA | d A bAS |
S aA abAS abS abd
?
7
Follow集
c | S A , 且c FIRST ( ), FOLLOW ( A) VT , V , A VN
3
确定分析的思想
S→pA|qB A→cAd|a B→dB|b 试分析串 pccadd

文法
S
pA pccadd
pcAd
pccAdd
4
例子
S→Ap,S →Bq, A →a,A →cA B →b,B →dB 分析串ccap有如下结论：

S
Ap
cAp
ccAp
ccap
5
开始符号集
FIRST ( A) c | A cB, c VT , A, B V
10
定理
一个CFG是LL(1)的充要条件是： 对每个非终结符A的不同产生式，满 足： Select A Select A
11
程序中错误的级别

lexical，譬如拼错了关键字 syntactic，譬如括号没有成对 semantic，譬如操作数与操作符不匹配 logical，譬如无限的递归调用
12
引用的统计数据


60％的程序在语法和语义上是正确的 存在错误的语句，有80％只有一个错误， 13％有两个 大部分错误都是极小的错误
13

ch5自顶向下语法分析_(张素琴)

ch5自顶向下语法分析_(张素琴)
如*, SELECT(A)=(First()-{}) FOLLOW(A).
LL(1)文法定义:
对于文法中每个非终结符的任意两个不同的产生式A， A，满足SELECT(A)SELECT(A)= 。
16
S→Qc|c 1.将非终结符排序为R、Q、S Q → Rb|b 2.R不存在左递归规则，将R代入Q： R → Sa|a
Q → Sab|ab|b
3. Q不存在左递归规则，将Q代入S
例子：对如下文法消除左递归：
S→ Sabc|abc|bc|c
4.消除直接左递归后，得文法：
17
S→abcS’| bcS’| cS’ S’→abcS’| ε Q → Rb|b R → Sa|a 5.化简文法
29
例1：对于文法G[E] E→TE’ E’ → +TE’|ε T →FT’ T’→*FT’| ε F→(E)|id 求每个非终结符的 FIRST和FOLLOW集
解：FIRST(F)={(,id} FIRST(T’)={*, ε} FIRST(T )= FIRST(F) = {(,id} FIRST(E’)={+, ε}
23
例:有文法G（S） S →BA First(S)=First(BA)={a,b,c} A →BS First(A)=First(BS)={a,b,c} A → d First(A)={d} First(A)={a,b,c,d} B →aA First(B)={a} B → bS First(B)={b} B→c First(B)={c} First(B)={a,b, c} •课堂练习例5.5(课本p79)，试写出其每个 非终结符和产生式右侧符号串的FIRST集
24
2)用关系图法求FIRST(X)算法p81 图5.4

第5部分自顶向下语法分析方法-

调用返回
编译原理
对 和Aβ不→同α，时A推→导β其出中空A时∈（V设N ,α不α, 推β ∈导V出N空*，，当β推α 导出空），则当 FIRST(α)∩(FIRST(β)∪FOLLOW(A))=Φ时， 对于非终结符A的替换仍可唯一地确定候选。
编译原理
定义：给定上下文无关文法的产生式A→α， A若∈α V*Nε，, α则∈SVEL*，ECT(A→α)=FIRST(α) 如果α *ε，则 SELECT(A→α)=FIRST(α)∪FOLLOW(A)
FOLLOW(S)= {#} FOLLOW(A)= {a,c,#} FOLLOW(B)= {#} FOLLOW(C)= {#} FOLLOW(D)= {#}
4.计算SELECT集
S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c
SELECT(S→AB)={a,b,ε,#} SELECT(S→bC)={b} SELECT(A→ε)={a,c,#,ε} SELECT(A→b)={b} SELECT(B→ε)={#,ε} SELECT(B→aD)={a} SELECT(C→AD)={a,b,c} SELECT(C→b)={b} SELECT(D→aS)={a} SELECT(D→c)={c}
• 3.若XY…是一个产生式且YVN,则把FIRST(Y)中 的所有非元素都加到FIRST(X)中;若X Y1Y2…YK 是一个产生式,Y1,Y2,…,Y(i-1)都是非终
结符,而且,对于任何j,1≤j ≤i-1,FIRST(Yj)都含 有元(素即都Y加1..到Y(Fi-I*1R) ST(X)),中则;把特F别IR是ST,(若Yj所)中有的的所有非 FIRST(Yj , j=1,2,…,K)均含有,则把加到 FRIST(X)中.

第5章 自顶向下语法分析方法-g

确定的自顶向下分析 确定的自顶向下分析方法对文法要求比较严格， 必须无二义性、且消除左递归和回溯。 典型的方法是递归下降分析方法和LL分析方法。
递归下降分析方法便于手工构造语法分析器。
LL分析法便于用语法分析器的自动构造工具，自 动构造语法分析器。
8
5.1 语法分析概述
（2）自底向上分析方法 语法分析从底部到顶部为输入的符号串建立分析树。 最常见的LR分析方法就是自底向上分析方法。而且 是确定的。
例：S Sa | b, 改为： S b | Sa ，若推导’baa’
S b (不行) S b S a S S b a S a
（不行）
33
3. 自上而下分析法的问题及解决

Q2：左递归文法将使自上而下分析陷入无限循环
2. 将左递归右递归（或迭代） （解决方法2）
如： 左递归文法 S Sa | b 生成语言 L = ba* 右递归文法： S bA A aA|ε
向
下 语 法 分
（消除左递归和回溯）
非确定的自顶向下语法分析
析
（带回溯）
14
构造最左推导的关键问题 在构造最左推导的过程中，面对当前读入的单 词符号a和当前被替换的非终极符A，应该选择A的 哪条候选式去替换它(推导)。 关键： 找出选择一个非终极符号的候选式的方法。
15
构造最右推导的关键问题 在构造最右推导的过程中，面对当前读入的单 词符号a，已分析过的符号串中是否已构成一个产 生式的右部，即句柄（可归约）。如果已构成句 柄，即用相应的产生式左部(非终结符号)去替换它 (归约)。
18
5.2.1 带回溯的自顶向下语法分析
例如： 文法G[S] S →aAb A →** | *
S b * a A * (c) 试探成功

第5章自顶向下语法分析方法


程序设计语言的语法结构是用上下文无 关文法描述的，因此，语法分析器的实 现原理就是按所给定的文法G，识别输入 符号串α是否为一个句子（即α∈L(G) 成立吗？），同时检查和处理语法错误。 语法分析的关键是句型识别问题。给定 一串单词（即文法的终结符），怎样知 道它是不是该文法产生的一个句子呢？ 可以利用推导，或者利用语法树来进行 判断。一般来说，语法分析的过程就是 为一个句子建立语法树的过程。
(S,a)
(A,c)
S→aAB
aca#
3 acAB
4 acε B 5 aca
A→cA
A→ ε B→a
aca#
aca# aca#
(A,a)
(B,a) 推导成功
以上最左推导所建立输入串aca的语法树如图所 示。
S
a c A B A ε a
讨论
考查以上推导，在第3步到第4步的推导中， 即acABacB时，因为当前要替换的最左非终结 符为A，面临输入符为a，而关于A的产生式右部 的首终结符集都不包含a，但有ε，因此对于a 的匹配自然认为只能依赖于在可能的推导过程 中A的后面的符号，所以这时选用产生式A→ε 往下推导，而当前A后面的符号为B，B的产生式 右部的首终结符集包含了a，所以可匹配。由此 可以看出，当前输入符a与A后面的非终结符B匹 配。
文法的特点
文法G2有以下两个特点：
(1)每个产生式的右部都由终结符号开始；
(2)如果两个产生式有相同的左部，那么它们 的右部由不同的终结符开始。 对于这样的文法显然在推导过程中完全 可以根据当前要替换的非终结符和输入符 号决定选择哪个产生式往下推导，因此分 析过程是唯一确定的。
示例二
【例4.3】若有文法G3[S]为： S→Aa S→Bb A→c A→dA B→e B→fB

自顶向下语法分析方法


7
PL/0语言文法的EBNF表示
PL/0语言文法的EBNF表示 <程序>∷=<分程序>. <分程序>∷=[<常量说明部分>][<变量说明部分>][<过程说明部分>]<语句> <常量说明部分>∷=CONST<常量定义部分>{，<常量定义>}； <无符号整数>∷=<数字>{<数字>} <变量说明部分>∷=VAR<标识符>{，<标识符>}； <标识符>∷=<字母>{<字母>|<数字>} <过程说明部分>∷=<过程首部><分程序>{；<过程说明部分>}； <过程首部>∷=PROCEDURE <标识符>； <语句>∷=<赋值语句>|<条件语句>|<当型循环语句>|<过程调用语句>| <读语句>|<写语句>|<复合语句>|<空> <赋值语句>∷=<标识符>:=<表达式> <复合语句>∷=BEGIN <语句>{；<语句>} END <条件>∷=<表达式><关系运算符><表达式>|ODD<表达式>
例如对文法G3[S]： S→aAS|b A→bA| SELECT(S→aAS)={a} SELECT(S→b)={b} SELECT(A→bA)={b} SELECT(A→)={a,b}
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

编译原理
2015年4月25日
【例】 G3[S]: S → aA|d A →bAS|ε 识别输入串w= abd是否是G3[S]的句子 试探推导过程： S aA abAS abS 试探成功 abd 这个文法的特点： 1、含有空产生式
2、非空产生式右部首符号集合两两 不相交
3、紧跟该非终结符右边可能出现的 终结符集合也不相交
T→FT'
T'→*FT'| F→(E)|i
编译原理
2015年4月25日
构造集合FOLLOW的算法
E→TE' E'→+TE'|
T→FT' （1）若A为开始符号，则把‚#‖加入FOLLOW(A)中； T'→*FT'| #∈FOLLOW(E)
（2）若B→A (≠)，则把FIRST()-{}加入FOLLOW(A)中； 由F→(E)可知， )∈FOLLOW(E)
FOLLOW(T)=｛＋，)，＃｝
FOLLOW(T′)=｛＋,)，#}
编译原理
FOLLOW(F)= ｛*,＋，),#} 2015年4月25日
【例】 G[E]：E→TE' E'→+TE'| T'→*FT'| F→(E)|i
E’ –> +TE’ |
T→FT'
FIRST(+TE')=｛+｝ FOLLOW(E')=｛)，＃｝ T’ –> *FT’ | FIRST(*FT')=｛*｝ FOLLOW(T')=｛+,)，＃｝ F –> (E) | i FIRST((E))=｛(｝ FIRST(i)=｛i｝ 所以G[E]是LL（1）的
自底向上分析
编译原理
2015年4月25日
自顶向下分析算法的基本思想为： +S 若x G[S] 则xL(G[S]) 否则xL(G[S])
存在主要问题: 回溯问题,左递归问题 主要方法：递归子程序法、 LL分析法 自底向上分析算法的基本思想为： +S 若xG[S] 则xL(G[S]) 否则xL(G[S])
a …，a∈VT
，则规定∈FIRST() 【例】 S→Aa A→a|
FIRST(α)：从α可能推导出的所有开头终结符号或ε
FIRST(aAb) ={a} FIRST(cd) ={c} FIRST(c) ={c} FIRST(a) ={a} FIRST() = {} FIRST(Aa) ={a}
编译原理
2015年4月25日
2. FOLLOW集
对于文法 G 的非终结符的后继符号集称为 FOLLOW集，定义如下：
FOLLOW(A) ={a|S
若S
…Aa…，a ∈VT}
…A，则规定#∈FOLLOW(A)
FOLLOW(A)：是所有句型中紧接A之后的终结符号或# E→TE' E'→+TE'| E T+TE ' ，则+∈FOLLOW(T)
编译原理
2015年4月25日
注意：要顺序往下做，一旦不满足条件， 过程就要中断进行
【例】 G2[S]: S → Ap |Bq A →a|cA B →b|dB 识别输入串w= ccap是否是G2[S]的句子 试探推导过程： S Ap cAp ccAp ccap 试探成功
FIRST（Ap）＝｛a，c｝
2015年4月25日
自顶向下分析存在的主要问题
1.回溯问题
什么是回溯（backtracking）?
分析工作要部分地或全部地退回去重做叫回溯
造成回溯的条件：
文法中，对于某个非终结符号的规则其右部有 多个选择，并根据所面临的输入符号不能准确的确 定所要选择时，就可能出现回溯。
回溯带来的问题： 严重的低效率：语法分析要重做、语义处理工作要推倒重来
F→(E)|i
（3）若B→A 或B→A，且
，
则把FOLLOW(B)加入FOLLOW(A) 中。 由E→TE'，应把FOLLOW(E)加入∈FOLLOW(E') 由E ' →+ TE ' 且E ' ε，应把FOLLOW(E ')加入FOLLOW(T) 注：FOLLOW集合中不含有ε
编译原理
编译原理
2015年4月25日
5.2 LL(1)文法的判别
要构造确定的自顶向下分析程序要求描述文法必 须是LL(1)文法。
LL的含义
－自左向右扫描分析输入符号串
－从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号，便能唯一确定当前应选择的规则
LL(k):向前看k个输入符号，才能唯一确定当前应选择的规则
编译原理
2015年4月25日
自顶向下分析面临的问题
• 问题1：回溯
•例1：设有文法 (1) S -> xAy (2) A -> **|* 现有输入串：x*y 其分析过程如下：
x * S A * * y
输入符号串：
x*y
失败，需要退回，重新选取A的侯选式
产生的原因？
编译原理
这时使得分析器的动作不稳定
2015年4月25日
【例】 G[E] 求FOLLOW集合
E→TE'
E'→+TE'|
FOLLOW(E)={#,)} T→FT' ∵E是开始符号∴#∈FOLLOW(E) 又F →(E) ∴ )∈FOLLOW(E) T'→*FT'| FOLLOW(E’)={#,)} ∵E → TE’ ∴FOLLOW(E)加入 FOLLOW(E’) F→(E)|i FOLLOW(T)={+,),#} ∵E’ → +TE’ ∴FIRST(E’)-{ε}加入FOLLOW(T) FIRST(F)={(,i} 又E’ε， ∴ FOLLOW(E’)加入FOLLOW(T) FIRST(T’)={*,ε} FOLLOW(T’)= FOLLOW(T)= {+,),#} ∵T → FT’ ∴ FOLLOW(T)加入FOLLOW(T’) FIRST(T) ={(,i} FOLLOW(F)={*,+,),#} FIRST(E’)={+,ε} ∵T → FT’ ∴ FOLLOW(F)=FIRST（T’）-{ε} FIRST(E)={(,i} 又T’ε ∴ FOLLOW(T)加入FOLLOW(F)
FIRST(S) ={a} FIRST(A) ={c}
编译原理
FIRST(S) ={a} FIRST(A) ={a, }
2015年4月25日
E→TE'
构造FIRST集的算法 （1）若α=aβ ，且a∈VT ，则 a∈FIRST(α)； 例： FIRST(i)={ i } FIRST(+TE')={ + } E'→+TE'| T→FT' T'→*FT'| F→(E)|i
编译原理
2015年4月25日
LL(1)文法的判别条件 * ε ，则 SELECT(Aα )=First(α ) • 若α => * • 若α =>ε ，则 SELECT(Aα )=(First(α )-{ε })∪Follow(A)
一个文法是LL(1)的充要条件 ： 对于每个形如Ａ α β 的产生式，满足 Select(Ａα ) ∩ Select(Ａβ ) = 其中： α 、β 不能同时推出ε
存在主要问题:―可归约串‛的识别问题
主要方法：算符优先分析法、 LR分析法
编译原理
2015年4月25日
5.1
自顶向下分析法
自顶向下分析的一般过程
从S出发采用最左推导，试图逐步推出输入串α,αL(G[S])?
S作为语法树的根，试图自上而下地为α构造一棵语法树 o 若叶结点从左向右排列恰好α，则表示α是文法的句子， 而这棵语法树就是句子α的语法结构 o 若构造不出语法树，则α不是文法的句子
FIRST（Bq）＝｛b，d｝
编译原理
2015年4月25日
计算文法中非终结符的First集合 【例】 G[E]
E→TE'
E'→+TE'|
T→FT'
T'→*FT'| F→(E)|i
FIRST(F)={(,i} FIRST(T’)={*,ε} FIRST(T)=FIRST(F)-{ε}={(,i} FIRST(E’)={+,ε} FIRST(E)= FIRST(T)-{ε}={(,i}
编译原理
2015年4月25日
迷 宫 求 解
编译原理
2015年4月25日
消除回溯的途径： 改写文法
对具有多个右部的规则反复提取左因子
【例】对下述两个产生式，提取公共左因子改造文法。 <if语句>→if E then S1 else S2 <if语句>→ if E then S1 <if语句>→if E then S1 U U→ else S2 |ε
FIRST(F)={(,i} 【例】 G[E]： FIRST(T’)={*,ε} E→TE' FIRST(T) ={(,i} E'→+TE'| FIRST(E’)={+,ε} T→FT' FIRST(E)={(,i} T'→*FT'| F→(E)|i FOLLOW(E)=｛),＃｝ 判别该文法是否为LL(1)文法？ FOLLOW(E′)=｛)，＃｝
1、产生式的右部不全是由终结符开始
2、如果两个产生式有相同的左部，它们的 右部是由不同的终结符或非终2015年4月25日
1. FIRST集 对于文法G的所有非终结符的每个候选式 ，其终 结首符号集称为FIRST集，定义如下： FIRST()={a| 若 【例】 S→aAb A→cd|c