编译原理第三次实验

0x01 实验目的

掌握语法分析器的构造原理，掌握递归下降法的编程方法。

0x02 实验内容

用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。（注意，需要改写文法，消除左递归等）

0x03 实验要求

1. 个人完成，提交实验报告
2. 实验报告中给出采用测试源代码片断，及其对应的最左推导过程

0x04 实验内容

1 改写文法

对实验所给产生式消除左递归、提取公共左因子

program 	→   block
block 	    → 	{ decls stmts }
decls       →   decl decls | `e`
decl        →   type id;
type        →   int | float| char
stmts 	    →   stmt stmts | `e`
stmt 	    →	id = expr ; 
			|	if ( bool ) stmt
			|	if ( bool) stmt else stmt
			|	while (bool) stmt 
			|	do stmt while (bool ) ; 
			|	break ; 
			|	block
bool 	    → 	expr bool2
bool2       →   relop expr | `e`
expr 	    → 	term expr2
expr2       →   B expr2 | `e`
B           →   + term 
            |   - term
term 	    → 	factor term2
term2       →   C term2 | `e`
C           →   * factor
			|   / factor
factor	    → 	( expr ) | id | num

2 带预测的语法分析器

将示例中的parser.cpp进行改写补充，以实现带预测的语法分析器

例如，对于decls，由于$First(decls)=First(decl)=First(type)={INT,FLOAT,CHAR}$ 则，其预测分析函数改写为：

void decls()
{
    if (lookahead == INT || lookahead == FLOAT || lookahead == CHAR) {
        printf("decls -> decl decls\n");
        decl();
        decls();
    }
}

再如对于 stmt → if ( bool ) stmt | if ( bool) stmt else stmt | others 也可以用预测分析解决：

case IF:
	printf("stmt -> if(expr) stmt ");
	match(IF);
	match('(');
	bool1();
	match(')');
	stmt();
	if ( lookahead == ELSE )
	{
		printf("else stmt");
		match(ELSE);
		stmt();
	}
	printf("\n");
	break;

其他的函数思路都差不多，不再赘述，完整代码见parser.cpp

3 实验结果

对于code1.txt

{ 
	int i; 
	i = 2; 
	while (i <= 100) 
	{ 
		sum = sum + i; 
		i = i + 2; 
	} 
}

其对应结果如下：