编译原理 第4章 语法分析—自上而下分析1

语法分析( 第4章 语法分析(1)

4.1 常用终结符号集1、 FIRST集(首符号集) FIRST集 首符号集) 定义：设 G[S] = (VT ,VN , S , P) 是上下文无关文法，则 是上下文无关文法，* ay,a∈ FIRST(x) = {a|x ay,a∈ VT,x,y ∈ V*} * ε,则规定ε 若x ε,则规定ε∈FIRST(x) 实际上， FIRST(x)是指由符号串 是指由符号串x 实际上， FIRST(x)是指由符号串x出发能够推导出来的 所有符号串中，处于串头的终结符号的集合。 所有符号串中，处于串头的终结符号的集合。

FIRST(X)可按以下算法求得： 可按以下算法求得： 可按以下算法求得 则有： 设：X=X1X2…Xn,FIRST(X)=Φ,i=1则有： , 则有 1. 若Xi∈VT,则Xi∈FIRST(X),进入第 步; 进入第4步 进入第 2. 若Xi∈VN, * 进入第4步 ①若Xi ε,则FIRST(Xi)∈FIRST(X),进入第 步; ∈ 进入第 * 然后令i=i+1, ②若Xi ε,则FIRST(Xi)\ ε∈FIRST(X),然后令 然后令 i≤n,进入第1步 否则进入第 否则进入第3步 若i≤n,进入第 步,否则进入第 步； 3.若 X ε,则ε∈FIRST(X); 若 * ; 4.退出 退出

2、 FOLLOW集(后继符号集) FOLLOW集 后继符号集) 定义：设 G[S] = (VT ,VN , S , P) 是上下文无关文法， 是上下文无关文法，A∈VN , 则 FOLLOW(A)={a|S * …Aa… ,a∈VT} ,a∈V

* …A 若S ,则规定 #∈FOLLOW(A) …A, 实际上， FOLLOW(A)是指文法 是指文法G[S] 的所有句型中， 实际上， FOLLOW(A)是指文法G[S] 的所有句型中， 紧跟在非终结符A后的终结符号的集合。 紧跟在非终结符A后的终结符号的集合。 #作为输入串的结束符，或称为句子括号，如：abc# 作为输入串的结束符，或称为句子括号，

FOLLOW(A)可采用以下算法求得： FOLLOW(A)可采用以下算法求得： 可采用以下算法求得 1.对于文法G[S]的开始符号S,有#∈FOLLOW(S); 1.对于文法 对于文法G[S]的开始符号 的开始符号S FOLLOW(S); 2.若文法G[S]中有形如U→xA的规则,其中x∈V﹡,则 2.若文法 若文法G[S]中有形如 中有形如U→xA的规则 其中x 的规则, FOLLOW(U)∈ FOLLOW(U)∈FOLLOW(A) 3.若文法G[S]中有形如U→xAy的规则,其中x∈V﹡,y∈V﹡, 3.若文法 若文法G[S]中有形如 中有形如U→xAy的规则 其中x 的规则, ,y∈ * FIRST(y)∈FOLLOW(A) FIRST(y)∈ 当 y ε时 ,* 当 y ε时 ,

FIRST(y)\ ε∈FOLLOW(A) FIRST(y)\ FOLLOW(U)∈ FOLLOW(U)∈FOLLOW(A)

3、 SELECT集(可选集) SELECT集 可选集)定义:给定上下文无关文法的产生式A→x,A∈ 定义:给定上下文无关文法的产生式A→x,A∈VN, x∈V*,则 V*,则 * ε, SELECT(A→x)=FIRST(x) 若x ε,则SELECT(A→x)=FIRST(x) * ε, SELECT(A→x)=FIRST(x)\ 若x ε,则SELECT(A→x)=FIRST(x)\ε∪FOLLOW(A) 实际上SELECT(A→x)是指 在推导过程中， 实际上SELECT(A→x)是指，在推导过程中，如果采用 是指，

