第五章 LL1文法及其分析程序

1、.1第第5 5章章 自顶向下语法分析方法自顶向下语法分析方法主要内容：主要内容： 自上而下的语法分析自上而下的语法分析 预测分析程序预测分析程序 递归下降子程序递归下降子程序 表驱动的预测分析程序表驱动的预测分析程序 LL(1) LL(1)分析程序的生成分析程序的生成 LL(1) LL(1)文法文法 FIRST FIRST和和FOLLOWFOLLOW集集 定义和计算定义和计算非非LL(1)LL(1)文法的改造文法的改造 .25.15.1确定的自顶向下语法分析思想确定的自顶向下语法分析思想1.语法分析概念语法分析概念2.自上而下的语法分析的一般过程自上而下的语法分析的一般过程3.3.自上而下的语

2、法分析面临的问题自上而下的语法分析面临的问题4. 开始符号集开始符号集5. 后跟符号集后跟符号集6.select集集7.LL(1)文法文法.31。语法分析。语法分析在语言的编译实现中，把在语言的编译实现中，把句子分析句子分析的过程称的过程称为为语法分析，即语法分析，即完成这个任务的程序称为完成这个任务的程序称为语法分析语法分析程序或称为程序或称为识别程序识别程序。分析算法分析算法又称识别算法。又称识别算法。从左到右的分析算法从左到右的分析算法，即，即总是从总是从左左到到右右地地识识别输入符号串别输入符号串，首先识别符号串中的，首先识别符号串中的最左最左符号，进而符号，进而依次识别右边依次识别右

3、边的一个符号，的一个符号，直直到分析结束到分析结束。.4（上下文无关文法）上下文无关文法）句型的分析句型的分析句型分析句型分析就是就是识别识别一个符号串是否为某文法一个符号串是否为某文法的的句型的句型的过程，或者说是某个过程，或者说是某个推导推导的构造的构造过程。过程。.5语法树推导的几何表示语法树推导的几何表示z句型句型aabbaa的可能的可能推导序列和语法树推导序列和语法树 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAa

4、aabAaaabbaa.6分析算法分类分析算法分类分析算法可分为：分析算法可分为：自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号出发，寻找寻找与与输入符号输入符号串串匹配匹配的的推导，推导，或者说，为输入串寻找一或者说，为输入串寻找一个最左推导。个最左推导。自下而上分析法自下而上分析法：从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开始符号开始符号。 .7两种方法反映了语法树的两种构两种方法反映了语法树的两种构造过程。造过程。自上而下方法自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是

5、输入符号串自下而上方法自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树.82。自上而下分析方法。自上而下分析方法 对任何输入串，试图用一切可能的办法，对任何输入串，试图用一切可能的办法，从文法开始符号着手，自上而下地为输入从文法开始符号着手，自上而下地为输入串构造一棵语法树，或者说，为输入串寻串构造一棵语法树，或者说，为输入串寻找一个最左推导。本质上是一个试探过程，找一个最左推导。本质上是一个试探过程，反复使用不同地产生式谋求匹配输入串的反复使用不同地产生式谋求匹配输入串的过程。过程。 .9自上而下的语法分析的一般过程自上而下的语法分析的一般过程例：文法例：文法G：

6、 S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd 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为根的子树剪掉，扫描过的输入串

7、中的a吐出来,再试探用产生式（3）构造推导S cAd cad识别输入串识别输入串w=caa的的过程过程： 1.S cAd2.选择(2)扩展A，得到推导S cAd cabd3.回溯回回溯回到推导S cAd 4.选择(3)扩展A，得到推导S cAd cad5. A没有选择了！回溯回溯到推导S cAd 6.再回溯回溯S有无另一个选择？没有！ 宣告分析失败。（请思考（请思考 若有 (4) S cB (5) B aa 会怎样会怎样? ）.11自上而下分析的进一步讨论的进一步讨论自上而下分析自上而下分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子，若能构造出推导

