编译原理-Chapt4-1.ppt

第四章 语法分析—自上而下分析;本章主要内容;四元式;语法分析的任务; ;语法分析;什么是语言;什么是语言;如何描述一种语言？;如何描述一种语言？;语言概述;文法和语法分析;文法和语法分析;文法及语言的形式定义;文法;文法及语言的形式定义;文法的形式定义;文法的形式定义;终结符号集VT = { he, has, a, pen} 非终结符号集VN = { ?句子?，?主语?，?谓语?，?冠词?，?形容词?，?名词? ，? 动词? ，?宾语? ，?名词?……} 产生式集合P = {?句子? → ?主语??谓语? ，……} 开始符号S = ?句子?;句子的推导___根据规则;句子 = 主语谓语宾语 = 代词谓语宾语 = he 动词宾语 = he has 宾语 = he has 冠词名词 = he has a 名词 = he has a pen;上下文无关文法的形式定义;例，定义只含+，*的算术表达式的文法 G={i，+，*，(，)}，{E}，E， P， 其中，P由下列产生式组成： E ? i E ? E+E E ? E*E E ? (E) ;4.1 语法分析器的功能;源程序;语法分析的方法： 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约;G(E)： E ? i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E;语法分析的方法： 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。 递归下降分析法 预测分析程序 优点：直观、简单和宜于手工实现。 ;4.2　自顶向下分析法;【例4.1】 α=acb G[S]: S→aAb A→cd|c ;3.选用A的右部符号串匹配输入串 A有两个右部,选第一个 ;自顶向下分析方法分类　;1.回溯问题;例如： 假定有文法G(S): (1) S→xAy (2) A→**|* 分析输入??x*y(记为?)。;效率低的原因;2.左递归问题; ;4.3 LL(1)分析法;1.递归规则：产生式右部有与左部相同的符号 左递归规则：A→A… 右递归规则：A→…A 自嵌入递归规则：A→…A…;递归文法;递归文法;4.3.1 左递归的消除;一般而言，假定P关于的全部产生式是 P→P?1 | P?2 | … | P?m | ?1 | ?2|…|?n 其中，每个?都不等于?，每个?都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成： P→?1P? | ?2P? | … | ?nP? P?→?1P? | ?2P? |… | ?mP? | ? ;例 文法G(E): E→E＋T | T T→T*F | F F→(E) | i 经消去直接左递归后变成： E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i ;例如文法G(S): S→Qc|c Q→Rb|b R→Sa|a (4.3) 虽没有直接左递归，但S、Q、R都是左递归的 S?Qc?Rbc?Sabc;消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如Pi→Pj?的规则改写成 Pi→?1?|?2?|…|?k? ; (其中Pj→?1|?2|…|?k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。;例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a 令它的非终结符的排序为R、Q、S。 对于R，不存在直接左递归。 把R代入到Q的有关候选后，把Q的规则变为 Q→Sab | ab | b ;