第4章语法分析-自上而下分析

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

第四章 语法分析—自上而下分析

知识结构：

带回溯分析法 回溯

自上而下分析 面临的问题 左递归 问题的解决

语法分析－ 求FIRST、FOLLOW集合的算法 自上而下分析 LL(1)分析法 证明LL(1)文法 构造LL(1)分析表

递归子程序的构造思想 递归子程序法 递归子程序的特点 递归子程序的设计

第一节 语法分析综述 一、语法分析的任务

按照语言即定的语法规则，对字符串形式的源程序进行语法检查，并识别出相应的语法成分。即语法结构是否符合语法规则。 二、语法分析器在编译程序中的地位（一遍扫描）

源程序 单词符号 分析树 语义分析 词法分析器 语法分析器 中间代码生成 取下一个单词 制作人：李明新 共28页第1页 13-3-24

符号表 编译原理 第四章 语法分析—自上而下分析

三、语法分析方法

通常把语法分析方法分为两大类，既自上而下分析与自下而上分析。

1、自上而下分析方法

实际上是一种产生的方法，分析过程是一个推导过程。 ⑴自上而下分析过程

从文法G的开始符号S出发，通过反复使用产生式，逐步推导出与输入的符号串完全相匹配的句子。采用最左推导，以文法开始符号为根结点，逐步为输入串自上而下地构造一棵语法树。

面临的输入符号为a，A所有的产生式： A??1 ??2 ? ? ??n

①若a?FISRT(?i)，则指派去执行匹配任务。 ②若a不属于任何一个候选首字符集，则：

a、若 ? 属于某个FISRT(?i)且a?FOLLOW(A)，则让A与?自动匹配；

b、否则，a的出现是一种错误。 例：设有文法G和输入符号串W：a*a+a G：S ? aA?a

A ? BaA?? B ? +? -?*?/

推导过程：

S?aA?aBaA?a*aA?a*aBaA?a*a+aA?a*a+a=W

制作人：李明新 共28页第2页 13-3-24

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

构造语法树： S a A B a A * B a A + ? ⑵自上而下分析法

自上而下分析法又可分为确定和不确定的两种。 ①不确定的分析法（带回溯）

是一种穷举的试探方法，效率低、代价高，极少使用。 ②确定的分析法（不带回溯）

实现方法简单、直观，便于手工构造或自动生成语法分析器，是目前常用的方法之一。但是对文法有一定的限制。

2、自下而上分析法 ⑴自下而上分析过程

分析过程是归约过程。从给定的输入串W开始，不断寻找与文法G中某个产生式P的侯选式（右部）进行匹配，并用P代替也称为归约。

⑵自下而上分析法 ①算符优先分析法

定义算符（广义讲是文法的终结符号）之间的某种优先和结合关系，借助这种关系来寻找并确定可归约字符串，并进行归约。

制作人：李明新 共28页第3页 13-3-24

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

②LR分析法

是一类自左向右对输入串进行扫描的自下而上分析方法，分析过程是规范归约的序列。适用于语法分析器的自动构造。

第二节 自上而下分析面临的问题 一、不确定的自上而下分析方法

是从文法的开始S出发，试图用一切可能的方法向下推导，产生句子，这种分析过程的本质是一种试探推导过程。

例：文法G ⑴ S ? aAd

⑵ A ? ab?a

构造W=aad的最左推导：S?aAd?aad。 构造语法树：

①产生树的根结点，即文法的开始符号。 ②选用文法G的文法规则去延伸树。

③判断当前延伸的子结与输入串扫描到的字符是否匹配。 ④若不匹配注销掉当前延伸的子树，选用文法规则的另一个产生式延伸分析树。

⑤直到输入串与语法树末端结点相匹配，分析结束。 S S S a A d a A d a A d a b a 这种试探识别句子的过程，只会使分析的过程不确定。

制作人：李明新 共28页第4页 13-3-24

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

二、不确定性的原因

由于分析过程中选择的侯选式不确定，造成输入串匹配的假象，甚至会导致算法实现的失败。

1、左递归问题

由于采用最左推导，左递归将使得输入串的分析过程陷入无限循环之中。

2、回溯问题