8、则表明输入串是给定文法的句子，否则表明该输入不是给定文法的句子。自上而下分析对文法的要求文法不能含有左递归文法不能含有左递归规则。规则。自上而下分析自上而下分析又可分为确定的确定的和不确定的不确定的两种 不确定的不确定的分析方法称为带回溯的分析方法，这种方法实际上是一种穷举的试探方法 确定的分析方法确定的分析方法需对文法有一定的限制.123 3。自上而下的语法分析面临的问题。自上而下的语法分析面临的问题- -实现考虑实现考虑z回溯z文法的左递归性 SSa.13自上而下分析对文法的要求例文法G0S: (1) SSa (2) Sb 分析baa是不是文法的句子按照自上而下的分析思想选用产生式(1)来

9、推导SSa 语法树末端结点最左符号为非终结符，所以选用（1）继续推导SSaSaa 此时语法树末端结点最左符号仍为非终结符，所以选用（1）继续推导SSaSaa Saaa 问题问题试图用试图用S匹配输入串时，出现：在没有读入任何输入符匹配输入串时，出现：在没有读入任何输入符 号的情况下，号的情况下，又得重新要求又得重新要求S去进行新的匹配去进行新的匹配.无法确定什么时候使用（2）产生式最适当，只能采用带回溯的不确定方法解决。原因原因文法含有左递归。文法含有左递归。.14回溯的原因回溯的原因例GS: SxAy Aaba 若当前输入串为xay，首先构造的推导SxAy 匹配 进一步推导对A可选择Aab替

10、换，得SxAy xaby xay xaby 匹配 xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式Aa进行试探， SxAy xay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯由于相同左部的产生式的右部开始符号相同而引起回溯。.15在自上而下的分析方法中在自上而下的分析方法中如何如何选择选择使用使用哪个哪个产生式产生式进行推导进行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且有，且有n条条规则：规则：BA1|A2|An，那么如何确定用哪个右，

11、那么如何确定用哪个右部去替代部去替代B？-什么信息用于什么信息用于Parser做正确选做正确选择择?(输入串输入串,文法特点文法特点).16可预测的试探可预测的试探推导过程推导过程例例 文法文法GS: S pA |qB A cAd| |a B d B | |c 识别输入串识别输入串w= pccadd是否是是否是G1S的句子的句子可预测的试探可预测的试探推导过程：推导过程：S pA pcAd pccAddpccadd 试探试探成功。成功。.174 4。 开始符号集开始符号集-FIRST-FIRST集集设设G=(VG=(VT T,V,VN N,P,P，S)S)是上下文无关文法是上下文无关文法FIR

12、STFIRST（ ）=a|=a| =* a a ,a,aV VT T, , 、 VV* * 若若 =* 则规定则规定FRISTFRIST（ ）.18FOLLOWFOLLOW（A A）=a=a S S =* A A 且且a a FRISTFRIST（ ），）， VV* *， VV+ + 若若S S =* u A u A , ,且且 =* ，则，则#F#FOLLOW(A)OLLOW(A)5 5。后跟符号集。后跟符号集-FOLLOW-FOLLOW集集.196。SELECT集给定上下文无关文法的产生式给定上下文无关文法的产生式 A AV VN N, , VV* *若若* ，则，则SELECT(SELE

13、CT()=FIRST()=FIRST() )若若=* , ,则则SELECT(SELECT()=(FIRST()=(FIRST()-)- )FOLLOW(A)FOLLOW(A) ).20 7 7。 LLLL（1 1）文法）文法 一个文法一个文法G G是是LLLL（1 1）的，当且仅当对于）的，当且仅当对于G G的的每一个非终结符的任何两个不同产生式每一个非终结符的任何两个不同产生式 ，下面的条件成立：，下面的条件成立： SELECT(SELECT() SELECT() SELECT()=)= 其中其中和和不能同时不能同时=* .21z书中例子.22 5.2 LL5.2 LL（1 1）文法的判别

