第四章 语法分析(2)

null第四章 语法分析(2)*第四章 语法分析(2)4.4 自顶向下语法分析4.4 自顶向下语法分析*4.4 自顶向下语法分析自顶向下(top-down)的语法分析算法是通过最左推导来分析输入的单词序列(tokens) 自顶向下的分析算法有两类 递归下降分析(recursive-descent parsing) LL(1)分析(LL(1) parsing)例4.14 id+id*id的语法分析树构造过程*例4.14 id+id*id的语法分析树构造过程对应文法 E  TE E  +TE |  T  FT  T  *FT |  F  ( E ) | id null*null*4.4.1 递归下降语法分析的一般方法*4.4.1 递归下降语法分析的一般方法为输入tokens寻找最左推导。 递归下降分析的基本方法 将一个非终结符A的文法规则看作识别A的过程的定义。 A的文法规则的右部指示过程的代码结构 匹配文法规则中出现的终结符a：match(a) 调用文法规则中出现的非终结符非终结符对应的典型过程*非终结符对应的典型过程例4.15 文法*考虑文法S  cAd A  ab | a 为输入串w = cad 建立分析树。例4.15 文法缺点*缺点不能处理左递归 复杂的回溯技术 回溯导致语义工作推倒重来 难以 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 出错的确切位置 效率低 4.4.2 预测语法分析器 (Predictive Parsing) *4.4.2 预测语法分析器 (Predictive Parsing) 通过改写文法，消除左递归，提取左因子，也许可以得到不带回溯的递归下降分析器。 对A 1 | 2 | …| n，通过观测候选式所推导出的第一个符号，能够选择合适的产生式来扩展 例：stmt  if expr then stmt else stmt | while expr do stmt | begin stmt_list end4.4.4 非递归的预测分析*4.4.4 非递归的预测分析可以使用显式的栈，而不是递归调用来完成分析。成功的自顶向下的分析的一般示意法：*成功的自顶向下的分析的一般示意法：两个基本动作： 利用文法选择A  将栈顶部的非终结符A替换成串。 将栈顶的记号和下一个输入记号匹配。分析栈 输入 动作 $StartSymbol InputString$ … … … … $ $ 接受 例：生成配对括号的文法S  (S) S | *例：生成配对括号的文法S  (S) S | 对串（），下 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 给出自顶向下的分析程序的动作：分析栈 输入 动作 $ S ( ) $ S  (S) S $ S ) S ( ( ) $ 匹配 $ S ) S ) $ S   $ S ) ) $ 匹配 $ S $ S   $ $ 接受 自顶向下的分析程序的动作null*算法4.3 非递归预测分析方法*输入：输入符号串w和文法G的分析表M 输出：若wL(G)，则输出w的最左推导； 否则，报告出错信息。 方法：初始状态： $在栈底，S在栈顶； w$在输入缓冲区中。 预测分析程序利用预测分析表M对于输入作出分析。 算法4.3 非递归预测分析方法null*Set ip to point to the first symbol of w$; repeat let X be the top stack symbol and a the symbol pointed to by ip; if X is terminal or $ then if X=a then pop X from the stack and advance ip else error() else /* X is a non-terminal */ if M[X,a] = XY1Y2…Yk then begin pop X from stack; push Yk, Yk-1, … , Y1 onto stack, with Y1 on top output the production XY1Y2…Yk end else error() until X=$ /* stack is empty */Input pointerMay also execute other code based on the production usednull*置ip指向w$的第一个符号 repeat 令X是栈顶符号, a是ip所指向的符号； if X 是一个终结符号或$ then if X=a then 从栈中弹出X，ip指向下一个符号 else error() else /*X是非终结符号*/ if M[X,a]=XY1Y2.. .. Yk then begin 从栈中弹出X; 将 Yk,Yk-1,.. ..,Y1压入栈中，即Y1在栈顶； 输出产生式 XY1Y2.. .. Yk end else error() until X=$ /*栈为空*/图4-14 预测分析程序例4.16 图4-15 文法的分析表M*例4.16 图4-15 文法的分析表MNon-terminalE  TE E  +TE |  T  FT T  *FT |  F  ( E ) | id图4-16 预测分析器在输入id+id*id上的动作 *图4-16 预测分析器在输入id+id*id上的动作 $E $E’T $E’T’F $E’T’id $E’T’ $E’ $E’T+ $E’Tid + id * id$ id + id * id$ id + id * id$ id + id * id$ + id * id$ + id * id$ + id * id$ id * id$ E TE’ T FT’ F  id T’   E’  +TE’ STACKINPUTOUTPUT图4-16 预测分析器在输入id+id*id上的动作 (续)*图4-16 预测分析器在输入id+id*id上的动作 (续)STACKINPUTOUTPUT$E’T’F $E’T’id $E’T’ $E’T’F* $E’T’F $E’T’id $E’T’ $E’ $id * id$ id * id$ * id$ * id$ id$ id$ $ $ $T FT’ F  id T’  *FT’ F  id T’   E’  Leftmost Derivation for the Example*Leftmost Derivation for the ExampleE  TE’  FT’E’  id T’E’  id E’  id + TE’  id + FT’E’  id + id T’E’  id + id * FT’E’  id + id * id T’E’  id + id * id E’  id + id * id已经扫描过的输入符号加上栈中的文法符号(from top to bottom)构成该推导的左句型。How to construct the Parsing Table M?*How to construct the Parsing Table M?1st : Calculate First & Follow for Grammar 2nd: Apply Construction Algorithm for Parsing Table4.4.3 FIRST和FOLLOW函数*4.4.3 FIRST和FOLLOW函数对文法加什么样的限制可以保证没有回溯？ 先定义两个和文法有关的函数 FIRST() FOLLOW(A)FIRST()*FIRST()FIRST()是从推导出的串的起始终结符的集合。 FIRST() = {a |  *a…, aVT} 特别是， *时，规定FIRST() 对A的任何两个不同的选择i 和j，希望有 FIRST(i )  FIRST(j ) =  但有一个前提， FIRST(i )和FIRST(j)都不含FOLLOW(A)*FOLLOW(A)FOLLOW(A)是在所有句型中紧跟在A后面的终结符集合。 FOLLOW(A) = {a|S * …Aa…，a  VT} S * Aa 约定：如果A是某个句型的最右符号（S*A），那么$属于FOLLOW(A) 计算FIRST(X)*计算FIRST(X)若XVT，则FIRST(X) = {X}。 若X  ，则将 加入FIRST(X)。 若XVN，且X Y1Y2…Yk ，则 将FIRST(Y1)加入FIRST(X) 若Y1* ，将FIRST(Y2)加入FIRST(X)； 若Y2* ，将FIRST(Y3)加入FIRST(X)； …… 若Yk-1* ，将FIRST(Yk)加入FIRST(X)； 若对所有的j=1,2,…,k, Yj* ，将加入FIRST(X)；计算FOLLOW(A)*计算FOLLOW(A)给定一个非终结符号A，则集合FOLLOW(A)由终结符号或$组成，定义如下： 若A是文法开始符号，则$在FOLLOW(A)中； 若存在产生式A  B ，则FIRST()-{}在Follow(B)中； 若存在产生式A  B或A  B，且*，则FOLLOW(B)包括FOLLOW(A)。 (若A  B，则所有包含A的串中，A可以被B代替)null*注意： $标记输入结束。 永远也不是FOLLOW集合中的元素。 FOLLOW仅针对非终结符定义。 例4.19　已知文法产生式：*例4.19　已知文法产生式：S  iEtSS’ | a S’  eS |  E  bFIRST(S) = {i, a} FIRST(S’) = {e, } FIRST(E) = {b}FOLLOW(S) 包含$； S  iEtSS’，将FIRST(S’)–{}即{e}加入 FOLLOW(S) S’  eS，将FOLLOW(S’)加入FOLLOW(S) S  iEtSS’ ，将FOLLOW(S)加入FOLLOW(S’) 因此，有FOLLOW(S’) = FOLLOW(S) ={e, $ } FOLLOW(E) = {t}例4.17 计算FIRST集和FOLLOW集*E  TE E  + TE |  T  FT T  * FT |  F  (E) | id例4.17 计算FIRST集和FOLLOW集FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E) = {+, } FRIST(T) = {*, } FOLLOW(E) = FOLLOW(E) = { ), $} FOLLOW(T) = FOLLOW (T) = { +, ), $} FOLLOW(F) = {+, *, ), $} 4.4.6 预测分析表的构造*4.4.6 预测分析表的构造算法4.4 预测分析表的构造 输入：文法G 输出：分析表M 方法： （1）对文法的每个产生式A   ，执行(2)和(3)。 （2）对FIRST()的每个终结符a，把A加入M[A, a]。 （3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$），把A  加入M[A, b]。 （4）M的其它没有定义的条目都是error。例4.38*例4.38FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E) = {+, } FRIST(T) = {*, } FOLLOW(E) = FOLLOW(E) = { ), $} FOLLOW(T) = FOLLOW (T) = { +, ), $} FOLLOW(F) = {+, *, ), $} E  TE E  + TE |  T  FT T  * FT |  F  (E) | id4.4.7 LL(1)文法*4.4.7 LL(1)文法L: Scan input from Left to Right L : Construct a Leftmost Derivation 1 : Use “1” input symbol as lookahead in conjunction with stack to decide on the parsing action 分析表中没有多重定义的表目的文法称为LL(1)文法。例4.19 多重定义的条目 *例4.19 多重定义的条目 S  iEtSS | a S  eS |  E  bFIRST(S) = { i, a } FIRST(S) = { e,  } FIRST(E) = { b } FOLLOW(S) = FOLLOW(S) ={e, $ } FOLLOW(E) = {t}null*该文法是具有二义性的：遇到e(else)时不知该选择哪个产生式。 消除二义性 可以只选择S  eS ，遵循与e最近的t(then)配对的原则 LL(1)文法*LL(1)文法LL(1)文法中的任何两个产生式A  |  都满足下列条件： FIRST( )  FIRST( ) =  不存在终结符a，使得 和 导出的串都以a开始。 若 *  ，那么FIRST()  FOLLOW(A) =  和 至多一个能导出空串 如果导出空串，那么不能导出以FOLLOW(A)中终结符开始的任何串。LL(1)文法*LL(1)文法LL(1)文法具有的特殊性质 没有公共左因子 不是二义的 不含左递归4.4.8 出错恢复（Error Recovery）*4.4.8 出错恢复（Error Recovery）词法错误 如标识符、关键字或算符的拼写错 语法错误 如算术表达式的括号不配对 语义错误 如算符作用于不相容的运算对象 逻辑错误 如无穷的递归调用分析器对错误处理的基本目标*分析器对错误处理的基本目标清楚而准确地报告错误的出现 迅速地从每个错误中恢复过来，以便诊断后面的错误，并尽量少出现伪错误 不应该使正确程序的处理速度降低太多 非递归预测分析在什么场合下发现错误*栈顶的终结符和下一个输入符号不匹配 栈顶是非终结符A，输入符号是a，而M[A , a]是空白– No allowable actions非递归预测分析在什么场合下发现错误Panic Mode Recovery(应急方式)*Panic Mode Recovery(应急方式)非递归预测分析采用紧急方式的错误恢复，发现错误时，分析器抛弃一些输入记号，直到输入记号属于某个指定的同步记号集合为止。选择同步记号集合的启发式方法*选择同步记号集合的启发式方法把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合中。 if expr then （then是expr的一个同步记号）选择同步记号集合的启发式方法*选择同步记号集合的启发式方法把高层结构的开始符号加到低层结构的同步记号集合中。 assign-stmt := expr ; if … （赋值语句的开始符号作为表达式的同步符号，以免遗漏分号时忽略一大段程序。）选择同步记号集合的启发式方法*选择同步记号集合的启发式方法把FIRST(A)的终结符加入A的同步记号集合。 如果A * ，可以将产生空串的产生式作为默认选择 如果栈顶的终结符不能被匹配，弹出该记号，相当于所有其它记号都在同步记号集合中。Revised Parsing Table / Example*Revised Parsing Table / ExamplesynchFrom Follow sets. Pop stack entry – T or NTSkip input symbol习题*习题P126 4.3.1 P136 4.4.3