《8114整理新第五章 LL1文法及其分析程序》由会员分享，可在线阅读，更多相关《8114整理新第五章 LL1文法及其分析程序（63页珍藏版）》请在金锄头文库上搜索。
1、1,第5章 自顶向下语法分析方法,主要内容： 自上而下的语法分析 预测分析程序 递归下降子程序 表驱动的预测分析程序 LL(1)分析程序的生成 LL(1)文法 FIRST和FOLLOW集 定义和计算 非LL(1)文法的改造,2,5.1确定的自顶向下语法分析思想,1.语法分析概念 2.自上而下的语法分析的一般过程 3.自上而下的语法分析面临的问题 4. 开始符号集 5. 后跟符号集 6.select集 7.LL(1)文法,3,1。语法分析,在语言的编译实现中，把句子分析的过程称为语法分析，即完成这个任务的程序称为语法分析程序或称为识别程序。分析算法又称识别算法。 从左到右的分析算法，即总是从左到
2、右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,4,（上下文无关文法）句型的分析,句型分析就是识别一个符号串是否为某文法的句型的过程，或者说是某个推导的构造过程。,5,语法树推导的几何表示,句型aabbaa的可能推导序列和语法树,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,6,分析算法分类,分析算法可分为： 自上而下分析法：从文法的开始符号出
3、发，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。 自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,7,两种方法反映了语法树的两种构造过程。,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串 自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树,8,2。自上而下分析方法,对任何输入串，试图用一切可能的办法，从文法开始符号着手，自上而下地为输入串构造一棵语法树，或者说，为输入串寻找一个最左推导。本质上是一个试探过程，反复使用不同地产生式谋求匹配输入串的过程。,9,自上而下的语法
4、分析的一般过程,例：文法G： S cAd A ab A a识别输入串w=cabd是否为该文法的句子,SSS cAdcAd a b 推导过程：S cAd cAd cabd,10,自上而下的语法分析的一般过程(1)S cAd (2) A ab (3) A a 识别输入串w=cad是否为,该文法的句子 1.S cAd 2.后选择(2)扩展A，得到推导S cAd cabd 这时 w的第二个符号可以与叶子结点a得以匹配，但第三个符号d却不能与下一叶子结点b匹配 怎么办？-查看A有无另一个选择，有！回溯，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）构造推导S cAd cad,识别输
5、入串w=caa的过程： 1.S cAd 2.选择(2)扩展A，得到推导S cAd cabd 3.回溯回到推导S cAd 4.选择(3)扩展A，得到推导S cAd cad 5. A没有选择了！回溯到推导S cAd 6.再回溯S有无另一个选择？没有！ 宣告分析失败。 （请思考 若有 (4) S cB (5) B aa 会怎样? ）,11,自上而下分析的进一步讨论,自上而下分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子，若能构造出推导则表明输入串是给定文法的句子，否则表明该输入不是给定文法的句子。 自上而下分析对文法的要求文法不能含有左递归规则。 自上而
6、下分析又可分为确定的和不确定的两种 不确定的分析方法称为带回溯的分析方法，这种方法实际上是一种穷举的试探方法 确定的分析方法需对文法有一定的限制,12,3。自上而下的语法分析面临的问题-实现考虑,回溯 文法的左递归性 SSa,13,自上而下分析对文法的要求,例文法G0S: (1) SSa (2) Sb 分析baa是不是文法的句子 按照自上而下的分析思想 选用产生式(1)来推导SSa 语法树末端结点最左符号为非终结符，所以选用（1）继续推导SSaSaa 此时语法树末端结点最左符号仍为非终结符，所以选用（1）继续推导SSaSaa Saaa 问题试图用S匹配输入串时，出现：在没有读入任何输入符 号的
7、情况下，又得重新要求S去进行新的匹配.无法确定什么时候使用（2）产生式最适当，只能采用带回溯的不确定方法解决。 原因文法含有左递归。,14,回溯的原因,例GS: SxAy Aaba 若当前输入串为xay，首先构造的推导SxAy 匹配 进一步推导对A可选择Aab替换，得SxAy xaby xay xaby 匹配 xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式Aa进行试探， SxAy xay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。 由于相同左部的产生式的右部开始符号相同而引起回溯。,15,在自上而下的分析方法中
8、如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？-什么信息用于Parser做正确选择?(输入串,文法特点),16,可预测的试探推导过程,例 文法GS: S pA |qB A cAd|a B d B |c 识别输入串w= pccadd是否是G1S的句子 可预测的试探推导过程： S pA pcAd pccAddpccadd 试探成功。,17,4。 开始符号集-FIRST集,设G=(VT,VN,P，S)是上下文无关文法 FIRST（）=a| =* a,aVT, 、V* 若 =* 则规定FRIST（）,18,FOLL
9、OW（A）=aS =* A 且a FRIST（）， V*， V+ 若S =* u A ,且 =* ，则#FOLLOW(A),5。后跟符号集-FOLLOW集,19,6。SELECT集,给定上下文无关文法的产生式 AVN, V* 若* ，则SELECT()=FIRST() 若=* ,则SELECT()=(FIRST()-)FOLLOW(A),20,7。 LL（1）文法 一个文法G是LL（1）的，当且仅当对于G的每一个非终结符的任何两个不同产生式 ，下面的条件成立： SELECT() SELECT()= 其中和不能同时=* ,21,书中例子,22,5.2 LL（1）文法的判别 判别步骤： 1）。求出
10、能推出的非终结符,23,2）。 计算FIRST集,1.若XV,则FIRST(X)=X 2.若XVN,且有产生式Xa，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中. 3.若XY是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X Y1Y2YK 是一个产生式,Y1,Y2,Y(i-1)都是非终结符,而且,对于任何j,1j i-1, FIRST(Yj)都含有 (即Y1.Y(i-1) =* ),则把FIRST(Yj)中的所有非元素和FIRST(Yi)中的所有元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2
11、,K)均含有,则把加到FRIST(X)中.,24,3）。 计算FOLLOW集,1.对于文法的开始符号S,置#于FOLLOW(S) 中; 2.若B是一个产生式,则把 FIRST()-加至FOLLOW(B)中; 3.若B是一个产生式,或 B是 一个产生式而 =* (即FIRST()）， 则把FOLLOW（A）加至FOLLOW（B）中,25,G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a,各非终结符的FIRST集合如下： FIRST(E)=(,a FIRST(E)=+, FIRST(T)=(,a FIR
12、ST(T)=*, FIRST(F)=(,a,各非终结符的FOLLOW集合为： FOLLOW(E)=), FOLLOW(E)=)， FOLLOW(T)=，)， FOLLOW(T)=,)，# FOLLOW(F)=*,，),#,26,4）。 计算SELECT集,计算产生式的SELECT集,27,G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a,E +TE | FIRST(+TE)=+ FOLLOW(E)=)， T *FT | FIRST(*FT)=* FOLLOW(T)=+,)， F (E) | a FI
13、RST( (E)=( FIRST( a)=a 所以GE是LL（1）的,28,5）。判断文法是否LL（1）文法,若文法所有具有相同左部产生式的SELECT集两两不相交，则文法是LL(1)文法。,29,LL(1)文法的性质： LL(1)文法是无二义的 LL(1)文法不含左递归,30,5.3 某些非LL(1)文法的改造,1。提取左公共因子 提左公因子： 将产生式 | 变换为： B B |,31,一般形式：, 1|2|n 提取左公共因子后： AA A1|2|n,32,2。消除左递归,左递归 关于非终结符P的规则 直接左递归 ： P P | 、 V*且、不以P开头 一般 左递归 ： P =* P 例：
14、SAa ASb ,33,消除文法中左递归规则,1） 消除直接左递归： 形如：P P | 非， ，不以P打头 改写为：P Q Q Q| 其中Q为新增加的非终结符,34,消除文法中左递归规则举例,例:E E+T|T T T*F|F F (E)| a G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a,35,消除一般左递归对文法要求: 1. 无回路(A(=+(A) 2. 无空产生式,2） 消除一般左递归的方法： （1） .以某种顺序将文法非终结符排列A1 ,A2 An （2） for i:=1 to n d
15、o begin for j:=1 to i-1 do 用Aj-1| 2| k 替代形如Ai- Ajr的规则, 其中Aj- 1| 2| k是关于Aj的全部产生式; 消除Ai规则的直接左递归; end; （3）化简由（2）得到的文法:去掉无用产生式,36,例P90,37,消除左递归和提左公因子并不一定都能将非LL(1)文法改造为LL(1)的,S if C t S | if C t S e S C b 提左因子 S if C t S A A e S | ,First集 Follow集 S if #,e A e, #, e C b t Select(AeS)Select(A ) =e#, e 改造后文法不是LL(1)文法,38,5.5 确定的自顶向下分析方法,特征根据下一个(几个）输入符号为当前要处理 的非终结符选择产生式 要求文法是LL(1)的 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号（lookahead),39,无回溯的自顶向下分析程序,预测分析程序的实现技术 1. 递归（下降）子程序 2.
