第4章语法分析

1、第第4 4章语法分析章语法分析编译程序的功能和组织结构表表 处处 理理词法分析源源程程序序目目标标程程序序错错 误误 处处 理理语法分析语义分析目标代码生成前 端后 端中间代码优化中间代码生成3 3语法分析概述 语法分析语法分析 4.1 自顶向下分析 4.1.1 自顶向下分析思想 4.1.2 LL（1）文法 4.1.3 递归下降分析法 4.1.1 自顶向下分析思想7 7. 1.自顶向下分析方法特点2. 自顶向下分析存在的问题及解决方法1） 左递归文法：在采用最左推导的自顶向下分析中，左递归的存在是十分有害在采用最左推导的自顶向下分析中，左递归的存在是十分有害的，例如，考虑文法的，例如，考虑文法

2、GSGS： S SSa|bSa|b，分析输入串，分析输入串baaabaaa是否为是否为文法的合法句子。按照自顶向下分析法，对输入串文法的合法句子。按照自顶向下分析法，对输入串baaabaaa的当前的当前输入符输入符b b从开始符号从开始符号S S开始进行最左推导，若首次使用开始进行最左推导，若首次使用S SSaSa则则可能得到：可能得到： S SSaSaSaaSaaSaaaSaaaSaaaaSaaaa 证明的关键步骤：证明的关键步骤：lP-P | lP- | | | | lP- ( | | | | )lP- P， P- | | | | lP- P， P- | P文法文法lE-E+T | TlT

3、-T*F | FlF-(E) | i消除左递归后：消除左递归后：lE-TE， E-+TE | lT-FT， T-*F T| lF-(E) | i基本思想基本思想先用代入法把间接左递归变成直接左递归，再消除先用代入法把间接左递归变成直接左递归，再消除直接左递归，最后去掉多余规则以化简文法。直接左递归，最后去掉多余规则以化简文法。算法说明算法说明要求文法不能含有回路要求文法不能含有回路( (即形如即形如P P + + P P的推导的推导) )，并且，并且不含不含 作为作为规则的右部。规则的右部。2） 回溯问题非终结符的候选式的首符集两两不相交非终结符的候选式的首符集两两不相交 符号串符号串的所有可

4、能推导出的开头终结符或的所有可能推导出的开头终结符或文法文法G G：S cAd A ab |a S cAd A ab |a 识别识别输入串输入串w=cadw=cad试探：推导过程：S cAd cabd SSScAd c A d a b 回溯：试探推导过程：S cAd cad S c A d a对对S： FIRST(Aa)=d，c， FIRST(Bb)=a，b， FIRST(Aa) 对对A： FIRST(d)=d， FIRST(CA)=c， FIRST(d) 对对B： FIRST(b)=b， FIRST(aB)=a， FIRST(b) S=Bb=aBb=abb2323消除回溯的途径：消除回溯的途

5、径：4.1.2 LL(1)4.1.2 LL(1)分析法分析法1、LL分析程序构造及分析过程i+*()#EETEETEEE+TEEETT FTT FTTTT*FTTTFFiF(E) i + * ( ) # E E : : = T E E : : = T E E F : : = i E : : = + T E E : : = E : : = T T : : = F T T : : = F T T T : : = T : : = * F T T : : = T : : = F F : : = i F : : = ( E ) i + * ( ) # E E : : = T E E : : = T E

6、E E : : = + T E E : : = E : : = T T : : = F T T : : = F T T T : : = T : : = * F T T : : = T : : = F F : : = i F : : = ( E ) 3737由定义可见，由定义可见，SELECT(Ax)实际上是指在推导实际上是指在推导过程中，若采用规则过程中，若采用规则Ax进行推导时，可能推进行推导时，可能推导出的下一个终结符号组成的集合。导出的下一个终结符号组成的集合。 3939+LLLL（）分析方法（）分析方法 使用这种方法进行语法分析，可借助于一张分析表及一个语法分析栈，在一个总控程序控制下

7、很方便地实现。LL（）分析器的逻辑结构和工作过程。LL（）分析器的构造方法。LLLL（）分析器的逻辑结构：（）分析器的逻辑结构：在逻辑上，一个在逻辑上，一个LLLL（）分析器由一个总控（）分析器由一个总控程序、一张分析表和一个分析栈组成程序、一张分析表和一个分析栈组成 。 LLLL（）分析方法分析程序模型（）分析方法分析程序模型# #总控程序总控程序预测分析表预测分析表stackstackInput Input a1a2an#InputInput“输入”即待分析的符号串（在输入串的末尾放置一个#，仅为了分析算法格式的统一）。预测分析表M可用一个矩阵（或二维数组）来表示，它概括了相应文法的全部信

8、息。矩阵 的每一行与文法的一个非终结符号A相关联，而每一列则与文法的一个终结符号或#相关联。分析表元素分析表元素MAMA，aa或者指示了当前推导所应使用的或者指示了当前推导所应使用的产生式，或者产生式，或者 指出了输入串中含有语法错误。指出了输入串中含有语法错误。F(E) FiFTTT*FTTTTFTTFTTEEE+TEEETEETEE#)(*+iGE GE （1 1）E TEE TE（2 2）E E+TE+TE（3 3）E E （4 4）TFTTFT （5 5）T T* *FTFT （6 6）T T （7 7）F F （E E） （8 8）F iF iLLLL（）分析方法（）分析方法第一步

