编译原理——第4章 自顶向下语法分析

1、语法分析的作用语法分析的作用 是编译程序的核心部分。其作用是识别由词法分析给出的是编译程序的核心部分。其作用是识别由词法分析给出的 单词符号序列是否是给定文法的正确句子单词符号序列是否是给定文法的正确句子(程序程序)。语法分析方法概述语法分析方法概述 按照构建语法树的方式可分为自顶向下和自底向上分析。按照构建语法树的方式可分为自顶向下和自底向上分析。1 确定的自顶向下分析思想确定的自顶向下分析思想 综述：关键是从文法的开始符号出发，如何根据当前的输综述：关键是从文法的开始符号出发，如何根据当前的输入符号入符号(单词单词)唯一地确定选用哪个产生式向下推导，或构唯一地确定选用哪个产生式向下推导，或

2、构造一棵相应的语法树。造一棵相应的语法树。 注：该推导一定是最左推导。注：该推导一定是最左推导。第四章第四章 自顶向下语法分析自顶向下语法分析例例1GS: S pA | qB A cAd | a B dB输入以下单词序列 : pccadd分析树将以下面产生式开始 S pA特点：分析时，选取产生式的过程是唯一确定的特点：分析时，选取产生式的过程是唯一确定的例例2type simple | id | array simple of typesimple integer | char | num dotdot num开始符号开始符号 自顶向下分析 自顶向下生成语法树 考虑右边的文法:输入以下单词序列

3、 : array num dotdot num of integer分析树将以下面产生式开始 type array simple of type特点：产生式的右部含有非终结符的情况特点：产生式的右部含有非终结符的情况输入 : array num dotdot num of integertypesimpleofarraytypenumnumdotdotsimpletypesimpleofarraytypenumnumdotdotsimpleinteger向前指针向前指针对一个文法符号串的开始符号集合定义如下：对一个文法符号串的开始符号集合定义如下：定义定义1 设设G=(VT ，VN ，S，P)

4、是上下文无关文法是上下文无关文法FIRST()=a | a，a VT ， ， V * 若若 ，则规定，则规定 FIRST() *例例3输入以下单词序列 : abd分析树将以下面产生式开始 S aA特点：某一非终结符含有空产生式的情况特点：某一非终结符含有空产生式的情况GS: S aA S d A bAS A 定义一个文法符号的后跟符号的集合：定义一个文法符号的后跟符号的集合：定义定义2 设设G=(VT ，VN ，S ，P)是上下文无关文法是上下文无关文法A VN , S是文法的开始符号是文法的开始符号FOLLOW(A)=a | S A且且a VT ， a (FIRST()-) ， VT * ,

5、 V + 若若S A 且且 ，则，则# FOLLOW(A)也可定义为：也可定义为： FOLLOW(A)= a | S Aa ，a VT 若若S A ，则，则# FOLLOW(A)这里用这里用#作为输入串的结束符或称为句子括号，如作为输入串的结束符或称为句子括号，如#输入串输入串#*综合以上情况定义选择集合综合以上情况定义选择集合SELECT如下：如下：定义定义3 给定上下文无关文法的产生式给定上下文无关文法的产生式A ， A VN ， V * ，若，若 ，则，则SELECT(A )=FIRST()如果如果 ，则，则SELECT(A )=(FIRST()-) U FOLLOW(A)*更进一步能够

6、使用自顶向下分析技术必须使文法满足如下条更进一步能够使用自顶向下分析技术必须使文法满足如下条件，我们称满足条件的文法为件，我们称满足条件的文法为LL(1)文法，其定义为：文法，其定义为：定义定义4 一个上下文无关文法是一个上下文无关文法是LL(1)文法的充分必要条件是，文法的充分必要条件是，对每个非终结符对每个非终结符A的两个不同产生式，的两个不同产生式， A ， A 满足满足SELECT(A ) SELECT(A )=其中其中、 不同时推出不同时推出例例4GS: S aAS S b A bA A 该文法是否可用确定的自顶向下分析方法分析？该文法是否可用确定的自顶向下分析方法分析？LL(1)文

7、法的判别文法的判别求出能推出求出能推出 的非终结符的非终结符计算产生式右部的计算产生式右部的FIRST集集计算非终结符的计算非终结符的FOLLOW集集计算产生式的计算产生式的SELECT集集(只针对同一个非终结符对应多只针对同一个非终结符对应多条产生式的情况条产生式的情况)。对第对第4步的结果两两求交集以判断是否是步的结果两两求交集以判断是否是LL(1)文法。文法。例例5GS: S AB S bC A b A B B aD C AD C b D aS D c该文法是否可用确定的自顶向下分析方法分析？该文法是否可用确定的自顶向下分析方法分析？3 某些非某些非LL(1)文法到文法到LL(1)文法的

