[编译原理第四章..pptVIP

第四章 语法分析(Parsing / Syntax Analysis) —自顶向下分析方法 在设计语言时，每种程序设计语言都有一组精确的规则来描述良构（well-formed)程序的语法结构。 高级语言的大部分语法结构可用上下文无关文法描述，因而宜于将上下文无关文法用作语法分析的基础。 语法分析程序的功能 语法分析方法的分类： 自顶向下语法分析方法 (Top-Down) 自底向上语法分析方法 (Bottom-Up) 两种自顶向下语法分析方法： 非确定的自顶向下语法分析方法 确定的自顶向下语法分析方法： 递归下降子程序方法 LL（1）方法 First 集、Follow集、 Predict集 语法分析方法的分类： 自顶向下语法分析方法(Top-Down) ，亦称面向目标的分析方法; 自底向上语法分析方法(Bottom-Up) 。 自顶向下分析概述 从文法开始符出发试图推导出所给的终极符串。 例 G[z] : [1] Z ?aBd [2] B ?d [3] B ?c [4] B ?bB 对给定的终极符串abcd，推导过程： 自底向上分析概述 从终极符串出发归约（reduce）出文法的开始符。 例 G[z] : [1] Z ?aBd [2] B ?d [3] B ?c [4] B ?bB 对给定的终极符串abcd，归约过程： 4.1.2 语法错误的处理原则 4.1.2 语法错误的处理原则 （续2） 4.1.3 自顶向下语法分析基本思想 自顶向下语法分析方法，亦称面向目标的分析方法。 思想：从文法的开始符出发企图用最左推导推导出与输入的单词串完全相匹配的句子。若输入的单词串是给定文法的句子，则必能推出，反之必然以推导失败而终止。 自顶向下语法分析方法分为： 1、非确定的自顶向下语法分析方法; 2、确定的自顶向下语法分析方法：实现方法简单、直观，便于手工构造和自动生成，是目前常用的语法分析方法。 递归下降方法； LL（1）方法。 确定的自顶向下语法分析方法：实现方法简单、直观，便于手工构造和自动生成，是目前常用的语法分析方法。 递归下降方法； LL（1）方法。 4.1.4 三个重要的集合 First集 First(?) = { a ?VT | ??* a ...} ? (if ?? *? then {?} else ? ) Follow集 Follow(A) = { a ?VT | S?+ ...Aa...} ? (if S?*... A then {#} else ? ) Predict集(Select集) 对每一文法符号X计算First(X)集 若X ?VT ： First(X)={X} 若X ?VN : 对关于X的每一个产生式进行如下处理: Step1.形如: X? ? , 则: ? ? First(X) Step2.形如:X? a… , a ?VT则 : a ? First(X) 对每一文法符号X计算First(X)集 Step3.对形如下的产生式: X?Y1Y2…Yi-1Yi…Yn 若：Y1,Y2, … ,Yi ?VN且Y1,Y2, … ,Yi-1?* ? 则: First(Y1)- {?} , First(Y2)- {?}, … , First(Yi-1)- {?}, First(Yi)都包含在First(X)中。 若： Yi ?VN且Yi ?* ? (i=1,2,…n), 则: First(Y1) , First(Y2), … , First(Yn) 都包含在First(X)中。 重复Step3 ，直至对所有A?VN，First(A)收敛为止。 例： E? ? T E’ E’ ? + T E’ | ? T ? F T’ T’ ? * F T’ | ? F ? id | ( E ) 计算First(?)集 若符号串?=X1X2…Xn， 当X1,X2, … , Xi-1?*?，Xi 不能 ?* ?， 则: First(?)=?1i-1(First(Xj)-{?}) ? First(Xi) 若所有Xi 都能?*?， 则: First(?)= ?1n First(Xj) 例： E? ? T E’ E’ ? + T E’ | ? T ? F T’ T’ ? * F T’ | ? F ? i