自上而下分析 4.4.

自上而下分析 4.4

复习

4.3 自上而下分析 4.3.2 LL(1)文法对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数
FIRST( ) = {a |  * a…, a  VT} 特别是， * 时，规定  FIRST( ) FOLLOW(A) = {a | S * …Aa…，aVT} 如果A是某个句型的最右符号，那么$属于FOLLOW(A)

任何两个产生式A  |  都满足下列条件：
4.3 自上而下分析 LL(1)文法任何两个产生式A  |  都满足下列条件： FIRST( )  FIRST( ) =  若 *  ，那么FIRST()  FOLLOW(A) =  例如, 对于下面文法，面临a…时，第2步推导不知用哪个产生式 S  A B A  a b |  a  FIRST(ab)  FOLLOW(A) B  a C C  …

任何两个产生式A  |  都满足下列条件：
4.3 自上而下分析 LL(1)文法任何两个产生式A  |  都满足下列条件： FIRST( )  FIRST( ) =  若 *  ，那么FIRST()  FOLLOW(A) =  LL(1)文法有一些明显的性质没有公共左因子不是二义的不含左递归

计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或ε可以被加入到FIRST(X)
4.3 自上而下分析计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或ε可以被加入到FIRST(X) 如果X是终结符，FIRST(X)= X

4.3 自上而下分析计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或ε可以被加入到FIRST(X) 如果X是终结符，FIRST(X)= X 如果XY1Y2…Yk, 且a在FIRST(Yi)集合中，并且Y1 * ε, Y2 * ε, …, Yi-1 * ε，则将a插入到FIRST(X)中。

4.3 自上而下分析计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或ε可以被加入到FIRST(X) 如果X是终结符，FIRST(X)= X 如果XY1Y2…Yk, 且a在FIRST(Yi)集合中，并且Y1 * ε, Y2 * ε, …, Yi-1 * ε，则将a插入到FIRST(X)中。如果X ε是一个产生式，则将ε插入到FIRST(X)中。

计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A)
4.3 自上而下分析计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A) 将$放到FOLLOW(S)中，S是开始符，$是输入右端的结束标记

4.3 自上而下分析计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A) 将$放到FOLLOW(S)中，S是开始符，$是输入右端的结束标记如果存在AαBβ，那么FIRST(β)中非ε的所有符号都在FOLLOW(B)中

4.3 自上而下分析计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A) 将$放到FOLLOW(S)中，S是开始符，$是输入右端的结束标记如果存在AαBβ，那么FIRST(β)中非ε的所有符号都在FOLLOW(B)中如果存在AαB或AαBβ，且FIRST(β)包含ε，则FOLLOW(A)中的所有符号都在FOLLOW(B)中。

4.3 自上而下分析例 E  TE  E   + TE  |  T  FT  T    FT  | 
F  (E) | id FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E ) = {+, } FRIST(T ) = {, } FOLLOW(E) = FOLLOW(E ) = { ), $} FOLLOW(T) = FOLLOW (T ) = {+, ), $} FOLLOW(F) = {+, , ), $} * 在FRIST(T)中，+, )和$在FOLLOW (T) 中。

4.3 自上而下分析一个辅助过程 void match (terminal t) {
if (lookahead == t) lookahead = nextToken( ); else error( ); }

4.3 自上而下分析 void type( ) { if ( (lookahead == integer) || (lookahead == char) || (lookahead == num) ) simple( ); else if ( lookahead ==  ) { match(); match(id);} else if (lookahead == array) { match(array); match( [ ); simple( ); match( ] ); match(of ); type( ); } else error( ); type  simple |  id | array [simple] of type

4.3 自上而下分析 void simple( ) { if ( lookahead == integer) match(integer); else if (lookahead == char) match(char); else if (lookahead == num) { match(num); match(dotdot); match(num); } else error( ); simple  integer | char | num dotdot num

4.3 自上而下分析 4.4.4 非递归的预测分析 a + b $ X Y Z 输入预测分析程序输出栈分析表M
以自然语言例子：我上课请开门做例子讲解非递归的自上而下分析

4.3 自上而下分析 4.4.4 非递归的预测分析算法初始时分析器的格局是：Ｓ$在栈里，其中Ｓ是开始符号并且在栈顶；ｗ$ 在输入缓冲区
主程序

4.3 自上而下分析 4.4.4 非递归的预测分析预测分析程序根据当前的栈顶符号Ｘ和输入符号a决定分析器的动作，它有四种可能：
如果Ｘ是非终结符，程序访问分析表Ｍ

4.3 自上而下分析 4.4.5 构造预测分析表（1）对文法的每个产生式A   ，执行(2)和(3)
（2）对FIRST()的每个终结符a，把A   加入M[A, a] （3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$）, 把A  加入M[A, b] （4）M中其它没有定义的条目都是error

4.3 自上而下分析 4.4.5 构造预测分析表例： E  TE  E   + TE  |  T  FT 
F  (E) | id FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E ) = {+, } FRIST(T ) = {, } FOLLOW(E) = FOLLOW(E ) = { ), $} FOLLOW(T) = FOLLOW (T ) = {+, ), $} FOLLOW(F) = {+, , ), $}

