第4篇 语法分析—自上而下分析1.ppt

第4章 语法分析（1） 定义：设 G[S] = (VT ,VN , S , P) 是上下文无关文法，则 FIRST(x) = {a|x ay,a∈ VT,x,y ∈ V*} 若x ε，则规定ε∈FIRST(x) 实际上， FIRST(x)是指由符号串x出发能够推导出来的所有符号串中，处于串头的终结符号的集合。 提取公共左因子: 假定关于A的规则是 A→?? 1 | ?? 2 | …| ?? n | ? 1 | ? 2 | … | ?m (其中，每个? 不以?开头) 那么，可以把这些规则改写成: A→?A? | ? 1 | ? 2 | … | ? m A?→? 1 | ? 2 | … | ? n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。 * * 4.1 常用终结符号集 1、 FIRST集（首符号集） ? * ? * FIRST(X)可按以下算法求得： 设：X=X1X2…Xn，FIRST(X)=Φ，i=1则有： 1. 若Xi∈VT,则Xi∈FIRST(X),进入第4步; 2. 若Xi∈VN, ①若Xi ε,则FIRST(Xi)∈FIRST(X),进入第4步; ②若Xi ε,则FIRST(Xi)\ ε∈FIRST(X),然后令i=i+1, 若i≤n，进入第1步,否则进入第3步； 3.若 X ε，则ε∈FIRST(X)； 4.退出 ? * ? * ? * 定义：设 G[S] = (VT ,VN , S , P) 是上下文无关文法，A∈VN , 则  FOLLOW(A)={a|S …Aa… ,a∈VT}  若S …A，则规定 #∈FOLLOW(A) 实际上， FOLLOW(A)是指文法G[S] 的所有句型中， 紧跟在非终结符A后的终结符号的集合。 #作为输入串的结束符，或称为句子括号，如：abc# 2、 FOLLOW集（后继符号集） ? * ? * FOLLOW(A)可采用以下算法求得： 1.对于文法G[S]的开始符号S，有#∈FOLLOW(S)； 2.若文法G[S]中有形如U→xA的规则,其中x∈V﹡,则 FOLLOW(U)∈FOLLOW(A) 3.若文法G[S]中有形如U→xAy的规则,其中x∈V﹡,y∈V﹡, 当y ε时, FIRST(y)∈FOLLOW(A) 当y ε时, FIRST(y)\ ε∈FOLLOW(A) FOLLOW(U)∈FOLLOW(A) ? * ? * 定义:给定上下文无关文法的产生式A→x,A∈VN, x∈V*,则 若x ε，则SELECT(A→x)=FIRST(x) 若x ε，则SELECT(A→x)=FIRST(x)\ε∪FOLLOW(A) 实际上SELECT(A→x)是指，在推导过程中，如果采用 了A→x进行推导，下一个可能推导出的终结符号。 3、 SELECT集（可选集） ? * ? * 一、自顶向下分析方法 1.带回溯的自顶向下分析 所谓带回溯的自顶向下分析，实际上是指在推导过程中，总是试图用尽一切可能的方法进行推导。 2.确定的自顶向下分析 所谓确定的自顶向下分析方法，是指若输入串是文法的句子，则从文法的开始符号出发，每一步直接推导都只有唯一的规则可以选择。 条件： 对于文法，要能够进行确定的自顶向下分析，当且仅当对文法的任意非终结符号A，其所有的规则A→X1|X2|…|Xn满足： SELECT(A→Xi) ∩SELECT(A→Xj)=Φ 其中i,j=1,2, …,n,且i≠j. 4.2 语法分析方法概述 二、与自顶向下分析方法有关的文法变换 1.SELECT集相交时的候选式提取左公因子； 只有当文法的每一非终结符的所有的规则SELECT集两两不相交时，才能进行确定的自顶向下分析。当文法不满足确定自顶向下分析的条件时，则须改造文法，即对SELECT集相交的候选式提取左公因子。 2.消除文法的左递归； 当采用最左推导的自顶向下的分析方法，如果文法具有左递归，将使分析过程陷入无限循环。在左递归文法中，对于左递归的非终结符，其规则的SELECT集必然相交。因此消除左递归，是进行确定的自顶