9、分析开始时，首先将符号#及文法的开始符号S依次置于分析栈底部，并把各指示器调整至起始位置，即初始格局为：#Sa a1 1a a2 2a an n# #分析器对每一输入串的分析在总控程序控制下进行。其算法如下：第二步设在分析的某一步，分析栈及余留的输入符号串处于如下的格局。 #X#X1 1X X2 2X Xm-1m-1X Xm ma ai ia ai+1i+1# # X1 X2Xm-1 Xm为分析过程中所得的文法符号，此时，可视栈顶符号Xm的不同情况，分别做如下的动作： 、若XmVN，则以Xm及ai组成符号对（Xm， a，）查分析表M，设MXm，ai为一产生式，譬如说XmUVW，此时将Xm从分析

10、栈中退出，并将UVW按反序推入栈中（即用该产生式推导一步），从而得到新的格局。#X#X1 1X X2 2。X Xm-1m-1WVUWVUaiai+1#LLLL（）分析方法（）分析方法但若MXm，ai=“ERROR”，则调用出错处理程序进行处理：、若Xm=ai#，则表明栈顶符号已与当前正扫视的输入符号得到匹配，此时应将Xm（即ai）从栈中退出，并将输入符号指示器向前推进一个位置：、若Xm=ai=#，则表明输入串已完全得到匹配，此时即可宣告分析成功而结束分析工作。LL(1)LL(1)文法及文法及LL(1)LL(1)语言的性质语言的性质 任何任何LL(1)LL(1)文法都是无二义性的：文法都是无二义

11、性的： 若一文法中的非终结符含有左递归，则若一文法中的非终结符含有左递归，则它必然是非它必然是非LL(1)LL(1)文法：文法： 非非LL(1)LL(1)语言是存在的：语言是存在的： 存在一种算法，它能判定任一文法是否存在一种算法，它能判定任一文法是否为为LL(1)LL(1)文法：文法： 不存在这样的算法，它能判定上下文无不存在这样的算法，它能判定上下文无关语言能否由关语言能否由LL(1)LL(1)文法产生。文法产生。# LLLL（）分析表构造方法（）分析表构造方法 上述LL（）分析算法对于不同的LL（）文法都是相同的。也就是说，对不同的LL（）分析器而言，它们的总控程序都是相同的，不同的仅仅

12、是分析表。总控程序十分简单，非常容易实现，所以我们只着重讨论构造分析表的问题。 F(E) FiFTTT*FTTTTFTTFTTEEE+TEEETEETEE#)(*+iGEGE：（：（1 1）E TE E TE （2 2）E +TEE +TE（3 3）E E （4 4）T FTT FT（5 5）T T * *FTFT（6 6）T T （7 7）F F （E E）（）（8 8）F iF iLLLL（）分析表构造算法（）分析表构造算法、对文法G的每个产生式执行第二步和第三步：、对每个终结符aFIRST（）把加至A ，a中，、若 FIRST（），则对任何bFOLLOW（A）把加至A，b中，、把所有无定

13、义的A，a标上“出错标志”。F(E) FiFTTT*FTTTTFTTFTTEEE+TEEETEETEE#)(*+iG E： (1)E TE (2)E +TE (3)E (4)T FT (5)T *FT (6)T (7)F (E) (8)F iFIRST（E）=FIRST（T）=FIRST（F）=(，i，FIRST（E）=+，FIRST（T）=*，FOLLOW（E）=FOLLOW（E）=)，#，FOLLOW（T）=FOLLOW（T）=+，)，#，FOLLOW（F）=+，*，），），#。LLLL（）分析表构造算法（）分析表构造算法GEGE： （1 1） E TEE TE （2 2） E +TEE

14、+TE （3 3） E E （4 4） T FT T FT （5 5） T T * *FTFT （6 6） T T （7 7） F F （E E） （8 8） F iF i LLLL（1 1）分析方法）分析方法F(E) FiFTTT*FTTTTFTTFTTEEE+TEEETEETEE#)(*+i GEGE：（：（1 1）E TE E TE （2 2）E +TEE +TE（3 3）E E （4 4）T FT T FT （5 5）TT* *FTFT（6 6）T T （7 7）F F （E E） （8 8）FiFi步骤分析栈 余留输入串 所用产生式 1 1#E#Ei+ii+i* *i#i#ETEET

15、E2 2#ET#ET i+ii+i* *i#i# TFTTFT3 3#ETF#ETFi+ii+i* *i#i#FiFi4 4#ETI#ETIi+ii+i* *i#i#5 5#ET#ET +i+i* *i#i# T T 6 6#E#E+i+i* *i#i# E+TEE+TE7 7#ET+#ET+i+i* *i#i#8 8#ET#ET i i* *i#i# TFTTFT9 9#ETF#ETFi i* *i#i#FiFi1010 #ETi#ETii i* *i#i# 步骤 分析栈 余留输入串 所用产生式 11#ET *i# T*FT12#ETF* *i#13#ETF i#Fi14#ETi i#15#