4.3 自上而下分析 4.4.5 构造预测分析表非终结符输入符号 id +  . . . E E  TE  E 
输入符号 id +  . . . E E  TE  E  E   +TE  T T  FT  T  T    T   FT  F F  id

4.3 自上而下分析 4.4.5 构造预测分析表多重定义的条目例：
stmt  if expr then stmt e_part | other e_part  else stmt |  other  b FOLLOW(e_part) = (else, $) M[e_part, else]包括e_part  else stmt 和 e_part  

4.3 自上而下分析非终结符输入符号 other b else . . . stmt stmt  other e_part
多重定义的条目非终结符输入符号 other b else . . . stmt stmt  other e_part e_part else stmt e_part   expr expr  b

4.3 自上而下分析非终结符输入符号 other b else . . . stmt stmt  other e_part
多重定义的条目非终结符输入符号 other b else . . . stmt stmt  other e_part e_part else stmt expr expr  b

预测分析的错误恢复

4.3 自上而下分析 4.4.6 预测分析的错误恢复 1、先对编译器的错误处理做一个概述词法错误，如标识符、关键字或算符的拼写错语法错误，如算术表达式的括号不配对语义错误，如算符作用于不相容的运算对象逻辑错误，如无穷的递归调用

4.3 自上而下分析 2、分析器对错误处理的基本目标清楚而准确地报告错误的出现，并尽量少出现伪错误迅速地从每个错误中恢复过来，以便诊断后面的错误它不应该使正确程序的处理速度降低太多

4.3 自上而下分析 3、非递归预测分析在什么场合下发现错误栈顶的终结符和下一个输入符号不匹配 a + b $ X Y Z 输入
预测分析程序分析表M 输出 X Y Z 栈

4.3 自上而下分析 3、非递归预测分析在什么场合下发现错误栈顶是非终结符A，输入符号是a，而M[A , a]是空白 a + b $ X
预测分析程序分析表M 输出 X Y Z 栈

4、非递归预测分析：采用紧急方式的错误恢复
4.3 自上而下分析 4、非递归预测分析：采用紧急方式的错误恢复发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定的同步记号集合为止 5、同步词法分析器当前提供的记号流能够构成的语法构造，正是语法分析器所期望的不同步的例子语法分析器期望剩余的前缀构成过程调用语句，而实际剩余的前缀形成赋值语句

4.3 自上而下分析 6、同步记号集合的选择把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合

4.3 自上而下分析 6、同步记号集合的选择把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合
if expr then stmt （then和分号等记号是expr的同步记号）

把高层构造的开始符号加到低层构造的同步记号集合中

把高层构造的开始符号加到低层构造的同步记号集合中 a = expr; if … (语句的开始符号作为表达式的同步记号，以免表达式出错又遗漏分号时忽略if语句等一大段程序)

把高层构造的开始符号加到低层构造的同步记号集合中把FIRST(A)的终结符加入A的同步记号集合 a = expr; , if … （语句的开始符号作为语句的同步符号，以免多出一个逗号时会把if语句忽略了）

把高层构造的开始符号加到低层构造的同步记号集合中把FIRST(A)的终结符加入A的同步记号集合如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式

4.3 自上而下分析非终结符输入符号 id +  . . . E ETE E E+TE T TFT  T 
例栈顶为T ，面临id时出错非终结符输入符号 id +  . . . E ETE E E+TE T TFT  T  出错 T   T FT 

4.3 自上而下分析非终结符输入符号 id +  . . . E ETE E E+TE T TFT  T 
输入符号 id +  . . . E ETE E E+TE T TFT  T  出错，用T   T   T FT 

把高层构造的开始符号加到低层构造的同步记号集合中把FIRST(A)的终结符加入A的同步记号集合如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式如果终结符在栈顶而不能匹配，弹出此终结符

4.3 自上而下分析错误恢复例： E  TE  E   + TE  |  T  FT  T    FT  | 
F  (E) | id FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E ) = {+, } FRIST(T ) = {, } FOLLOW(E) = FOLLOW(E ) = { ), $} FOLLOW(T) = FOLLOW (T ) = {+, ), $} FOLLOW(F) = {+, , ), $}

自底向上的分析 4.5

4.4 自下而上分析 4.4.1 归约例 S  aABe A  Abc | b B  d

4.4 自下而上分析 4.4.1 归约例 S  aABe A  Abc | b B  d abbcde（读入ab） a b

4.4 自下而上分析 4.4.1 归约例 S  aABe A  Abc | b B  d abbcde aAbcde（归约） a A

