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

第四章 语法分析--自上而下分析 引言 在词法分析完成之后，进入语法分析阶段。 语法分析是编译过程的核心。其任务是：在词法分析识别出的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。 语法分析的基础——上下文无关文法 语法分析的 输入：单词符号串 输出：程序的内部中间表示形式。 4.2 自上而下分析面临的问题 自上而下分析的实质：从推导的角度看，从文法的开始符号出发，自上而下，推出句子。（一般是最左推导） 自上而下分析的主旨：对任何输入串，试图尝试一切可能的办法，文法的开始符号（根节点）出发，试图自上而下建立一个语法树，其末端节点正好与输入符号串相同。 例4.1 上述过程面临的一些问题 左递归问题 回溯 成功的暂时性 不成功时找不到出错的位置 效率底、代价高（穷尽一切方法） 1.1 消除直接左递归 2.1 消除回溯 为什么要消除回溯？ ——无回溯就意味着不用做无谓的尝试。 如何消除回溯？ 对于任一非终结符号A的产生式的右部的后选式： ? 1| ? 2|…| ? n，如果其对应的第一个终结符号两两各不相同，那么A在匹配过程中就不用试探了，而是根据所面临的输入符号a唯一确定用哪个后选式匹配，即该后选式的成败全权代表了A。 FIRST（ ? ）求法示例 文法G4.2 E ::= TE’ E’ ::= + TE’ | ? T ::=FT’ T’ ::= *FT’| ? F ::= ( E ) | i FOLLOW(B)的算法（书P79） 步骤1 文法的开始符号S，置# ?FOLLOW(B) 步骤2 如果有规则A→? B ? ，那么FIRST(?)中所有的非?符号都在FOLLOW(B)中。 步骤3 如果有规则A→ ? B或则 A→ ? B ?且? ?FIRST(?)，那么FOLLOW(A)中的一切符号都在FOLLOW(B)中。 注意：步骤3需要重复执行，直到没有哪个非终结符号的FOLLOW集合增长为止。 FOLLOW例子 文法G4.3’[E]: E→TE’ E’ →TE’| ? T→FT’ T’ →*FT’| ? F→ (E)|i FOLLOW(E)={#,)} FOLLOW(E’)=FOLLOW(E)={#,)} FOLLOW(T)=FIRST(E’)?FOLLOW(E)-{?}={+,#,)} FOLLOW(T’)=FOLLOW(T)= {?}={+,#,)} FOLLOW(F)=FIRST(T’) ?FOLLOW(T)= {+,#,),*} LL(1)分析条件 满足构造不带回溯的自上而下分析的文法，即LL（1）文法的判定条件： (1)文法不含左递归。 （2）对文法的每个非终结符号A 的任何后选首符集两两不相交A → ?1 | ?2 | ?3 … | ?n 满足如下条件： FIRST(?i )?FIRST(?j ) =? （i不等于j） （3）如果某个非终结符号A，如果它的某个后选式首符集包含 ?，那么 FIRST(A) ?FOLLOW(A)=? 无回溯的自顶向下分析技术 先决条件： 无递归 既没有规则左递归，也没有文法左递归。 无回溯性 对于任一非终结符号U的规则右部x1|x2|…|xn，其对应的字的头终结符号两两不相交。 递归下降分析技术（实现思想） 实现思想： 识别程序由一组过程组成。每个过程对应于一个非终结符号。 每一个过程的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该终结符号对应的过程来完成。 递归下降技术（实例） 文法G4.3 E → E+T|T T → T*F F →(E)|i 消左递归得到 E → TE’ E’ → +TE’| ? T → FT’ T’ → *FT’| ? F →(E)|i 递归分析程序的优点 实现思想简单明了。程序结构和语法规则有直接的对应关系。 因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 需要书写程序的语言支持递归调用。如果递归调用机制是高效的，那么分析程序也是高效的。 预测分析表 利用预测分析表进行预测分析 预测分析表的构造 当我们需要将U选择某个规则展开时，如果当前的输入为a，表示我们要将U展开为以a为首符号的字。如果有规则U::=u，且a ?FIRST(u)，那么表示这个规则是个好的选择。 分析表构造算法 对于每个规则U → u，执行一下步骤 对于每个终结符号a ?FIRST(u)，A[U,a]=‘U → u’. 如果? ?FIRST(y)，对于每个FOLLOW(U)中的每个终结符号b和#，让A[U,b]=‘U → ?’。 将其它为定义的分析表元素为ERROR。 分析表的例子 文法G4.3’[E]: E → TE’ E’ → +TE’| ? T → FT’ T’ → *