16、ET# T16#E # E17# #成功LLLL（）文法（）文法一个文法G，若它的分析表M不含多重元素，则称它是一个LL（）文法。一个LL（）文法是无二义的，它所定义的语言恰好就是它的分析表M所能识别的全部句子。 LLLL（）文法的判定（）文法的判定一个文法G是LL（1）的，当且仅当对于G的每一个非终结符的任何两个不同产生式，下面的条件成立：、FIRST（）FIRST（）=，也就是和推导不出以同一个终结符a为首的符号串：它们不应该都能推出空字。*、假若 ，那么，FIRST（)FOLLOW（A）。也就是，若 。则所能推出的串的首符号不应在FOLLOW（A）中。非非LLLL（）文法的改造（）文法的

17、改造对每一个文法G G，尽管都可按上述算法为它们构造一个分析表M M。然而，在某些情况下，例如G存在左递归或二义性等等，则在相应的分析表中，必然会出现多重定义的元素。 非非LLLL（）文法的改造（）文法的改造消除左递归提左公因子将产生式| 变换为：BB |非非LLLL（1 1）文法的改造）文法的改造G=（S，A，B，C，a，b，c，P，S），其中，P由如下产生式组成：SabB，ASC，ABAA，A， BAbA，CB，Cc，因为FIRST（S）=aFIRST（A）=，a，b FIRST（B）=a，bFIRST（C）=a，b，c故由上述算法的规则1可知：MA，a中含有“ASC”及“ABAA”，MA

18、，b中含有“ABAA”。再由A中含有的产生式A，且bFOLLOW（A），故由规则2可知，MA，b中也含有产生式“A”。可见在此文法的分析表中，元素MA，a及MA，b都是多重定义的。原因，在于G中存在如下的问题。（）G中含有左递归变量A和B：（）对于G中的三个A产生式，有：FIRST（SC）FIRST（BAA）FIRST（BAA）FOLLOW（a）。也就是说，G不是一个LL（1）方法。 非非LLLL（1 1）文法的改造）文法的改造对于非LL（1）文法EE+T|T，T（E）|a（E）|a，经消除其中的左递归并对T-产生式提取左因子之后，我们就把它改造为如下的LL（1）文法：ETE E+TE|TaT

19、|（E），T（E）| 但是，并非所有的非LL（1）文法都能改造为LL（1）文法。因对于S-产生式，有FIRST（AU）FIRST（BR），故它不是一个LL（1）文法。为了对S-产生式提取左因子，将其中的非终结符号A，B分别以其各候选式替入，我们得到：例如，对于文法SAU|BR，AaAU|b，BaBR|b，Uc，Rd，SaAUU|bU|aBRR|bR经提取左因子后，得到了与原文法等价的新文法：SaS|bS，SU|RSAUU|BRR，AaAU|b，BaBR|b，Uc，Rd。显然，它仍不是一个LL（1）文法。且不难看出，无论把上述手续重复多次，都不能把它改造为LL（1）文法。 例：下面文法GS是否为

20、LL（1）文法？S AB|PQx A xyB bcP dP| Q aQ|，对S来说，由于xFIRST（AB），同时也有xFIRST（PQx）（因为P和Q都可能为空）FIRST（AB）FIRST（PQx），所以该文法不是LL（1）文法。例：设有以下文法：例：设有以下文法：GS：SaAbDe|d ABSD|e BSAc|cD| DSe|（1）求出该文法的每一个非终结符U的FOLLOW集。GS：SaAbDe|d ABSD|e BSAc| cD| DSe| S是识别符号，且有ABSD、BSAc、DSe，所以FOLLOW（S）应包含FIRST(D)FIRST(Ac)FIRST（e）#=a，da，d，c，

21、ee#=a，c，d，e#SaAbDe|d ABSD|e BSAc|cD| DSe| 又因为ABSD和D，所以FOLLOW（S）中还包含FOLLOW（A）。因为SaAbDe和BSac，所以FOLLOW（A）=FIRST（bDe）FIRST（c）=b，c综合、得FOLLOW（S）=a，d，c，e，#b，c SaAbDe|dABSD|e BSAc|cD|DSe|因为ABSD，所以FOLLOW（B）=FIRST（SD）=a，d 因为SaAbDe|d、ABSD|e和BSAc|cD，所以FOLLOW（D）=FIRST（e）FOLLOW（A）FOLLOW（B）=eb，ca，d=a，b，c，d，e4.1.3

22、4.1.3 递归子程序法（递归下降分析法）递归子程序法（递归下降分析法）递归下降分析法也称递归子程序法，是一种直观易于构造的递归下降分析法也称递归子程序法，是一种直观易于构造的自顶向下分析方法。自顶向下分析方法。思想思想对文法中的每个非终结符编写一个处理子程序，处理子程序的对文法中的每个非终结符编写一个处理子程序，处理子程序的代码结构由相应的非终结符的规则右部来决定：规则右部的终代码结构由相应的非终结符的规则右部来决定：规则右部的终结符号与输入符号相匹配，非终结符与相应的子程序调用相对结符号与输入符号相匹配，非终结符与相应的子程序调用相对应，非终结符对应的各个候选式与分支结构相对应。应，非终结

