编译原理语法4(自顶向下语法分析：LL分析法).ppt

《编译原理语法4(自顶向下语法分析：LL分析法).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7讲编译原理西北农林科技大学本科教程主讲教师：赵建邦第三章语法分析3.1文法和语言3.2推导与语法树3.3自顶向下的语法分析3.4自底向上的语法分析3.5规范规约的自底向上语法分析方法第三章《语法分析》3.3自顶向下的语法分析递归下降分析法（上一讲内容）LL(1)分析法重点掌握LL(1)分析器工作原理LL(1)分析表的构造FIRST集合、FOLLOW集合本讲目标3.3自顶向下的语法分析3.3.2LL(1)分析法LL(1)分析法又称预测分析法，是一种不带回溯的非递归自顶向下分析法。LL(1)的含义是：第

2、一个L表明自顶向下分析是从左至右扫描输入串的；第二个L表明分析过程中将用最左推导；“1”表明只需向右查看一个符号就可决定如何推导(即可知用哪个产生式进行推导)类似地，也可以有LL(k)文法，也就是向前查看k个符号才能确定选用哪个产生式，不过LL(k)(k>1)在实际中极少使用。1、表驱动的LL(1)分析器LL(1)分析法的基本思想根据输入串的当前输入符号来惟一确定选用某条规则(产生式)进行推导；当这个输入符号与推导第一个终结符相同时，再取输入串的下一个符号，继续确定下一个推导应选的规则；如此下去，直到推

3、导出被分析的输入串为止。举例：G[A]:A→aBcB→bB

4、d输入串：abbdc3.3自顶向下的语法分析AbBBcadbBaBcabBcabbBcabbdcabbdc1、表驱动的LL(1)分析器一个LL(1)分析器由一张LL(1)分析表(也称预测分析表)、一个先进后出分析栈和一个控制程序(表驱动程序)组成，如图3-16所示:3.3自顶向下的语法分析图3-16LL(1)分析器(1)输入串是待分析的符号串，它以界符“#”作为结束标志。(注：#∈VT但不是文法符号，是由分析程序自动添加的。)1、表驱动的LL(

5、1)分析器1、表驱动的LL(1)分析器(2)分析栈中存放分析过程中的文法符号。分析开始时栈底先放入一个“#”，然后再压入文法的开始符号；当分析栈中仅剩“#”，输入串指针也指向串尾的“#”时，分析成功。1、表驱动的LL(1)分析器(3)分析表用一个矩阵(或二维数组)M表示，它概括了相应文法的全部信息。一个文法：对应一个分析表；表中一行：对应一个非终结符；表中一列：对应一个终结符或者“#”。1、表驱动的LL(1)分析器②若x=a≠“#”，即栈顶符号x与当前扫描的输入符号a匹配；则将x从栈顶弹出，输入指针指向

6、下一个输入符号，继续对下一个字符进行分析。(4)控制程序根据分析栈顶符号x和当前输入符号a来决定分析器的动作：①若x=a=“#”，则分析成功，分析器停止工作。③若x为一非终结符A，则查M[A,a]：i．若M[A,a]中为一个A的产生式，则将A自栈顶弹出，并将M[A,a]中的产生式右部符号串按逆序逐一压入栈中；如果M[A,a]中的产生式为A→ε，则只将A自栈顶弹出。ii．若M[A,a]中为空，则发现语法错误，调用出错处理程序进行处理。控制程序描述如下：将“#”和文法开始符依次压入栈中；把第一个输入符号读

7、入a；do{把栈顶符号弹出并放入x中；if(x∈VT){if(x==a){if(a!=‘#’)将下一输入符号读入a;}elseerror();//字符串不匹配，语法错误}elseif(M[x,a]=″x→y1y2…yk″){按逆序依次把yk、yk−1、…、y1压入栈中;输出″x→y1y2…yk″;//显示当前分析所使用的规则}elseerror( );//分析表中没有当前产生式，语法错误}while(x!=″#″)1、表驱动的LL(1)分析器文法3.2的LL(1)分析表2、LL(1)分析表的构造在表驱

8、动的LL(1)分析器中，除了分析表因文法的不同而异之外，分析栈、控制程序都是相同的。因此，构造一个文法的表驱动LL(1)分析器的关键就是构造该文法的分析表。为了构造分析表M，需要预先定义和构造两族与文法有关的集合FIRST和FOLLOW3.3自顶向下的语法分析2、LL(1)分析表的构造关键概念之1：FIRST集合假定α是文法G[S]的任一符号串(α∈(VT∪VN)*)，可定义如果αε，则规定ε∈FIRST(α)。也即，FIRST(α)是α的所有可能推导的开头终结符或可能的ε。3.3自顶向下的语法分析FI

9、RST集合构造方法对文法中的每一个非终结符X构造FIRST(X)，其方法是连续使用下述规则，直到每个集合的FIRST不再增大为止。(注：对终结符a而言，FIRST(‘a’)={a}，因而无需构造。)①若有产生式X→a…，且a∈VT，则把a加入到FIRST(X)中；若存在X→ε，则将ε也加入到FIRST(X)中；②若有X→Y…，且Y∈VN，则将FIRST(Y)中的所有非ε元素(记为“{ε}”)都加入到FIRST(X)中；3.3自顶向下的语法