A→x进行推导 下一个可能推导出的终结符号。 进行推导， 了A→x进行推导，下一个可能推导出的终结符号。

4.2

语法分析方法概述

一、自顶向下分析方法 1.带回溯的自顶向下分析 1.带回溯的自顶向下分析 所谓带回溯的自顶向下分析，实际上是指在推导过程中， 所谓带回溯的自顶向下分析，实际上是指在推导过程中， 总是试图用尽一切可能的方法进行推导。 总是试图用尽一切可能的方法进行推导。 2.确定的自顶向下分析 2.确定的自顶向下分析 所谓确定的自顶向下分析方法， 所谓确定的自顶向下分析方法，是指若输入串是文法的句 则从文法的开始符号出发， 子，则从文法的开始符号出发，每一步直接推导都只有唯一的 规则可以选择。 规则可以选择。 条件： 条件： 对于文法，要能够进行确定的自顶向下分析， 对于文法，要能够进行确定的自顶向下分析，当且仅当对 文法的任意非终结符号A 其所有的规则A→X 满足： 文法的任意非终结符号A,其所有的规则A→X1|X2|…|Xn满足： SELECT(A→Xi) ∩SELECT(A→Xj)=Φ 其中i,j=1,2, …,n,且 其中i,j=1,2, …,n,且i≠j.

二、与自顶向下分析方法有关的文法变换 1.SELECT集相交时的候选式提取左公因子 1.SELECT集相交时的候选式提取左公因子； 集相交时的候选式提取左公因子； 只有当文法的每一非终结符的所有的规则 SELECT集两两不相交时 SELECT集两两不相交时，才能进行确定的自 集两两不相交时， 顶向下分析。当文法不满足确定自顶向下分析 顶向下分析。 的条件时，则须改造文法，即对SELECT集相 的条件时，则须改造文法，即对SELECT集相 交的候选式提取左公因子。 交的候选式提取左公因子。

提取公共左因子: 提取公共左因子 假定关于A的规则是 假定关于 的规则是 A→δβ 1 | δβ 2 | …| δβ n | γ 1 | γ 2 | … | γm δβ (其中，每个γ 不以δ开头 其中， 其中 每个γ 不以δ开头) 那么，可以把这些规则改写成: 那么，可以把这些规则改写成 A→δA′ | γ 1 | γ 2 | … | γ m δ ′ A′→β 1 | β 2 | … | β n ′ β 经过反复提取左因子， 经过反复提取左因子，就能够把每个非 终结符(包括新引进者 包括新引进者)的所有候选首符集变 终结符 包括新引进者 的所有候选首符集变 成为两两不相交。 成为两两不相交。

2.消除文法的左递归； 2.消除文法的左递归 消除文法的左递归； 当采用最左推导的自顶向下的分析方法， 当采用最左推导的自顶向下的分析方法， 如果文法具有左递归， 如果文法具有左递归，将使分析过程陷入无限 循环。在左递归文法中， 循环。在左递归文法中，对于左递归的非终结 其规则的SELECT集必然相交 集

必然相交。 符，其规则的SELECT集必然相交。因此消除 左递归，是进行确定的自顶向下分析的必然。 左递归，是进行确定的自顶向下分析的必然。

4.3 递归子程序法递归子程序法也称为递归下降分析法，是一种简 递归子程序法也称为递归下降分析法， 单直观易于构造的自顶向下分析方法，起方法思想是： 单直观易于构造的自顶向下分析方法，起方法思想是： 对文法的每一个非终结符号编制一个处理子程序，而 对文法的每一个非终结符号编制一个处理子程序， 处理子程序的代码结构则由相应的非终结符号的规则 右部所决定：规则右部的终结符号应与输入符号匹配， 右部所决定：规则右部的终结符号应与输入符号匹配， 规则右部的非终结符号与相应的子程序调用相对应。 规则右部的非终结符号与相应的子程序调用相对应。