自下而上的语法分析.PPT

上传人:国*** 文档编号:764155 上传时间:2018-10-31 格式:PPT 页数:49 大小:265.50KB
下载 相关 举报
自下而上的语法分析.PPT_第1页
第1页 / 共49页
自下而上的语法分析.PPT_第2页
第2页 / 共49页
自下而上的语法分析.PPT_第3页
第3页 / 共49页
自下而上的语法分析.PPT_第4页
第4页 / 共49页
自下而上的语法分析.PPT_第5页
第5页 / 共49页
点击查看更多>>
资源描述

1、第六章 自下而上的语法分析清华大学计算机系1 自下而上语法分析概述 简单优先分析 算符优先分析2自下而上语法分析概述 As the name suggests, bottom-up parsing begins with a string and tries to backwards to the start symbol by applying the productions in reverse. 也称为移进 -归约分析自底向上的语法分析.VAR ;A BEGIN ENDREAD ( )A VAR A; BEGIN READ(A) END.移进规约接受错误3自下而上语法分析概述 如名字如示

2、,自下而上语法分析试图将一个字符串反向归约至开始符号。 自下而上语法分析比自上而下语法分析更有效率,对语法的限制更少4文法 GS:(1) S aAcBe(2) A b(3) A Ab(4) B da b b c d e步骤 符号栈 输入符号串 动作1) # abbcde# 移进2) #a bbcde# 移进A3) #ab bcde# 归约 (A b)4) #aA bcde# 移进A5) #aAb cde# 归约 (A Ab)6) #aA cde# 移进7) #aAc de# 移进B8) # aAcd e# 归约 (B d)9) #aAcB e# 移进11) #S # 接受S10) #aAcBe

3、 # 归约 (S aAcBe)分析符号串 abbcde是否 GS的句子对输入串 abbcde#的移进 -规约分析过程SaAcBeaAcdeaAbcdeabbcde5自下而上语法分析算法的一般描述Let I = input stringrepeatpick a non-empty substring of Iwhere X is a productionif no such , backtrackreplace one by X in Iuntil I = “S” (the start symbol) or all possibilities are exhausted6算法应考虑的问题 算法是

4、否能够终止? 算法是否快速? 算法是否能够处理所有的情况? 在每一步中如何选择子串进行归约?7 自下而上语法分析的策略:移进 -规约分析; 移进 就是将一个终结符推进栈 归约 就是将 0个或多个符号从栈中弹出,根据产生式将一个非终结符压入栈 移进 -归约过程是自顶向下最右推导的逆过程(规范归约)8规约 T intT + int | 移进T + | int移进int | * int + int移进int * | int + int移进|int * int + intE |规约 E T + ET + E |规约 E TT + T |移进T | + int规约 T int * Tint * T | + int规约 T intint * int | + int文法 GE:E T + E | TT int * T | int | (E)ET E+ int*intTintT9A Shift-Reduce Parse in Detail (1)+ int*int int|int * int + int10

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 重点行业资料库 > 1

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。