第四章语法分析-自上而下分析

《第四章语法分析-自上而下分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第四章语法分析-自上而下分析编译原理第四章语法分析一自上而下分析第四章语法分析一自上而下分析知识结构：带回溯分析法回溯白上而下分析面临的问题左递归问题的解决语法分析一求FIRST、FOLLOW集合的算法自上而下分析分析法证明LL(1)文法构造LL⑴分析表递归子程序的构造思想递归了程序法递归了程序的特点递归子程序的设计第一节语法分析综述一、语法分析的任务按照语言即定的语法规则，对字符串形式的源程序进行语法检杳，并识别岀相应的语法成分。即语法结构是否符合语法规则。二、语法分析器在编译程序中的地位(一遍扫描)制作人：李明新共28页第

2、1页13-4-28编译原理第四章语法分析一自上而下分析三、语法分析方法通常把语法分析方法分为两人类，既自上而下分析与自下而上分析。1、自上而下分析方法实际上是一种产生的方法，分析过程是一个推导过程。⑴口上而下分析过程从文法G的开始符号S岀发，通过反复使用产生式，逐步推导出与输入的符号串完全相匹配的句了。采用最左推导，以文法开始符号为根结点，逐步为输入串自上而下地构造一棵语法树。面临的输入符号为a,A所有的产生式：A12n①若aFISRT(i),则指派去执行匹配任务。②若a不属于任何一个候选首字符集，贝归a.若属于某个FISRT

3、(i)且aFOLLOW(A),则让A与自动匹配；b、否则，a的出现是一种错误。例：设有文法G和输入符号串W：a*a+aG：SaAaABaAB+-*/推导过程：SaAaBaAa*aAa*aBaAa*a+aAa*a+a二W制作人：李明新共28页笫2页13-4-28编译原理第四章语法分析一自上而下分析构造语法树：(2)自上而下分析法自上而下分析法又叮分为确定和不确定的两种。①不确定的分析法(带回溯)是一种穷举的试探方法，效率低、代价高，极少使用。①确定的分析法(不带回溯)实现方法简单、直观，便于手工构造或自动生成语法分析器，是目前常

4、用的方法之一。但是对文法有一定的限制。2、自下而上分析法(1)自下而上分析过程分析过程是归约过程。从给定的输入串W开始，不断寻找与文法G中某个产生式P的侯选式(右部)进行匹配，并用P代替也称为归约。(2)自下而上分析法①算符优先分析法定义算符(广义讲是文法的终结符号)Z间的某种优先和结合关系，借助这种关系來寻找并确定可归约字符串，并进行归约。制作人：李明新共28页第3页13-4-28编译原理第四章语法分析一口上而下分析②LR分析法是一类自左向右对输入串进行扫描的自下而上分析方法，分析过程是规范归约的序列。适用于语法分析器的自动

5、构造。第二节自上而下分析面临的问题一、不确定的自上而下分析方法是从文法的开始S出发，试图用一切可能的方法向下推导，产生句子，这种分析过程的本质是一种试探推导过程。例：文法G⑴SaAd(2)Aaba构造W二aad的最左推导：SaAdaado构造语法树：①产生树的根结点，即文法的开始符号。②选用文法G的文法规则去延伸树。③判断当前延伸的子结与输入串扫描到的字符是否匹配。④若不匹配注销掉当前延伸的子树，选用文法规则的另一个产生式延伸分析树。⑤直到输入串与语法树末端结点相匹配，分析结束。aba这种试探识别句子的过程，只会使分析的过程不

6、确定。制作人：李明新共28页第4页13-4-28编译原理第四章语法分析一自上而下分析二、不确定性的原因由于分析过程中选择的侯选式不确定，造成输入串匹配的假象，甚至会导致算法实现的失败。1、左递归问题由于采用最左推导，左递归将使得输入串的分析过程陷入无限循环Z屮。2、回溯问题⑴采用试探的方法，如匹配不成功冋溯到前血分析的某一-步。⑵可能出现假匹配，造成对输入串识别的失败。⑶不能准确报告输入串的出错位置。三、确定的自上而下分析方法1、确定的自上而下分析方法的必要条件(1)消除文法中的左递归;⑵消除文法屮的回溯问题。2、消除文法的左

7、递归文法的左递归可以通过对文法产生式进行改写，使Z不含有左递归的非终结符号。左递归一般冇两种情况，直接左递归和间接左递归。⑴直接左递归如呆文法中任意一个非终结符P,若PP(VNUVT),并且在最左推导中有PP形式，称为直接左递归。⑵间接左递归制作人：李明新共28页第5页13-4-28编译原理第四章语法分析一自上而下分析+在最左推导中有P二〉P形式，称为间接左递归。①消除岂接左递归P->P

8、改写为：p-PPP例：表达式文法EE+TT改写为：ETEE+TETT*FF改写为：TFTT*FTF(E)i②消除文法的左递归一般规则p->p

9、1p2””Pm12niH改写为：p->IP2P,,,,,,nPp->IP2P“mP③消除间接左递归A-B,,B-C,,间接左递归：AB„C„A,,C—A,,制作人：李明新共28页第6页13-4-28编译原理第四章语法分析一自上而下分析例：文法GS—Qc

10、cQfRb

11、bRfSa