23、符对应的各个候选式与分支结构相对应。限制限制：对文法要求高，必须满足对文法要求高，必须满足LL(1)LL(1)文法：文法：由于递归调用多，速度慢，占用空间多。由于递归调用多，速度慢，占用空间多。尽管这样，它还是许多高级语言的编译系统尽管这样，它还是许多高级语言的编译系统经常采用的语法分析方法。经常采用的语法分析方法。 扩展的巴科斯范式(EBNF) EBNF是在BNF基础上扩展如下三组符号： “ ”：表示花括号内的语法成分可以重复： “ ”：表示方括号内的成分是可选项： “( )”：表示括号内的成分优先。 用EBNF改写文法 对于非终结符A的一组形如Ax|y|z|Aa的规则，可表示成A(x|y|

24、z)a。例如，对于规则EE+T|T，可以写成ET+T。例 设有文法GE： EE+T|E-T|T TT*F|T/F|F FPF|P P(E)|i 用EBNF表示消除左递归得到文法GE： ET(+|-)T TF(*|/)F FPP P(E)|i递归子程序 E的递归子程序 E() T()： while(w=“+”|w=“-”) get_w()： T()： T的递归子程序 T() F()： while(w=“*”|w=“/”) get_w()： F()： F的递归子程序 F() P()： while(w=“”) get_w()： P()： P的递归子程序 P() if(w=“(”) get_w()：

25、E()： if(w=“)”) get_w()： else error()： else if(w=“i”) get_w()： else error()： 另一个例子 对于文法GE： EE+T|T TT*F|F F(E)|i 经消除左递归后得到GE： ETE E +TE| TFT T *FT| F(E)|i E的递归子程序 E() T()： E()： E的递归子程序 E() if(w=“+”) get_w()： T()： E()： T的递归子程序 T() F()： T()： T的递归子程序 T() if(w=“*”) get_w()： F()： T()： F的递归子程序 F() if(w=“(”)

26、 get_w()： E()： if(w=“)”) get_w()： else error()： else if(w=“i”) get_w()： else error()： 4.2 自底向上分析4.2.1 移进移进-归约分析归约分析 (自底向上分析的一般过程自底向上分析的一般过程)4.2.2 简单优先分析法简单优先分析法4.2.3 算符优先分析法算符优先分析法 4.2.4 LR分析法分析法自底向上分析自底向上分析基本算法：4.2.1 移进移进归约分析（归约分析（Shift-reduce parsing)#L.R.P #符号栈符号栈输入串输入串要点要点：建立符号栈，用来纪录分析的历史和现状，：建立

27、符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是并根据所面临的状态，确定下一步动作是移进移进还是还是归约归约。步骤符号栈输入符号串分析动作1 # bbcde# 移进2 #b bcde# 归约(Ab)3 #A bcde# 移进4 #Ab cde# 归约(AAb)5 #A cde# 移进6 #Ac de# 移进7 #Acd e# 归约(Bd)8 #AcB e# 移进9 #AcBe # 归约(SAcBe)10 #S # 接受Aba)AbAbb)AbAbcdBc)cdBeAbAbSd)自下而上分析一般过程自下而上分析一般过程例：文法G：S cAd A a A ab识别输入串w=c

28、abd是否该文法的句子A A a ! S cAbd ?c a b d c a b d S A A c a b d c a b d c a b d 归约过程形成的推导：归约过程形成的推导：S S cAd cAd cabd cabd文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作1）#abbcde#移进移进2）#abbcde#移进移进A3）#abbcde#归约归约(Ab)4）#aAbcde#移进移进A5）#aAb cde#归约归约(AAb)6）#aAcde#移进移进7）#aAc de# 移进移进B

29、8） #aAcd e# 归约归约(Bd)9） #aAcB e# 移进移进11）#S # 接受接受S10）#aAcBe #归约归约(SaAcBe)分析符号串abbcde是否GS的句子对输入串对输入串abbcde#的移进的移进-规约分析过程规约分析过程SaAcBe aAcde aAbcde abbcde上述每一步都是归约当前句型的句柄。且句柄出现上述每一步都是归约当前句型的句柄。且句柄出现在符号栈栈顶，不会在栈中间，上述分析过程并未真正解在符号栈栈顶，不会在栈中间，上述分析过程并未真正解决句柄的识别问题。例如，对于上面的例子，分析进行到决句柄的识别问题。例如，对于上面的例子，分析进行到第（第（5

30、5）步，当时）步，当时 栈内符号串为栈内符号串为aAbaAb。根据该符号串，我。根据该符号串，我们有规则们有规则AAbAAb。和规则。和规则AbAb。那么，符号串。那么，符号串AbAb和和b b都是都是 某条规则的右部，故都有可能被判别是句型的句柄。假如某条规则的右部，故都有可能被判别是句型的句柄。假如我们选择我们选择b b作为句柄，并把作为句柄，并把b b归约归约 为为A A，那么，最终就达不，那么，最终就达不到归约到到归约到S S的目的。因而，我们也就的目的。因而，我们也就 无从得知输入串无从得知输入串abbcdeabbcde是一个句子了。是一个句子了。 文法文法GS：(1) S aAcB

31、e(2) A b(3) A Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进A 3） #ab bcde# 归约归约(Ab) 4） #aA bcde# 移进移进A 5） #aAb cde# 归约归约(AAb) 6） #aA cde# 移进移进 7） #aAc de# 移进移进B 8） # aAcd e# 归约归约(Bd) 9） #aAcB e# 移进移进11） #S # 接受接受S10） #aAcBe # 归约归约(SaAcBe)分析符号串abbcde是否GS的句子对输入串abbcde#

