编译原理讲义
(第四章,语法分析 --
自顶向下分析技术 )
南京大学计算机系赵建华引言
在词法分析完成之后，进入语法分析阶段。
语法分析阶段的任务是：检查程序的语法是否正确，并生成内部中间表示形式。
语法分析的
– 输入：属性字序列。
– 输出：程序的内部中间表示形式。
自顶向下分析技术与识别算法
从推导的角度看，从识别符号出发，试图推导出与输入符号串相同的符号串。
一般来讲，构造出的推导是最左推导。
从语法树的角度看，从根节点，试图向下一个语法树，其末端节点正好与输入符号串相同。
讨论前提
输入的是符号序列，不对符号构造情况感兴趣。
语法分析的文法是上下文无关文法。
自顶向下分析技术的理论基础是定理 2.7：
如果 Z::=X1X2…Xn 且 y为句子。那么如果 X1X2…X n=>y，必然存在 y1,y2,…,y n使得 Xi=>*yi且 y=y1y2… y n。
要解决的基本问题
对于特定的终结符号，实用那个重写规则来替换？
无回溯的自顶向下分析技术
先决条件：
无递归
– 既没有规则左递归，也没有文法左递归。
无回溯性
– 对于任一非终结符号 U的规则右部 x1|x2|…|x n，
其对应的字的头终结符号两两不相交。
递归下降分析技术（实现思想）
实现思想：
识别程序由一组过程组成。每个过程对应于一个非终结符号。
每一个过程的功能是：选择正确的右部，
扫描完相应的字。在右部中有非终结符号时，调用该终结符号对应的过程来完成。
基本架构 (1)
对于每个非终结符号 U::=u1|u2|…|u n处理的方法如下,
U(){
ch=当前符号
if(ch可能是 u1字 的开头 ) 处理 u1的程序部分
else if(ch可能是 u2字 的开头 ) 处理 u2的程序部分
…
else error() }
对于无回溯的文法保证选择是唯一的。
当存在空规则的时候，可以把 error()替代为 {return;}这样的处理使发现错误的情况比较晚。
约定：进入这个过程时，对于 U的第一个符号已经被读到当前符号。离开这个程序的时候，下一个符号已经被读到当前符号。
基本架构 (2)
对于每个右部 u1=x1x2…x n的处理架构如下：
处理 x1的程序；
处理 x2的程序；
… … …
处理 xn的程序；
如果右部为空，则不处理。
基本架构 (3)
对于右部中的每个符号 xi
如果 xi为终结符号：
if(x== 当前的符号 )
{NextCh()； return;}
else
出错处理
如果 xi为非终结符号，直接调用相应的过程：
xi()
递归下降技术（实例）
文法 G4.3
E::=E+T|T T::=T*F F::=(E)|i
消左递归得到
E::=TE’ E’::=+TE’|? T::=FT’
T’::=*FT’|? F::=(E)|i
递归下降技术（实例续）
对应于文法 G4.3’中的每个非终结符号，都有一个过程。
E()
{
if(当前符号可能是 T的开始符号 )
{ T(); E1();}
else
error();
}
和书上不同的是，我们作了出错处理。一般，当只有一个右部的时候，
可以不作出错处理。
递归下降技术（实例续）
E1()
{
if(ch=‘+’)
{
getnextchar(); T(); E1()；
}
else
return;
}
因为 E1对应有空规则，所以其处理中，
不左错误处理，而是直接 return。实际表示它没有读入任何字符。
递归分析程序的运行栈底
E()
T()
输入,i * i + i
T1()
处理完 *，当前符号为 i
过程调用栈：
F()
递归分析程序的主程序
假设识别符号对应的过程为 Z()，那么相应的主程序为
{
GetSymbol(); //首先需要读入一个符号，以满
// 足约定。
Z();
}
递归分析程序的优点
实现思想简单明了。程序结构和语法规则有直接的对应关系。
因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。
需要书写程序的语言支持递归调用。如果递归调用机制是高效的，那么分析程序也是高效的。
预测分析法
使用下推自动机的方式实现。
使用一个二维分析表和栈联合进行控制来实现递归下降分析技术。
分析表 A实际上是一个从 VN?(VT?{#})到规则的映射。当自顶向下分析过程中需要将 U展开时，如果当前符号为 T时，应该选择规则 A[U,T]。如果 A[U,T]为空，
表示输入符号串不正确。
预测分析过程
PUSH(S,#)； PUSH(S,Z);
a=下一个符号； X=TOP(S);
如果 X为终结符号且 a==X且 a!=#,POP(S); a=下一个符号。
如果 X为终结符号且 a==X且 a==#，分析结束，接受句子。
如果 X为终结符号且 a!=X，出错处理。
如果 X为非终结符号且 A[X,a]为报错标识，出错处理。
如果 X为非终结符号且 A[X,a]=‘X= X1 X2…X n1,
{ POP(S);
将右部 Xn …X 2 X1压入 S中。
}
例子
文法 G4.3’[E]
E::=TE’ E’::=+TE’|? T::=FT’
T’::=*FT’|? F::=(E)|i
例子
i + * ) #(
E TE’ TE’
E’ +T
E’
T FT’ FT’
T’? FT’
F i (E)
i+i*i#
i+i*i#
+i*i#
i*i#
+i*i#
i+i*i#
+i*i#
i+i*i#
i*i#
i*i#
*i#
#E
#E’T
#E’T’F
#E’T+
#E’T
#E’T’
#E’T’i
#E’
#E’T’i
#E’T’F
#E’T’
预测分析表的生成
从前面的论述我们看到，预测分析过程的驱动程序时固定的。对于某个文法，
分析表是分析过程的核心。
表中 A[U,T]=‘U::=X1X2…X n’表示对应于
X1X2…X n字的首符号可以是 T。就是说
X1X2…X n=>*Tw。我们可以通过这个方式来确定分析表中的值。
预测分析表的生成
一般来讲，对于一个符号串 X1X2…X n的字的第一个终结符号就是 X1对应的字的第一个终结符号。但是空规则的存在是情况有一点复杂。
对于 U1U2…U n，如果 U1=>*?，那么符号串对应的字的首符号也可以是 U2对应的字的首符号。计算一个符号串对应的字的首符号的算法也需要考虑到这些。
FIRST(u)和 FOLLOW(U)
FIRST(u)={T|u=>*T…,T?VT}，如果 u=>*?，
那么，我们规定 FIRST(u)。
FOLLOW(U)={T|Z=>* … UT…,T?VT?{#}}
其中，如果 Z=>*…U,那么 #?FOLLOW(U)
直观地讲：
– FIRST(u)包含了 u对应的字的所有可能的首终结符号。
– FOLLOW(U)表示了句型中可能紧跟再 U后面的终结符号
FIRST(u) 构造算法
对于文法 X构造 FIRST(X)
– 步骤 1：如果 X?VT，那么 FIRST(X)={X}
– 步骤 2,如果 X?VN，且有规则 X::=T…,那么将 T添加到 FIRST(X)中。如果 X::=?，那么?也再 FIRST(X)中。
– 步骤 3：对于规则 X::= X1X2…X n,把 FIRST(X1)中的非
符号添加到 FIRST(X)中。如果?在 FIRST(X1)中，把
FIRST(X2)中的非?符号添加到 FIRST(X)中 … ；如果?
在 FIRST(Xn)中，把?添加到 FIRST(X)中。
对于 FIRST(u)，可是使用类似于步骤 3的方法求解得到。
FIRST的例子
文法 G4.3’[E]:
E::=TE’ E’::=+TE’|? T::=FT’
T’::=*FT’|? F::=(E)|i
FIRST(F)={ (,i }
FIRST(T)=FIRST(F)= { (,i }
FIRST(E’)={ +,?} FIRST(T’)={*,?}
… … … …
FOLLOW(U)的构造算法
步骤 1 #?FOLLOW(Z)
步骤 2 如果有规则 U::=xWy，那么 FIRST(y)中所有的非?符号都在 FOLLOW(W)中。
步骤 3 如果有规则 U::=xW或则 U::=xWy且?
FIRST(y)，那么 FOLLOW(U)中的一切符号都在 FOLLOW(W)中。
注意：步骤 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)= {+,#,),*}
预测分析表的构造
基本思想：
当我们需要将 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’::=*FT’|?
F::=(E)|i
i + * ) #(
E TE’ TE’
E’ TE’
T FT’ FT’
T’? FT’
F i (E)
分析表的冲突
文法 G4.6[S] S::=iCtSS’|a S’::=eS|? C::=b
FIRST(iCtSS’)={i} FIRST(eS)={e}
FIRST(S)={i,a} FIRST(C)={b}
FIRST(S’)={e,?}
FOLLOW(S)=FOLLOW(S’)={#,e}
a b e i t #
S a iCtSS’
S’ eS;?
C b
LL(1)文法
定义：如果其预测分析表中没有多重定义的元素，
则该文法被称为 LL(1)文法。
LL(1)文法是无二义性的。
定理 4.1，文法 G是 LL(1)的，当且仅当每个非终结符号 U的任何两个不同的重写规则 U::=x | y满足如下条件：
– FIRST(x)?FIRST(y)=?
– x=>*?和 y=>*?不能同时成立
– 如果 x=>*?，那么 FIRST(x)?FOLLOW(y)=?
(第四章,语法分析 --
自顶向下分析技术 )
南京大学计算机系赵建华引言
在词法分析完成之后，进入语法分析阶段。
语法分析阶段的任务是：检查程序的语法是否正确，并生成内部中间表示形式。
语法分析的
– 输入：属性字序列。
– 输出：程序的内部中间表示形式。
自顶向下分析技术与识别算法
从推导的角度看，从识别符号出发，试图推导出与输入符号串相同的符号串。
一般来讲，构造出的推导是最左推导。
从语法树的角度看，从根节点，试图向下一个语法树，其末端节点正好与输入符号串相同。
讨论前提
输入的是符号序列，不对符号构造情况感兴趣。
语法分析的文法是上下文无关文法。
自顶向下分析技术的理论基础是定理 2.7：
如果 Z::=X1X2…Xn 且 y为句子。那么如果 X1X2…X n=>y，必然存在 y1,y2,…,y n使得 Xi=>*yi且 y=y1y2… y n。
要解决的基本问题
对于特定的终结符号，实用那个重写规则来替换？
无回溯的自顶向下分析技术
先决条件：
无递归
– 既没有规则左递归，也没有文法左递归。
无回溯性
– 对于任一非终结符号 U的规则右部 x1|x2|…|x n，
其对应的字的头终结符号两两不相交。
递归下降分析技术（实现思想）
实现思想：
识别程序由一组过程组成。每个过程对应于一个非终结符号。
每一个过程的功能是：选择正确的右部，
扫描完相应的字。在右部中有非终结符号时，调用该终结符号对应的过程来完成。
基本架构 (1)
对于每个非终结符号 U::=u1|u2|…|u n处理的方法如下,
U(){
ch=当前符号
if(ch可能是 u1字 的开头 ) 处理 u1的程序部分
else if(ch可能是 u2字 的开头 ) 处理 u2的程序部分
…
else error() }
对于无回溯的文法保证选择是唯一的。
当存在空规则的时候，可以把 error()替代为 {return;}这样的处理使发现错误的情况比较晚。
约定：进入这个过程时，对于 U的第一个符号已经被读到当前符号。离开这个程序的时候，下一个符号已经被读到当前符号。
基本架构 (2)
对于每个右部 u1=x1x2…x n的处理架构如下：
处理 x1的程序；
处理 x2的程序；
… … …
处理 xn的程序；
如果右部为空，则不处理。
基本架构 (3)
对于右部中的每个符号 xi
如果 xi为终结符号：
if(x== 当前的符号 )
{NextCh()； return;}
else
出错处理
如果 xi为非终结符号，直接调用相应的过程：
xi()
递归下降技术（实例）
文法 G4.3
E::=E+T|T T::=T*F F::=(E)|i
消左递归得到
E::=TE’ E’::=+TE’|? T::=FT’
T’::=*FT’|? F::=(E)|i
递归下降技术（实例续）
对应于文法 G4.3’中的每个非终结符号，都有一个过程。
E()
{
if(当前符号可能是 T的开始符号 )
{ T(); E1();}
else
error();
}
和书上不同的是，我们作了出错处理。一般，当只有一个右部的时候，
可以不作出错处理。
递归下降技术（实例续）
E1()
{
if(ch=‘+’)
{
getnextchar(); T(); E1()；
}
else
return;
}
因为 E1对应有空规则，所以其处理中，
不左错误处理，而是直接 return。实际表示它没有读入任何字符。
递归分析程序的运行栈底
E()
T()
输入,i * i + i
T1()
处理完 *，当前符号为 i
过程调用栈：
F()
递归分析程序的主程序
假设识别符号对应的过程为 Z()，那么相应的主程序为
{
GetSymbol(); //首先需要读入一个符号，以满
// 足约定。
Z();
}
递归分析程序的优点
实现思想简单明了。程序结构和语法规则有直接的对应关系。
因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。
需要书写程序的语言支持递归调用。如果递归调用机制是高效的，那么分析程序也是高效的。
预测分析法
使用下推自动机的方式实现。
使用一个二维分析表和栈联合进行控制来实现递归下降分析技术。
分析表 A实际上是一个从 VN?(VT?{#})到规则的映射。当自顶向下分析过程中需要将 U展开时，如果当前符号为 T时，应该选择规则 A[U,T]。如果 A[U,T]为空，
表示输入符号串不正确。
预测分析过程
PUSH(S,#)； PUSH(S,Z);
a=下一个符号； X=TOP(S);
如果 X为终结符号且 a==X且 a!=#,POP(S); a=下一个符号。
如果 X为终结符号且 a==X且 a==#，分析结束，接受句子。
如果 X为终结符号且 a!=X，出错处理。
如果 X为非终结符号且 A[X,a]为报错标识，出错处理。
如果 X为非终结符号且 A[X,a]=‘X= X1 X2…X n1,
{ POP(S);
将右部 Xn …X 2 X1压入 S中。
}
例子
文法 G4.3’[E]
E::=TE’ E’::=+TE’|? T::=FT’
T’::=*FT’|? F::=(E)|i
例子
i + * ) #(
E TE’ TE’
E’ +T
E’
T FT’ FT’
T’? FT’
F i (E)
i+i*i#
i+i*i#
+i*i#
i*i#
+i*i#
i+i*i#
+i*i#
i+i*i#
i*i#
i*i#
*i#
#E
#E’T
#E’T’F
#E’T+
#E’T
#E’T’
#E’T’i
#E’
#E’T’i
#E’T’F
#E’T’
预测分析表的生成
从前面的论述我们看到，预测分析过程的驱动程序时固定的。对于某个文法，
分析表是分析过程的核心。
表中 A[U,T]=‘U::=X1X2…X n’表示对应于
X1X2…X n字的首符号可以是 T。就是说
X1X2…X n=>*Tw。我们可以通过这个方式来确定分析表中的值。
预测分析表的生成
一般来讲，对于一个符号串 X1X2…X n的字的第一个终结符号就是 X1对应的字的第一个终结符号。但是空规则的存在是情况有一点复杂。
对于 U1U2…U n，如果 U1=>*?，那么符号串对应的字的首符号也可以是 U2对应的字的首符号。计算一个符号串对应的字的首符号的算法也需要考虑到这些。
FIRST(u)和 FOLLOW(U)
FIRST(u)={T|u=>*T…,T?VT}，如果 u=>*?，
那么，我们规定 FIRST(u)。
FOLLOW(U)={T|Z=>* … UT…,T?VT?{#}}
其中，如果 Z=>*…U,那么 #?FOLLOW(U)
直观地讲：
– FIRST(u)包含了 u对应的字的所有可能的首终结符号。
– FOLLOW(U)表示了句型中可能紧跟再 U后面的终结符号
FIRST(u) 构造算法
对于文法 X构造 FIRST(X)
– 步骤 1：如果 X?VT，那么 FIRST(X)={X}
– 步骤 2,如果 X?VN，且有规则 X::=T…,那么将 T添加到 FIRST(X)中。如果 X::=?，那么?也再 FIRST(X)中。
– 步骤 3：对于规则 X::= X1X2…X n,把 FIRST(X1)中的非
符号添加到 FIRST(X)中。如果?在 FIRST(X1)中，把
FIRST(X2)中的非?符号添加到 FIRST(X)中 … ；如果?
在 FIRST(Xn)中，把?添加到 FIRST(X)中。
对于 FIRST(u)，可是使用类似于步骤 3的方法求解得到。
FIRST的例子
文法 G4.3’[E]:
E::=TE’ E’::=+TE’|? T::=FT’
T’::=*FT’|? F::=(E)|i
FIRST(F)={ (,i }
FIRST(T)=FIRST(F)= { (,i }
FIRST(E’)={ +,?} FIRST(T’)={*,?}
… … … …
FOLLOW(U)的构造算法
步骤 1 #?FOLLOW(Z)
步骤 2 如果有规则 U::=xWy，那么 FIRST(y)中所有的非?符号都在 FOLLOW(W)中。
步骤 3 如果有规则 U::=xW或则 U::=xWy且?
FIRST(y)，那么 FOLLOW(U)中的一切符号都在 FOLLOW(W)中。
注意：步骤 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)= {+,#,),*}
预测分析表的构造
基本思想：
当我们需要将 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’::=*FT’|?
F::=(E)|i
i + * ) #(
E TE’ TE’
E’ TE’
T FT’ FT’
T’? FT’
F i (E)
分析表的冲突
文法 G4.6[S] S::=iCtSS’|a S’::=eS|? C::=b
FIRST(iCtSS’)={i} FIRST(eS)={e}
FIRST(S)={i,a} FIRST(C)={b}
FIRST(S’)={e,?}
FOLLOW(S)=FOLLOW(S’)={#,e}
a b e i t #
S a iCtSS’
S’ eS;?
C b
LL(1)文法
定义：如果其预测分析表中没有多重定义的元素，
则该文法被称为 LL(1)文法。
LL(1)文法是无二义性的。
定理 4.1，文法 G是 LL(1)的，当且仅当每个非终结符号 U的任何两个不同的重写规则 U::=x | y满足如下条件：
– FIRST(x)?FIRST(y)=?
– x=>*?和 y=>*?不能同时成立
– 如果 x=>*?，那么 FIRST(x)?FOLLOW(y)=?
