自上而下分析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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 自上而下 分析 4.4
限制150内