分析器"/>
实验四（二）实现一门语言的语法分析器
代码地址 Github
（二）实现一门语言的语法分析器
一、实验目的
通过本次实验，加深对语法分析的理解，学会编制语法分析器。
二、实验任务
用C或JAVA语言编写一门语言的语法分析器。
三、实验内容
（1）语言确定：C－语言，其定义在《编译原理及实践》附录A中。也可选择其它语言，不过要有该语言的详细定义（可仿照C－语言）。一旦选定，不能更改，因为要在以后继续实现编译器的其它部分。鼓励自己定义一门语言。
（2）完成C－语言的BNF文法到EBNF文法的转换。通过这一转换，消除左递归，提取左公因子，将文法改写为LL（1）文法，以适用于自顶向下的语法分析。规划需要将哪些非终结符写成递归下降函数。
（3）为每一个将要写成递归下降函数的非终结符，如：变量声明、函数声明、语句序列、语句、表达式等，定义其抽象语法子树的形式结构，然后定义C－语言的语法树的数据结构。
（4）仿照前面学习的语法分析器，编写选定语言的语法分析器。
（5）准备2~3个测试用例，测试并解释程序的运行结果。
四、语言确定 （c-Minus语言）
这里定义了一个编程语言称作C－M i n u s (或简称为C－)，这是一种适合编译器设计方案的语言，它比T I N Y语言更复杂，包括函数和数组。本质上它是C的一个子集，但省去了一些重要的部分，因此得名。
1 关键字
else if int return void while2 专用符号
+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */3 其它标记，通过正则表达式定义：
ID = letter letter*
NUM = digit digit*
letter = a|..|z|A|..|Z
digit = 0|..|9五、具体实现 （c-Minus语言）
1 程序总定义： gloal.h
1.1 宏定义：
#define BUFLEN 256 //每一行读取的最大字符串长度
#define MAXLEN 256
#define MAXTOKENLEN 40 //词法单元的最大长度
#define MAXCHILDREN 41.2 变量定义：
static int lineno; //当前读取到第几行
static int linepos = 0; //读取的字符在 lineBuf 的位置
static int EOF_FLAG = false; //判断文件是否结束
static int bufsize = 0; //某行字符串的长度
static char lineBuf[BUFLEN]; //暂存某一行源程序字符串
FILE * source; //输入文件
char tokenString[MAXTOKENLEN+1]; //暂存扫描到的词法单元字符串
string output; //输出文件
TokenType token; //当前词法单元1.3 结构体定义：
enum TokenType //词法单元类型
enum StateType //状态类型
struct{ char* str;TokenType tok;} ReserverWords[6] //关键字
struct{ string str;TokenType tk;} Ope[11] //操作符
enum NodeKind//节点类型//节点类型和字符串关系
struct{string str;NodeKind nk;}nodekind[18]
struct TreeNode //树节点
{struct TreeNode * child[4];struct TreeNode * sibling;int lineno;NodeKind nodekind;union{TokenType op;int val;const char * name;} attr;
};
1.4 BNF文法对应的函数声明：
TreeNode * declaration_list(void);
TreeNode * declaration(void);
TreeNode * params(void);
TreeNode * param_list(TreeNode * p);
TreeNode * param(TreeNode * p);
TreeNode * compound_stmt(void);
TreeNode * local_declaration(void);
TreeNode * statement_list(void);
TreeNode * statement(void);
TreeNode * expression_stmt(void);
TreeNode * selection_stmt(void);
TreeNode * iteration_stmt(void);
TreeNode * return_stmt(void);
TreeNode * expression(void);
TreeNode * var(void);
TreeNode * simple_expression(TreeNode * p);
TreeNode * additive_expression(TreeNode * p);
TreeNode * term(TreeNode * p);
TreeNode * factor(TreeNode * p);
TreeNode * call(TreeNode * p);
TreeNode * args(void);
2 词法分析部分：scan.h
2.1 词法分析的DFA：
2.2 函数说明：
void UnGetNextChar() //回退一个字符
int GetNextChar() //获取下一字符
TokenType GetToken() //获取词法单元
TokenType ReservedLookUp(char * s) //是否是关键字
string OpeLookUp(TokenType tk)
string Change(NodeKind nk)3 语法分析部分：pase.h
3.1 设计思想：
pase用递归下降分析的方法实现，通过调用GetToken函数获取词法单元来实现语法分析。
3.2 c-的BNF文法：
3.3 函数说明：
void parse(void) //语法分析求解函数
void match(TokenType expected) //匹配当前词法单元，获取下一词法单元
void PreOrder(TreeNode* t) //递归下降求解
char * copyString(char *s) //复制字符串
TreeNode * args(void) //arg_list | empty
TreeNode * call(TreeNode * k) //ID (args)
TreeNode * factor(TreeNode * k) //expression) | var | call | NUM
TreeNode * term(TreeNode * k) //term mulop factor | factor
TreeNode * additive_expression(TreeNode * k) //additive_expression addop term | term
TreeNode * simple_expression(TreeNode * k) //additive_expression relop additive_expression// | additive_expression
TreeNode * var(void) //ID | ID [expression]
TreeNode * expression(void) //var = expression | simple-expression
TreeNode * expression_stmt(void) //expression ; | ;
TreeNode * return_stmt(void) //return ;| return expression
TreeNode * iteration_stmt(void) //while (expression) | statement
TreeNode * selection_stmt(void) //if(expression) tatement// | if(expression) tatement else statement
TreeNode * statement(void) //expression-stmt | compound-stmt | selection-stmt// | iteration-stmt | return-stmt
TreeNode * statement_list(void) //statement-list statement | selection-stmt
TreeNode * local_declaration(void) //local-declaration var-declaration | empty
TreeNode * param(TreeNode * k) //type-specifier ID | type-specifier Id [ ]
TreeNode * compound_stmt(void) //{local-declarations statment-list}
TreeNode * param_list(TreeNode * k) //params-list,param | param
TreeNode * params(void) //params-list | void
TreeNode * declaration(void) //var-declaration|fun-declaration
TreeNode * declaration_list(void) //declaration-list declaration | declaration
TreeNode * newNode(NodeKind kind) // 新建节点4 测试
4.1 测试一： test.c
/* A program to perform Euclid's
Algorithm to compute gcd. */
int gcd (int u, int v)
{if (v == 0)return u ;elsereturn gcd(v,u-u/v*v);/* u-u/v*v == u mod v */
}
void main(void)
{int x;int y;x = input();y = input();output(gcd(x,y));
}
输出：
Syntax tree:FunckIntKIdK: gcdParamsKParamKIntKIdK: uParamKIntKIdK: vCompKIfOp: ==IdK: vConstK: 0ReturnIdK: uReturnCallKIdK: gcdArgsKIdK: vOp: -IdK: uOp: *Op: /IdK: uIdK: vIdK: vFunckVoidKIdK: mainParamsKVoidKCompKVar_DeclKIntKIdK: xVar_DeclKIntKIdK: yAssignIdK: xCallKIdK: inputAssignIdK: yCallKIdK: inputCallKIdK: outputArgsKCallKIdK: gcdArgsKIdK: xIdK: y
4.2 测试二 test1.c
/* A program to perform Euclid's
Algorithm to compute max. */
int max (int u, int v)
{if (u > v)return u ;elsereturn v;/* u-u/v*v == u mod v */
}void main(void)
{int x;int y;x = input();y = input();output(max(x,y));
}测试结果：
Syntax tree:FunckIntKIdK: maxParamsKParamKIntKIdK: uParamKIntKIdK: vCompKIfOp: >IdK: uIdK: vReturnIdK: uReturnIdK: vFunckVoidKIdK: mainParamsKVoidKCompKVar_DeclKIntKIdK: xVar_DeclKIntKIdK: yAssignIdK: xCallKIdK: inputAssignIdK: yCallKIdK: inputCallKIdK: outputArgsKCallKIdK: maxArgsKIdK: xIdK: y
4.3 测试三 test2.c
/* A program to perform Euclid's
Algorithm to compute add. */
int add (int a,int b)
{return a+b;
}
void main(void)
{int x;int y;x = input();y = input();output(add(x,y));
}结果：
Syntax tree:FunckIntKIdK: addParamsKParamKIntKIdK: aParamKIntKIdK: bCompKReturnOp: +IdK: aIdK: bFunckVoidKIdK: mainParamsKVoidKCompKVar_DeclKIntKIdK: xVar_DeclKIntKIdK: yAssignIdK: xCallKIdK: inputAssignIdK: yCallKIdK: inputCallKIdK: outputArgsKCallKIdK: addArgsKIdK: xIdK: y
更多推荐
实验四（二）实现一门语言的语法分析器
发布评论