32、的移进-规约分析过程SaAcBe aAcde aAbcde abbcde在自底向上分析中，如何寻找确定一个句型的句柄是构造一个自左向右扫描，自底向上分析方法必须要解决的一个问题。在每一步中如何选择子串进行归约？文法GS，S AS A且且A A 则称则称是句型是句型相相对于非终结符对于非终结符A A的短语。的短语。*短语、直接短语、句柄短语、直接短语、句柄的定义：的定义：若有若有A A 则称则称是句型是句型相对于该相对于该规则规则AA的直接短语。的直接短语。一个句型的最左直接短语称为该句型的句柄。一个句型的最左直接短语称为该句型的句柄。基本问题基本问题 检查是否为句柄检查是否为句柄归约条件归约条

33、件 选用哪一条规则进行归约选用哪一条规则进行归约归约原则归约原则1、简单优先分析法概述简单优先分析法概述 基本思想基本思想 简单优先分析法的基本思想是对一个文简单优先分析法的基本思想是对一个文法按一定原则求出该文法的所有符号之法按一定原则求出该文法的所有符号之间的优先关系，按照这种关系确定归约间的优先关系，按照这种关系确定归约过程中的句柄以进行归约。过程中的句柄以进行归约。4.2.2 简单优先优先分析法简单优先优先分析法简单优先文法简单优先文法 若一个文法是简单优先文法，必须满足以下若一个文法是简单优先文法，必须满足以下条件：条件：在文法符号集在文法符号集V中，任意两个符号之间最多中，任意两个

34、符号之间最多只有一种优先关系成立：只有一种优先关系成立：在文法中任意两个产生式没有相同的右部。在文法中任意两个产生式没有相同的右部。 简单优先分析法的基本思想是找到形如简单优先分析法的基本思想是找到形如 Sj-1 Sj Sj+1 Si Si+1的句柄。的句柄。 简单优先分析法的算法思想是：在不断将输简单优先分析法的算法思想是：在不断将输入符号移进分析栈的过程中通过比较优先级，入符号移进分析栈的过程中通过比较优先级，首先发现句柄的尾，然后再反向找到句柄的首先发现句柄的尾，然后再反向找到句柄的头，从而找到句柄。之后寻找句柄以句柄为头，从而找到句柄。之后寻找句柄以句柄为右部的规则，如找到则进行规约，

35、否则出错右部的规则，如找到则进行规约，否则出错优先关系的定义 X Y 表示表示X与与Y的优先关系相等的优先关系相等 X Y 表示表示X优先级小于优先级小于Y的优先级的优先级 X Y 表示表示X优先级大于优先级大于Y的优先级的优先级注意：这里注意：这里 、 、 与数学中的与数学中的= =、 不同。不同。优先关系确定 定理定理 X Y 当且仅当当且仅当G中存在产生式中存在产生式AXY X Y 当且仅当当且仅当G中存在产生式中存在产生式AXB， 且且BY X Y 当且仅当当且仅当G中存在产生式中存在产生式ABD， 且且BX，DY+*例 若有文法GS： SbAb A(B|a BAa) 则确定的优先关系

36、用矩阵表示(称作优先关系矩阵)如下：SbA(Ba)SbA(Ba) 简单优先分析法是按照文法符号（终结符和简单优先分析法是按照文法符号（终结符和非终结符）的优先关系确定句柄的，因此我们首非终结符）的优先关系确定句柄的，因此我们首先介绍任意两个文法符号之间的优先关系是怎样先介绍任意两个文法符号之间的优先关系是怎样确定的，及如何构造优先关系表。确定的，及如何构造优先关系表。 1.1.简单优先分析法简单优先分析法按照文法符号（包括终结符和非终结符）按照文法符号（包括终结符和非终结符）的优先关系确定句柄。的优先关系确定句柄。首先定义优先关系的表示：首先定义优先关系的表示：X X Y Y 表示表示X X和

37、和Y Y的优先关系相等。的优先关系相等。X X Y Y 表示表示X X的优先性比的优先性比Y Y的优先性大。的优先性大。X X Y Y 表示表示X X的优先性比的优先性比Y Y的优先性小。的优先性小。这样我们就可以对已知文法对它的任意两个这样我们就可以对已知文法对它的任意两个文法符号文法符号X X，Y Y按其在句型中可能会出现的相邻关按其在句型中可能会出现的相邻关系来确定它们的优先关系。（注意系来确定它们的优先关系。（注意 、 、 和数学中的和数学中的= = 、 b=A=(=a=)#b=A=(=a=)#b=A=(=a=)#步骤步骤符号栈符号栈输入符号串输入符号串动作动作1）#b(aa)b#b，

38、移进，移进2）#b (aa)b# b(，移进，移进3）#b(aa)b#(a，归约，归约Aa5）#b(A a)b#A=a，移进，移进6）#b(Aa )b#a=)，移进，移进7）#b(Aa) b#)b，归约，归约BAa)8）#b(B b#Bb，归约，归约A(B9）#bA b#A=b，移进，移进10）#bAb #b#，归约，归约SbAb11）#S #接受接受对输入串b(aa)b#的简单优先分析过程简单优先关系矩阵4.2.3 算符优先分析法概述算符优先分析法概述算符文法算符文法定义：如果不含空产生式的上下文无关文法定义：如果不含空产生式的上下文无关文法 G G中没有形如中没有形如U UVWVW的产生式

