简介
继上节8说到利用手动构建的语法树解析下面的c语言代码:
a = 1
sum = 0
input(x)
while(a <= x){
sum = sum + a
a = a+1;
}
print(sum)
而一个编译器不应该依赖用户去手动构建对应语言的语法树,我们需要的是一种支持自动构建语法树的策略。本节将要说明的就是如何利用前面1-6节学到的lex,yacc以及符号表,7-8节学到的语法树来支持给定c语言代码自动构建过程。
动机
在第5节变量支持的计算器中,对于expr的语法解析有如下的yacc代码:
lines : lines expr EOL { printf("%g\n", $2); }
| lines EOL
| lines COMMENT
|
;
expr : expr PLUS expr { $$ = $1 + $3; }
| expr MINUS expr { $$ = $1 - $3; }
| expr TIMES expr { $$ = $1 * $3; }
| expr OVER expr { $$ = $1 / $3; }
| LP expr RP { $$ = $2; }
| '-' expr %prec UMINUS { $$ = -$2; }
| NUMBER {$$=$1;} //$$=$1 can be ignored
| ID {$$ = sym_table.getValue($1);}//get value from sym_table
| ID ASSIGN expr {sym_table.setValue($1, $3); $$=$3; }//modify the value
已经知道的是上面每一行都是对应的语法匹配规则(例如expr PLUS expr)以及当规则匹配后要执行的动作(位于{}中,例如$$ = $1 + $3;)。如果将上面要执行的动作修改为创建对应的语法表达式节点,不就可以实现自动构建语法树了吗? 针对上面的expr PLUS expr,其对应的动作可以修改为
$$ = expr.NewRoot(EXPR_NODE, OP_EXPR, NodeAttr(PLUS), Integer, $1, $3);
同理,其他语法规则的执行动作也可以进行相应的修改,这样当一个表达式语法分析完毕后,对应的表达式语法树也就构建完成了。
总体概览
- lex和yacc进行相应的词法,语法分析,并构建对应的语法树
- tree.h和tree.cpp用来支撑语法树的构建过程,提供相应的创建函数,被yacc使用
- symtable.h和symtable.cpp用来支撑符号表的构建过程,提供符号表的创建,访问,修改等操作,用于支持变量以及可能的函数扩展。
- 只支持最基本的c语言,也就是第8节已经进行测试过的。总述如下:变量,变量赋值,算术逻辑等运算,if语句,while语句,输入输出语句,表达式语句,复合语句(不支持变量声明,变量名出现的第一次开始将其加入到符号表,默认值为0,使用赋值运算符可对变量值进行修改)。
可支持如下的代码:
其为迭代法解一元二次方程组,方程的三个参数为a,b,c。
main()
{
//求解X1,在曲线对称轴处选择初始点
//x^2+3x+2 = 0
a = 1;
b = 3;
c = 2;
accuracy = 0.00001;
index=(-1.0*b)/(2*a);
if(b!=0)//b不等于0时进行迭代
{
temp=index;
index=-1.0*(a*temp*temp+c)/b;
while((fabs(index-temp))>accuracy)
{
temp=index;
index=-1.0*(a*temp*temp+c)/b;
}
x1=index;
x2=(-1.0*b)/a-x1;
}
else//b=0时ax^2+c=0直接求解
{
x1=sqrt(-1.0*c/a);
x2=-x1;
}
output(x1);
output(x2);
}
编译器输出结果
lex文件源代码以及解析
前面所述,lex文件完成的词法解析的工作。 它将输入的字符串进行拆分成一个个的token,然后返回相应的token类型,将其传入到yacc中。例如:
letter [a-zA-Z]
digit [0-9]
id {letter}({letter}|{digit})*
上述三行lex代码定义了三种token,字母,数字以及标示符。
lex在解析c语言代码时候,如果遇到相应的token,会向执行token中预定义的动作,例如:
{id} {
int p = sym_table.lookup(yytext);
if(p == -1){//not find
p = sym_table.insert(yytext);//insert the default value 0.0
}
yylval = &dummy;
yylval->attr.symtbl_seq = p;//return the position
return ID;
}
{number} {
yylval = &dummy;
yylval->attr.vali = atof(yytext);
return NUMBER;
}
上述代码显得有些复杂了。id是标示符的解析,yytext是已经切分的token,首先向符号表sym_table中查找yytext,如果没有找到,那么将其插入到符号表;如果找到,直接返回此yytext对应的符号表的索引位置p。 随后对yylval赋值,并设置它的符号表的序号为p,最后返回ID,表明它是一个标示符。 注意p要被yacc所用,例如当碰到a=2,这个赋值动作是在yacc中进行分析的,在yacc构建语法树的时候,必须能够得到a这个标示符,然而lex仅仅返回了ID标示符,但lex通过yylval这个变量间接告诉了yacc词法解析器,此ID确切的内容,即是a。 如果id能够完全理解,那么number就更简单了,直接使用atof函数将字符串转换为double值,并赋值给yylval。
你可能有疑问yacc在哪里使用的yylval呢? 下面给出一小段yacc的代码,作为引子:
var : ID { $$ = createId(parser_tree, (int)($1->attr.symtbl_seq));} //$1 stores yylval, returned by lex.l
上面的是yacc语法分析动作,当碰到ID标示符的时候,调用createId创建一个Node节点,并传入$1->attr.symtbl_seq。 $1就是lex中构造的yylval,这里直接使用它的符号表的序号。
下面是完整的lex代码:
%{
//this code will be added into the header of generated .cpp file
#include <iostream>
#include "sym_table.h"
#include "yacc.h"
#include "tree.h"
using namespace std;
int lineno = 1;
Node dummy;
//already defined in yacc.y, use %token...
//enum{LT, EQ, GT, IF, ELSE, ID, NUMBER, PLUS, MINUS, TIMES, OVER, INT, DOUBLE,CHAR, LP,RP};
const char* tokenStr[] = {"LT", "EQ", "GT", "IF", "ELSE", "ID", "NUMBER", "PLUS", "MINUS", "TIMES", "OVER", "INT", "DOUBLE","CHAR"};
static void print_token(int token, char* lex);
%}
%name lexer
delim [ \t]
ws {delim}+
letter [a-zA-Z]
digit [0-9]
id {letter}({letter}|{digit})*
/* can support 12.34 */
number -?{digit}+(\.{digit}+)?
//(-?[1-9]+[0-9]*)|(-?[1-9])|0
%%
%{
//this code will be added into yyaction function
YYSTYPE YYFAR& yylval = *(YYSTYPE YYFAR*)yyparserptr->yylvalptr;
%}
{ws} {/* do nothing */}
"int" {print_token(INT, yytext); return INT;}
"double" {print_token(DOUBLE, yytext);}
"char" {print_token(CHAR, yytext);}
";" {return SEMICOLON;}
"," {return COMMA;}
"+" {print_token(PLUS, yytext); return PLUS;}
"-" {print_token(MINUS, yytext); return MINUS;}
"*" {print_token(TIMES, yytext); return TIMES;}
"/" {print_token(OVER, yytext); return OVER;}
"(" {return LP;}
")" {return RP;}
"<" {return LT;}
">" {return GT;}
"<=" {return LE;}
">=" {return GE;}
"==" {return EQ;}
"!=" {return NE;}
"\n" {lineno++;}
"=" {return ASSIGN;}
"if" {return IF;}
"else" {return ELSE;}
"while" {return WHILE;}
"input" {return INPUT;}
"output" {return OUTPUT;}
"main" {return MAIN;}
"$" {return END;}
"{" {print_token(LBRACE, yytext); return LBRACE;}
"}" {print_token(RBRACE, yytext); return RBRACE;}
"||" {print_token(OR, yytext); return OR;}
"&&" {print_token(AND, yytext); return AND;}
"!" {print_token(NOT, yytext); return NOT;}
"sqrt" {return SQRT;}
"fabs" {return FABS;}
{id} {
int p = sym_table.lookup(yytext);
if(p == -1){//not find
p = sym_table.insert(yytext);//insert the default value 0.0
}
yylval = &dummy;
yylval->attr.symtbl_seq = p;//return the position
return ID;
}
{number} {
yylval = &dummy;
yylval->attr.vali = atof(yytext);
return NUMBER;
}
"//" {
char c;
do
{
c = input();
}while(c != '\n');
lineno++;
}
"\"" {
char c = '0';
int i = 0;
char* buf = (char*)malloc(1024);
while(c != '\"')
{
c = input();
buf[i++] = c;
};
buf[i] = '\0';
yylval->sibling = (Node*)buf;
printf("buf=%s\n", buf);
//return STRING;
}
"." {printf("Mystery character %s\n", yytext); }
%%
static void print_token(int token, char* lex)
{
#ifdef LEX_DEUB
cout<<"token:" << token<<" "<<"lex:"<<lex<<endl;
#endif
}
符号表代码及分析
符号表顾名思义就是一个表格,能够根据符号的名字找到它的详细信息。为了简单,这里使用数组实现,能够根据符号名得到它隶属于的表格的序号,以及它的节点Node指针(这个是构建语法树使用的节点)。
比较简单,不再详细解析
sym_talbe.h:
#include <iostream>
#include <map>
#include <vector>
#include "yacc.h"
#include "lex.h"
using namespace std;
struct Node;
struct TableNode
{
string name;
double value;
Node* p_node;//also store the corresponding node pointer of name
};
class SymTable
{
public:
SymTable(){
}
public:
int lookup(const string& name){
for (int i = 0; i < idValueTable.size(); ++i)
{
if(idValueTable[i].namepare(name) == 0){
return i;
}
}
return -1;//not find
}
int insert(const string& name){//when parser x=2 (current we get x)
TableNode node;
node.name = name;
node.value = 0.0;
node.p_node = NULL;
idValueTable.push_back(node);
return idValueTable.size()-1;
}
void setValue(int pos, double value){//when parser x=2 (current we get x)
idValueTable[pos].value = value;
}
double getValue(int pos){
return idValueTable[pos].value;
}
Node* getNode(int pos){
return idValueTable[pos].p_node;
}
void setNode(int pos, Node* p){
idValueTable[pos].p_node = p;
}
const string& getName(int pos){
return idValueTable[pos].name;
}
private:
vector<TableNode> idValueTable;
};
extern SymTable sym_table;
sym_table.cpp
#include "sym_table.h"
SymTable sym_table;
yacc代码以及分析
yacc语句描述的就是构建语法树的过程,例如:
program : MAIN LP RP compond_stmt { $$=$4; parser_tree.setRoot($$); executeTree(parser_tree); exit(0);} //for test
;
compond_stmt : LBRACE stmt_list RBRACE
{
$$ = createCompStmt(parser_tree, $2);
}
;
首先program是由后面的MAIN LP RP compond_stmt构建的,分别对应于$1-$4。也就是说它需要碰到main()这样的格式才算语法正确。执行的动作首先$$=$4,表明首先计算compond_stmt,这就会递归到compond_stmt节点进行构建,并将返回的结果赋值给当前的$$, 随后将其设置为根root, 并执行此语法树。 这就与第8节的有所不同,这里利用yacc的规则动作自动构建的语法树,第8节是手动一个节点一个节点的组合构造。
再举例if语句:
if_stmt : IF LP expression RP stmt ELSE stmt {$$ = createIfStmt(parser_tree, $3, $5, $7);}
| IF LP expression RP stmt {$$ = createIfStmt(parser_tree, $3, $5);}
这定义了if的规则需要满足if( expr ) stmt else stmt 或者 if (expr) stmt,执行的动作为创建一个if语句Node,并将expr, stmt1, stm2放入到此Node节点中。
其他所有的规则与这个都非常相似,简单分析即可明白其原因。
下面是完整yacc代码:
#include <fstream>
#include "lex.h"
#include "sym_table.h"
#include "tree.h"
%}
%name parser
// class definition
{
// place any extra class members here
}
// constructor
{
// place any extra initialisation code here
}
// destructor
{
// place any extra cleanup code here
}
// place any declarations here
%include {
#ifndef YYSTYPE
#define YYSTYPE Node *
#endif
}
%token NUMBER ID
%token PLUS MINUS TIMES OVER
%token LP RP EOL COMMENT LBRACE RBRACE
%TOKEN INT DOUBLE CHAR
%token ASSIGN LT GT GE NE LE EQ AND OR NOT SQRT FABS
%token IF ELSE WHILE INPUT OUTPUT
%token SEMICOLON COMMA MAIN END
%right UMINUS
%%
program : MAIN LP RP compond_stmt { $$=$4; parser_tree.setRoot($$); executeTree(parser_tree); exit(0);} //for test
;
compond_stmt : LBRACE stmt_list RBRACE
{
$$ = createCompStmt(parser_tree, $2);
}
;
stmt_list : stmt_list stmt
{
YYSTYPE t = $1;
if($1 != NULL){
while(t->sibling != NULL)
t = t->sibling;
t->sibling = $2;
$$ = $1;
}else {
$$ = $2;
}
}
| stmt {$$ = $1;}
;
stmt : expr_stmt{$$=$1;}
| compond_stmt {$$=$1;}
| if_stmt {$$=$1;}
| while_stmt {$$=$1;}
| input_stmt {$$=$1;}
| output_stmt {$$=$1;}
;
if_stmt : IF LP expression RP stmt ELSE stmt {$$ = createIfStmt(parser_tree, $3, $5, $7);}
| IF LP expression RP stmt {$$ = createIfStmt(parser_tree, $3, $5);}
;
while_stmt : WHILE LP expression RP stmt {$$ = createWhileStmt(parser_tree, $3, $5);}
;
input_stmt : INPUT LP var RP {$$ = createInputStmt(parser_tree, $3);}
;
output_stmt : OUTPUT LP var RP {$$ = createOutStmt(parser_tree, $3);}
;
expr_stmt : expression SEMICOLON {$$=$1;}
| SEMICOLON {$$=NULL;} //not to create any Node
;
expression: var ASSIGN expression {$$ = createOpExpr(parser_tree, $1, $3, ASSIGN);}
| or_expression {$$=$1;}
| MINUS expression %prec UMINUS { $$ = createOpExpr(parser_tree, $2, NULL, UMINUS_EXPR); }
;
or_expression : or_expression OR and_expression {$$ = createOpExpr(parser_tree, $1, $3, OR);}
| and_expression {$$ = $1;}
;
and_expression : and_expression AND additive_expression {$$ = createOpExpr(parser_tree, $1, $3, AND);}
| additive_expression {$$=$1;}
;
additive_expression : additive_expression EQ rel_expression {$$ = createOpExpr(parser_tree, $1, $3, EQ);}
| additive_expression LT rel_expression {$$ = createOpExpr(parser_tree, $1, $3, LT);}
| additive_expression GT rel_expression {$$ = createOpExpr(parser_tree, $1, $3, GT);}
| additive_expression LE rel_expression {$$ = createOpExpr(parser_tree, $1, $3, LE);}
| additive_expression GE rel_expression {$$ = createOpExpr(parser_tree, $1, $3, GE);}
| additive_expression NE rel_expression {$$ = createOpExpr(parser_tree, $1, $3, NE);}
| rel_expression {$$ = $1;}
;
rel_expression : rel_expression PLUS term {$$ = createOpExpr(parser_tree, $1, $3, PLUS);}
| rel_expression MINUS term {$$ = createOpExpr(parser_tree, $1, $3, MINUS);}
| term { $$ = $1; }
;
term : term TIMES factor {$$ = createOpExpr(parser_tree, $1, $3, TIMES);}
| term OVER factor {$$ = createOpExpr(parser_tree, $1, $3, OVER);}
| factor { $$ = $1; }
;
factor : LP expression RP { $$ = $2; }
| var { $$ = $1; }
| NUMBER {$$ = createConst(parser_tree, $1->attr.vali);}
//| CONSTCHAR {$$ = createOpExpr(parser_tree, $1, $3, OVER);}
| NOT factor {$$ = createOpExpr(parser_tree, $2, NULL, NOT_EXPR);}
| SQRT factor {$$ = createOpExpr(parser_tree, $3, NULL, SQRT);}
| FABS factor {$$ = createOpExpr(parser_tree, $3, NULL, FABS);}
;
var : ID { $$ = createId(parser_tree, (int)($1->attr.symtbl_seq));} //$1 stores sym_seq, returned by lex.l
;
%%
int main(int argc, char *argv[])
{
printf("This is a simple compiler.\n");
printf("You can copy the main functions in input.txt and paste it here\n");
printf("There are two main functions and they will work both.\n");
int n = 1;
lexer lexer;
parser parser;
if (parser.yycreate(&lexer)) {
if (lexer.yycreate(&parser)) {
//lexer.yyin = new ifstream("input.txt");
//lexer.yyin = new ifstream(argv[1]);
//lexer.yyout = new ofstream(argv[2]);
n = parser.yyparse();
executeTree(parser_tree);
//parse_tree.get_label();
//parser_tree.gen_code(*lexer.yyout);
}
}
getchar();
return n;
}
语法树提供的简单函数以及遍历的代码
tree.h:
#ifndef __TREE__H__
#define __TREE__H__
#include <iostream>
#include <malloc.h>
using namespace std;
#define MAX_CHILDREN 4
enum // 结点类型——kind
{
STMT_NODE = 0,
EXPR_NODE,
DECL_NODE
};
enum // 语句结点子类型——kindkind
{
IF_STMT = 0,
WHILE_STMT,
INPUT_STMT,
PRINT_STMT,
COMP_STMT,
EXPR_STMT, //只是一个包装而已
};
enum // 表达式结点子类型——kindkind
{
TYPE_EXPR = 0,
OP_EXPR,
NOT_EXPR,
UMINUS_EXPR,
ARRAY_EXPR,
CONST_EXPR,
ID_EXPR,
};
enum // 声明结点子类型——kindkind
{
VAR_DECL = 0,
ARRAY_DECL
};
/*
enum // 运算——op
{
//加减乘除,算术运算符
PLUS = 0,
MINUS,
TIMES,
OVER,
//与或,逻辑运算符
AND,
OR,
//比较运算符
EQ,
LT,
GT,
GE,
LE,
NE,
ASSIGN,
};
*/
enum
{
Integer = 0,
};
union NodeAttr {
int op; // 表达式结点,子类型是运算类型时,用op保存具体运算
double vali; // 表达式结点,常量表达式时,用vali保存整型常量值
char valc; // 字符值
int symtbl_seq; //符号表位置
NodeAttr(void) { op = 0; } // 几种构造函数
NodeAttr(int i) { op = i; }
NodeAttr(double i) { vali = i; }
NodeAttr(char c) { valc = c; }
};
struct Node
{
struct Node *children[MAX_CHILDREN]; // 孩子结点
struct Node * sibling;
int kind; // 结点类型
int kind_kind; // 子类型
NodeAttr attr; // 结点属性
int addr; // 分配的内存空间(数组下标)
};
class tree // 语法树类
{
private:
Node *root; // 根结点
private:
void recursive_get_addr(Node *t); // 为临时变量(如表达式)分配存储空间
void recursive_execute(Node *t); // 遍历树,执行源程序
public:
void setRoot(Node* p){root = p;}
Node *NewRoot(int kind, int kind_kind, NodeAttr attr, int type,
Node *child1 = NULL, Node *child2 = NULL, Node *child3 = NULL, Node *child4 = NULL); // 创建一个结点,设置其属性,连接孩子结点
void get_addr(void); // 分配空间和执行代码的接口
void execute(void);
};
extern tree parser_tree;
Node* createOpExpr(tree& expr, Node* p, Node* q, int type);
Node* createId(tree& expr);
Node* createId(tree& expr, int seq); //创建变量节点,其属性存储其符号表的序号
Node* createConst(tree& expr, double value);
Node* createSTMT(tree& expr, int type, Node* p1, Node* p2=NULL, Node* p3 = NULL, Node* p4=NULL);
Node* createIfStmt(tree& expr,Node* p1, Node* p2, Node* p3 = NULL );
Node* createWhileStmt(tree& expr, Node* p1, Node* p2);
Node* createInputStmt(tree& expr, Node* p);
Node* createOutStmt(tree& expr, Node* p);
Node* createExprStmt(tree& expr, Node* p);
Node* createAssignStmt(tree& expr, Node* variable, int value);
Node* createAssignStmt(tree& expr, Node* variable, Node* q);
Node* createCompStmt(tree& expr, Node* p1, Node* p2=NULL, Node* p3 = NULL, Node* p4=NULL);
void executeTree(tree& expr, Node* root);
void executeTree(tree& expr);
#endif//__TREE__H__
基本利用了先前的框架,加入很多功能辅助函数,例如createXXX的语句,这样yacc中进行规则执行的动作的时候可以很方便的调用。例如刚才的createIfStmt(parser_tree, 3, 5, $7)就是对应的这个里面的createIfStmt。
tree.cpp就是相应的功能实现。绝大部分时间我都在复制,粘贴,修改,调试中,没太大的技术函数。代码量虽然不小,但是语句重复率很高,唯一需要特别注意的就是recursive_execute函数。当发现赋值语句,输入语句的时候,需要修改符号表中的value值,当碰到ID标示符的时候,需要从符号表把相应的值取出来。
tree.cpp:
#include "tree.h"
#include "sym_table.h"
#include <math.h>
tree parser_tree;
double my_mem[10000]; // “内存”
int offset;
Node * tree::NewRoot(int kind, int kind_kind, NodeAttr attr, int type,
Node *child1, Node *child2, Node *child3 , Node *child4)
{
Node* node = new Node();
node->sibling = NULL;
node->kind = kind;
node->kind_kind = kind_kind;
node->attr = attr;
node->children[0] = child1;
node->children[1] = child2;
node->children[2] = child3;
node->children[3] = child4;
return node;
}
void tree::get_addr(void)
{
cout << "allocate memory..." << endl;
offset = 0;
recursive_get_addr(root); // 接口函数直接调用实际分配空间的递归函数
}
void tree::recursive_get_addr(Node *t)
{
if (t) { // 空指针什么也不做
if (t->kind == EXPR_NODE) { // 为表达式结点分配存储空间
t->addr = offset++;
//cout << t->addr << " | "<<t->kind<<" " <<t->kind_kind<<endl;
}
for (int i = 0; i < MAX_CHILDREN; i++) // 递归处理所有子树——先序遍历
recursive_get_addr(t->children[i]);
//TODO: 专门的sibing到children的转换函数。
recursive_get_addr(t->sibling);
}
}
void tree::execute(void)
{
cout << "execute..." << endl;
recursive_execute(root); // 接口函数调用递归函数
//cout << my_mem[root->addr] << endl; // 从内存取出执行结果,输出
}
/*
功能逐步添加摘要:
if条件判断功能:
根据if的condition来决定是否执行statement代码,因此不能首先对其所有的孩子进行后续遍历,需要根据第一个孩子的执行结果来决定是否执行第二个孩子。
while循环功能:
此功能框架代码与if功能相似,只是多了一个while循环而已
变量赋值:
读取用户输入,并赋值到变量,支持input(a),它将用户的输入赋值到变量a,a为其第一个孩子。
赋值语句:
支持a=2,包括两个孩子,左边为变量,右边为值,当前值为左边的值。
输入功能:
能够接收用户输入,并赋值到变量中,前提需要增加赋值功能
输出功能:
构建输出语句,它只有一个孩子,即要输出的变量。
*/
void tree::recursive_execute(Node *t)
{
if (t) {
// printf("deal with recursive_execute:%d %d\n", t->kind, t->kind_kind);
if(t->kind == STMT_NODE){
if(t->kind_kind == IF_STMT){
//if条件判断结果,第二个孩子存储if成功的代码,第三个孩子存储else成功的代码
recursive_execute(t->children[0]);
if (my_mem[t->children[0]->addr] )
recursive_execute(t->children[1]);
else
recursive_execute(t->children[2]);
}else if(t->kind_kind == WHILE_STMT){
//第一个孩子存储条件判断结果,第二个孩子存储while成功的代码
recursive_execute(t->children[0]);
while (my_mem[t->children[0]->addr])
{
recursive_execute(t->children[1]);
recursive_execute(t->children[0]);
}
}else if(t->kind_kind == INPUT_STMT){//input statement has one expr child
cout<<"please input data:";
cin>>my_mem[t->children[0]->addr];
int seq = t->children[0]->attr.symtbl_seq;
sym_table.setValue(seq, my_mem[t->children[0]->addr]);//修改符号表
}else if(t->kind_kind == PRINT_STMT){//print statement has one expr child to print.
recursive_execute(t->children[0]);
int seq = t->children[0]->attr.symtbl_seq;
const string& name = sym_table.getName(seq);
cout<<name.c_str()<<" = "<<my_mem[t->children[0]->addr]<<endl;
}else if(t->kind_kind == COMP_STMT){//组合语句,逐个语句执行即可。
Node* p = t->children[0];
while (p)
{
recursive_execute(p);
p = p->sibling;
}
//for (int i = 0; i < MAX_CHILDREN; ++i)
// recursive_execute(t->children[i]);
}else if(t->kind_kind == EXPR_STMT){
recursive_execute(t->children[0]);
}
}
if (t->kind == EXPR_NODE){ // 表达式结点
recursive_execute(t->children[0]);
recursive_execute(t->children[1]);
if (t->kind_kind == OP_EXPR) { // 运算类型表达式
if (t->attr.op == PLUS) // 加法表达式
// 从内存(my_mem)中取出两个孩子的值,进行加法,结果写回内存
my_mem[t->addr] = my_mem[t->children[0]->addr] + my_mem[t->children[1]->addr];
else if (t->attr.op == MINUS) // 减法的处理类似加法
my_mem[t->addr] = my_mem[t->children[0]->addr] - my_mem[t->children[1]->addr];
else if (t->attr.op == TIMES)
my_mem[t->addr] = my_mem[t->children[0]->addr] * my_mem[t->children[1]->addr];
else if (t->attr.op == OVER){
if(my_mem[t->children[1]->addr] == 0){
cout<<"error: divide by zero"<<endl;
my_mem[t->addr] = 0;
}else{
my_mem[t->addr] = my_mem[t->children[0]->addr] / my_mem[t->children[1]->addr];
}
}
else if (t->attr.op == AND)
my_mem[t->addr] = my_mem[t->children[0]->addr] && my_mem[t->children[1]->addr];
else if (t->attr.op == OR)
my_mem[t->addr] = my_mem[t->children[0]->addr] || my_mem[t->children[1]->addr];
else if (t->attr.op == EQ)
my_mem[t->addr] = (my_mem[t->children[0]->addr] == my_mem[t->children[1]->addr]);
else if (t->attr.op == GT)
my_mem[t->addr] = my_mem[t->children[0]->addr] > my_mem[t->children[1]->addr];
else if (t->attr.op == LT)
my_mem[t->addr] = (my_mem[t->children[0]->addr] < my_mem[t->children[1]->addr]);
else if (t->attr.op == NE)
my_mem[t->addr] = !(my_mem[t->children[0]->addr] == my_mem[t->children[1]->addr]);
else if (t->attr.op == GE)
my_mem[t->addr] = (my_mem[t->children[0]->addr] > my_mem[t->children[1]->addr]) || (my_mem[t->children[0]->addr] == my_mem[t->children[1]->addr]);
else if (t->attr.op == LE)
my_mem[t->addr] = (my_mem[t->children[0]->addr] < my_mem[t->children[1]->addr]) || (my_mem[t->children[0]->addr] == my_mem[t->children[1]->addr]);
else if(t->attr.op == ASSIGN){
int seq = t->children[0]->attr.symtbl_seq;
sym_table.setValue(seq, my_mem[t->children[1]->addr]);//修改符号表
my_mem[t->addr] = my_mem[t->children[0]->addr] = my_mem[t->children[1]->addr];//得到表达式的值
}else if(t->attr.op == SQRT){
my_mem[t->addr] = sqrt(my_mem[t->children[0]->addr]);
}else if(t->attr.op == FABS){
my_mem[t->addr] = fabs(my_mem[t->children[0]->addr]);
}else if(t->attr.op == UMINUS_EXPR){
my_mem[t->addr] = -my_mem[t->children[0]->addr];
}
}
else if (t->kind_kind == CONST_EXPR) // 常量表达式,将值(在vali中)保存至分配的内存中
my_mem[t->addr] = t->attr.vali;
else if(t->kind_kind == ID_EXPR){//变量的值从符号表中取得,不保存在my_mem内存中
my_mem[t->addr] = sym_table.getValue(t->attr.symtbl_seq);
}else if(t->kind_kind == NOT_EXPR){
my_mem[t->addr] = ! my_mem[t->children[0]->addr];
}
}//EXPR_NODE
}
}
Node* createOpExpr(tree& expr, Node* p, Node* q, int type)
{
Node* p1;
p1 = expr.NewRoot(EXPR_NODE, OP_EXPR, NodeAttr(type), Integer, p,q);
return p1;
}
Node* createId(tree& expr)
{
Node* p;
p = expr.NewRoot(EXPR_NODE, ID_EXPR, NodeAttr(0), Integer);
return p;
}
//the Node object is only created once.
Node* createId(tree& expr, int seq) //创建变量节点,其属性存储其符号表的序号
{
/*
Node* p;
p = sym_table.getNode(seq);
if(p == NULL){
p = expr.NewRoot(EXPR_NODE, ID_EXPR, NodeAttr(seq), Integer);
sym_table.setNode(seq, p);
}
*/
Node* p = expr.NewRoot(EXPR_NODE, ID_EXPR, NodeAttr(seq), Integer);
return p;
}
Node* createConst(tree& expr, double value)
{
Node* q2;
q2 = expr.NewRoot(EXPR_NODE, CONST_EXPR, NodeAttr(value), Integer);
return q2;
}
Node* createSTMT(tree& expr, int type, Node* p1, Node* p2, Node* p3 , Node* p4)
{
Node* r;
r = expr.NewRoot(STMT_NODE, type, NodeAttr(), Integer, p1,p2,p3,p4);
return r;
}
Node* createIfStmt(tree& expr,Node* p1, Node* p2, Node* p3 )
{
return createSTMT(expr, IF_STMT, p1, p2, p3);
}
Node* createWhileStmt(tree& expr, Node* p1, Node* p2)
{
return createSTMT(expr, WHILE_STMT, p1, p2);
}
Node* createInputStmt(tree& expr, Node* p)
{
return createSTMT(expr, INPUT_STMT, p);
}
Node* createOutStmt(tree& expr, Node* p)
{
return createSTMT(expr, PRINT_STMT, p);
}
Node* createExprStmt(tree& expr, Node* p)
{
return expr.NewRoot(STMT_NODE, EXPR_STMT, NodeAttr(0), Integer, p);//xxxx; xxxx为表达式,组合成语句
}
Node* createAssignStmt(tree& expr, Node* variable, int value)
{
Node* p = variable;
Node *q, *r, *s;
q = createConst(expr, value);
r = createOpExpr(expr, p,q, ASSIGN);
return createExprStmt(expr, r);
}
Node* createAssignStmt(tree& expr, Node* variable, Node* q)
{
Node* p = variable;
Node *r, *s;
r = createOpExpr(expr, p,q, ASSIGN);
return createExprStmt(expr, r);
}
Node* createCompStmt(tree& expr, Node* p1, Node* p2, Node* p3, Node* p4)
{
return createSTMT(expr, COMP_STMT, p1,p2,p3,p4);
}
void executeTree(tree& expr, Node* root)
{
expr.setRoot(root);
expr.get_addr(); // 为(子)表达式(们)分配存储空间
expr.execute(); // 执行代码
cout<<endl;
}
void executeTree(tree& expr)
{
expr.get_addr(); // 为(子)表达式(们)分配存储空间
expr.execute(); // 执行代码
cout<<endl;
}
/*
if: st_if -> (condition, action)
while: st_while->(condition, action)
*/
void basicTest()
{
tree expr;
Node *p, *q, *r;
// 创建结点a
p = expr.NewRoot(EXPR_NODE, CONST_EXPR, NodeAttr(9), Integer);
// 创建结点5
q = expr.NewRoot(EXPR_NODE, CONST_EXPR, NodeAttr(5), Integer);
// 创建减法结点,孩子结点为9和5
r = expr.NewRoot(EXPR_NODE, OP_EXPR, NodeAttr(MINUS), Integer, p, q);
// q = expr.NewRoot(EXPR_NODE, CONST_EXPR, NodeAttr(2), Integer);
// p = expr.NewRoot(EXPR_NODE, OP_EXPR, NodeAttr(PLUS), Integer, r, q);
expr.setRoot(r);
expr.get_addr(); // 为(子)表达式(们)分配存储空间
expr.execute(); // 执行代码
}
void assignTest()
{
/*
a = 1
output(a)
两个语句
*/
tree expr;
Node *p, *q, *r, *s, *o, *u, *t;
//构建赋值语句
// 创建结点a
p = expr.NewRoot(EXPR_NODE, ID_EXPR, NodeAttr(0), Integer);
// 创建结点1
q = expr.NewRoot(EXPR_NODE, CONST_EXPR, NodeAttr(5), Integer);
//赋值
r = expr.NewRoot(EXPR_NODE, OP_EXPR, NodeAttr(ASSIGN), Integer, p, q);
s = expr.NewRoot(STMT_NODE, EXPR_STMT, NodeAttr(0), Integer, r);//赋值语句:孩子赋值表达式
//构建输出语句
t = expr.NewRoot(STMT_NODE, PRINT_STMT, NodeAttr(), Integer, p);
//构建组合语句
o = expr.NewRoot(STMT_NODE, COMP_STMT, NodeAttr(), Integer, s, t);
expr.setRoot(o);
expr.get_addr(); // 为(子)表达式(们)分配存储空间
expr.execute(); // 执行代码
cout<<endl;
}
void inputOutTest()
{
/*
input(a)
output(a)
*/
tree expr;
Node *p, *q, *r, *s, *o, *u, *t;
//输入语句
// 创建结点a
p = expr.NewRoot(EXPR_NODE, ID_EXPR, NodeAttr(0), Integer);
s = createInputStmt(expr, p);
q = createOutStmt(expr, p);
o = createCompStmt(expr, s, q);
executeTree(expr, o);
}
void ifTest()
{
/*
a = 1
if(a>10){
a = 11
}else{
a = 7
}
print(a)
*/
tree expr;
Node *p, *q, *r, *s, *o, *u, *t;
//输入语句
// 创建结点a
p = expr.NewRoot(EXPR_NODE, ID_EXPR, NodeAttr(0), Integer);
s = createAssignStmt(expr, p, 1);//a=1
//if语句
q = createOpExpr(expr, p, createConst(expr, 10), GT);//a>10
r = createIfStmt(expr, q, createAssignStmt(expr, p, 11), createAssignStmt(expr, p, 7));//if(a>10) a=11 else a=7
//构建输出语句
t = createOutStmt(expr, p);//print(a)
//构建组合语句
o = createCompStmt(expr,s ,r, t );
executeTree(expr , o);
}
void whileTest()
{
/*
a =1
sum = 0
while(a <= 10){
sum = sum + a
a = a+1;
}
print(sum)
*/
tree expr;
Node *p, *q, *r, *s, *o, *u, *t,*p1,*q1;
p = createId(expr);//a
q = createId(expr);//sum
p1 = createAssignStmt(expr,p, 1);//a=1
q1 = createAssignStmt(expr, q, 0);//sum=0
Node *a, *b, *c, *d, *e, *f, *g;
a = createOpExpr(expr, p, createConst(expr, 10), LE);//a<=10
b = createOpExpr(expr, p, q, PLUS);//sum+a
c = createAssignStmt(expr, q, b);//sum = sum+a
d = createOpExpr(expr, p, createConst(expr, 1), PLUS);
e = createAssignStmt(expr, p, d); //a=a+1
f = createCompStmt(expr, c, e); //{sum = sum+a, a= a+1}
r = createWhileStmt(expr, a, f);//while
t = createOutStmt(expr, q);//print sum
o = createCompStmt(expr, p1, q1, r, t);
executeTree(expr, o);
}
void whileInputTest()
{
/*
a = 1
sum = 0
input(x)
while(a <= x){
sum = sum + a
a = a+1;
}
print(sum)
*/
tree expr;
Node *p, *q, *r, *s, *o, *u, *t,*p1,*q1;
p = createId(expr);//a
q = createId(expr);//sum
p1 = createAssignStmt(expr, p, 1);//a=1
q1 = createAssignStmt(expr, q, 0);//sum=0
Node *a, *b, *c, *d, *e, *f, *g;
g = createId(expr);//x
f = createInputStmt(expr,g);
u = createCompStmt(expr, p1, q1, f);//first 3 sentences. because Comp not support more than 4 children.
a = createOpExpr(expr, p, g, LE);//a<=x, x from input
b = createOpExpr(expr, p, q, PLUS);//sum+a
c = createAssignStmt(expr, q, b);//sum = sum+a
d = createOpExpr(expr, p, createConst(expr, 1), PLUS);
e = createAssignStmt(expr, p, d); //a=a+1
f = createCompStmt(expr, c, e); //{sum = sum+a, a= a+1}
r = createWhileStmt(expr, a, f);//while
t = createOutStmt(expr, q);//print sum
o = createCompStmt(expr, u, r, t);
executeTree(expr, o);
}
int xxx(int argc, char *argv[])
{
//assignTest();
//inputOutTest();
//ifTest();
//whileTest();
whileInputTest();
return 0;
}
main函数
main其实位于yacc文件中,我们不需要额外定义main函数,直接在yacc.y中写好,当编译yacc.y的时候,就会将相应的main函数放置到yacc.cpp中。
它的实现很简单,创建lex和yacc,并创建连接。调用yyparse进行语法解析构建语法树,然后执行语法树:
int main(int argc, char *argv[])
{
printf("This is a simple compiler.\n");
printf("You can copy the main functions in input.txt and paste it here\n");
printf("There are two main functions and they will work both.\n");
int n = 1;
lexer lexer;
parser parser;
if (parser.yycreate(&lexer)) {
if (lexer.yycreate(&parser)) {
//lexer.yyin = new ifstream("input.txt");
//lexer.yyin = new ifstream(argv[1]);
//lexer.yyout = new ofstream(argv[2]);
n = parser.yyparse();
executeTree(parser_tree);
//parse_tree.get_label();
//parser_tree.gen_code(*lexer.yyout);
}
}
getchar();
return n;
}
输入测试用例
我的测试两个例子如下所示:
1.简单的if,while测试
main()
{
a = 1;
if(a>10){
a = 11;
}else{
a = 7;
}
output(a);
sum = 0;
a = 1;
while(a<100){
sum = sum + a;
a = a + 1;
}
output(sum);
a = 1;
output(a);
while(a != 100){
input(a);
if(a<10){
output(a);
}else{
output(sum);
}
}
}
2.求解方程的根
main()
{
//求解X1,在曲线对称轴处选择初始点
//x^2+3x+2 = 0
a = 1;
b = 3;
c = 2;
accuracy = 0.00001;
index=(-1.0*b)/(2*a);
if(b!=0)//b不等于0时进行迭代
{
temp=index;
index=-1.0*(a*temp*temp+c)/b;
while((fabs(index-temp))>accuracy)
{
temp=index;
index=-1.0*(a*temp*temp+c)/b;
}
x1=index;
x2=(-1.0*b)/a-x1;
}
else//b=0时ax^2+c=0直接求解
{
x1=sqrt(-1.0*c/a);
x2=-x1;
}
output(x1);
output(x2);
}
如何运行
首先将上述的tree.h, tree.cpp, sym_table.h, sym_table.cpp包含到vs工程中,还需要加入lex.l和yacc.y编译后的文件,lex.h, lex.cpp, yacc.h, yacc.cpp。 这些代码文件包含完毕后,还需要配置vs环境的包含目录pargen的目录,我的目录是C:\Program Files (x86)\Parser Generator 2\Cpp\Include, 还需要包含它的lib库目录,库目录为./,输入中的附加依赖项的库文件为ylmtri.lib。 我使用的动态链接库,需要将库文件ylmtri.lib, ylmtri.dll放入到工程目录下。
如图:
代码
万事都是这样,说起来简单,做起来难。 好多一个毫不起眼的bug就可能耗费一整天的功夫,尤其是对于这种依赖外部的pargen进行编译运行的库。只配置好环境可能就需要大半天,因此我将我弄好的vs2013工程代码上传到github上了,你如果想测试代码可以直接拿来用。
github地址:https://github/lpstudy/compile
更多推荐
小白说编译原理-9-最简单minus-c语言编译器
发布评论