[电脑基础知识]05-LL1文法及其分析程序.ppt

1,编译原理,第五章 自顶向下语法分析,2,主要内容,本章学习目标 5.1 LL(1)文法 FIRST和FOLLOW集定义和计算 LL(1)文法定义 LL(1)分析程序的生成 5.2 自顶向下的分析方法 5.3 非LL(1)文法的改造 小结本章 重点习题解析 思考练习 相关术语的回顾（英文版）,3,本章学习目标,一学习目标 理解语法分析器的功能 掌握自上而下的分析方法 LL(1)文法的相关定义First、Follow、Select集 LL(1)文法的判定 LL(1)文法的分析 了解非LL(1)文法的改造 二课程安排 3学时,4,语法分析概述,一、语法分析的功能 语法分析是编译原理的核心部分，其作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子。 二、语法分析器在编译程序中的地位（一遍扫描）,5,语法分析概述,三、语法分析方法 通常把语法分析方法分为两大类： 自上而下分析与自下而上分析。,6,本章知识结构,7,自上而下分析,要点： .由根向下构造语法树 .构造最左推导 .推导出的终结符是否与当前输入符匹配 S aaab A B a A,S AB A aA | B b | bB aaab. S AB S AB aAB A aA aaAB A aA aaaAB A aA aaa B A aaab B b,8,自上而下分析例5.1,若有文法G1S: S pA|qB, A cAd|a, B dB|b 若输入串W=pccadd， 则自顶向下的推导过程为：S pA pcAd pccAdd pccadd 文法的特点： 每个产生式的右部都由终结符开始； 若两个产生式有相同的左部，那么他们的右部由不同的终结符开始。 结论： 这样的文法在推导过程中，完全可以根据当前的输入符号决定选择哪个产生式，因此分析过程是唯一确定的。,9,自上而下分析例5.2,构造最左推导(自顶向下） 若有文法G2S, SAp|Bq AcA|a BdB|b 输入串：w=ccap, 则推导过程为：S Ap cAp ccAp ccap 文法特点： 产生式的右部不全是由终结符开始； 如果两个产生式有相同的左部，他们的右部是由不同的终结符或非终结符开始 文法中无空产生式； 结论:在推导过程中完全可以根据向前看符号是属于哪个产生式右部的开始符号集合（First（a）引出）而决定选择相应的产生式进行推导，因此，分析过程是完全确定的。,10,自上而下分析例5.3,若有文法GS， SaB|d BbBS| 若输入串w=abd，则构造最左推导的过程如下：S aB abBS abS abd 注：把紧跟非终结符A的终结符号集记作FOLLOW(A)。 结论 在构造最左推导的过程中，使用A候选式替换A去推导的条件： 向前看符号a不出现A的所有非空候选式的FIRST集合中； 向前看符号a应该出现在FOLLOW(A)中。 P77:当文法中有形如A|的产生式时， 、不同时推导出空时，设推导不出空， 推导出空， 则A的替换可唯一确定的条件： FIRST()(FIRST()FOLLOW(A)= ,11,带回溯的自上而下分析,S AB A aA | B b | bB a a a b b. S (1) A. S AB (2) aA. A aA (3) aaA. A aA (4) aaaA. A aA (5) aaa B. A (6) aaab B b,aaabb. S (1) A. S AB (2) aA. A aA (3) aaA. A aA (4) aaaA. A aA (5) aaa B A (6) aaa b B B bB (7) aaabb B b,12,LL（1）文法,自顶向下包括确定分析（无回溯）和不确定分析（带回溯的分析方法） 无回溯的自顶向下分析程序（称为预测分析程序Predictive parser） 我们定义一种文法（LL1文法） LL(1)文法的含义： 第一个L 表明自顶向下分析是从左到右扫描输入串 第二个L 表明分析过程将用是最左推导 1 向前看一个输入符号（lookahead),13,FIRST集和FOLLOW集的定义 设G=(VT,VN,P，S)是上下文无关文法 FIRST（）=a| =* a,aVT, , V* 若 =* 则规定FRIST（） FOLLOW（A）=aS =* A 且a FRIST（）， V*， V+ 若S =* u A ,且 =* ，则 #FOLLOW(A),LL (1)文法的相关定义,14,计算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)都含有 (即Y1Y(i-1) =* ),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,K)均含有,则把加到FRIST(X)中.,15,举例,文法G2S, SAp|Bq AcA|a BdB|b 输入串：w=ccap, 则推导过程为： S Ap cAp ccAp ccap First（Ap）=a,c First(Bq) =b,d,16,计算FOLLOW集,1.对于文法的开始符号S,置#于FOLLOW(S) 中; 2.若 B 是一个产生式,则把 FIRST()加至FOLLOW(B)中; 3.若 B是一个产生式,或 B是一个产生式而 =* (即FIRST()），则把FOLLOW（A）加至FOLLOW（B）中,17,举例,若有文法G3S， SaA|d AbAS| 若输入串w=abd，则构造最左推导的过程如下： S aA abAS abS abd First(aA)=a First(d)=d First(bAS)=b First()= Flollow(A)=a,d,# Select(SaA )=a Select(Sd )=d Select(AbAS )=b Select(A)=(First- )U FollowA=a,d,# Select(SaA ) Select(Sd )= Select(AbAS) Select(A )= 所以文法G3是LL1文法。,18,计算Select集,定义：给定上下文无关文法的产生式 ， A VN， V* 若 * ，则Select( )=First() 若 * ，则Select( )=(First()-)Follow(A),19,LL（1）文法的判定，方法之一,一个上下文无关文法是LL（1）文法的充分必要条件是相同左部产生式的Select集合交集为空。,20,LL（1）文法的判定，方法之二,一个文法G是LL（1）的，当且仅当对于G的每一个非终结符的任何两个不同产生式 ，下面的条件成立： FIRST（）FIRST()=,也就是和推导不出以同一个终结符a为首的符号串；它们不应该都能推出空字 .假若 =* ，那么， FIRST（)FOLLOW（A）. 也就是， 若 =* .则所能推出的串的首符号不应在FOLLOW(A）中,21,举例 P94,各非终结符的FIRST集合如下: FIRST(E)=(,a FIRST(E)=+, FIRST(T)=(,a FIRST(T)=*, FIRST(F)=(,a,各非终结符的FOLLOW集合为： FOLLOW(E)=), FOLLOW(E)=)， FOLLOW(T)=，)， FOLLOW(T)=,)，# FOLLOW(F)=*,，),#,G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a,22,G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a,Select(E +TE)=+ Select(E )= )， Select(T *FT) =* Select(T )=+,)， Select(F (E) )=( Select(F a)=a Select(E TE)=（，a Select(T FT) =（，a 由上可知，相同左部产生式的Select集合交集为空，所以GE是LL（1）文法。,23,5.2无回溯的自顶向下分析方法,特征根据下一个输入符号为当前要处理的非终结符选择产生式 要求文法是LL(1)的 LL(1)文法的含义： 第一个L 表明自顶向下分析是从左到右扫描输入串 第二个L 表明分析过程将用是最左推导 1 向前看一个输入符号（lookahead) 无回溯的自顶向下分析方法 1 递归子程序法 2 预测分析法Predictive parser,24,5.2.1递归下降子程序的分析,一、递归下降分析程序的实现思想 对文法中的每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按照LL(1)形式可唯一地确定选择某个候选进行推导。 二、递归下降分析程序的特点 1、程序结构清晰，易于手工操作。 2、对语义处理灵活。 三、递归下降分析法的必要条件 必须是不包含左递归和回溯的上下文无关文法。,25,PL/0语言的EBNF,程序=分程序. 分程序=常量说明部分变量说明部 分过程说明部分语句 常量说明部分=CONST常量定义部分，常量 定义； 变量说明部分=VAR标识符，标识符； 过程说明部分= PROCEDURE 标识符分程序 ；过程说明部分； 语句= 标识符：=表达式 |IF 条件 then语句|CALL|READ|BEGIN 语句；语句 END|WHILE|,26,例：递归子程序实现 表达式的语法分析,表达式的EBNF 表达式=+|-项（+|-）项 项=因子（*|/）因子 因子=ident|number|（表达式）,27,表达式 表达式=+|-项（+|-）项,procedure expr; begin if sym in plus, minus then begin getsym; term; end else term; while sym in plus, minus do begin getsym; term; end end;,28,Procedure term; begin factor; while sym in times,slash do begin getsym; factor end end;,项 项=因子（*|/）因子,29,Procedure factor; begin if sym=ident then getsym else if sym=number then getsym else if sym=( then begin getsym; expr; if sym=) then getsym else error end else error end;,因子 因子=ident|number|（表达式）,30,5.2.2预测分析法Predictive parser 预测分析程序模型,Input,#,总控程序,预测分析表,stack,预测分析器由三部分组成： 预测分析程序； 先进后出栈； 预测分析表。,31,带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an,有限控制器,磁头,识别程序的数学模型下推自动机,32,上下文无关语言句型分析（识别）程序的数学模型,下推自动机Pda=(K,f,H,h0,S,Z) H:下推栈符号的有穷字母表 h0 :H中的初始符号 f: K （) H K H* Pda的一个组态是K * H 中的一个（k,w,) k:当前状态，w:余留输入串， ：栈中符号，最左边的符号在栈顶。Pda的一次移动用组态表示 终止和接受的条件: 1.到达输入串结尾时，处在Z中的一个状态 或 2.某个动作序列导致栈空时,33,例：Pda P=(A,B,C),a,b,c),f,h,i,i A, ),f(A,a,i) = (B,h) f(B,a,h) = (B,hh) f(C,b,h) = (C, ) f(A,c,i) = (A, ) f(B,c,h) = (C,h) 接受输入串aacbb的过程 (A,aacbb,i)读a, pop i, push h, goto B (B,acbb,h) 读a, pop h, push hh, goto B (B,cbb,hh) 读c, pop h, push h , goto C (C,bb,hh) 读b, pop h, push , goto C (C,b,h) 读b ,pop h, push , goto C (C, , ),34,预测分析表 构造算法,1.对文法G的每个产生式 执行第二步和第三步； 2.对每个终结符aSelect( ),把 加至A,a中， 3.把所有无定义的A,a标上“出错标志”。 可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的,35,例：不含左递归的表达式文法 G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a,预测分析表的构造举例,例：含左递归的表达式文法GE： EE+T|T TT*F|F F(E)|a,36,G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a,37,预测分析程序的 总控程序算法,BEGIN 首先把#然后把文法开始符号推入栈；把第一个输入符号读进b; FLAG：=TRUE； WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在中； IF X Vt THEN IF X=b THEN 把下一个输入符号读进b ELSE ERROR ELSE IF X=# THEN IF X=b THEN FLAG:=FALSE ELSE ERROR ELSE IF X,b=X X1X2XK THEN 把XK，X K-1,X1一一推进栈 ELSE ERROR END OF WHILE; STOP/*分析成功，过程完毕* END,38,分析输入串#a+a#,栈内容 栈顶符号 当前输入 余留串 MX,b 1 #E E a +a# E TE 2 #ET T a +a# T FT 3 #ETF F a +a# F a 4 #ETa a a +a# 5 # ET T + a# T 6 #E E + a# E +TE 7 #ET+ + + a# 8 # ET T a # T FT 9 #ETF F a # F a 10 #ETa a a # 11 #ET T # T 12 #E E # E 13 # # #,39,5.3 非LL(1)文法的改造,LL(1)文法的性质： LL(1)文法是无二义的 LL(1)文法不含左递归 非LL(1)文法的改造方法 提左公因子 消除左递归,40,提左公因子,将产生式A | 变换为： A B B |,41,左递归规则,GS: SSa Sb L=ban | n0 W=baaa S S a S a S a b,42,左递归 关于非终结符P的规则,直接左递归 若 P P | 、 V*且不以P开头 一般 左递归 若 P =* P SAa ASb ,43,消除左递归,消除直接左递归 形如：P P | 非，不以P打头 改写为：P Q Q Q| ,44,消除左递归,例: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,形如：P P | 非，不以P打头 P Q Q Q| ,45,消除一般左递归,消除一般左递归要求文法:1.无回路(A(=+(A) 2.无空产生式 （1）以某种顺序将文法非终结符排列A1 ,A2 An （2） for i:=1 to n do begin for j:=1 to i-1 do 用Ai1| 2r| k r替代 形如Ai Ajr的规则,其中 Aj 1| 2| k是关于Aj的全部产生式; 消除Ai规则的直接左递归; end; p89 （3）化简由2得到的文法,46,LL(1)分析中的一种错误处理办法,发现错误 1栈顶的终结符与当前输入符不匹配 2非终结符A于栈顶，面临的输入符为a，但分析表M的MA,a为空 “应急”恢复策略 跳过输入串中的一些符号直至遇到“同步符号”为止。 同步符号的选择 1把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续 2把FIRST(A)中的符号加到A的同步符号集，当FIRST(A)中的符号在输入中出现时，可根据A恢复分析,47,关于LL(1)的一些结论,能由LL(1)文法产生的语言称为LL(1)语言.它们已被证明具有许多重要特性, 主要有: (1) 任何LL(1)文法都是无二义性的; (2) 左递归文法是非LL(1)的; (3) 存在一种算法,它能判定任意文法是否为LL(1)的; (4) 存在一种算法,它能判定任意两个LL(1)文法是否等价; (5) CFL是否是LL(1)语言是不可判定的; (6) 非LL(1)语言是存在的. 若在分析过程中,每步向前扫描k个符号来确定选用的产生式,此分析方法称为是LL(k)分析.此法极少用,故从略.,48,重点习题的解析,P94-97 一、填空题 自上而下语法分析方法的基本思想是：从文法的开始符号出发。不断建立最左直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。 自上而下分析方法会遇到的主要问题有回溯和左递归。 在语法分析中，最常见的两种方法一定是自上而下分析法，另一种是自下而上分析法。 二、选择题 编译过程中，语法分析器的任务是B，C，D。 A、分析单词是怎样构成的 B、分析单词串是如何构成语句的 C、分析语句是如何构成程序的 D、分析程序结构 高级语言编译程序常用的语法分析方法中，递归下降分析法属于B分析方法。 A、自左至右 B、自上而下 C、自下而上 D、自右至左,49,重点习题的解析,三、分析解答题 1.已知文法G： AaAa 该文法是LL（1）文法吗？为什么？ 若采用LL（1）方法进行分析，如何得到该文法的LL（1）分析表。,50,重点习题的解析,解： 因为FOLLOW（A）FOLLOW（A）FIRST（A）=a，#，造成FOLLOW（A）FIRST（A）=a，#a，所以该文法不是LL（1）文法。 若采用LL（1）方法进行语法分析，必须修改该文法。因该文法产生偶数（可以为0）个a，所以得到文法G：AaaA。 此时 FOLLOW（A）=#，因此 FOLLOW（A）FIRST（A）=#a，= 所以文法G是LL（1）文法。,51,重点习题的解析,该文法的LL（1）分析表： a # A AaaA A,52,三、分析解答题,2. P97 例题2,53,重点习题的解析,考察本章知识点最典型的题目是P94,54,综合案例,给定一个文法GE，要求： 1)求First、Follow、 Select集 2)判定是否为LL(1)文法 若不是请改造其为LL(1)文法 3)若是LL(1)文法，请构造预测分析表，并写出构造算法 4)写出预测分析算法 5)写出输入串aa#的预测分析步骤 6)写出GE的递归子程序算法,55,本章小结,56,本章小结,1.LL(1)文法的相关概念 2.LL(1)文法的判定 3.非LL(1)文法的改造 4.综合案例,57,作业,P99： 1 p100 ：3,58,review-parsing,The syntax analysis phase of a compiler verifies that the sequence of tokens returned from the scanner represent valid sentences in the grammar of the programming language. There are two major parsing approaches: top-down and bottom-up. In top-down parsing, you start with the start symbol and apply the productions until you arrive at the desired string. In bottom-up parsing, you start with the string and reduce it to the start symbol by applying the productions backwards.,59,In the top-down parsing,we begin with the start symbol and at each step, expand one of the remaining nonterminals by replacing it with the right side of one its productions. We repeat until only terminals remain. The top-down parse prints a leftmost derivation of the sentence.,A bottom-up parse works in reverse. We begin with the sentence of terminals and each step applies a production in reverse, replacing a substring that matches the right side with the nonterminal on the left. We continue until we have substituted our way back to the start symbol. If you read from the bottom to top, the bottom-up parse prints out a rightmost derivation of the sentence.,60,lookahead symbol The lookahead symbol is the next symbol coming up in the input. backtracking. Based on the information the parser currently has about the input, a decision is made to go with one particular production. If this choice leads to a dead end, the parser would have to backtrack to that decision point, moving backwards through the input, and start again making a different choice and so on until it either found the production that was the appropriate one or ran out of choices.,61,predictive parser and LL(1)grammar,Predictive parser is a non-backtracking top-down parser. A predictive parser is characterized by its ability to choose the production to apply solely on the basis of the next input symbol and the current nonterminal being processed. To enable this, the grammar must take a particular form. We call such a grammar LL(1). The first “L” means we scan the input from left to right; the second “L” means we create a leftmost derivation; and the 1 means one input symbol of lookahead.,62,recursive-descent,The first technique for implementing a predictive parser is called recursive-descent. A recursive descent parser consists of several small functions(procedures), one for each nonterminal in the grammar. As we parse a sentence, we call the functions (procedures) that correspond to the left side nonterminal of the productions we are applying. If these productions are recursive, we end up calling the functions recursively.,63,Table-driven LL(1) parsing,In a recursive-descent parser, the production information is embedded in the individual parse functions for each nonterminal and the run-time execution stack is keeping track of our progress through the parse. There is another method for implementing a predictive parser that uses a table to store that production along with an explicit stack to keep track of where we are in the parse.,64,How a table-driven predictive parser works,We push the start symbol on the stack and read the first input token. As the parser works through the input, there are the following possibilities for the top stack symbol X and the input token nonterminal a: 1. If X = a and a = end of input (#): parser halts and parse completed successfully 2. If X = a and a != #: successful match, pop X and advance to next input token. This is called a match action. 3. If X != a and X is a nonterminal, pop X and consult table at X,a to see which production applies, push right side of production on stack. This is called a predict action. 4. If none of the preceding cases applies or the table entry from step 3 is blank, there has been a parse error,65,The first set of a sequence of symbols u, written as First(u ) is the set of terminals which start all the sequences of symbols derivable from u. A bit more formally, consider all strings derivable from u by a leftmost derivation. If u =* v , where v begins with some terminal, that terminal is in First(u). If u =* , then is in First(u ).,66,The follow set of a nonterminal A is the set of terminal symbols that can appear immediately to the right of A in a valid sentence. A bit more formally, for every valid sentence S =*uAv , where v begins with some terminal, that terminal is in Follow(A).,67,Computing first,To calculate First(u) where u has the form X1X2.Xn, do the following: 1. If X1 is a terminal, then add X1 to First(u), otherwise add First(X1) - to First(u ) . 2. If X1 is a nullable nonterminal, i.e., X1 =* , add First(X2) - to First(u). Furthermore, if X2 can also go to , then add First(X3) - and so on, through all Xn until the first nonnullab