39、，其中的产生式，其中V V，WVWVN N，则称则称G G为算符文法（为算符文法（OGOG）。）。性质性质1 1：在算符文法中任何句型都不包含两：在算符文法中任何句型都不包含两个相邻的非终结符。个相邻的非终结符。性质性质2 2：如：如VxVx或或xVxV出现在算符文法的句型出现在算符文法的句型 中，其中中，其中VVVVN N，xVxVT T，则，则 中任何含中任何含x x的短语必的短语必含有含有V V。定义：设定义：设G G是一个算符文法，是一个算符文法，a a和和b b是任意两是任意两个终结符，个终结符，A A、B B、C C是非终结符，算符优先关系是非终结符，算符优先关系 、 、 定义如下

40、：定义如下：算符文法的优先关系算符文法的优先关系（1 1）a a b b当且仅当当且仅当G G中含有形如中含有形如AAabab或或 AAaBbaBb的产生式。的产生式。（2 2）a a b b当且仅当当且仅当G G中含有形如中含有形如AAaBaB的的产生式，且产生式，且B bB b或或B CbB Cb。（3 3）a a b b当且仅当当且仅当G G中含有形中含有形AABbBb的的产生式，且产生式，且B B a a或或B B aCaC。 a b pp B b a B a b A AA(a)a b(b)a b(c)a ba b 当且仅当当且仅当G中含有形如中含有形如Aab或或AaBb的产生式的产生

41、式a b 当且仅当当且仅当G中含有形如中含有形如AaB的产生式，且的产生式，且B b或或B Cba b 当且仅当当且仅当G中含有形如中含有形如ABb的产生式，且的产生式，且B a或或B aC算符文法的优先关系算符文法的优先关系算符优先文法算符优先文法设有一不含设有一不含产生式的算符文法产生式的算符文法G G，如果对任意两个，如果对任意两个终结符对终结符对a a，b b之间至多只有之间至多只有 、 和和 三种关系的一种成三种关系的一种成立，则称立，则称G G一个算符优先文法。（一个算符优先文法。（Operator Precedence Operator Precedence GrammarGra

42、mmar）即）即OPGOPG文法。文法。 注意：允许注意：允许b b c c，c c b b，不允许，不允许b b c c，b b c c，b b c c。算符优先关系表的构造算符优先关系表的构造首先引入两个概念：由定义直接构造：FIRSTVTFIRSTVT（B B）= =b|B bb|B b或或B CbB Cb对于非终结符对于非终结符B B，其往下推导所可能出现的，其往下推导所可能出现的首个算符。首个算符。LASTVTLASTVT（B B）= =a|B a|B a a或或B B aCaC对于非终结符对于非终结符B B，其往下推导所可能出现的，其往下推导所可能出现的最后一个算符。最后一个算符。

43、算符优先关系算符优先关系1) 1) 关系关系直接看产生式的右部，若出现了直接看产生式的右部，若出现了AAabab或或AAaBbaBb，则，则a a b b2) 2) 关系关系求出每个非终结符求出每个非终结符B B的的FIRSTVTFIRSTVT（B B）若）若AAaBaB，则，则 bFIRSTVTbFIRSTVT（B B），），a a b b3) 3) 关系关系求出每个非终结符求出每个非终结符B B的的LASTVTLASTVT（B B）若）若AABbBb，则，则 aLASTVTaLASTVT（B B），），a a b b文法文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F

44、(4) TF(5) FP F|P(6) P(E)(7) Pi + * ( ) i # + * ( = i # * ( = i # = 算符优先分析算法算符优先分析算法算符优先分析法仍然是一种自底向上的分析算符优先分析法仍然是一种自底向上的分析算法，但不是严格从左到右的。在每一步分析中，算法，但不是严格从左到右的。在每一步分析中，它将识别和归约那些所谓的最左素短语。归约过它将识别和归约那些所谓的最左素短语。归约过程中，只考虑终结符之间的优先关系来确定句柄，程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归而与非终结符无关。这样去掉了单非终结符的归约，所以用算符

45、优先分析法的规约过程与规范归约，所以用算符优先分析法的规约过程与规范归约是不同的。约是不同的。为解决在算符优先分析过程中如何寻找句柄，为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念。引进最左素短语的概念。定义：文法定义：文法G G的句型的素短语是一个短语的句型的素短语是一个短语 ，它至少包含一个终结符，且除自身外不再包含其它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短他素短语。处于句型最左边的素短语为最左素短语。语。句型的素短语句型的素短语文法文法GEGE：（1 1）EE+TEE+T（2 2）ETET（3 3）TTTT* *F F（4 4）T

46、FTF（5 5）FPFP F|PF|P（6 6）PP（E E）（7 7）PiPi句型句型#T+T#T+T* *F+i#F+i#其短语有：其短语有：T+TT+T* *F+iF+iT+TT+T* *F FT TT T* *F Fi i+EET+ETF*FTTi最左素短语为：最左素短语为：T T*F F句型句型#N+N#N+N* *N+i#N+i#的归约过程的归约过程NN+NNi* NNN算符文法的任一句型有如下形式：算符文法的任一句型有如下形式：#N#N1 1a a1 1N N2 2a a2 2.N.Nn na an nN Nn+1n+1# #定理：定理： 一个一个OPGOPG句型的最左素短语是满

