自顶向下的语法分析器

一、问题及解决：

什么是Dictionary File？

在这里插入图片描述

这种类型的文件为Windows虚拟PC 2007，虚拟机，它允许一些版本的Windows在一台计算机上运行生成。它包括像发音和单词的定义以及各种语言，如德国和法国的辞典数据。

如何实现语法分析器？
- 词法分析器
  - 在 $c l an g . l e x$ 增补需要识别的词法单元(do、while、%)，并在 $l e x . yy . h$ 定义（%需要转义[%%])
  - 这里对 ‘%’ 做了简化，按照与 *、/ 同优先级处理，实际优先级：乘除（*/）>取余（%）> 加减（+ -）
- 左递归和公共左因子的处理
  - $p a rser . c pp$ 初始版本的处理存在左递归和公共左因子，需要改造成 $LL (1)$ 文法（消除递归可以进一步化简）
- First集与Follow集
  - 注意产生式符合 $\alpha B \beta,\ \beta->\epsilon$ 的情况，要将follow(A)加到follow(B)中
```
C →	+ term C | - term C | ɛ 
```
- 预测分析器
  - 编译
```
./flex clang.tex  				/*更新*/
gcc lex.yy.c parser.cpp -o p    /*两个文件一起*/
```
  - 运行
```
./flex clang.lex
```
- if语句二义性的处理
  - 对提取左公因子的式子：
    
    stmt → if ( bool ) stmt else_part | 其它语句
    
    else_part → else stmt | ɛ
    
    如果 $l oo kah e a d$ 是词法单元 $e l se$ 时，使用产生式 $else\_part→ else stmt$ ；否则使用产生式 $else\_part→ \epsilon$

二、实验结果：

程序片断：

{
i = 2;
   sum = 0;
	   while (i <=100) 	{
	   	   sum = sum + i;
		   i = i + 2;
          if(i%50==0) break;
	   }
}

打印产生式如下：

在这里插入图片描述

附：

提取公共左因子：

program → 	block
block 	→	{ stmts }
stmts 	→  	stmt stmts | ɛ
stmt 	→	id = expr ; 
        |	if ( bool ) stmt A
        |	while (bool) stmt 
        |	do stmt while (bool ) ; 
        |	break; 
        |	block
 A		→	else stmt | ɛ
bool 	→ 	expr B
 B	 	→ 	relop expr | ɛ
expr 	→ 	expr C | term
 C 		→   + term | - term 
term 	→ 	term D | factor
 D 		→ 	* factor | 	/ factor | % factor
factor	→ 	( expr ) | id | num

消除直接左递归：

program → 	block
block 	→	{ stmts }
stmts 	→  	stmt stmts | ɛ
stmt 	→	id = expr ; 
        |	if ( bool ) stmt A
        |	while (bool) stmt 
        |	do stmt while (bool ) ; 
        |	break; 
        |	block
 A		→	else stmt | ɛ
bool 	→ 	expr B
 B	 	→ 	relop expr | ɛ
expr 	→ 	term C
 C		→	+ term C  | - term C | ɛ 
term 	→	factor D
 D		→	* factor D | / factor D| % factor D| ɛ 
factor	→ 	( expr ) | id | num

First集：

first(program) = first(block) = {'{'};
first(stmts) = first{id, if, while, do, break, '{', ɛ};
first(stmt) = {id, if, while, do, break, '{'};
first(A) = {else, ɛ};
first(bool) = first(expr) = first(term) = first(factor) = {'(', id, num};
first(B) = {relop, ɛ};
first(C) = {+, -, ɛ};
first(D) = {*, /, %, ɛ};

Follow集：

follow(program) = {$};
follow(block) = {$, id, if, while, do, break, '{', '}', else};
follow(stmts) = {'}'};
follow(stmt) = {id, if, while, do, break, '{', '}', else};
follow(A) = {id, if, while, do, break, '{', '}', else, '}'};
follow(bool) = {')'};
follow(B) = {')'};
follow(expr) = {relop, ';', ')'};
follow(C) = {relop, ';', ')'};
follow(term) = {+, -, relop, ';', ')'};
follow(D) = {+, -, relop, ';', ')'};
follow(factor) = {+, -, relop, ';', ')', *, /, %};