自上而下分析4.4.ppt-得力文库

资源描述

《自上而下分析4.4.ppt》由会员分享，可在线阅读，更多相关《自上而下分析4.4.ppt（56页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、自上而下分析4.4,上节课重点,上下文无关文法的定义，四元组的构成推导，最左推导，最右推导形式语言与文法左递归提取左公因子消除二义性自上而下分析LL(1)文法FIREST函数FOLLOW函数,4.3 自上而下分析,4.3.1 自上而下分析的一般方法例文法S aCbC cd | c为输入串w = acb建立分析树,不能处理左递归,4.3 自上而下分析,不能处理左递归的例子算术表达文法E E + T | TT T F | FF ( E ) | id,E,4.3 自上而下分析,4.3.1 自上而下分析的一般方法例文法S aCbC cd | c为输入串w = acb建立分析树,不能处理左递归、复杂的

2、回溯技术,4.3 自上而下分析,4.3.1 自上而下分析的一般方法例文法S aCbC cd | c为输入串w = acb建立分析树,不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来,4.3 自上而下分析,4.3.1 自上而下分析的一般方法例文法S aCbC cd | c为输入串w = acb建立分析树,不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置,4.3 自上而下分析,4.3.1 自上而下分析的一般方法例文法S aCbC cd | c为输入串w = acb建立分析树,不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效

3、率低,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 *

4、 Aa，aVT如果A是某个句型的最右符号，那么$属于FOLLOW(A),4.3 自上而下分析,LL(1)文法任何两个产生式A | 都满足下列条件： FIRST( ) FIRST( ) = 若 * ，那么FIRST() FOLLOW(A) = 例如, 对于下面文法，面临a时，第2步推导不知用哪个产生式S A BA a b | a FIRST(ab) FOLLOW(A) B a CC ,4.3 自上而下分析,LL(1)文法任何两个产生式A | 都满足下列条件： FIRST( ) FIRST( ) = 若 * ，那么FIRST() FOLLOW(A) = LL(1)文法有一些明显的性质没有公共左因子

5、不是二义的不含左递归,4.3 自上而下分析,计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或可以被加入到FIRST(X)如果X是终结符，FIRST(X)= X,4.3 自上而下分析,计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或可以被加入到FIRST(X)如果X是终结符，FIRST(X)= X如果XY1Y2Yk, 且a在FIRST(Yi)集合中，并且Y1 * , Y2 * , , Yi-1 * ，则将a插入到FIRST(X)中。,4.3 自上而下分析,计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或可以被加入到FIRST(X)如果X是终结

6、符，FIRST(X)= X如果XY1Y2Yk, 且a在FIRST(Yi)集合中，并且Y1 * , Y2 * , , Yi-1 * ，则将a插入到FIRST(X)中。如果X 是一个产生式，则将插入到FIRST(X)中。,4.3 自上而下分析,计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A)将$放到FOLLOW(S)中，S是开始符，$是输入右端的结束标记,4.3 自上而下分析,计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A)将$放到FOLLOW(S)中，S是开始符，$是输入右端的结束标记

7、如果存在AB，那么FIRST()中非的所有符号都在FOLLOW(B)中,4.3 自上而下分析,计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A)将$放到FOLLOW(S)中，S是开始符，$是输入右端的结束标记如果存在AB，那么FIRST()中非的所有符号都在FOLLOW(B)中如果存在AB或AB，且FIRST()包含，则FOLLOW(A)中的所有符号都在FOLLOW(B)中。,4.3 自上而下分析,例 E TE E + TE | T FT T FT | F (E) | idFIRST(E) = FIRST(T) = FIRST(F) = (

8、 , id FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = FOLLOW(E ) = ), $FOLLOW(T) = FOLLOW (T ) = +, ), $FOLLOW(F) = +, , ), $,4.3 自上而下分析,4.3.3 递归下降的预测分析为每一个非终结符写一个分析过程这些过程可能是递归的例type simple | id | array simple of typesimple integer | char | num dotdot num,4.3 自上而下分析,一个辅助过程void match (terminal t) if (lookah

9、ead = 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( )

10、;,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 非递归的预测分析,4.3 自上而下

11、分析,分析表的一部分,4.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,4.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,4.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,4.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,4.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,4.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,4.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,4.3 自上而下分

14、VPNP 我IM 请VP V V 上 | 开N 课|门,S,我,上,课,4.3 自上而下分析,4.4.4 非递归的预测分析算法初始时分析器的格局是： $在栈里，其中是开始符号并且在栈顶；$ 在输入缓冲区主程序,4.3 自上而下分析,4.4.4 非递归的预测分析预测分析程序根据当前的栈顶符号和输入符号a决定分析器的动作，它有四种可能：如果 a $，分析器宣告分析完全成功而停止如果 a $ ，分析器弹出栈顶符号，并推进输入指针，指向下一个符号。如果是终结符但不是a，则分析器报告出错，调用错误恢复例程如果是非终结符，程序访问分析表,4.3 自上而下分析,4.3 自上而下分析,4.4.5 构造预测分析

15、表（1）对文法的每个产生式A ，执行(2)和(3)（2）对FIRST()的每个终结符a，把A 加入MA, a（3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$）, 把A 加入MA, b（4）M中其它没有定义的条目都是error,4.3 自上而下分析,4.4.5 构造预测分析表例：E TE E + TE | T FT T FT | F (E) | idFIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = FOLLOW(E ) = ), $FOLLOW(T) = F

展开阅读全文