47、足下句型的最左素短语是满足下列条件的最左子串列条件的最左子串N Ni ia ai i.N.Nj ja aj jN Nj+1j+1，a ai-1i-1 a ai i a ai+1i+1 . . a aj-1j-1 a aj j a aj+1j+1出现出现在在a aj j右端或右端或a ai i左端的非终结符号一定属于这个素左端的非终结符号一定属于这个素短语。短语。 算符优先分析算法算符优先分析算法若若a a b b，则在，则在r r中必含有中必含有b b而不含而不含a a的短语存的短语存在。在。若若a a b b，则在，则在r r中必含有中必含有a a而不含而不含b b的短语存的短语存在。在。若

48、若a a b b，则在，则在r r中含有中含有a a的短语必含有的短语必含有b b反之反之亦然。亦然。由语法树和最左素短语的定义可以明显看出，由语法树和最左素短语的定义可以明显看出，下面归约过程，每次所归约的当前句型的最左子下面归约过程，每次所归约的当前句型的最左子串也就是句型的最左素短语。串也就是句型的最左素短语。 对于算符优先文法如果对于算符优先文法如果aNbaNb（或（或abab）出现在）出现在句型句型r r中：中：文法文法GE：（1）EE+T（2）ET（3）TT*F（4）TF（5）FPF|P（6）P（E）（7）Pi句型句型#T+T*F+i#最左素短语为：最左素短语为：T*FEE+F#+

49、#E+F#-4Fi#+i#E+i#-3ET+T#+i#T+T+i# -2TT*F#+*+i#T+T*F+i-1归约符号最左子串关 系句型步骤+EET+ETF* FTTi在上述分析中，虽然指出了每个素短语所应在上述分析中，虽然指出了每个素短语所应归约的非终结符号。但是请注意，在查找所应归归约的非终结符号。但是请注意，在查找所应归约的最左素短语的过程中，我们没有用到非终结约的最左素短语的过程中，我们没有用到非终结符号。算符优先文法在归约过程中只考虑终结符符号。算符优先文法在归约过程中只考虑终结符之间的优先关系确定句柄，而与非终结符无关。之间的优先关系确定句柄，而与非终结符无关。只需知道把当前句柄归

50、约为某一非终结符，只需知道把当前句柄归约为某一非终结符，不必知道该非终结符的名字是什么，因此，在符不必知道该非终结符的名字是什么，因此，在符号栈中放不放相应的非终结符号，对分析过程中号栈中放不放相应的非终结符号，对分析过程中寻找最左素短语是毫无影响的。故我们可以取任寻找最左素短语是毫无影响的。故我们可以取任意的名字来代替它们设立一个栈（运算对象栈）意的名字来代替它们设立一个栈（运算对象栈）来存放它们。来存放它们。现在，就可以来分析现在，就可以来分析OPGOPG文法的句子了。该文法的句子了。该 算法所遵循的原则是：每次归约均是归约当前句算法所遵循的原则是：每次归约均是归约当前句型的最左素短语。型

51、的最左素短语。 停止停止#N13# #N*N12# #N*(N)11#) #N*(N10#) #N*(N+N9#) #N*(N+i8)#i #N*(N+7i)#+ #N*(N6i)#+ #N*(i5+i)#i #N*(4i+i)#( #N*3(i+i)#* #N2(i+i)#* # i1*(i+i)#i #0T（k）R关系关系S（1）步骤步骤算符优先文法的句子分析过程算符优先文法的句子分析过程i i* *（i+ii+i）算符优先分析法就是仿照算术式的四则运算算符优先分析法就是仿照算术式的四则运算过程而设计的一种语法分析方法。实际上，该方过程而设计的一种语法分析方法。实际上，该方法在一开始就是为

52、了分析和翻译程序语言中的表法在一开始就是为了分析和翻译程序语言中的表达式而设计的。这种方法首先是要规定运算符之达式而设计的。这种方法首先是要规定运算符之间（更一般说是终结符号之间）的优先关系和结间（更一般说是终结符号之间）的优先关系和结合性质，然后就利用这种关系，用比较相邻运算合性质，然后就利用这种关系，用比较相邻运算符的优先顺序来确定句型的符的优先顺序来确定句型的“句柄句柄”和进行归约。和进行归约。 上述文法虽是二义性的（存在不同的规范归上述文法虽是二义性的（存在不同的规范归约），但用算符优先法分析其句子时，其归约过约），但用算符优先法分析其句子时，其归约过程是唯一的。我们所规定的运算符之间

53、的优先顺程是唯一的。我们所规定的运算符之间的优先顺序和左结合的原则，就是避免二义性的充分条件。序和左结合的原则，就是避免二义性的充分条件。直观直观算符优先分析法算符优先分析法通常在算术表达式求值过程中，运算次序是通常在算术表达式求值过程中，运算次序是先乘除后加减，这说明了乘除运算的优先级高于先乘除后加减，这说明了乘除运算的优先级高于加减运算的优级，乘除为同一优先级但运算符在加减运算的优级，乘除为同一优先级但运算符在前边的先做，同样加减运算也是如此，这也说明前边的先做，同样加减运算也是如此，这也说明了运算的次序只与运算符有关，而与运算对象无了运算的次序只与运算符有关，而与运算对象无关，因而直观算

