《13Ch04SyntaxAnalysis2》由会员分享，可在线阅读，更多相关《13Ch04SyntaxAnalysis2（22页珍藏版）》请在金锄头文库上搜索。
1、确定的自上而下分析方法确定的自上而下分析方法 LL（1）预测分析法。（实验三）预测分析法。（实验三）又称预测分析法，是一种确定的自上而下语法分又称预测分析法，是一种确定的自上而下语法分析方法。析方法。基本思想：从基本思想：从S出发，生成句子的出发，生成句子的最左推导最左推导。选择合适产生式：从左到右扫描输入的字符串，选择合适产生式：从左到右扫描输入的字符串，每次通过向前查看每次通过向前查看1个字符，选择确定的产生式进个字符，选择确定的产生式进行行最左推导；最左推导；或者无法选择（此时字符串非法）或者无法选择（此时字符串非法） 递归下降分析法。（实验二）递归下降分析法。（实验二） 两种方法都仅对
2、两种方法都仅对LL(1)文法文法适用。适用。College of Computer1Copyright SE Dept GPC关于关于LL（1）文法）文法 第一个第一个 L 从从左左到右扫描输入串到右扫描输入串 第二个第二个 L 生成的是最生成的是最左左推导推导 1 向前看一个输入符号向前看一个输入符号 在我们针对在我们针对LL（1）文法）文法所描述的语言进所描述的语言进行语法分析时，对于一个任意输入的行语法分析时，对于一个任意输入的正确正确句子句子 w，总可以找到唯一的最左推导与之，总可以找到唯一的最左推导与之对应。对于一个对应。对于一个错误的句子错误的句子w，总可以由，总可以由推导过程快速
3、的判断出来。推导过程快速的判断出来。College of Computer2Copyright SE Dept GPCLL（1）文法的定义）文法的定义设设U是文法是文法G的任一个非终结符，其产生式为的任一个非终结符，其产生式为 U:=x1|x2|xn 如果有如果有 FIRST(xi) FIRST(xj) = (i j；i ,j=1,2.n) 而当而当 FIRST(xi) 时，有时，有 FIRST(xi) FOLLOW(U) = ( i =1,2.n ) 则文法则文法G为为LL(1)文法。文法。什么是什么是 FIRST() ； FOLLOW() College of Computer3Copyr
4、ight SE Dept GPC什么是什么是FIRST集集 简单说，简单说，First集就是文法的集就是文法的某个字符串某个字符串可能推导出的可能推导出的最左终结符集合最左终结符集合。对于对于X(VNVT)* ,FIRST(X) 的构造方法的构造方法1：若：若X VT，则，则FIRST(X)=X2：若若X VN，且有产生式，且有产生式X:=a,a VT ， 则则a FIRST(X)；如果；如果X:= ，那么，那么 FIRST(X)。3：若若有产生式有产生式X:= Y,Y VN ,则则FIRST(Y)- FIRST(X); 如果有产生式如果有产生式X:=Y1Y2YK, 其中其中Y1，Y2，Yi1
5、 VN 且且Y1Y2。Yi1* , 则则FIRST(Yi) - FIRST(X)； 若若Y1Y2YK * ，则，则 FIRST(X)。College of Computer4Copyright SE Dept GPC求求FIRST集集举例举例设有文法设有文法G(S): S aAbDe | d A BSD | e B SAc | cD | D Se | 考虑考虑First(aAbDe)=?First(BSD)=?First(D)=?College of Computer5Copyright SE Dept GPC什么是什么是FOLLOW集集 简单说，简单说，Follow集就是对于集就是对于某个非
6、终结符某个非终结符而言，该非而言，该非终结符在文法句型中紧跟其后的可能出现的终结符在文法句型中紧跟其后的可能出现的终结符集合终结符集合。1、# FOLLOW(S) 注：注：S为文法开始符号为文法开始符号 2、如果有产生式、如果有产生式 A:=xUy 那么那么 FIRST(y) - FOLLOW(U)。 3、如果有产生式、如果有产生式 A:=xU 或有或有 A:=xUy 且且 y可空可空 那么那么FOLLOW(A) FOLLOW(U) 。注意：上述步骤注意：上述步骤3需要重复执行，直到没有哪个非终结符需要重复执行，直到没有哪个非终结符号的号的FOLLOW集合增长为止。集合增长为止。College
7、 of Computer6Copyright SE Dept GPC求求FOLLOW集集举例举例设有文法设有文法G(S): S aAbDe | d A BSD | e B SAc | cD | D Se | 考虑每个考虑每个Vn的的follow集集因为因为S是识别符号，且有是识别符号，且有ABSD; BSAc; DSe 有：有：follow（S）=# U First(D) U Follow(A) U First(Ac) U First(e) = a, c, d, e, # U Follow(A) 因因Follow(A)尚未求出。尚未求出。College of Computer7Copyrigh
8、t SE Dept GPC判断一个文法是否是判断一个文法是否是LL（1）定义法定义法，通过求出各，通过求出各First，Follow集，依次考察文法各集，依次考察文法各产生式是否满足定义条件，若满足则判定文法是产生式是否满足定义条件，若满足则判定文法是LL（1）文法；若有产生式不满足条件，则直接给出，并指明文法文法；若有产生式不满足条件，则直接给出，并指明文法不是不是LL（1）文法。）文法。可制表说明可制表说明非终结符是否可空First()Follow()SACollege of Computer8Copyright SE Dept GPCLL（1）文法判断例题）文法判断例题有文法：ETEE+
9、TE| TFTT*FT| Fi|（E）非终非终结符结符是否是否可空可空First()Follow()EN( i) #E Y+ ) #TN( i+ ) #T Y* + ) #FN( i* + ) #College of Computer9Copyright SE Dept GPC实验二（实验二（递归下降分析法）递归下降分析法）实现思想：实现思想： 识别程序由一组子程序组成。每个子程识别程序由一组子程序组成。每个子程序对应于一个序对应于一个非终结符号非终结符号。 每一个子程序的功能是：选择正确的右每一个子程序的功能是：选择正确的右部，扫描完相应的字符。如果在右部中又有部，扫描完相应的字符。如果在右
10、部中又有非终结符号时，再调用该非终结符号对应的非终结符号时，再调用该非终结符号对应的子程序来完成。子程序来完成。College of Computer10Copyright SE Dept GPC递归下降分析方法（基本步骤）递归下降分析方法（基本步骤）1 1）构造文法及改造文法：消除二义性、消除左递归、提）构造文法及改造文法：消除二义性、消除左递归、提取左因子等。取左因子等。2 2）求每个）求每个候选式的候选式的FIRSTFIRST集集 和和 非终结符的非终结符的FOLLOWFOLLOW集集3 3）检查是不是）检查是不是 LL(1) LL(1) 文法文法若不是若不是 LL(1),LL(1),说
11、明文法的复杂性超过自顶向下方法的说明文法的复杂性超过自顶向下方法的分析能力，可在编程时附加新的分析能力，可在编程时附加新的“信息信息”。4 4）为每个非终结符构造一个为每个非终结符构造一个子程序框图子程序框图。5 5）按按程序流程图程序流程图编写程序（编写程序（文法开始符号文法开始符号对应的子程序对应的子程序 为入口）。为入口）。College of Computer11Copyright SE Dept GPC递归下降分析程序基本架构递归下降分析程序基本架构(1) 对于每个非终结符号对于每个非终结符号U:= 1| 2| n处理方法如下：处理方法如下：P（U） if chFIRST(1 )th
12、en P(1) /处理处理1的程序部分的程序部分 else if chFIRST(2 )then P(2) /处理处理2的程序部分的程序部分 else if chFIRST(n )then P(n) else if chFOLLOW(U)then return /处理空产生式情况处理空产生式情况 else error 对于无回溯的文法保证选择是唯一的。当存在空产生式的对于无回溯的文法保证选择是唯一的。当存在空产生式的时候，可以时候，可以把把error替代替代为为return,这样的处理使发现错误的这样的处理使发现错误的情况比较晚。情况比较晚。College of Computer12Copyr
13、ight SE Dept GPC递归下降分析程序基本架构递归下降分析程序基本架构(2)对于每个右部对于每个右部 =x1x2xn的处理架构如下：的处理架构如下：P( ) begin P(x1 ); /处理处理x1的程序的程序 P(x2 ); /处理处理x2的程序的程序 P(xn ); /处理处理xn的程序的程序 end 说明：如果右部为空，则不处理。说明：如果右部为空，则不处理。College of Computer13Copyright SE Dept GPC递归下降分析程序基本架构递归下降分析程序基本架构(3)对于右部中的每个符号对于右部中的每个符号xi如果如果xi为终结符号：为终结符号：i
14、f(ch= a)READ (ch)/对于终结符，直接将指针前调对于终结符，直接将指针前调elseerror如果如果xi为非终结符号，直接调用相应的过为非终结符号，直接调用相应的过程：程：p (xi)College of Computer14Copyright SE Dept GPC递归下降技术（实例）文法文法GE := E+T | T T := T*F | T F:=(E)|i消左递归得到等价的消左递归得到等价的LL（1）文法）文法E := TEE:=+TE | T := FTT:= *FT | F:=(E)|iCollege of Computer15Copyright SE Dept GP
15、C递归下降技术（实例续）递归下降技术（实例续）对应于文法对应于文法G中的每个非终结中的每个非终结符号，都有一个过程。符号，都有一个过程。P(E) if chFIRST(T) then P (T); P (E); elseerror;College of Computer16Copyright SE Dept GPC递归下降技术（实例续）递归下降技术（实例续）P (E)if(ch=+)READ(ch); P (T); P (E)；elsereturn;因为因为E E对应有空产生式，对应有空产生式，所以处理中，不做错误处理，所以处理中，不做错误处理，而是直接而是直接returnreturn。表示它
16、没有读入任何字符。表示它没有读入任何字符。College of Computer17Copyright SE Dept GPC递归下降技术（实例续）递归下降技术（实例续）P(T) if chFIRST(F) then P (F); P (T); elseerror;College of Computer18Copyright SE Dept GPC递归下降技术（实例续）递归下降技术（实例续）P (T)if(ch=*)READ(ch); P (F); P (T)；elsereturn;空产生式，直接空产生式，直接return。表示没有读表示没有读入任何字符。入任何字符。College of Co
17、mputer19Copyright SE Dept GPC递归下降技术（实例续）递归下降技术（实例续）P (F)if(ch=i) thenREAD(ch); else if ch=() then READ(ch) ; P (E); if ch=)then READ(ch)elseerror;College of Computer20Copyright SE Dept GPC递归分析程序的主程序递归分析程序的主程序假设识别符号对应的过程为假设识别符号对应的过程为S()，那么相应那么相应的主程序为的主程序为预处理，读入要处理的字符串。预处理，读入要处理的字符串。 P(S);College of Computer21Copyright SE Dept GPC递归分析程序的优点递归分析程序的优点 实现思想简单易懂。程序结构和语法产实现思想简单易懂。程序结构和语法产生式有直接的对应关系。生式有直接的对应关系。 因为每个过程表示一个非终结符号的处因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。理，添加语义加工工作比较方便。 要求源程序支持递归调用。如果递归调要求源程序支持递归调用。如果递归调用机制是高效的，那么分析程序也是高效用机制是高效的，那么分析程序也是高效的。的。College of Computer22Copyright SE Dept GPC