⑴采用试探的方法，如匹配不成功回溯到前面分析的某一步。 ⑵可能出现假匹配，造成对输入串识别的失败。 ⑶不能准确报告输入串的出错位臵。 三、确定的自上而下分析方法

1、确定的自上而下分析方法的必要条件 ⑴消除文法中的左递归； ⑵消除文法中的回溯问题。 2、消除文法的左递归

文法的左递归可以通过对文法产生式进行改写，使之不含有左递归的非终结符号。左递归一般有两种情况，直接左递归和间接左递归。

⑴直接左递归

如果文法中任意一个非终结符P，若P?P?（??VNUVT），并且在最左推导中有P?P?形式，称为直接左递归。

⑵间接左递归

制作人：李明新 共28页第5页 13-3-24

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

+

在最左推导中有P=>P?形式，称为间接左递归。 ①消除直接左递归 P→P? | ? 改写为：P→?P ?

P ??? P ? ? ?

例：表达式文法 E? E+T ? T 改写为：E? TE?

E?? +TE? ? ? T? T*F ? F 改写为：T? FT?

T?? *FT? ? ? F? (E) ? i

②消除文法的左递归一般规则

P→P?1?P?2?…… P?m??1??2? …… ??n ?i≠? 改写为：

P→?1P???2P??………?n P? P→?1P???2P??………?m P? ?? ③消除间接左递归

A→B…

B→C… 间接左递归: A?B…?C…?A… C→A…

制作人：李明新 共28页第6页 13-3-24

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

例：文法G

S→Qc|c Q→Rb|b R→Sa|a

最左推导：S?Qc?Rbc?Sabc（间接左递归）

⑶清除间接左递归

非终结符排序为R，Q，S。R不存在直接左递归，把的规则：

Q→Sab | ab | b 再把Q代入S：

S→Sabc | abc | bc | c 消除S的左递归：

S→abcS?

| bcS?

| cS?

S?→abcS?

| ?

Q和R的产生式不再被引用，将Q和R删除。

非终结符排序为S，Q，R。S不存在直接左递归，不包含S，再把S代入得到R:

R→Rbca | bca | ca | a 消除S的左递归：

R→bcaR?

| caR?

| aR?

R?→bcaR?

| ?

改写为：

制作人：李明新 共28页第7页 13-3-24

R代入QQ的产生式编译原理 第四章 语法分析—自上而下分析

S→Qc|c 不能删除 Q→Rb|b 不能删除

R→bcaR?|caR?|aR?

R?→bcaR?|?

3、消除回溯，提取左因子 ⑴消除回朔

文法G不包含左递归，则G中非终结符号的每个候选式首字符集FIRST（?）为：

** *

FIRST（?）={a??=>a…,a?VT ，??（VNUVT）}若?=>?，则

? ? FIRST（?）。

⑵提取最左公共因子

采用提取最左公共因子的方法改写文法，使得所有侯选式的首字符集两两不相交。

A→??1???2? …… ???n ??1??2? …… ??m 提取公因子:

A→?(?1??2? …… ??n) ??1??2? …… ??m 改写后为:

A→?A???1??2? …… ??m

A?→?1??2? …… ??n

4、确定的自上而下分析方法 ⑴预测分析法（LL（1）分析法）。 ⑵递归子程序法。

制作人：李明新 共28页第8页 13-3-24

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

第三节 预测分析法（LL（1）分析法） 一、LL（1）分析方法

1、是按自左（第一个“L”）向右的顺序扫描输入字符串；

2、在分析过程中产生句子的最左（第二个“L”）推导； 3、 “1”表示在分析过程中，每一步推导，最多只能向前查 看（向右扫描）一个字符。 二、LL（K）分析方法

如果分析过程的每一步推导，要向前查看K个输入字符，则称为LL（K）分析法。 三、LL（1）文法的定义

该文法是上下文无关的一个子集，是自上而下分析技术的一类文法。

四、LL（1）分析法的必要条件

1、文法中的非终结符号不包含左递归；

2、对于文法中的每一个非终结符A的各个产生式的侯选首字符集两两不相交。对于产生式A????:

⑴若? ? ?，证明侯选式?，?的首字符集是否相交。

FIRST（?）∩FIRST（?）= Ф