54、符优先分析法的关键是对一个给关，因而直观算符优先分析法的关键是对一个给定文法定文法G G，人为地规定其算符的优先顺序，人为地规定其算符的优先顺序 ，即给，即给出优先级别和同一级别中的结合性质。出优先级别和同一级别中的结合性质。 但必须注意，这三个关系和数学中的但必须注意，这三个关系和数学中的 是不同的，它们是有序的，也就是若有是不同的，它们是有序的，也就是若有a a b b，不一定有不一定有b b a a，a a b b成立不一定有成立不一定有b b a a，例如：，例如：通常表达式中运算符的优先关系有通常表达式中运算符的优先关系有+ + - -，但没有，但没有- - + +成立，成立，（ ）

55、成立但没有成立但没有） （成立。成立。很显然所给表达式文法显然是二义性文法，很显然所给表达式文法显然是二义性文法，但我们认为直观地给出运算符之间的优先关系且但我们认为直观地给出运算符之间的优先关系且这种优先关系是唯一的。这种优先关系是唯一的。文法文法GEGE：EE+E|E-E|EEE+E|E-E|E* *E|E/E|EE|(E)|iE|E/E|EE|(E)|i文法文法GEGE：EE+E|E-E|EEE+E|E-E|E* *E|E/E|EE|(E)|iE|E/E|EE|(E)|i+-*/ ()i#+-*/ (=i#=步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1 1） # i+i# i+i

56、* *i# #ii# #i，移进，移进 2 2） #i +i#i +i* *i# #+i# #+，规约，规约 3 3） #E +i#E +i* *i# #+i# #+，移进，移进 4 4） #E+ i#E+ i* *i# +ii# +i，移进，移进 5 5） #E+i #E+i * *i# +i# +* *，规约，规约 6 6） #E+E #E+E * *i# +i# +* *，移进，移进 7 7） #E+E#E+E* * i# i# * *ii，移进，移进 8 8） #E+E#E+E* *i # i # * *#，规约，规约 9 9） #E+E#E+E* *E # +E # +#，规约，规约

57、1010） #E+E # #E+E # #，规约，规约1111） #E # #E # 接受接受对输入串i+i*i的算符优先分析过程算符优先关系表直观算符优先分析法直观算符优先分析法优先函数优先函数在实际上，实现算符优先分析法时，一般不在实际上，实现算符优先分析法时，一般不用文法的优先关系矩阵，而是用两个优先函数用文法的优先关系矩阵，而是用两个优先函数f f和和g g。对算符之间的优先关系，优先矩阵表示，。对算符之间的优先关系，优先矩阵表示，这样需占用大量的内存空间，当文法有这样需占用大量的内存空间，当文法有n n个非终个非终结符时，就需要有（结符时，就需要有（n+1n+1）2 2个内存单元（终

58、结符个内存单元（终结符和和# #号），因而，在实际应用中往往用优先函数号），因而，在实际应用中往往用优先函数来代替优先矩阵表示优先关系。来代替优先矩阵表示优先关系。它对具有它对具有n n个终结符的文法，只需个终结符的文法，只需2 2（n+1n+1）个单元存放优先函数，这样可节省大量的存储空个单元存放优先函数，这样可节省大量的存储空间。缺点是原先不存在优先关系的，由于间。缺点是原先不存在优先关系的，由于 与自与自然数相对应，变成可比较。然数相对应，变成可比较。优先函数优先函数我们可以定义两个函数我们可以定义两个函数f f，g g满足如下条件：满足如下条件：当当a a b b，则令，则令f f（a

59、 a）=g=g（b b）当当a a b b，则令，则令f f（a a）ggg（b b）对对f f，g g我们称它为优先函数。它的值可用整我们称它为优先函数。它的值可用整数表示。数表示。+*i（）#f3557171g2466611优先函数优先函数优先函数的构造优先函数的构造由定义直接构造优先函数：若已知文法G终结符之间的优先关系，可按如下步骤构造其优先函数f，g。a）对每个终结符aVT（包括#号在内）令f（a）=g（a）=1，（也可是其它整数）。b）如果a b，而f（a）g（b）则令 f（a）=g（b）+1。c）如果a b，而f（a）g（b）则令 g（b）=f（a）+1。d）如果ab，而f（a）

60、g（b）则令minf（a）， g（b）=maxf（a），g（b）。e）重复b）d）直到过程收敛。如果重复过程中有一个值大于2n，则表明该算符优先文法不存在算符优先函数。其优先函数的构造过程为：其优先函数的构造过程为：首先：把所有首先：把所有f f（a a），），g g（a a）的）的 值置为值置为1 1然然后对算符优先关系矩阵逐行扫描，按前述算法规后对算符优先关系矩阵逐行扫描，按前述算法规则的则的b b）e e）修改函数）修改函数f f（a a），），g g（a a）的值，这）的值，这是个迭代过程，一直进行到优先函数的值再无变是个迭代过程，一直进行到优先函数的值再无变化为止。化为止。优先函数优