第四章 语法分析-自顶向下分析方法.ppt

第四章 语法分析——自顶向下分析方法 主要内容： 自顶向下语法分析的基本思想 三个重要的集合 自顶向下分析的条件 递归下降语法分析 LL(1)语法分析 4.1 语法分析程序介绍 语法分析器和识别器 语法分析的功能 语法错误类别 语法错误的处理 自顶向下分析的基本思想 语法分析器和识别器 语法分析器的功能： 语法错误类别 程序的开始符，语句（表达式）的开始符 （后继符）错 ?? 标识符（常量）错：该出现时未出现 ???? 括号类错误：不匹配 ??分隔符错：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的出现。 三个集合的定义 First(?)={ a ?VT | ??* a......} ? (if ??*? then {?} else ?) Follow(A)={ a ?VT | S?+ ....Aa..... } ?(if S?*...A then {#} else ?) 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:对所有A?VN，令Follow(A):={ }；对开始符S, 令Follow(S):={# }； 2:若有产生式A→xBy， 如果??First(y) 则： Follow(B):= First(y) 否则 Follow(B):=(First(y)－{?}) ? Follow(A) 3:重复2和3，直至对所有A?VN，Follow(A)收 敛为止。 计算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’) =