任 务 书

1.设计内容

在计算机科学中，抽象语法树（Abstract Syntax Tree 或者缩写为 AST）， 是将源代码的语法结构的用树的形式表示，树上的每个结点都表示源程序代码中的一种语法成分。抽象语法树作为程序的一种中间表示形式,在程序分析等诸多领域有广泛的应用。利用抽象语法树可以方便地实现多种源程序处理工具,比如源程序浏览器、智能编辑器、语言翻译器等。首先需要采用形式化的方式，使用巴克斯（BNF）范式定义高级语言的词法规则（字符组成单词的规则）、语法规则（单词组成语句、程序等的规则）。再利用形式语言自动机的的原理，对源程序的文件进行词法分析，识别出所有单词；使用编译技术中的递归下降语法分析法，分析源程序的语法结构，并生成抽象语法树,最后可由抽象语法树生成格式化的源程序。

 

 

2.设计要求

（1）语言定义

选定 C 语言的一个子集，要求包含：

1）基本数据类型的变量、常量，以及数组。不包含指针、结构，枚举等。

2) 双目算术运算符（+-*/%），关系运算符、逻辑与（&&）、逻辑或（||）、赋值运算符。不包含逗号运算符、位运算符、各种单目运算符等等。

3）函数定义、声明与调用。

4）表达式语句、复合语句、if 语句的 2 种形式、while 语句、for 语句，

return 语句、break 语句、continue 语句、外部变量说明语句、局部变量说明语句。

5）编译预处理（宏定义，文件包含）

6）注释（块注释与行注释）

（2）单词识别

设计 DFA 的状态转换图（参见实验指导），实验时给出 DFA，并解释如何在状态迁移中完成单词识别（每个单词都有一个种类编号和单词的字符串这 2 个特征值），最终生成单词识别（词法分析）子程序。