自上而下分析 4.4.

自上而下分析 4.4

上节课重点上下文无关文法的定义，四元组的构成推导，最左推导，最右推导形式语言与文法左递归提取左公因子消除二义性自上而下分析
LL(1)文法 FIREST函数 FOLLOW函数

4.3 自上而下分析 4.3.1 自上而下分析的一般方法例文法 S  aCb C  cd | c 为输入串w = acb建立分析树
不能处理左递归

4.3 自上而下分析不能处理左递归的例子算术表达文法 E  E + T | T T  T  F | F
F  ( E ) | id E E + T E + T E + T … … …

不能处理左递归、复杂的回溯技术

不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来

不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置

不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效率低

4.3 自上而下分析 4.3.2 LL(1)文法对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数
FIRST( ) = {a |  * a…, a  VT} 特别是， * 时，规定  FIRST( ) 对A的任何两个不同选择i 和j，希望有 FIRST(i )  FIRST(j ) =  若FIRST(i ) 或 FIRST(j )含，还需增加条件

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 自上而下分析非终结符输入符号 id +  . . . E E  TE  E  E   +TE  T
分析表的一部分非终结符输入符号 id +  . . . E E  TE  E  E   +TE  T T  FT  T  T    T   FT  F F  id

4.3 自上而下分析预测分析器接受输入id * id + id的前一部分动作栈输入输出 $E id  id + id$

4.3 自上而下分析栈输入输出 $E id  id + id$ $E T E  TE 
输入输出 $E id  id + id$ $E T E  TE 

4.3 自上而下分析栈输入输出 $E id  id + id$ $E T E  TE  $E T F T  FT 
输入输出 $E id  id + id$ $E T E  TE  $E T F T  FT 

输入输出 $E id  id + id$ $E T E  TE  $E T F T  FT  $E T  id F  id

输入输出 $E id  id + id$ $E T E  TE  $E T F T  FT  $E T  id F  id $E T   id + id$

输入输出 $E id  id + id$ $E T E  TE  $E T F T  FT  $E T  id F  id $E T   id + id$ $E T F  T   FT 

输入输出 $E id  id + id$ $E T E  TE  $E T F T  FT  $E T  id F  id $E T   id + id$ $E T F  T   FT  id + id$

4.3 自上而下分析自然语言例子 S  NP VP | IM VP NP  我 IM  请 VP  V Ｎ V  上 | 开
我　上　课

ＮＰＶＰＶＰＮＰ我　上　课

ＮＰＶＰ我ＶＰ我我　上　课

ＮＰＶＰ我ＶＰ上　课

ＮＰＶＰＶＮ我 N Ｖ上　课

ＮＰＶＰＶＮ我上 N 上上　课

ＮＰＶＰＶＮ我上 N 课

ＮＰＶＰＶＮ我上课课课

ＮＰＶＰＶＮ我上课

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

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

4.3 自上而下分析

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

为字母表{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

反馈