14、）文法的判别判别步骤：判别步骤：1 1）。求出能推出）。求出能推出的非终结符的非终结符.232 2）。）。 计算计算FIRSTFIRST集集1.1.若若X X V V , ,则则FIRST(X)=XFIRST(X)=X2.2.若若X X V VN N, ,且有产生式且有产生式X Xaa，则把，则把a a加入到加入到FIRST(X)FIRST(X)中中; ;若若X X也是一条产生式也是一条产生式, ,则把则把 也加到也加到FIRST(X)FIRST(X)中中. .3.3.若若X XYY是一个产生式且是一个产生式且Y Y V VN N, ,则把则把FIRST(Y)FIRST(Y)中的中的所有非所有

15、非 元元素都加到素都加到FIRST(X)FIRST(X)中中; ;若若X X Y Y1 1Y Y2 2YYK K 是是一个产生式一个产生式,Y,Y1 1,Y,Y2 2,Y,Y(i-1)(i-1)都是非终结符都是非终结符, ,而且而且, ,对对于任何于任何j,1j,1j j i-i-1, FIRST(Y1, FIRST(Yj j) )都含有都含有 ( (即即Y Y1 1.Y.Y(i-1) (i-1) =* ), ),则把则把FIRST(YFIRST(Yj j) )中的所有非中的所有非 元素元素和和FIRST(YFIRST(Yi i) )中的所有元素都加到中的所有元素都加到FIRST(X)FIRS

16、T(X)中中; ;特别特别是是, ,若所有的若所有的FIRST(YFIRST(Yj j , , j=1,2,K)j=1,2,K)均含有均含有 , ,则把则把 加到加到FRIST(X)FRIST(X)中中. . .243 3）。）。 计算计算FOLLOWFOLLOW集集1.1.对于文法的开始符号对于文法的开始符号S,S,置置# #于于FOLLOW(S) FOLLOW(S) 中中; ;2.2.若若BB是一个产生式是一个产生式, ,则把则把 FIRST()-FIRST()- 加至加至FOLLOW(B)FOLLOW(B)中中; ;3.3.若若BB是一个产生式是一个产生式, ,或或 B B是是 一个产生

17、式而一个产生式而 =* ( (即即FIRST()FIRST()），）， 则把则把FOLLOWFOLLOW（A A）加至）加至FOLLOWFOLLOW（B B）中）中.25G 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)=(,aFIRST(E)=+,FIRST(T)=(,aFIRST(T)=*,FIRST(F)=(,a各非终结符的FOLLOW集合为：FOLLOW(E)=),FOLLOW(E)=)，FOLLOW(T)=，)，FOLLOW(T)=,)，# F

18、OLLOW(F)=*,，),# .264）。 计算SELECT集z计算产生式的SELECT集.27G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F aE +TE | FIRST(+TE)=FIRST(+TE)=+ + FOLLOW(E)=FOLLOW(E)=) )，T *FT | FIRST(FIRST(* *FT)=FT)=* * FOLLOW(T)=FOLLOW(T)=+,)+,)，F (E) | a FIRST( (E)=FIRST( (E)=( ( FIRST( a)=FIRST( a)=a a

19、所以所以GEGE是是LLLL（1 1）的）的.285）。判断文法是否LL（1）文法z若文法所有具有相同左部产生式的SELECT集两两不相交，则文法是LL(1)文法。.29LL(1)LL(1)文法的性质文法的性质： LL(1)LL(1)文法是无二义的文法是无二义的 LL(1)LL(1)文法不含左递归文法不含左递归.305.3 5.3 某些非某些非LL(1)LL(1)文法的改造文法的改造1 1。提取左公共因子。提取左公共因子 提左公因子：提左公因子： 将产生式将产生式 | 变换为：变换为： B B B B | .31一般形式：z 1 1| | 2 2| n nz提取左公共因子后：提取左公共因子后：