4.4 自下而上分析 4.4.1 归约例 S  aABe A  Abc | b B  d abbcde aAbcde（再读入bc）

4.4 自下而上分析 4.4.1 归约例 S  aABe A  Abc | b B  d abbcde aAbcde
aAde（归约） a b A c

4.4 自下而上分析 4.4.1 归约例 S  aABe A  Abc | b B  d abbcde aAbcde
aAde（再读入d） a b A d c

4.4 自下而上分析 4.4.1 归约例 S  aABe A  Abc | b B  d abbcde aAbcde aAde

aABe(再读入e) e a b A d c B

S rm aABe rm aAde rm aAbcde rm abbcde
4.4 自下而上分析 4.4.1 归约例 S  aABe A  Abc | b B  d abbcde aAbcde aAde aABe S S rm aABe rm aAde rm aAbcde rm abbcde S e a b A d c B

句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步
4.4 自下而上分析 4.4.2 句柄句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步 S  aABe A  Abc | b B  d S rm aABe rm aAde rm aAbcde rm abbcde 句柄的右边仅含终结符如果文法二义，那么句柄可能不唯一

4.4 自下而上分析例句柄不唯一 E  E + E | E  E | (E ) | id

4.4 自下而上分析例句柄不唯一 E  E + E | E  E | (E ) | id E rm E  E rm E  E + E rm E  E + id3 rm E  id2 + id3 rm id1  id2 + id3

4.4 自下而上分析例句柄不唯一 E  E + E | E  E | (E ) | id E rm E  E E rm E + E rm E  E + E rm E + id3 rm E  E + id3 rm E  E + id3 rm E  id2 + id3 rm E  id2 + id3 rm id1  id2 + id3 rm id1  id2 + id3 在句型E  E + id3中，句柄不唯一

4.4 自下而上分析 4.4.3 用栈实现移进归约分析先通过来了解移进归约分析的工作方式
移进归约分析器在分析输入串id1  id2 + id3时的动作序列来了解移进归约分析的工作方式

4.4 自下而上分析栈输入动作 $ id1  id2 + id3$

4.4 自下而上分析栈输入动作 $ id1  id2 + id3$ 移进

4.4 自下而上分析栈输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$

4.4 自下而上分析栈输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约

输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E

输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$

输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$

输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE

输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$

输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3

输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E

输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约

输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约按E  EE归约

输入动作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约按E  EE归约接受

要想很好地使用移进归约方式，尚需解决一些问题
4.4 自下而上分析要想很好地使用移进归约方式，尚需解决一些问题如何决策选择移进还是归约进行归约时，确定右句型中将要归约的子串进行归约时，如何确定选择哪一个产生式

4.4 自下而上分析 4.4.4 移进归约分析的冲突 1、移进归约冲突例 stmt  if expr then stmt | if expr then stmt else stmt | other 如果移进归约分析器处于格局栈输入 … if expr then stmt else … $

4.4 自下而上分析 2、归约归约冲突由A(I, J)开始的语句栈输入 … id ( id , id )… 归约成expr还
stmt  id (parameter_list) | expr = expr parameter_list  parameter_list, parameter | parameter parameter  id expr  id (expr_list) | id expr_list  expr_list, expr | expr 由A(I, J)开始的语句栈输入 … id ( id , id )… 归约成expr还是parameter ?

4.4 自下而上分析 2、归约归约冲突 stmt  id (parameter_list) | expr = expr
parameter_list  parameter_list, parameter | parameter parameter  id expr  id (expr_list) | id expr_list  expr_list, expr | expr 由A(I, J)开始的语句(词法分析查符号表,区分第一个id) 栈输入 … procid ( id , id )… 需要修改上面的文法

4.4 自下而上分析 2、归约归约冲突 stmt  procid (parameter_list) | expr = expr
parameter_list  parameter_list, parameter | parameter parameter  id expr  id (expr_list) | id expr_list  expr_list, expr | expr 由A(I, J)开始的语句(词法分析查符号表,区分第一个id) 栈输入 … procid ( id , id )…

为字母表{a,b}上的下列每个语言设计一个文法
练习为字母表{a,b}上的下列每个语言设计一个文法每个a后面至少有一个b的所有串 a和b的个数相等的所有串

练习构造下面LL(1)文法的分析表 D->TL T->int|real L->id R R->, id R | ε

练习构造下面文法的LL(1)分析表 S-aBS|bAS|ε A->bAA|a B->aBB|b

练习下面文法是否是LL(1)文法？说明理由。 S->AB|PQx A->xy B->bc P->dP|ε
Q->aQ|ε

自上而下分析 4.4.

Similar presentations

Presentation on theme: "自上而下分析 4.4."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

自上而下分析 4.4.

Similar presentations

Presentation on theme: "自上而下分析 4.4."— Presentation transcript:

Similar presentations

About project

反馈