⑵若?＝ε，证明FIRST（A）和FOLLOW（A）是否相交。

FIRST（A）∩FOLLOW（A）=φ

五、构造FIRST集合的算法 对每一文法符号X?（VNUVT）

制作人：李明新 共28页第9页 13-3-24

*

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

1、若X?VT ，则 FIRST（X）={X}。

2、若X?VN ，且有产生式X?a?，a?VT，则a?FIRST（X）。 3、若X?VN ，X??，则??FIRST（X） 4、若X?VN ，且Y1，Y2，?，Yi ?VN，

*

而有产生式X? Y1，?，Yn。当Y1，Y2，?，Yi-1都 =>?时，（其中1≤i≤n），则FIRST（Y1，）-{?}，?，FIRST（Yi-1）-{?}， FIRST（Yi）都包含在FIRST（X）中。若FIRST（Yj）包含?把?加到FIRST（X）中。

例 文法G

E →TE` E`→+TE`|ε T →FT` T`→*FT`|ε F→（E）|i

FIRST（E）=FIRST（T）=FIRST（F）={（，i ）} FIRST（E?）={ +，ε} FIRST（T?）={ *，ε}

六、构造FOLLOW集合的算法

*

FOLLOW (A)={a | S=>….Aa…. , a? VT } *

若S=>…A, 则 #? FOLLOW (A)

FOLLOW (A)为所有句型中紧跟在非终结符A后面的所有终结符集合。

制作人：李明新 共28页第10页 13-3-24

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

构造算法：

1、对文法开始符号S，将“#”臵于FOLLOW(S)中。 即FOLLOW(S) = ? # ?。

2、若A →?B? 是一个产生式，则把FIRST（β）-{ε}加至 FOLLOW(B)中。

3、若A →?B是一个产生式，或A→?B? 是一个产生式，而 ???（即??FIRST（?））；则把FOLLOW(A)加至FOLLOW(B)中。

例 文法G

E →TE` E`→+TE`|ε T →FT` T`→*FT`|ε F→（E）|i

求FOLLOW（E）：

因为 F→（E） ，所以FIRST（））加入FOLLOW(E)中， FOLLOW(E) = ? ) ? ；

又因为E→TE`,E是文法的开始符号，则#加至FOLLOW(E)中，所以

FOLLOW(E)= ? # ? U FOLLOW(E)=? #,) ?。 求FOLLOW（E`）：

因为E→TE`, 满足算法(3)若A →?B是一个产生式，则 把FOLLOW(A)加至FOLLOW(B)中，所以

制作人：李明新 共28页第11页 13-3-24

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

FOLLOW(E`)= FOLLOW(E)U FOLLOW(E)

= ? #，) ?

求FOLLOW（T）：

因为E→TE`, 满足算法⑵若A →?B? 是一个产生式，则把 FIRST（β）\\{ε}加至FOLLOW(B)中，所以

FOLLOW(T) = FOLLOW(T) U FIRST（E`）\\{ε}

= {+}

又因为E`??，满足算法(3)若A→?B? 是一个产生式，而 ???，则把FOLLOW(A)加至FOLLOW(B)中。所以

FOLLOW(T) = FOLLOW(E) U FOLLOW(T)

= ? #，) ?U ?+? = ? #，)，+?

求FOLLOW（T`）：

因为T→FT`,满足算法(3)若A →?B是一个产生式，则 把FOLLOW(A)加至FOLLOW(B)中，所以

FOLLOW(T) = FOLLOW(T) U FOLLOW(T`)

= ? #，)，+?

求FOLLOW（F）：

