分析器"/>
实验四(二)实现一门语言的语法分析器
代码地址 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 while
2 专用符号
+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */
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 4
1.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
更多推荐
实验四(二)实现一门语言的语法分析器
发布评论