20、 A AAA A A1 1|2 2|n n.322。消除左递归左递归 关于非终结符P的规则直接左递归 ： P P | | 、 V V* *且且、不以不以P开头一般 左递归 ： P =* P 例：例： SAa SAa A ASbSb .33消除文法中左递归规则消除文法中左递归规则1） 消除直接左递归： 形如：P P | | 非非 ， ，不以不以P P打头打头 改写为：P Q Q Q Q Q| Q| 其中Q为新增加的非终结符.34消除文法中左递归规则举例消除文法中左递归规则举例例:E E+T|T |T T T TT* *F|FF|F F F (E)| a(E)| a G E: (1) E TE (

21、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 2） 消除一般左递归的方法消除一般左递归的方法：（1 1） .以某种顺序将文法非终结符排列A1 ,A2 An（2 2） for i:=1 to n dofor i:=1 to n do begin begin for j:=1 to i-1 do 用Aj-1| 2| k 替代形如Ai- Ajr的规则, 其中Aj- 1| 2| k是关于Aj的全部产生式; 消除Ai规则的直接左递归; end; end;

22、（3 3）化简由（2）得到的文法:去掉无用产生式.36z例P90.37消除左递归和提左公因子并不一定都消除左递归和提左公因子并不一定都能将能将非非LL(1)LL(1)文法改造为文法改造为LL(1)LL(1)的的S S ifif C t S | C t S | ifif C t S e S C t S e SC bC b提左因子提左因子 S S ifif C t S A C t S A A e S | A e S | First First集集 FollowFollow集集S S ifif #,e #,eA e, A e, #, eC b tSelect(AeSAeS)Select(AA ) =

23、e#, e 改造后文法不是LL(1)文法.385.5 确定的自顶向下分析方法特征根据下一个(几个）输入符号为当前要处理 的非终结符选择产生式要求文法是LL(1)的 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号（lookahead).39无回溯的自顶向下分析程序预测分析程序的实现技术 1. 递归（下降）子程序 2. 表驱动分析程序.40例：例：递归下降子程序递归下降子程序ParseFunction()BNF（Backus-Naur Form）描述program function_listfunction_list function function_list

24、| function FUNC identifier ( parameter_list ) statementvoid ParseFunction()MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);ParseStatement();.41例：例：递归下降子程序递归下降子程序ParseFunction()（续）void MatchToken(int expected)if (lookahead != expected) printf(syntax

25、 error n);exit(0); else / if match, consume token and move onlookahead = yylex();/读入一个单词.42预测分析程序的实现预测分析程序的实现表驱动预测分析程序模型预测分析程序模型 Input Input #总控程序总控程序预测分析表预测分析表stack.43预测分析表构造算法预测分析表构造算法1.1.对文法对文法G G的每个产生式的每个产生式 执行第二步执行第二步 和第三步；和第三步；2.2.对每个终结符对每个终结符a a FIRST(FIRST( ) )，把，把 加加 至至A,aA,a中，中，3.3.若若 FIRS

26、T(FIRST( ) )，则对任何，则对任何b b FOLLOW(A)FOLLOW(A) 把把 加至加至A,bA,b中，中，4.4.把所有无定义的把所有无定义的A,aA,a标上标上“出错标志出错标志”。可以证明，一个文法可以证明，一个文法G G的预测分析表不含多重的预测分析表不含多重入口，当且仅当该文法是入口，当且仅当该文法是LL(1)LL(1)的的.44 例：表驱动予测分析程序予测分析程序G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a 用预测分析表表示状态转换。.45 a + * ( ) # E