因为T→FT`, 满足算法⑵若A →?B? 是一个产生式，则把 FIRST（β）\\{ε}加至FOLLOW(B)中，所以

FOLLOW(F) = FOLLOW(F) U FIRST（T`）\\{ε}= {*} 又因为T`??，满足算法(3)若A→?B? 是一个产生式，而

制作人：李明新 共28页第12页 13-3-24

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

???，则把FOLLOW(A)加至FOLLOW(B)中。所以

FOLLOW(F) = FOLLOW(T) U FOLLOW(F)

= ? #，)，+? U ?*? = ? #，)，+，* ?

连续使用上述三条规则，直到每个FOLLOW不再增大为止。 FOLLOW(E)= FOLLOW(E?)= ? #，) ? FOLLOW(T)= FOLLOW(T?)= ? #，)，+ ?

FOLLOW(F)= ? #，)，+，* ? 七、证明上述文法是否为LL(1)文法

对于产生式A????:

1、若? ? ?，证明侯选式?，?的首字符集是否相交。

FIRST（?）∩FIRST（?）= Ф 例：F?（E）?i

FIRST（（）∩FIRST（i）= Ф

2、若?＝ε，证明FIRST（A）和FOLLOW（A）是否相交。

FIRST（A）∩FOLLOW（A）=φ 例：E`?+TE`??

FIRST（E`）∩FOLLOW（E`） =? +，? ?∩? ），# ?=φ

八、构造分析表的算法

1、对文法G的每个产生式A→α执行第二步和第三步； 2、对每个终结符a?FIRST(?),把A→α加至M[A,a]中；

制作人：李明新 共28页第13页 13-3-24

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

3、若ε?FIRST（α），则对任何b?FOLLOW(A)把A→α（或A??）加至M[A,b]中；

4、把所有无定义的M[A，a]标上“出错标志” 例： E→TE` ， E`→+TE`′|ε

T→FT` ， T`→*FT`′|ε

F→（E）|i

求其FIRST的集合:

FIRST（E）=FIRST（T）=FIRST（F）={（，i ）} FIRST（E?）={ +，ε}，FIRST（T?）={ *，ε} 求其FOLLOW的集合:

FOLLOW(E)= FOLLOW(E?)= ? #，) ? FOLLOW(T)= FOLLOW(T?)= ? #，)，+ ?

FOLLOW(F)= ? #，)，+，* ? 根据算法构造LL（1）的分析表:

终结符 非终结符 i + * （ ） # E TE` TE` E` +TE` ? ? T FT` FT` T` ? *FT` ? ? F i (E) 九、LL（1）分析器的逻辑结构与分析程序 1、LL（1）分析器的逻辑结构

LL（1）分析法，由总控程序控制输入字符串，在一张LL（1）分析表和一个分析工作栈上运行，而完成语法分析任务的。

制作人：李明新 共28页第14页 13-3-24

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

输入字符串 a1 a2 ? ai ? an

X 总控程序 分析栈 分析表 # 其中：

①分析表，实现相应的分析动作，即对[Ai，aj]，设Ai??表示当前分析工作栈顶为Ai，输入字符为aj时，应选用Ai??进行推导。

②分析工作栈，用于存放分析过程中的文法符号。分析工作栈初始化时，在工作栈顶写入一个“#”，再写入文法开始符号。

③总控程序，依据分析工作栈和分析表联合控制输入串的识别和分析。

2、分析程序的工作原理

⑴把“＃”和文法开始符号推入分析工作栈；设臵指示器的初始值，用第一个输入符号（终结符号）与分析工作栈顶文法符号进行匹配。

⑵设在某一步的分析工作栈与输入串的当前工作状态： X1X2?Xm-1Xm为分析工作栈中的当前状态；aiai+1?#为输入串的当前状态。

①若Xm?VN，则以Xm及ai组成符号对（Xm，ai）查分析表M[Xm，ai]，设Xm?UVW，将Xm从分析工作栈顶退出，并将UVW按反向写

制作人：李明新 共28页第15页 13-3-24

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

入分析工作栈中。若M[Xm，ai]=“Error”，则调用出错处理程序。

②若Xm?VT并且Xm=ai，则表明分析工作栈顶的符号与当前输入符号相匹配，将工作栈顶的符号Xm退出，输入符号指针向右移一位。

③若Xm=#，则表明输入符号串已完全匹配，分析成功结束分析工作。

3、分析程序的算法（P77）

例：对输入串 # i*i+i #的预测分析过程 P78

第四节 递归下降分析程序的构造

一、递归下降分析程序的构造方法

对文法的每个非终结符号，根据各侯选式的结构，编写一个对应的子程序，完成非终结符相应的语法成分的识别和分析任务。 二、递归下降分析程序的功能

对某个非终结符，用产生式规则的右部符号进行匹配。 三、递归下降分析程序的特点

1、程序结构清晰，易于手工操作。

2、对语义处理灵活。 四、递归下降分析法的必要条件

必须是不包含左递归和回溯的上下文无关文法。 五、递归下降分析程序的设计

P74

制作人：李明新 共28页第16页 13-3-24

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

第五节 预测分析法的错误处理 一、出错情况

1、工作栈顶终结符与输入符号不匹配。

2、对应M[A，a]中为空(Error)。 二、出错处理

1、报告出错（出错位臵，出错性质）。 2、处理出错情况，使语法分析继续下去：

⑴若M[A，a]中为空(Error),跳过输入符号a，若该项为同步(synch)，则退出工作栈顶的非终结符A。

⑵工作栈顶的终结符无法与输入符号匹配，则弹出该符号。

第六节 学习与理解

一、填空题

⑴自上而下语法分析方法的基本思想是：从文法的开始符号出发。不断建立最左直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。

⑵自上而下分析方法会遇到的主要问题有回溯和左递归。 ⑶在语法分析中，最常见的两种方法一定是自上而下分析法，另一种是自下而上分析法。 二、选择题

⑴编译过程中，语法分析器的任务是B，C，D。

A、分析单词是怎样构成的 B、分析单词串是如何构成语句的

制作人：李明新 共28页第17页 13-3-24

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

C、分析语句是如何构成程序的 D、分析程序结构

⑵高级语言编译程序常用的语法分析方法中，递归下降分析法属于B分析方法。

A、自左至右 B、自上而下 C、自下而上 D、自右至左

三、解答题

⑴已知文法G： A?aAa??

①该文法是LL（1）文法吗？为什么？

②若采用LL（1）方法进行分析，如何得到该文法的LL（1）分析表。

③若输入串“aaaa”，请给出语法分析过程。 解：

①因为FOLLOW（A）＝FOLLOW（A）?FIRST（A）={a，#}，造成FOLLOW（A）?FIRST（A）={a，#}?{a，?}??，所以该文法不是LL（1）文法。

②若采用LL（1）方法进行语法分析，必须修改该文法。因该文法产生偶数（可以为0）个a，所以得到文法G`：A?aaA??。