8、等价变换文法的等价变换提取左公共因子提取左公共因子若文法中含有形如若文法中含有形如A |的产生式等价变换为：的产生式等价变换为：A A AA A |推广到一般形式为：推广到一般形式为：A 1|2| n提取左公共因子后变为：提取左公共因子后变为：A A AA A 1|2|n若产生式中仍含有左公共因子，可再次提取。若产生式中仍含有左公共因子，可再次提取。GS: S aSb S aS S 试消除该文法的左公共因子。试消除该文法的左公共因子。GS: A ad A Bc B aA B bB对于产生式右部有非终结符开始的先替换后提取。对于产生式右部有非终结符开始的先替换后提取。GS: S aSd S Ac

9、 A aS A b替换后检查是否有无用产生式产生。替换后检查是否有无用产生式产生。GS: S Ap|Bq A aAp|d B aBq|e无法消除左公共因子。无法消除左公共因子。请注意以下两点：请注意以下两点：不一定每个文法的左公共因子都能在有限的步骤内替换不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。成无左公共因子的文法。一个文法提取了左公共因子后，只解决了相同左部产生一个文法提取了左公共因子后，只解决了相同左部产生式右部的式右部的FIRST集不相交问题，当改写后的文法不含空集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是产生式，且无左递归时，则

10、改写后的文法是LL(1)文法，文法，否则还需用否则还需用LL(1)文法的判别式进行判断才能确定是否文法的判别式进行判断才能确定是否为为LL(1)文法。文法。含有左递归的文法一定不是含有左递归的文法一定不是LL(1)文法文法GS: S Sa S b 输入：输入：baaa#GS: A aB A Bb B Ac B d 输入：输入：adbcbcbc#消除左递归消除左递归一个文法含有下列形式的一个文法含有下列形式的产生式时称该文法含有左递归：产生式时称该文法含有左递归：A A A VN V * 直接左递归直接左递归A B B A A , B VN , V * 间接左递归间接左递归形如形如A A 称文法

11、中含有间接左递归称文法中含有间接左递归消除直接左递归：消除直接左递归：方法：方法：将直接左递归改写为右递归。将直接左递归改写为右递归。S Sa | b改写为改写为: S bS S aS | 一般情况下，假定关于一般情况下，假定关于A的全部产生式是：的全部产生式是：A A1 | A2 | | Am | 1 | 2 | | n消除直接左递归后改写为：消除直接左递归后改写为：A 1 A | 2 A| | n AA 1 A | 2 A | | m A | 消除间接左递归：消除间接左递归：对于间接左递归的消除需先将间接左递归变为直接左递归，对于间接左递归的消除需先将间接左递归变为直接左递归，然后再用消除

12、直接左递归的方法来消除。然后再用消除直接左递归的方法来消除。 GA: A aB A Bb B Ac B d消除文法中一切左递归的算法：消除文法中一切左递归的算法：把文法的所有非终结符按某一顺序排序把文法的所有非终结符按某一顺序排序按排列的顺序逐次消除直接左递归按排列的顺序逐次消除直接左递归去掉无用产生式去掉无用产生式看下例：看下例：GS: S Qc | c Q Rb | b R Sa | a试消除该文法的一切左递归试消除该文法的一切左递归 4 4 确定自顶向下分析方法确定自顶向下分析方法递归子程序法递归子程序法预测分析法预测分析法递归子程序法递归子程序法举例：举例：E TE E + TE |

13、T FT T * FT | F ( E ) | idmain() TD_E();TD_T() TD_F(); TD_T();TD_E() TD_T(); TD_E();TD_E() token = get_token(); if token = + then TD_T(); TD_E(); TD_F() token = get_token(); if token = ( then TD_E(); match(); else if token.value id then error + EXIT else .TD_T() token = get_token(); if token = * the

14、n TD_F(); TD_T(); 如何处理如何处理 -产生式产生式?注意注意: 并未并未显示所有出显示所有出错条件，造错条件，造成纠错延时成纠错延时.预测分析法模型预测分析法模型a+b$YX$Z输入输入预测分析程序预测分析程序Stack输出输出分析表分析表 MA,a(String + 终止符终止符)基于栈与输入来决定基于栈与输入来决定采取什么动作采取什么动作空栈标识空栈标识预测分析法举例：预测分析法举例：语法语法: E ET | T T T * F | F F i | (E) 输入输入 : i + i * i $E TE E + TE | T FT T * FT | F ( E ) | i消除左递归消除左递归 !预测分析表预测分析表 M非终结符非终结符输入字符输入字符i+*()$EETTFETETFTFiE+TET T*FTF(E)TFTETET E E T $E$ET$ETF$ETi$ET$E$ET+$ET$ETF$ETi$ET$ETF*$ETF$ETi$ET$E$i + i * i$i + i * i$i + i * i$i + i * i$+ i * i$+ i * i$+ i * i$i * i$i * i$i * i$* i$