3.3 自上而下分析

时间：2021-05-17 13:26:29 阅读：18 评论：0 收藏：0 [点我收藏+]

3.3 自上而下分析

3.3.1 自上而下分析的一般方法

例文法
S → aCb C
cd | c
为输入串w = acb建立分析树
技术分享图片
不能处理左递归的例子

不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效率低

3.3.2 LL(1)文法

对文法加什么样的限制可以保证没有回溯？

先定义两个和文法有关的函数

技术分享图片

LL(1)文法定义

技术分享图片

LL(1)文法有一些明显的性质

没有公共左因子
不是二义的
不含左递归

查找非终结符的First集

Step 1. 按产生式顺序来，从开始符找起；

Step 2. 如果右部的串首为终结符，则直接将该终结符填入左部非终结符的First集中；

Step 3. 如果右部的串首为非终结符，则左部非终结符的First集等价于串首非终结符的First集。因而，需要利用Step 2和Step 3继续寻找串首非终结符的First集。

查找非终结符的Follow集

Step 1. 按产生式顺序来，从开始符找起（开始符的Follow集必定包含$）；

**Step 2. **从所有产生式右部寻找目标非终结符，若其后紧跟终结符，则将终结符填入目标非终结符的Follow集。特别地，若其后紧跟$，则目标非终结符的Follow集等价于产生式左部非终结符的Follow集。

Step 3. 从所有产生式右部寻找目标非终结符，若其后紧跟非终结符，则将该非终结符的First集元素填入目标非终结符的Follow集。特别地，若该非终结符的First集元素中包含?，则需针对?情况时做特殊处理，即目标非终结符的Follow集等价于产生式左部非终结符的Follow集。
技术分享图片

3.3.3 递归下降的预测分析

为每一个非终结符写一个分析过程
这些过程可能是递归的

技术分享图片

一个辅助过程

void match (terminal t) {
		if (lookahead == t) lookahead = nextToken( );
		else error( );
}

void type( ) {
	if ( (lookahead == integer) || (lookahead == char) ||
 						    (lookahead == num) )
		simple( );
	else if ( lookahead == ??? ) { match(???); match(id);}
	else if (lookahead == array) {
		match(array); match( ?[? ); simple( );
		match( ?]? ); match(of ); type( );
	}
	else error( );
}

void simple( ) {
	if ( lookahead == integer) match(integer);
	else if (lookahead == char) match(char);
	else if (lookahead == num) {
		match(num); match(dotdot); match(num);
	}
	else error( );
}