此时 FOLLOW（A）={#}，因此

FOLLOW（A）?FIRST（A）={#}?{a，?}=?

所以文法G`是LL（1）文法。该文法的LL（1）分析表：

制作人：李明新 共28页第18页 13-3-24

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

VT a # VN A A?aaA A?? ③对符号串“aaaa”的分析过程：

步骤 1 2 3 4 5 6 7 8 分析栈 输入串 产生式/动作 #A aaaa# A?aaA #Aaa aaaa# 匹配 #Aa aaa# 匹配 #A aa# A?aaA #Aaa aa# 匹配 #Aa a# 匹配 #A # A?? # # 接受 ⑵设文法G(A)：

A?aABc?aA B?Bb?d

①试给出文法G(A)等价的LL（1）文法G`(A)。

②构造G`(A)的LL（1）分析表，给出输入串aadc#的分析过程。

解答：

①由于该文法G(A) A?aABc?a 存在回溯 B?Bb?d 存在左递归

所以不是LL(1)文法。

②改写文法G(A)

制作人：李明新 共28页第19页 13-3-24

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

A?aABc?a

提取最左公共因子使得：A?a（ABc??），定义A`?ABc?? 改写后的产生式：

A?aA` A`?ABc??

又因为：B?Bb?d存在左递归，消除左递归后的产生式：

B?dB` B`?bB`??

③构造文法每一个非终结符号FIRST和FOLLOW的集合。 a、构造文法每一个非终结符号FIRST的集合 FIRST（A）={a} FIRST（A`）={a，?} FIRST（B）={d} FIRST（B`）={b,?}

b、构造文法每一个非终结符号FOLLOW的集合 因为A?aA`和A`?ABc??，所以:

FOLLOW（A）={#}?FIRST（B）\\{?}={#,d}

因为A?aA`，所以FOLLOW（A`）= FOLLOW（A）={#,d} 因为A`?ABc，所以FOLLOW（B）={c}

因为B?dB`,所以FOLLOW（B`）=FOLLOW（B）， 最终结果:

FOLLOW（A）= FOLLOW（A`）={#，d}。

制作人：李明新 共28页第20页 13-3-24

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

FOLLOW（B）= FOLLOW（B`）={c} ④证明该文法是否是LL（1）文法？

因为文法G`(A)中只含有一个多候选式的定义式A`?ABc??和B`?bB`??。

只需证明：

FIRST（A`）?FOLLOW（A`）={a, ?}?{#，d}=? FIRST（B`）?FOLLOW（B`）={b, ?}?{#，d}=? 该文法是LL（1）文法。

⑤构造相应的LL（1）分析表

因为 FIRST（A）={a}，所以M[A，a]= A?aA`；

因为 FIRST（S`）={b，?}，所以M[S`，b]= S`?bAS`， 又因为??FIRST（S`），则对{d，#}?FOLLOW（S`）， 所以M[A`，d]= A`??，M[A`，#]= A`??； 因为FIRST（B）={d}，所以M[B，d]= B?dB`；

因为FIRST（B`）={b}，所以M[B`，b]= B`?Bb`， 又因为??FIRST（B`），则对{c}?FOLLOW（B`）， 所以M[B`，c]= B`??。 LL(1)分析表 a b c d # A A?aA` A` A`?ABc B A`?? A`?? B?dB` 制作人：李明新 共28页第21页 13-3-24

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

B` B`?Bb` B`??

⑥输入串aadc#的分析过程。

步骤 0 1 2 3 4 5 6 7 8 9 10 符号栈 ＃A ＃A`a ＃A` ＃cBA ＃cBA`a ＃cBA` ＃cB ＃cB`d ＃cB` ＃c ＃ 输入串 aadc＃ aadc＃ adc＃ adc＃ dc＃ dc＃ dc＃ dc＃ c＃ c＃ ＃ 所用产生式 A?aA` 匹配 A`?ABc A?aA` 匹配 A`?? 匹配 B`?? 匹配 结束 作业 :

⑴根据P76表4.1写出表达式 (i+i)*i 的预测分析过程。 ⑵P81 1, 2(1)(2)(3)

制作人：李明新 共28页第22页 13-3-24

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

作业解析

一、P76的文法写出表达式 (i+i)*i 的预测分析过程。 解答：

步骤 符号栈 输入串 所用的产生式

0 #E （i+i）*i# 1 #E`T （i+i）*i# E?TE` 2 #E`T`F （i+i）*i# T?FT` 3 #E`T`）E（ （i+i）*i# F?（E） 4 #E`T`）E i+i）*i#

5 #E`T`）E`T i+i）*i# E?TE` 6 #E`T`）E`T`F i+i）*i# T?FT` 7 #E`T`）E`T`i i+i）*i# F?i 8 #E`T`）E`T` +i）*i# 9 #E`T`）E` +i）*i# T`?? 10 #E`T`）E`T+ +i）*i# E`?+TE` 11 #E`T`）E`T i）*i#

12 #E`T`）E`T`F i）*i# T?FT` 13 #E`T`）E`T`i i）*i# F?i 14 #E`T`）E`T` ）*i#

15 #E`T`）E` ）*i# T`?? 16 #E`T`） ）*i# E`?? 18 #E`T` *i#

19 #E`T`F* *i# T`?*FT` 20 #E`T`F i# 21 #E`T`i i# F?i 22 #E`T` #

23 #E` # T`?? 24 # # E`??

二、考虑下面文法G

S? a?^?（T） T?T，S?S

⑴消除文法的左递归。

制作人：李明新 共28页第23页 13-3-24

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

⑵经改写后的文法是否是LL（1）的？给出它的预测分析表。 解答：

⑴经考察该文法S? a?^?（T）的各侯选式的首字符都是终结符号，所以只有T?T，S?S是直接左递归。根据改写算法，改写后的文法是：

S? a?^?（T） T?ST`

T`?，ST`??

⑵证明改写后的文法是否是LL（1）的.

①证明S? a?^?（T）各侯选式的FIRST是否两两相交。 FIRST（a）?FIRST（^）=?

FIRST（a）?FIRST（（）=? FIRST（^）?FIRST（（）=?

②证明T`?，ST`??的FIRST（T`）和FOLLOW（T`）是否相交。

求FIRST（T`）={，，?}

FOLLOW（T`）={ ? }

FIRST（T`）? FOLLOW（T`）={，，?}?{ ? }=?

该文法是LL（1）的。

⑶构造预测分析表

a ， ^ （ ） # S S? a S?^ S?（T） 制作人：李明新 共28页第24页 13-3-24

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

T T?ST` T?ST` T?ST`

T` T`?，ST` T`??

二、下面的文法G

E? TE` E`?+E?? T?FT`

T`?T?? F?PF` F`?*F`??

P?（E）?^?a?b

⑴计算这个文法的每个非终结符的FIRST和FOLLOW。⑵证明这个文法是LL（1）的 ⑶构造它的预测分析表。 解答：

⑴求非终结符的FIRST和FOLLOW。 求非终结符的FIRST：

因为E`?+E??，所以FIRST（E`）={+， ?}。 因为F`?*F`??，所以FIRST（F`）={*， ?}。 因为P?（E）?^?a?b，

所以FIRST（P）={（， ^， a， b ?。 因为F?PF`，所以FIRST（F）= FIRST（P）。 因为T?FT`，所以FIRST（T）={FIRST（F）。

制作人：李明新 共28页第25页 13-3-24

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

因为E? TE`，所以FIRST（E）= FIRST（T）。 因为T`?T??，

所以FIRST（T`）= FIRST（T）?{ ?} ={（， ^， a， b ，??。 求非终结符的FOLLOW：

因为E? TE`的E是文法的开始符号，FOLLOW（E）={#}，又因为P?（E），所以FOLLOW（E）={#}?FIRST（））\\{?}={#，)}

因为E? TE`，所以FOLLOW（E`）=FOLLOW（E） 因为E? TE`，并且E`≠?， 所以FOLLOW（T）=FIRST（E`）\\{?}, 又因为E`??,

所以FOLLOW（T）={+}? FOLLOW（E）={+}? {#,}}={+，#,? }. 因为T?FT`，所以FOLLOW（T`）=FOLLOW（T）={+，#,? }. 因为T? FT`，并且T`≠?，

所以FOLLOW（F）=FIRST（T`）\\{?},又因为T`??, 所以FOLLOW（F）={（，^，a，b ?? FOLLOW（T） ={（，^，a，b ??{+，#,? }={（，^，a，b ,+，#,? ? 因为F?PF`，

所以FOLLOW（F`）=FOLLOW（F）={（，^，a，b ,+，#,? ?. 因为F?PF`，并且F`≠?，

所以FOLLOW（P）=FIRST（F`）\\{?},又因为F`??, 所以FOLLOW（P）={*?? FOLLOW（F）

制作人：李明新 共28页第26页 13-3-24

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

={*}?{（，^，a，b,+,）,# ?

={*,（，^，a，b ,+，?,# ?. ⑵证明这个文法是LL（1）的

①证明P?(E)?^?a?b各侯选式的FIRST是否两两相交。 FIRST（(E)）?FIRST（^）=?

FIRST（(E)）?FIRST（a）=? FIRST（(E)）?FIRST（b）=?

FIRST（^）?FIRST（a）=?

FIRST（^）?FIRST（b）=? FIRST（a）?FIRST（b）=?

②证明E`?+E??,T`?T??,F`?*F`??非终结符号的FIRST和FOLLOW是否相交。

FIRST（E`）? FOLLOW（E`）={+，?}?{#, ? }=? FIRST（T`）? FOLLOW（T`） ={（， ^， a， b ，???{+，#,? }=? FIRST（F`）? FOLLOW（F`） ={*，?}?{（，^，a，b ,+，#,? ?=? 该文法是LL（1）的。

⑶构造预测分析表

+ * ( ) a b ^ # E TE` TE` TE` TE` E` +E` ? ? T FT` FT` FT` FT` T` ? T ? T T T ? F PF` PF` PF` PF` 制作人：李明新 共28页第27页 13-3-24 编译原理 第四章 语法分析—自上而下分析

F` ? *F` ? ? ? ? ? ? P (E) a b ^

制作人：李明新 共28页第28页 13-3-24

本文来源：https://www.bwwdw.com/article/62ia.html