三章语法分析

第三章第三章 语法分析语法分析 本章内容本章内容 上下文无关文法上下文无关文法 自上而下自上而下分析和自下而上分析分析和自下而上分析 围绕分析器的自动生成展开围绕分析器的自动生成展开词词 法法分析器分析器记记 号号取下一个取下一个记号记号源程序源程序分析分析树树前端的前端的其余部分其余部分分析器分析器中间中间表示表示符号表符号表3.1 上下文无关文法上下文无关文法3.1.1 上下文无关文法的定义上下文无关文法的定义正规式能定义一些简单的语言正规式能定义一些简单的语言，能表示给定结构能表示给定结构的固定次数的重复或者没有指定次数的重复的固定次数的重复或者没有指定次数的重复例：例：a (ba)5, a (ba)*正规式不能用于描述配对或嵌套的结构正规式不能用于描述配对或嵌套的结构例例1：配对括号串的集合配对括号串的集合例例2：wcw | w是是a和和b的串的串 3.1 上下文无关文法上下文无关文法 上下文无关文法上下文无关文法是四元组（是四元组（VT , VN , S, P）VT : : 终结符终结符集合集合VN : : 非非终结符终结符集合集合S : : 开始符号，非终结符中的一个开始符号，非终结符中的一个P : :产生式产生式集合，集合， 产生式形式产生式形式 : : A 例例 ( id, +, , , (, ), expr, op, expr, P )expr expr op expr expr (expr)expr expr expr idop + op 3.1 上下文无关文法上下文无关文法 简化表示简化表示expr expr op expr | (expr) | expr | idop + | 简化表示简化表示E E A E | (E ) | E | idA + | 3.1 上下文无关文法上下文无关文法3.1.2 推导推导 把产生式看成重写规则，把符号串中的非终结符把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替用其产生式右部的串来代替 例例 E E + E | E E | (E ) | E | id E E (E) (E + E) (id + E) (id + id) 概念概念 上下文无关语言上下文无关语言、等价的等价的文法、文法、句型句型 记号记号S * 、 S + w 3.1 上下文无关文法上下文无关文法 例例 E E + E | E E | (E ) | E | id 最左最左推导推导E lm E lm (E) lm (E + E) lm (id + E) lm (id + id) 最右最右推导（规范推导）推导（规范推导）E rm E rm (E) rm (E + E) rm (E + id) rm (id + id)3.1 上下文无关文法上下文无关文法3.1.3 分析树分析树 例例 E E + E | E E | (E ) | E | idEE ()EEE+idid3.1 上下文无关文法上下文无关文法3.1.4 二义性二义性E E E E E + E id E E E +E id E + E id E + E id id + E id id + E id id + id id id + id两个不同的最左推导两个不同的最左推导3.1 上下文无关文法上下文无关文法3.1.4 二义性二义性E E E E E + E id E E E +E id E + E id E + E id id + E id id + E id id + id id id + id两棵不同的语法树两棵不同的语法树EEE*+EEidididEEidE*+EEidid3.2 语言和文法语言和文法 文法的优点文法的优点 文法给出了精确的，易于理解的语法说明文法给出了精确的，易于理解的语法说明自动产生高效的分析器自动产生高效的分析器可以给语言定义出层次结构可以给语言定义出层次结构以文法为基础的语言的实现以文法为基础的语言的实现便于语言的修改便于语言的修改 文法的问题文法的问题文法只能描述编程语言的大部分语法，不能描述文法只能描述编程语言的大部分语法，不能描述语言中上下文有关的语法特征语言中上下文有关的语法特征3.2 语言和文法语言和文法 3.2.1 正规式和上下文无关文法的比较正规式和上下文无关文法的比较 正规式正规式(a|b)*ab 文法文法A0 a A0 | b A0 | a A1A1 b A2A2 12开始开始a0abb3.2 语言和文法语言和文法 3.2.2 分离词法分析器理由分离词法分析器理由 为什么要用正规式定义词法为什么要用正规式定义词法 词法规则非常简单，不必用上下文无关文法词法规则非常简单，不必用上下文无关文法对于词法记号，正规式描述简洁且易于理解对于词法记号，正规式描述简洁且易于理解从正规式构造出的词法分析器效率高从正规式构造出的词法分析器效率高3.2 语言和文法语言和文法 从软件工程角度看，词法分析和语法分析的从软件工程角度看，词法分析和语法分析的分离有如下好处分离有如下好处简化设计简化设计编译器的效率会改进编译器的效率会改进编译器的可移植性加强编译器的可移植性加强便于编译器前端的模块划分便于编译器前端的模块划分 3.2 语言和文法语言和文法 能否把词法分析并入到语法分析中，直接从能否把词法分析并入到语法分析中，直接从字符流进行语法分析字符流进行语法分析 若把词法分析和语法分析合在一起，则必须将语若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大言的注解和空白的规则反映在文法中，文法将大大复杂大复杂 注解和空白由自己来处理的分析器，比注解和空注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多格已由词法分析器删除的分析器要复杂得多3.2 语言和文法语言和文法 3.2.3 验证文法产生的语言验证文法产生的语言G : S (S) S | L(G) = 配对的括号串的集合配对的括号串的集合3.2 语言和文法语言和文法 3.2.3 验证文法产生的语言验证文法产生的语言G : S (S) S | L(G) = 配对的括号串的集合配对的括号串的集合 按推导步数进行归纳按推导步数进行归纳：推出的是：推出的是配对括号串配对括号串归纳基归纳基础：础： S 归纳假设：归纳假设：少于少于n步的推导都产生配对的括号串步的推导都产生配对的括号串 归纳步骤：归纳步骤：n步的最左推导步的最左推导如下：如下：S (S)S * (x) S * (x) y3.2 语言和文法语言和文法 3.2.3 验证文法产生的语言验证文法产生的语言G : S (S) S | L(G) = 配对的括号串的集合配对的括号串的集合 按串长进行归纳按串长进行归纳：配对括号串可由配对括号串可由S推出推出归纳基归纳基础：础： S 归纳假设：归纳假设：长度小于长度小于2n的都可以从的都可以从S推导出来推导出来 归纳步骤：归纳步骤：考虑长度为考虑长度为2n(n 1)的的w = (x) yS (S)S * (x) S * (x) y3.2 语言和文法语言和文法 3.2.4 适当的表达式文法适当的表达式文法 用一种层次观点看待表达式用一种层次观点看待表达式id id (id+id) + id id + id3.2 语言和文法语言和文法 3.2.4 适当的表达式文法适当的表达式文法 用一种层次观点看待表达式用一种层次观点看待表达式id id (id+id) + id id + idid id (id+id) 文法文法expr expr + term | termterm term factor | factor factor id | (expr)3.2 语言和文法语言和文法 expr expr + term | termterm term factor | factor factor id | (expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid + id id分析树分析树 id id id分析树分析树 3.2 语言和文法语言和文法 3.2.5 消除二义性消除二义性stmt if expr then stmt | if expr then stmt else stmt | other 句型：句型：if expr then if expr then stmt else stmt 两个最左推导：两个最左推导：stmt if expr then stmt if expr then if expr then stmt else stmtstmt if expr then stmt else stmt if expr then if expr then stmt else stmt 3.2 语言和文法语言和文法 无二义的文法无二义的文法stmt matched _stmt | unmatched_stmtmatched_stmt if expr then matched_stmt else matched_stmt | otherunmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt3.2 语言和文法语言和文法 3.2.6 消除左递归消除左递归 文法文法左递归左递归A+A 直接左递归直接左递归AA | |b b 串的特点串的特点 b . . . b . . . 消除直接左递归消除直接左递归A b b A A A | 3.2 语言和文法语言和文法 例例 算术表达文法算术表达文法E E + T | T（ T + T . . . + T ）T T F | F（ F F . . . F ）F ( E ) | id消除左递归后文法消除左递归后文法 E TE E + TE | T FT T F T | F ( E ) | id3.2 语言和文法语言和文法 非直接左递归非直接左递归S Aa | b A Sd | 先变换成直接左递归先变换成直接左递归S Aa | bA Aad | bd | 再消除左递归再消除左递归S Aa | bA bd A | A A adA | 3.2 语言和文法语言和文法 3.2.7 提左因子提左因子 有左因子的文法有左因子的文法A bb1 | bb2 提左因子提左因子A A A b b1 | b b2 3.2 语言和文法语言和文法 例例 悬空悬空else的文法的文法 stmt if expr then stmt else stmt | if expr then stmt | other提左因子提左因子stmt if expr then stmt optional_else_part | otheroptional_else_part else stmt | 3.2 语言和文法语言和文法 3.2.8 非上下文无关的语言构造非上下文无关的语言构造 L1 = wcw | w属于属于(a | b)*标识符的声明应先于其引用的抽象标识符的声明应先于其引用的抽象 L2 = anbmcndm | n 0, m 0 形参个数和实参个数应该相同的抽象形参个数和实参个数应该相同的抽象 L3 = anbncn | n 0 早先排版描述的一个现象的抽象早先排版描述的一个现象的抽象b e g i n：5个字母键，个字母键，5个回退键，个回退键，5个下划线键个下划线键3.2 语言和文法语言和文法 L1 = wcwR | w (a|b)* S aSa | bSb | c L2 = anbmcmdn | n 1, m 1S aSd | aAdA bAc | bc L 2 = anbncmdm | n 1，m 1S ABA aAb | abB cBd | cd3.2 语言和文法语言和文法 L3 =anbn | n 1S aSb | ab L3 是不能用正规式描述的语言的一个范例是不能用正规式描述的语言的一个范例 若存在接受若存在接受L3 的的DFA D，状态数为，状态数为k个个 设设D读完读完 , a, aa, , ak 分别到达状态分别到达状态s0, s1, , sk至少有两个状态相同，例如是至少有两个状态相同，例如是si和和sj，则，则ajbi属于属于L3 sifs0标记为标记为ai的路径的路径标记为标记为bi的路径的路径标记为标记为aj i的路径的路径 3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 13.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 短语文法短语文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但，但S 可以例外可以例外 短语文法短语文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但，但S 可以例外可以例外 短语文法、上下文有关文法短语文法、上下文有关文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但，但S 可以例外可以例外 2型文法：型文法：A b b，A VN , b b (VN VT)* 短语文法、上下文有关文法短语文法、上下文有关文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但，但S 可以例外可以例外 2型文法：型文法：A b b，A VN , b b (VN VT)* 短语文法、上下文有关文法、上下文无关文短语文法、上下文有关文法、上下文无关文法法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但，但S 可以例外可以例外 2型文法：型文法：A b b，A VN , b b (VN VT)* 3型文法：型文法：A aB或或A a，A, B VN , a VT 短语文法、上下文有关文法、上下文无关文短语文法、上下文有关文法、上下文无关文法法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但，但S 可以例外可以例外 2型文法：型文法：A b b，A VN , b b (VN VT)* 3型文法：型文法：A aB或或A a，A, B VN , a VT 短语文法、上下文有关文法、上下文无关文短语文法、上下文有关文法、上下文无关文法、正规文法法、正规文法3.2 语言和文法语言和文法 例例 L3anbncn| n 1的上下文有关文法的上下文有关文法S aSBC S aBC CB BCaB ab bB bbbC bccC ccanbncn的推导过程如下：的推导过程如下：S * an-1S(BC)n 1用用S aSBC n-1次次S + an(BC)n 用用S aBC 1次次S + anBnCn用用CB BC交换相邻的交换相邻的CBS + anbBn 1Cn用用aB ab 1次次S + anbnCn 用用bB bb n-1次次S + anbncCn-1用用bC bc 1次次S + anbncn用用cC cc n-1次次3.3 自上而下分析自上而下分析 3.3.1 自上而下分析的一般方法自上而下分析的一般方法 例例 文法文法 S aCb C cd | c为输入串为输入串w = acb建立分析树建立分析树SaCbSaCbcdSaCbc不能处理不能处理左递归左递归3.3 自上而下分析自上而下分析 不能处理左递归的例子不能处理左递归的例子 算术表达文法算术表达文法E E + T | TT T F | FF ( E ) | idEE+TE+TE+T 3.3 自上而下分析自上而下分析 3.3.1 自上而下分析的一般方法自上而下分析的一般方法 例例 文法文法 S aCb C cd | c为输入串为输入串w = acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术3.3 自上而下分析自上而下分析 3.3.1 自上而下分析的一般方法自上而下分析的一般方法 例例 文法文法 S aCb C cd | c为输入串为输入串w = acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导回溯导致语义工作推倒重来致语义工作推倒重来3.3 自上而下分析自上而下分析 3.3.1 自上而下分析的一般方法自上而下分析的一般方法 例例 文法文法 S aCb C cd | c为输入串为输入串w = acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导回溯导致语义工作推倒重来致语义工作推倒重来、难以报告出错的确切难以报告出错的确切位置位置3.3 自上而下分析自上而下分析 3.3.1 自上而下分析的一般方法自上而下分析的一般方法 例例 文法文法 S aCb C cd | c为输入串为输入串w = acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导回溯导致语义工作推倒重来致语义工作推倒重来、难以报告出错的确切难以报告出错的确切位置位置、效率低效率低3.3 自上而下分析自上而下分析 3.3.2 LL(1)文法文法 对文法加什么样的限制可以保证没有对文法加什么样的限制可以保证没有回溯回溯？ 先定义两个和文法有关的函数先定义两个和文法有关的函数 FIRST( ) = a | * a, a VT 特别是，特别是， * 时，规定时，规定 FIRST( ) 对对A的任何两个不同选择的任何两个不同选择 i 和和 j，希望有，希望有FIRST( i ) FIRST( j ) = 若若FIRST( i ) 或或 FIRST( j )含含 ，还需增加条件，还需增加条件3.3 自上而下分析自上而下分析 3.3.2 LL(1)文法文法 对文法加什么样的限制可以保证没有对文法加什么样的限制可以保证没有回溯回溯？ 先定义两个和文法有关的函数先定义两个和文法有关的函数 FIRST( ) = a | * a, a VT 特别是，特别是， * 时，规定时，规定 FIRST( ) FOLLOW(A) = a | S * Aa，a VT如果如果A是某个句型的最右符号，那么是某个句型的最右符号，那么$属于属于FOLLOW(A) 3.3 自上而下分析自上而下分析 LL(1)文法文法任何两个产生式任何两个产生式A | b b 都满足下列条件：都满足下列条件： FIRST( ) FIRST(b b ) = 若若b b * ，那么，那么FIRST( ) FOLLOW(A) = 例如例如, 对于下面文法，面临对于下面文法，面临a时，第时，第2步推导不步推导不知用哪个产生式知用哪个产生式S A BA a b | a FIRST(ab) FOLLOW(A) B a CC 3.3 自上而下分析自上而下分析 LL(1)文法文法任何两个产生式任何两个产生式A | b b 都满足下列条件：都满足下列条件： FIRST( ) FIRST(b b ) = 若若b b * ，那么，那么FIRST( ) FOLLOW(A) = LL(1)文法有一些明显的性质文法有一些明显的性质没有公共左因子没有公共左因子不是二义的不是二义的不含左递归不含左递归3.3 自上而下分析自上而下分析 例例 E TE E + TE | T FT T FT | F (E) | idFIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = FOLLOW(E ) = ), $FOLLOW(T) = FOLLOW (T ) = +, ), $FOLLOW(F) = +, , ), $ 3.3 自上而下分析自上而下分析 3.3.3 递归下降的预测分析递归下降的预测分析为每一个非终结符写一个分析过程为每一个非终结符写一个分析过程这些过程可能是递归的这些过程可能是递归的 例例type simple | id | array simple of typesimple integer | char | num dotdot num3.3 自上而下分析自上而下分析 一个辅助过程一个辅助过程void match (terminal t) if (lookahead = t) lookahead = nextToken( );else error( );3.3 自上而下分析自上而下分析 void type( ) if ( (lookahead = integer) | (lookahead = char) | (lookahead = num) )simple( );else if ( lookahead = ) match(); match(id);else if (lookahead = array) match(array); match( ); simple( );match( ); match(of ); type( );else error( ); type simple | id | array simple of type3.3 自上而下分析自上而下分析 void simple( ) if ( lookahead = integer) match(integer);else if (lookahead = char) match(char);else if (lookahead = num) match(num); match(dotdot); match(num);else error( ); simple integer | char | num dotdot num3.3 自上而下分析自上而下分析3.3.4 非递归的预测分析非递归的预测分析a + b $输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈3.3 自上而下分析自上而下分析非终非终结符结符输输 入入 符符 号号 id + . . .E E TE E E +TE T T FT T T T FT 分析表的一部分分析表的一部分3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出 $E id id + id$ 预测预测分析器接受输入分析器接受输入id * id + id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出 $E id id + id$ $E T id id + id$ E TE 预测预测分析器接受输入分析器接受输入id * id + id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT 预测预测分析器接受输入分析器接受输入id * id + id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT $E T id id id + id$ F id 预测预测分析器接受输入分析器接受输入id * id + id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT $E T id id id + id$ F id $E T id + id$ 预测预测分析器接受输入分析器接受输入id * id + id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT $E T id id id + id$ F id $E T id + id$ $E T F id + id$ T FT 预测预测分析器接受输入分析器接受输入id * id + id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT $E T id id id + id$ F id $E T id + id$ $E T F id + id$ T FT $E T F id + id$ 预测预测分析器接受输入分析器接受输入id * id + id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT $E T id id id + id$ F id $E T id + id$ $E T F id + id$ T FT $E T F id + id$ $E T id id + id$ F id 预测预测分析器接受输入分析器接受输入id * id + id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析3.3.5 构造预测分析表构造预测分析表 （1）对文法的每个产生式）对文法的每个产生式A ，执行，执行(2)和和(3)（2）对）对FIRST( )的每个终结符的每个终结符a，把把A 加入加入MA, a（3）如果）如果 在在FIRST( )中，对中，对FOLLOW(A)的每个终的每个终结符结符b（包括（包括$）, 把把A 加入加入MA, b（4）M中中其它没有定义的条目都是其它没有定义的条目都是error3.3 自上而下分析自上而下分析非终非终结符结符 输输 入入 符符 号号 other b else . . .stmt stmt other e_part e_part else stmte_part expr expr b 多重定义的条目多重定义的条目3.3 自上而下分析自上而下分析非终非终结符结符 输输 入入 符符 号号 other b else . . .stmt stmt other e_part e_part else stmtexpr expr b 消去多重定义消去多重定义3.3 自上而下分析自上而下分析3.3.6 预测分析的错误恢复预测分析的错误恢复1、先对编译器的错误处理做一个概述先对编译器的错误处理做一个概述 词法错误，如标识符、关键字或算符的拼写词法错误，如标识符、关键字或算符的拼写错错 语法错误，如算术表达式的括号不配对语法错误，如算术表达式的括号不配对 语义错误，如算符作用于不相容的运算对象语义错误，如算符作用于不相容的运算对象 逻辑错误，如无穷的递归调用逻辑错误，如无穷的递归调用3.3 自上而下分析自上而下分析2、分析器对错误处理的基本目标、分析器对错误处理的基本目标 清楚而准确地报告错误的出现，并尽量少出清楚而准确地报告错误的出现，并尽量少出现现伪错误伪错误 迅速地从每个错误中恢复过来，以便诊断后迅速地从每个错误中恢复过来，以便诊断后面的错误面的错误 它不应该使正确程序的处理速度降低太多它不应该使正确程序的处理速度降低太多 3.3 自上而下分析自上而下分析3、非递归预测分析在什么场合下发现错误、非递归预测分析在什么场合下发现错误栈顶的终结符和下一个输入符号不匹配栈顶的终结符和下一个输入符号不匹配a + b $输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈3.3 自上而下分析自上而下分析3、非递归预测分析在什么场合下发现错误、非递归预测分析在什么场合下发现错误栈顶是非终结符栈顶是非终结符A，输入符号是，输入符号是a，而，而MA , a是是空白空白a + b $输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈3.3 自上而下分析自上而下分析4、非递归预测分析：采用、非递归预测分析：采用紧急方式的错误恢复紧急方式的错误恢复发现错误时，分析器每次抛弃一个输入记号，直发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定的同步记号集合为止到输入记号属于某个指定的同步记号集合为止5、同步、同步词法分析器当前提供的记号流能够构成的语法构词法分析器当前提供的记号流能够构成的语法构造，正是语法分析器所期望的造，正是语法分析器所期望的不同步的例子不同步的例子语法分析器期望剩余的前缀构成过程调用语句，语法分析器期望剩余的前缀构成过程调用语句，而实际剩余的前缀形成赋值语句而实际剩余的前缀形成赋值语句3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合if expr then stmt（then和分号等记号是和分号等记号是expr的同步记号）的同步记号）3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中a = expr; if (语句的开始符号作为表达式的同步记号，以免表语句的开始符号作为表达式的同步记号，以免表达式出错又遗漏分号时忽略达式出错又遗漏分号时忽略if语句等一大段程序语句等一大段程序)3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中把把FIRST(A)的终结符加入的终结符加入A的同步记号集合的同步记号集合a = expr; , if （语句的开始符号作为语句的同步符号，以免多出（语句的开始符号作为语句的同步符号，以免多出一个逗号时会把一个逗号时会把if语句忽略了）语句忽略了）3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中把把FIRST(A)的终结符加入的终结符加入A的同步记号集合的同步记号集合如果非终结符可以产生空串，若出错时栈顶是这如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式样的非终结符，则可以使用推出空串的产生式3.3 自上而下分析自上而下分析非终非终结符结符 输输 入入 符符 号号 id+ . . .EETE E E+TE TTFT T 出错出错T T FT 例例 栈顶为栈顶为T ，面临，面临id时出错时出错3.3 自上而下分析自上而下分析非终非终结符结符 输输 入入 符符 号号 id+ . . .EETE E E+TE TTFT T 出错，出错，用用T T T FT T 可以产生空串，报错并用可以产生空串，报错并用T 3.3 自上而下分析自上而下分析同步记号集合的选择同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层结构的开始符号加到低层结构的同步记号把高层结构的开始符号加到低层结构的同步记号集合中集合中把把FIRST(A)的终结符加入的终结符加入A的同步记号集合的同步记号集合如果非终结符可以产生空串，若出错时栈顶是这如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式样的非终结符，则可以使用推出空串的产生式如果终结符在栈顶而不能匹配，弹出此终结符如果终结符在栈顶而不能匹配，弹出此终结符 3.4 自下而上分析自下而上分析 3.4.1 归约归约 例例 S aABe A Abc | bB d3.4 自下而上分析自下而上分析 3.4.1 归约归约 例例 S aABe A Abc | bB dabbcde（读入（读入ab）ab3.4 自下而上分析自下而上分析 3.4.1 归约归约 例例 S aABe A Abc | bB dabbcdeaAbcde（归约）（归约）abA3.4 自下而上分析自下而上分析 3.4.1 归约归约 例例 S aABe A Abc | bB dabbcdeaAbcde（再读入（再读入bc）abAbc3.4 自下而上分析自下而上分析 3.4.1 归约归约 例例 S aABe A Abc | bB dabbcdeaAbcdeaAde（归约）（归约）abAbAc3.4 自下而上分析自下而上分析 3.4.1 归约归约 例例 S aABe A Abc | bB dabbcdeaAbcdeaAde（再读入（再读入d）abAbdAc3.4 自下而上分析自下而上分析 3.4.1 归约归约 例例 S aABe A Abc | bB dabbcdeaAbcdeaAdeaABe（归约）（归约）abAbdAcB3.4 自下而上分析自下而上分析 3.4.1 归约归约 例例 S aABe A Abc | bB dabbcdeaAbcdeaAdeaABe(再读入再读入e)eabAbdAcB3.4 自下而上分析自下而上分析 3.4.1 归约归约 例例 S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS（归约）（归约）SeabAbdAcB3.4 自下而上分析自下而上分析 3.4.1 归约归约 例例 S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm abbcdeSeabAbdAcB3.4 自下而上分析自下而上分析 3.4.2 句柄句柄句型的句型的句柄句柄是和某产生式右部匹配的子串，是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步代表了最右推导过程的逆过程的一步S aABe A Abc | bB dS rm aABe rm aAde rm aAbcde rm abbcde句柄的右边仅含终结符句柄的右边仅含终结符如果文法二义，那么句柄可能不唯一如果文法二义，那么句柄可能不唯一3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E + E | E E | (E ) | id3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E + E | E E | (E ) | idE rm E E rm E E + E rm E E + id3 rm E id2 + id3 rm id1 id2 + id3 3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E + E | E E | (E ) | idE rm E E E rm E + E rm E E + Erm E + id3 rm E E + id3rm E E + id3 rm E id2 + id3 rm E id2 + id3 rm id1 id2 + id3 rm id1 id2 + id3 在句型在句型E E + id3中，句柄不唯一中，句柄不唯一3.4 自下而上分析自下而上分析 3.4.3 用栈实现移进用栈实现移进 归约分析归约分析先通过先通过移进移进 归约分析器在分析输入串归约分析器在分析输入串id1 id2 + id3时时的动作序列的动作序列来了解移进来了解移进 归约分析的工作方式归约分析的工作方式3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$ 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 $E E+ id3$ 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 $E E+ id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 $E E+ id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 $E E+ id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 $E E+ id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 $E E+ id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 $E E+ id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 $E E+ id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 $E E+ id3$ 移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作 $ id1 id2 + id3$ 移进移进 $ id1 id2 + id3$ 按按E id归约归约 $E id2 + id3$移进移进 $E id2 + id3$ 移进移进 $E id2 + id3$ 按按E id归约归约 $E E + id3$ 移进移进 $E E+ id3$ 移进移进 3.4 自下而上分析自下而上分析 要想很好地使用移进要想很好地使用移进 归约方式，尚需解决一归约方式，尚需解决一些问题些问题 如何决策选择移进如何决策选择移进还是还是归约归约进行归约时，确定右句型中将要归约的子串进行归约时，确定右句型中将要归约的子串进行归约时，如何确定选择哪一个产生式进行归约时，如何确定选择哪一个产生式3.4 自下而上分析自下而上分析 3.4.4 移进移进 归约分析的冲突归约分析的冲突 1、移进、移进 归约冲突归约冲突 例例stmt if expr then stmt | if expr then stmt else stmt | other如果移进如果移进 归约分析器处于格局归约分析器处于格局栈栈输入输入 if expr then stmtelse $ 3.4 自下而上分析自下而上分析 2、归约、归约 归约冲突归约冲突stmt id (parameter_list) | expr = exprparameter_list parameter_list, parameter | parameterparameter idexpr id (expr_list) | idexpr_list expr_list, expr | expr由由A(I, J)开始的语句开始的语句栈栈输入输入 id ( id, id ) 归约成归约成expr还还是是parameter ?3.4 自下而上分析自下而上分析 2、归约、归约 归约冲突归约冲突stmt id (parameter_list) | expr = exprparameter_list parameter_list, parameter | parameterparameter idexpr id (expr_list) | idexpr_list expr_list, expr | expr由由A(I, J)开始的语句开始的语句( (词法分析查符号表词法分析查符号表, ,区分第一个区分第一个id) )栈栈输入输入 procid ( id, id ) 需要修改上面的文法需要修改上面的文法3.5 LR分析器分析器 本节介绍本节介绍LR(k)分析技术分析技术 特点特点适用于一大类上下文无关文法适用于一大类上下文无关文法效率高效率高 主要介绍构造主要介绍构造LR分析表的三种技术分析表的三种技术简单的简单的LR方法（简称方法（简称SLR）规范的规范的LR方法方法向前看的向前看的LR方法（简称方法（简称LALR） 3.5 LR分析器分析器 3.5.1 LR分析算法分析算法输入输入LR分析程序分析程序输出输出 栈栈LR分析器的模型分析器的模型actiongotosmXmsm-1Xm-1s0a1aian$3.5 LR分析器分析器 例例 E E + T | E T T T F | T E F (E ) | F id状态状态动动 作作 转转 移移 id + ( ) $