当前位置：文档之家 › 编译原理：第四章 语法分析-自上而下分析

编译原理：第四章 语法分析-自上而下分析

  • 格式：ppt
  • 大小：1.09 MB
  • 文档页数：100

下载文档原格式

  / 100

合集下载

北方工业大学编译原理第4章习题

北方工业大学编译原理第4章习题
procedure T; begin if sym=ˊ(ˊor sym=ˊaˊ or sym=ˊbˊ or sym=ˊ∧ˊ then begin F; T end else error end;
（4）构造它的递归下降分析程序。
procedure T ; begin
if sym= ˊ(ˊ or sym= ˊaˊ or sym= ˊbˊ or sym= ˊ∧ˊ then T else if sym= ˊ*ˊ then error end;
（3）该文法不含左递归，而且每一个 非终结符的各个产生式的候选首符集两 两不相交。
FIRST(A)= {a}
FOLLOW(A)={d, #}
FIRST (A) = { ε, a} FOLLOW(A)={d, #}
FIRST(B) = {d} FOLLOW(B )={e}
FIRST(B) = {ε ,b} 法G ’
(S): S → a∣∧∣(T) T → ST ’ T’ → ,ST’ | ε
其中：过程advance把输入串指示器IP调至指向下一个输入 符号；sym是指IP当前所指的那个输入符号；error为出错诊 断处理程序。
（2）经改写后的文法是否是LL(1)的？给出它的预测分析表。
else error end else error end;
4.2 试消除下面文法G[A] 中的左递归，并提取公共左因子， 判断改写后的文法是否为LL(1)文法?
A→aABe∣a
B→Bb∣d
解: （1）首先消除左递归
A→aABe∣a B →dB B →bB | ε （2）提取公共左因子 A → aA A → ABe | ε B → dB B →bB | ε
证明：对于具有形如A|的产生式有： A → ABe | ε B →bB | ε

编译原理04自上而下语法分析PPT课件

编译原理04自上而下语法分析PPT课件
5
❖ 例4.1：假定有文法(4.1) S→xAy A→**|*
分析输入串x*y（记为α）。
S
S
S
x Ay
x Ay x A y
***来自(a)(b)(c)
6
❖ 由上例看到，自上而下分析法存在许多困难和缺点
文法的左递归性P+ Pα使分析陷入无限循环 回溯的不确定性，要求我们将已经完成工作推倒重来 虚假匹配问题 难于知道出错位置 效率低，代价高，实践价值不大
END
③ 化简上述文法
11
例4.3：考虑文法：SQc|c
Q Rb|b
R Sa|a
消除左递归。
解：将终结符排序为R、Q、S。对于R不存在直接左递归。把R带入 到Q中有关的候选式： Q Sab|ab|b
现在Q同样不含直接左递归，把它带入S的有关候选式：
S Sabc|abc|bc|c 经消除S的直接左递归后我们们得到整个文法
❖ 下图表明了语法分析器在编译程序中的地位
源程序
词法分析器
单词符号 取下一
语法分析器
语法 分析树
单词符号
后续部分
符号表
❖ 按照语法分析树的建立方法，我们可以粗略地把语法分析方 法分为两类：一类是自上而下分析法，另一类为自下而上分 析法
3
例：自顶向下构造最左推导（aabbaa) SaASa A SbA SS ba
执行任务。这个候选就是那个终结首符集含a 的
14
❖ 如何把一个文法改造成任何终结首符集的所有候选首符集两 两不相交呢？其办法是提取公共左因子
❖ 假定关于A 的规则是 A1| 2| … |n| 1| 2|… |m （其中每个不以开头）
那末，可以把这些规则改写成： A A’| 1| 2|… |m A’ 1 | 2 | …| n

编译原理第4章 语法分析——自上而下分析

编译原理第4章 语法分析——自上而下分析

17
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。
x*y
S
IP x A y **
18
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。
x*y
S
IP x A y **
19
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
(4.3)
虽没有直接左递归，但S、Q、R都是左递归的
SQcRbcSabc
一个文法消除左递归的条件
丌含以为右部的产生式
丌含回路
PP
30
例 文法G(S): S→Qc|c Q→Rb|b R→Sa|a
(4.3)
虽没有直接左递归，但S、Q、R都是左递归的
SQcRbcSabc
Q
Q
ⅹ
S
R
S→Qc|c Q→Rb|b R→Sa|a
35
例 考虑文法G(S)
S→Qc|c Q→Rb|b R→Sa|a
消除S的直接左递归后： S→abcS | bcS | cS S→abcS | Q→Sab |ab | b R→Sa|a
关于Q和R的觃则已是多余的，化简为：
S→abcS | bcS | cS
S→abcS |
(4.4)
36
注意，由于对非终结符排序的丌同，最 后所得的文法在形式上可能丌一样。但 丌难证明，它们都是等价的。
分析输入串x*y(记为)。
x*y
S
IP
15
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。

第四章 编译原理语法分析--自上而下

第四章 编译原理语法分析--自上而下
13
消除左递归 (P69.)

（1）直接左递归：文法存在产生式 A→Aα。 （2）间接左递归：文法不存在产生式 A→Aα， 但存在推导 A + Aα。
消除直接左递归的方法：引入新的非终结符号A‘，将 关于A的如下产生式 A→Aα|β (α非ε且β不以A打头) 替换为 A →βA‘ A‘ →αA‘｜ε 注意：不要掉了 A‘ →ε
4
自上而下分析法的思想(P66.)

从文法的开始符号出发，逐步向下推导，不断替换和展开非 终结符，去匹配输入符号串(终结符号串、句子)，即寻找输入 串的最左推导，推出句子，（---自上而下的实质） 并按与最左推导相对应的顺序，从文法的开始符号(根结）出 发，自上而下从左到右地建立输入串的语法分析树。---其末 端节点正好与输入符号串相同
3

4.2 自上而下分析法面临的问题

. 本小节首先通过例子P67：

说明自上而下分析的思想 认识自上而下分析时所遇到的主要困难



自上而下分析的主要困难是P66-68 : 文法的左递归性，可能使分析陷入无限循环 回溯的不确定性，要求将已完成的工作推倒重来 为解决这些问题，使得自上而下分析是确定的，考 虑要消除文法左递归和避免回溯。 最后构造确定的有效的自上而下分析器：递归下降 分析器
2
4.1 语法分析器的功能(P66.)

语法分析是编译程序的核心部分。
语法分析是在词法分析识别出单词符号的基础上， 分析并判定（即识别）一串单词符号(称为输入串) 的语法结构是否符合语法规则，是否是文法的一个 句子。
分析判定的方法：


建立输入串α的从文法开始符号S出发的推导 S α1 … αn α 即建立以开始符号S为根的与输入串α相匹配(即α 中的各个符号为叶结点)的语法树

编译原理张晶版 第四章 自上而下语法分析

编译原理张晶版 第四章 自上而下语法分析

1、消除左递归
•1) 什么是左递归 —左递归：文法存在产生式 P + Pa —直接左递归： P —间接左递归：P Pa Aa ,A + Pb
•2）消除左递归
—消除直接左递归 —消除间接左递归
第四章 自上而下语法分析（23）
第二节 自上而下分析法的一般问题 三、不带回溯的自上而下分析算法
2、消除直接左递归
第四章 自上而下语法分析（44）
第三节 预测分析程序与LL(1)文法 二、求串a的终结首符集和非终结符A的随符集
例：对如下文法G（已加上编号）
1. E
4. T 7. F
TE’
FT’ i
2. E’
5. T’ 8. F
+TE’
*FT’ (E)
3.E’
6.T’
e
e
求各非终结符号的终结首符集和随符集
第四章 自上而下语法分析（45）
第四章 自上而下语法分析（47）
第三节 预测分析程序与LL(1)文法 二、求串a的终结首符集和非终结符A的随符集
例：对如下文法G（已加上编号）
1. E
4. T 7. F
TE’
FT’ i
2. E’
5. T’ 8. F
+TBiblioteka ’*FT’ (E)3.E’
6.T’
e
e
求各非终结符号的终结首符集和随符集
第四章 自上而下语法分析（48）
第四章 自上而下语法分析（40）
第三节 预测分析程序与LL(1)文法 三、构造预测分析表
1. 基本思想 1)若A a是一个产生式，a ∈ First(a),那么当A 是栈顶符号且将读入a时，选择a取代A匹配成功的 希望最大，故,M[A,a]元素为A a 2)若A a而a=e,或a + e；当A是栈顶符号且将读 入a时，若a ∈ Follow(A),则栈顶的A应被e匹配； 此时读头不前进，让A的随符与读头下的符号进行 匹配，这样输入串匹配成功的可能最大，故M[A,a] 元素为A a(这里a=e或a + e)

编译原理第4章语法分析自上而下

编译原理第4章语法分析自上而下
Yn；当Y1 Y2 … Yi-1都ε时，(其中1≤i≤n)，则FIRST(Y1){ε}、FIRST(Y2) -{ε} 、…、FIRST(Yi-1)- {ε}，FIRST(Yi) 都包含在FIRST(X)中
(e) 当(d)中所有Yi * ε,(i=1,2,…n)，则 FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{ε}
一 . 自上而下语法分析方法
给定文法G和源程序串$。从G的开始符 号S出发，通过反复使用产生式对句型中的 非终结符进行替换(推导)，逐步推导出$ 。
是一种产生的方法，面向目标的方法。 分析的主旨是选择产生式的合适的侯选 式进行推导，逐步使推导结果与$匹配。
Ch4 语法分析 4.1 语法分析程序综述 4.1.2 语法分析的方法
计算Select集：
B ε | aD C AD | b
每个产生式的Select集合计算为:D aS | c
Select(SAB)= (first (AB) -{ε}) ∪Follow(S)={b,a,#}
Select(S bC)= first (bC)={b}
因为A B
Select(Aε)=(first (ε) -{}) ∪Follow (A)={c,a,#}
A ε | b B ε | aD C AD | b D aS | c
first(C)={first(A)-{}} ∪first(D) ∪first(b)={a,b, c}
first(D)={a} ∪{c}={a,c}
➢求出每个文法符号的FIRST集合后也就不难求出一个符号 串的FIRST集合
✓若符号串α∈V*，α=X1 X2 … Xn,当X1不能
∪{ε}
ε*,则置 ∈

编译原理完整课件_第4章 语法分析-自上而下分析


2022/3/20
中南大学软件学院 陈志刚
6
第四章 语法分析-自上而下分析
4.2 自上而下分析面临的问题
➢ 顾名思义，自上而下就是从文法的开始符号出 发，向下推导，推出句子。 • 带回溯的分析方法 • 不带回溯的递归子程序（递归下降）分析方 法
➢ 自上而下分析的主旨： 对任意输入串，试图用一切可能的办法，从文 法开始符号（根结）出发，自上而下地为输入 串建立一棵语法树。或者说，为输入串寻找一 个最左推导。
设 ，有P→Pα|β，若α≠>ε，β不以P开头 （否则不可能消除左递归）。
则改写为：
可消除左递归。
2022/3/20
中南大学软件学院 陈志刚
12
第四章 语法分析-自上而下分析
一般地，若 αi≠ε，βj不以P开头， 则可改写为：
从而消除直接左递归。 ■ 例：S→Sabc|Sab|ab ■ 消除直接左递归得：
2022/3/20
中南大学软件学院 陈志刚
13
2、完全消除左递归 分析
第四章 语法分析-自上而下分析
虽不含直接左递归，但
所以含有左递归。
■ 如果文法G不含回路（ ），也不含ε产生式，
则下列算法可消除左递归（完全）
①把G的非终结符按任意顺序排列成P1,…,Pn
②for i:=1 to n do
begin for j:=1 to i-1 do
➢ 关键：对一个文法，当给你一串（终结）符号 时，怎样知道它是不是该文法的一个句子呢？ 这就要判断，看是否能从文法的开始符号出发 推导出这个字符串。或者，从概念上讲，就是 要建立一棵与输入串相匹配的语法分析树。
2022/3/20
中南大学软件学院 陈志刚

编译原理自上而下语法分析


编译原理
基本架构(1)

变量： sym：当前符号 函数：advance( )：读输入串下一符号 对于每个非终结符号U→α 1|α 2|…|α n处理的方法如下： P(U) {
if sym ∈FIRST(α1 )then P(α1) //处理α1的程序部分 else if sym ∈FIRST(α2 )then P(α2) //处理α2的程序部分 … else if sym ∈FIRST(αn )then P(αn) else if sym ∈FOLLOW(U)then return //处理空产生式情况 else error }
编译原理
间接左递归举例
S→Qc|c Q→Rb|b R→Sa|a 以上文法不含直接左递归，但S，Q，R 都是左递归的，因为： S=>Qc =>Rbc =>Sabc Q =>Rb =>Sab =>Qabc R =>Sa =>Qca =>Rbca
编译原理
消除文法的左递归
前提：如果一个文法不含回路（形如P⇒+ P 的推导），也不含以ε 为右部的产生式， 那么可以通过执行消除文法左递归的算 法消除文法的一切左递归（改写后的文 法可能含有以ε 为右部的产生式）。
FIRST(u)包含了u对应的字的所有可能的首终结符号。 FOLLOW(U)表示了句型中可能紧跟再U后面的终结符号。
编译原理
FIRST(α) 构造算法
对于X∈(VN∪VT）,FIRST(X)
的构造 1：若XVT，则FIRST(X)={X} 2：若XVN，且有产生式X→a…, a VT ，则a FIRST(X)；如果X→ ，那么 FIRST(X)。 3：若有产生式X→ Y…,Y VN ,则FIRST(Y)\ {} ⊏ FIRST(X); 如果有产生式X→Y1Y2…YK,其中Y1，Y2，Yi－1 VN且Y1Y2…Yi－1 => * , 则FIRST(Yi) \ {} ⊏ FIRST(X)；若Y1Y2…YK => * ，则 FIRST(X)。

编译原理-自上而下的语法分析


高效性
由于从文法的最顶端开始分析， 一旦发现不匹配，就可以立即终 止当前分支的搜索，避免不必要 的计算，提高了编译器的效率。
易于处理左递归文
法
自上而下的分析方法可以很方便 地处理含有左递归的文法，而左 递归是许多实际编程语言的重要 特征。
局限性
无法处理左边界问题
自上而下的分析方法在处理某些含有左边界的文法时可能 会遇到问题，因为这种方法会优先匹配最左边的符号，而 左边界问题需要从右往左匹配符号。
案例三
在编译器优化中，自上而下的语法分析被用 于识别和修改源代码中的冗余和低效的语法 成分。例如，在C编译器的实现中，自上而 下的语法分析可以用于优化循环结构，减少 不必要的循环次数，提高程序的执行效率。
自上而下的语法分析还可以用于代码生成和 代码生成器的实现。通过识别和解析源代码 中的语法成分，可以生成更高效、更安全的 机器代码或字节码，提高程序的执行效率和
安全性。
THANKS
感谢观看
详细描述：递归下降分析算法易于理解，每个产生式规 则对应一个函数，函数的实现相对简单明了。
详细描述：对于每个产生式规则，需要编写相应的递归 函数，可能会导致代码冗余。
移入-规约分析算法
总结词
基于栈的算法
详细描述
移入-规约分析算法是一种自上而下的语法分 析算法，它将目标语句从左到右依次读入， 并根据文法的产生式规则进行移入或规约操 作，直到找到目标语句的语法结构。
词法分析
词法分析是编译过程的第一步，也称为扫描或词法扫描。它的任务是从左 到右读取源代码，将其分解成一个个的记号或符号。
词法分析器通常使用正则表达式或有限自动机来识别和生成记号，这些记 号可以是关键字、标识符、运算符、标点符号等。

编译原理 第4章 语法分析—自顶向下分析


例 S::=aABbcd|ε，A::=ASd|ε，B::=SAh|eC|ε，
C::=Sf|Cg|ε，求此文法的每一个非终结符号的
FOLLOW集。
解：FOLLOW(S)={#}∪FIRST(d) ∪(FIRST(Ah)-{ε}) ∪FIRST(f)
={#}∪{d}∪{a,d,h}∪{f} = {a,d,h,f,#}
4)若对于一切1≤i≤n，ε∈FIRST(Xi)，则将ε符号加 进FIRST(α)。
例4-1(P62) 有文法： E→TE′ E′→+TE′ E′→ε T→FT′ T′→*FT′ T′→ε F→(E)|i 求文法中非 终结符号以及各 产生式右部符号 串的FIRST集。
解：该文法的非终结符号有E、E′、 T、T′和F。 FIRST(E)=FIRST(TE′) =FIRST(FT′E′)={ ( ，i } FIRST(+TE′)={ + } FIRST(ε)={ε} FIRST(E′)=FIRST(+TE′) ∪FIRST(ε)={+ ，ε} FIRST(T)=FIRST(FT′)={ ( ，i } FIRST(*FT′)={ * } FIRST(T′)=FIRST(*FT′) ∪FIRST(ε)={* ，ε} FIRST((E))={ ( } FIRST(i)={ i } FIRST(F) =FIRST((E)) ∪FIRST(i)={( ，i}
分析法算符优先分析法简单优先分析法优先分析法自底向上带回溯递归下降分析法分析法不带回溯自顶向下语法分析lr回溯示例41p61自顶向下的分析方法就是从文法的开始符号出发按最左推导方式向下推导试图推导出要分析的输开始符号输入符号串自底向上的分析方法从输入符号串开始按最左归约方式向上归约到文法的开始符号
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

合肥工业大学 计算机信息学院软件所
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|* 分析输入串x*y(记为)。
x*y x*y
S S
y
IP x IPIP x A * **
合肥工业大学 计算机信息学院软件所
当某个非终结符有多个产生式候选时，可能 带来如下问题:
1. 分析过程中，当一个非终结符用某一个候选 匹配成功时，这种匹配可能是暂时的。出错 时，不得不‚回溯‛。 2. 文法左递归问题。一个文法是含有左递归的， 如果存在非终结符P
P→P | 其中不以P开头。
我们可以把P的规则等价地改写为如下的非 直接左递归形式： P→P 左递归变 P→P|
右递归
合肥工业大学 计算机信息学院软件所
一般而言，假定P关于的全部产生式是
P→P1 | P2 | … | Pm | 1 | 2|…|n
其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规则 改写成： P→1P | 2P | … | nP P→1P | 2P |… | mP |
• 如果非终结符A的所有候选首符集两两不相交，即 A的任何两个不同候选 i和 j FIRST(i)∩FIRST( j)＝ 当要求A匹配输入串时，A就能根据它所面临的第 一个输入符号a，准确地指派某一个候选前去执行 任务。这个候选就是那个终结首符集含a的。
合肥工业大学 计算机信息学院软件所
合肥工业大学 计算机信息学院软件所
注意，由于对非终结符排序的不同，最后 所得的文法在形式上可能不一样。但不难 证明，它们都是等价的。 例如，若对文法(4.3)的非终结符排序选为S、 Q、R，那么，最后所得的无左递归文法是： S→Qc | c Q→Rb | b R→bcaR | caR |a R (4.5) R→ bca R | 文法(4.4)和(4.5)的等价性是显然的。
P P
合肥工业大学 计算机信息学院软件所

消除左递归的算法:
1. 把文法G的所有非终结符按任一种顺序排列成P1， P2，…，Pn；按此顺序执行； 2. FOR i:=1 TO n DO
BEGIN FOR j:=1 TO i-1 DO
把形如Pi→Pj的规则改写成 Pi→1|2|…|k ; (其中Pj→1|2|…|k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性
合肥工业大学 计算机信息学院软件所
例 考虑文法G(S)
S→Qc|c Q→Rb|b R→Sa|a
令它的非终结符的排序为R、Q、S。 对于R，不存在直接左递归。 R→Sa|a产生 式中S的序号大于R，不作替换处理 对于Q， Q→Rb|b中R的序号小于Q，把R 代入到Q的有关候选后，把Q的规则变为 Q→Sab | ab | b 不存在直接左递归，并且产生式中S的序号 大于Q，不再做替换处理。
合肥工业大学 计算机信息学院软件所
例 考虑文法G(S)
S→Qc|c Q→Rb|b R→Sa|a
令它的非终结符的排序为R、Q、S。 Q的规则变为 Q→Sab | ab | b 对于S， S→Qc|c产生式中Q序号小于S，把 Q的产生式代入到S的有关候选后，S变成 S→Sabc | abc | bc | c
...
符号表
合肥工业大学 计算机信息学院软件所
语法分析的方法：
自下而上分析法(om-up) 基本思想：从输入串开始，逐步进行‚归
约‛，直到文法的开始符号。即从树末端开
始，构造语法树。所谓归约，是指根据文法的 产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结 合性质进行语法分析。适合分析表达式。 LR分析法：规范归约
合肥工业大学 计算机信息学院软件所
例 考虑文法G(S)
S→Qc|c Q→Rb|b R→Sa|a
S变成
S→Sabc | abc | bc | c 出现左递归，消除S的直接左递归后： S→abcS | bcS | cS S→abcS | Q→Sab |ab | b R→Sa|a
合肥工业大学 计算机信息学院软件所
4.3.3 LL(1)分析条件
E→TE E→+TE | T→FT T→*FT | F→(E) | i
i + i
合肥工业大学 计算机信息学院软件所
E
i + i
IP
G(E):
E→TE E→+TE | T→FT T→*FT | F→(E) | i
合肥工业大学 计算机信息学院软件所
4.3.2 消除回溯、提左因子
产生回溯的原因：推导时，若产生式存在多个候选 式，选择哪个进行推导存在不确定性。 为了消除回溯就必须保证：对文法的任何非终结符， 当要它去匹配输入串时，能够根据它所面临的输入 符号准确地指派它的一个候选去执行任务，并且此 候选的工作结果应是确信无疑的。
END
3. 化简由2所得的文法。去除那些从开始符号出发永 远无法到达的非终结符的产生规则。
合肥工业大学 计算机信息学院软件所
注：消除左递归算法的注意事项:
1. 此算法适用于，消除了P→P 产生式和不以为 右部的产生式的文法。
2. 该算法的第二步所做的工作可以理解为：
a) 若产生式出现直接左递归，则用消除直接左递归的 方法消除； b) 若产生式右部的最左符号是非终结符且序号大于左 部的非终结符，则不作替换处理； c) 若序号小于左部的非终结符， 则将序号小的非终 结符（已处理过）用其右部串替换，然后消除新的 直接左递归； d) 因此每次替换的非终结符均为前面已经处理过的非 终结符。
P：产生式集合(有限)，每个产生式形式为 P， PVN， (VT VN)* 开始符S至少必须在某个产生式的左部出现一次。
合肥工业大学 计算机信息学院软件所
例，定义只含+，*的算术表达式的文法 G=<{i，+，*，(，)}，{E}，E， P>， 其中， P由下列产生式组成：
合肥工业大学 计算机信息学院软件所
例 考虑文法G(S)
S→Qc|c Q→Rb|b R→Sa|a
消除S的直接左递归后： S→abcS | bcS | cS S→abcS | Q→Sab |ab | b R→Sa|a 关于Q和R的规则已是多余的，化简为： S→abcS | bcS | cS S→abcS | (4.4)
A→ 1 | 2 | … | n a…. IP ... S A ...
合肥工业大学 计算机信息学院软件所
令G是一个不含左递归的文法，对G的所有 非终结符的每个候选定义它的终结首符集 FIRST()为：
FIRST ( ) = {a | a..., a VT }
*
*
特别是，若 ，则规定FIRST()。
优点：直观、简单和宜于手工实现。
合肥工业大学 计算机信息学院软件所
4.2 自上而下分析面临的问题
自上而下就是从文法的开始符号出发，向下 推导，推出句子。
带‚回溯‛的 不带回溯的递归子程序(递归下降)分析方法。
自上而下分析的主旨：对任何输入串，试图 用一切可能的办法，从文法开始符号(根结点) 出发，自上而下地为输入串建立一棵语法树。 或者说，为输入串寻找一个最左推导。
合肥工业大学 计算机信息学院软件所
G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E E
E E i
+
E
* E
i
i
合肥工业大学 计算机信息学院软件所
语法分析的方法：
自下而上分析法(Bottom-up) 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反 复使用各种产生式，寻找"匹配"的推导。 递归下降分析法：对每一语法变量(非终结 符)构造一个相应的子程序，每个子程序识 别一定的语法单位，通过子程序间的信息 反馈和联合作用实现对输入串的识别。 预测分析程序
编译原理
第四章 语法分析—自上而下分析
合肥工业大学 计算机信息学院软件所
源程序 表 词法分析器 单词符号 语法分析器 语法单位
语义分析与中间代码 生成器
出
格
错
管
四元式
处
理
优化段 四元式 目标代码生成器 目标代码
理
合肥工业大学 计算机信息学院软件所
第四章 语法分析—自上而下分析
本章主要介绍语法分析的处理 要进行语法分析，必须对语言的语法结构进 行描述。
左递归变 右递归
合肥工业大学 计算机信息学院软件所
例 文法G(E):
E→E＋T | T T→T*F | F F→(E) | i
经消去直接左递归后变成： E→TE E→+TE | (4.2) T→FT P→P1 | P2 | … | Pm | 1 | T→*FT | 2|…|n F→(E) | i P→ P | P | … | P
语法分析的任务是分析一个文法的句子结 构。 语法分析器的功能：按照文法的产生式(语 言的语法规则)，识别输入符号串是否为一 个句子(合式程序)。
注：语法分析是编译程序的核心部分
合肥工业大学 计算机信息学院软件所
单词符号
源程序 词法分 析器
取下一单词
语法分 语法分 析树 编译程序 后续部分 析器
P P
含有左递归的文法将使自上而下的分 析陷入无限循环。
合肥工业大学 计算机信息学院软件所

4.3 LL(1)分析法
构造不带回溯的自上而下分析算法
要消除文法的左递归性
克服回溯
合肥工业大学 计算机信息学院软件所