- 1、本文档共33页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
编译原理 第四章 语法分析-自顶向下分析方法
第四章 语法分析-自顶向下分析方法 主要内容: 语法分析简介 三个重要的集合 自顶向下分析的条件 递归下降语法分析 LL(1)语法分析 语法分析简介 语法分析的功能 语法错误类别 语法错误的处理 自顶向下分析的基本思想 语法分析器的功能 语法错误类别 1) 程序的开始符,语句(表达式)的开始 符(后继符)错 ?? 2) 标识符(常量)错:该出现时未出现 ???? 3) 括号类错误:不匹配 ??4) 分隔符错:assignment 语法错误处理 要求:报告错误出现的位置 修复错误并继续检查后续部分 执行开销不应太大 处理策略: 1)紧急方式恢复; 2)短语级恢复; 3)出错产生式; 4)全局纠正; Follow集的定义 设G=(VT,VN,S,P)是上下文无关文法,A?VN,S是开始符号,则: Follow(A)={ a ?VT | S?+ ...Aa... } ?(if S?*...A then {#} else ?) 作用:当文法中存在产生式形如:A??时,如果当前的字符属于Follow(A),则用空取代A的出现。 Predict集的定义 Predict(A→?) = First(?) , 当??First(?) = First(?)-{?}?Follow(A) , 当??First(?) 计算First(X)集 对每一文法符号X计算First(X) 若X?VT,First(X)={X} 若X?VN则 First(X)={a| X?a…?PSet,a?VT} 若X?VN,且有产生式X??,则 ?? First(X) 若X?VN,有产生式X?Y1Y2…Yn,且Y1,Y2,…,Yi ?VN,则 当Y1,Y2,…,Yi-1?* ?, 则First(Y1)-{?},First(Y2)-{?},… First(Yi-1)-{?}, First(Yi)都包含在First(X)中。 当Yi ?* ?(i=1,2,…n), 将{?}并入First(X) 中。 计算First(?)集 若符号串?=X1X2…Xn, 当X1,X2,…Xi-1?*?,Xi不能 ?*?,则 First(?)=?1i-1(First(Xj)-{?}) ? First(Xi) 若所有Xi都能?*?,则 First(?)= ?1nFirst(Xj) 计算Follow集 1:对所有B?VN,令Follow(B):={ };对开始符S, 令Follow(S):={# }; 2:若有产生式A→xBy, 如果??First(y) 则: Follow(B):= First(y) 否则 Follow(B):=(First(y)-{?}) ? Follow(A) 3:重复2,直至对所有B?VN,Follow(B)收 敛为止。 计算Predict集 Predict(A→?) = First(?) , 当First(?)不含? = First(?)-{ ?} ? Follow(A) , 当First(?)含? 例子 E? ? T E’ E’ ? + T E’ | ? T ? F T’ T’ ? *F T’ | ? F ? id | ( E ) Predict( E?TE’ ) = first(TE’) = { id , ( } Predict( E’ ?+TE’ ) = first(+TE’) = { + } Predict( E’ ? ? ) = follow(E’) = { ) , # } Predict( T ? FT’ ) = first(FT’) = { id , ( } Predict( T’ ?*FT’ ) = first(*FT’) = { * } Predict( T’ ? ? ) = follow(T’) = { + , ) , # } Predict( F ?id ) = first(id) = { id } Predict( F ?(E) ) = first((E)) = { ( } 递归下降法 递归下降法(Recursive-Des
文档评论(0)