27、 (1) (1) E (2) (3) (3) T (4) (4) T (6) (5) (6) (6) F (8) (7)G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a 预测分析表预测分析表.46表驱动预测分析程序分析算法预测分析程序分析算法 首先把首先把#然后把文法开始符号推入栈；把第一个输入符然后把文法开始符号推入栈；把第一个输入符号读进号读进b;b; FLAGFLAG：=TRUE=TRUE； WHILE FLAG DOWHILE FLAG DO BEGIN BEGIN 把栈顶符号上托出去并放在

28、把栈顶符号上托出去并放在中；中； IF X IF X Vt THEN IF X=b THEN Vt THEN IF X=b THEN 把下一个输入符号读进把下一个输入符号读进b b ELSE ERROR ELSE ERROR ELSE IF X= ELSE IF X=# # THEN THEN IF b= IF b=# # THEN FLAG:=FALSE THEN FLAG:=FALSE ELSE ERROR ELSE ERROR ELSE IF ELSE IF X,b=X X,b=X X X1 1X X2 2.X.XK K THEN THEN 把把X XK K，X X K-1K-1,.,X

29、,.,X1 1一一推进栈一一推进栈 ELSE ELSEERRORERROR END OF WHILE; END OF WHILE; STOP/ STOP/* *分析成功，过程完毕分析成功，过程完毕* *.47分析输入串#a+a#的步骤栈内容 栈顶符号 当前输入 余留串 MX,b 1 #E E a +a# E TE2 #ET T a +a# T FT3 #ETF F a +a# F a4 #ETa a a +a#5 # ET T + a# T 6 #E E + a# E +TE7 #ET+ + + a#8 # ET T a # T FT 9 #ETF F a # F a10 #ETa a a #

30、11 #ET T # T 12 #E E # E 13 # # #.48LL(1)分析中的一种错误处理办法发现错误发现错误1栈顶的终结符与当前输入符不匹配2非终结符A于栈顶，面临的输入符为a，但分析表M的MA,a为空“应急应急”恢复策略恢复策略跳过输入串中的一些符号直至遇到“同步符号”为止。同步符号的选择同步符号的选择1把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续2把FIRST(A)中的符号加到A的同步符号集，当FIRST(A)中的符号在输入中出现时，可根据A恢复分析.49review-parsingThe sy

31、ntax 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 pr

32、oductions 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. .50In the top-down parsing,we begin with the start symbol and at each step, expand one of the remaining nonterminals by replacing

33、 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

34、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.51 lookahead symbol. The lookahead symbol is the next symbol comi

35、ng 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 a

36、gain making a different choice and so on until it either found the production that was the appropriate one or ran out of choices.52predictive parser and LL(1)grammarPredictive parser is a non-backtracking top-down parser. A predictive parser is characterized by its ability to choose the production t

37、o 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

38、 the 1 means one input symbol of lookahead.53recursive-descentThe 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

39、 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.54Table-driven LL(1) parsing In a recursive-descent parser, the production information is embedded in the individua

40、l 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.

41、55 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 h

42、alts and parse completed successfully2. 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 cal

43、led 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.56The first set of a sequence of symbols u, written as First(u ) is the set of terminals whichstart all the sequences of symbols derivable from u. A bit more formally,

44、 consider allstrings derivable from u by a leftmost derivation. If u =* v , where v begins with someterminal, that terminal is in First(u). If u =* , then is in First(u ).57The follow set of a nonterminal A is the set of terminal symbols that can appear immediately to the right of A in a valid sente

45、ntial form. A bit more formally, for every valid sentential form S =*uAv , where v begins with some terminal, that terminal is in Follow(A).58Calculating first setTo 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

46、(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 nonnullable one.3. If X1X2.Xn =* , add to the first set.59Calculating follow sets. For each nontermin

47、al in the grammar, do the following:1. Place# in Follow(S) where S is the start symbol and # is the inputs right endmarker.The endmarker might be end of file, it might be newline, it might be a special symbol, whatever is the expected end of input indication for this grammar. We will typically use # as the endmarker.2. For every production A uBv where u and v are any string of grammar symbols and B