编译器与解释器的设计流程
编译器前端部分
词法分析 (字符流->记号流)
词法分析也称作扫描,是编译器的第一个步骤,词法分析器读入组成源程序的字符流,并且将它们组织成为有意义的词素的序列,对于每一个词素,词法分析器产生如下形式的词法单元作为输出。实际上就是从字符流到单词流的过程。
语法分析(语法树)
也称作解析,语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。该中间表示给出了词法分析产生的词法单元流的语法结构。一个常用的表示方法是语法树,树中的每个内部结点表示一个运算,而该结点的子结点表示该运算的分量。
语义分析
语义分析器使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。它同时也收集类型信息,并把这些信息存放在语法树或符号表中,以便在随后的中间代码生成过程中使用。语义分析的一个重要部分是类型检查,编译器检查每个运算符是否具有匹配的运算分量,比如数组下标必须是整数,若用一个浮点数来做下标,编译器就会报错。程序设计语言可能允许某些类型转换,这被称作自动类型转换。
中间代码生成
在把一个源程序翻译成目标代码的过程中,一个编译器可能构造出一个或多个中间表示。这些中间表示可以有多种形式。其中语法树是一种中间表示形式。在源程序的语法分析和语义分析完成之后,很多编译器生成一个明确的低级的或类机器语言的中间表示,我们可以把这个表示看作是某个抽象机器的程序。该中间表示应该具有两个重要的性质:易于生成,且能够被轻松地翻译为目标机器上的语言。
编译器后端部分
代码优化
目标代码生成
解释器前端部分
词法分析
语法分析
语义分析
中间代码生成
执行
Tiny语言
TINY语言的介绍
- TINY的程序结构是一个由分号分隔开的语句序列。
- 既无过程也无声明。
- 所有的变量都是整型变量,通过对其赋值可较轻易地声明变量。
- 只有两个控制语句: if语句和repeat语句,这两个控制语句本身也可包含语句序列。If语句有一个可选的else部分且必须由关键字end结束。
- read语句和write语句完成输入/输出。
- TINY的表达式只有布尔表达式和整型算术表达式。布尔表达式由对两个算术表达式的比较组成,该比较使用<与=比较算符。算术表达式可以包括整型常数、变量、参数以及4个整型算符+、-、*、/,此外还有一般的数学属性。
Tiny 语言的文法
!(/home/ngkimbing/git/Tiny/BNF中Tiny的文法)
Lex & Yacc
Lex
首先,lex和yacc是开源工具,帮助开发者实现语法,词法分析。如果作为一个开发者去使用它们,就需要阅读它们的说明书,直到你会用,一句话,就是个工具而已。当然,如果你对编译原理很清楚,可以更好地理解它,甚至可以分析它们的源代码哦。
Lex和yacc都是贝尔实验室在20世纪70年代发明的。
lex 代表 lexical analyzar(词法分析器)
yacc 代表 yet another compiler compiler(编译器代码生成器)
一个简单的Lex程序
test.l
%{
int chars = 0;
int words = 0;
int lines = 0;
%}
mywords [a-zA-Z]+
mylines \n
mychars .
%%
{mywords} { words++; chars += strlen(yytext); }
{mylines} { chars++; lines++; }
{mychars} { chars++; }
%%
main(int argc, char **argv)
{
yylex();
printf("%8d%8d%8d\n", lines, words, chars);
}
分析:
这段lex程序的作用是:根据输入的字符串,输出其行数、单词数和字符的个数。
(1) %%把文件分为3段,第一段是c和lex的全局声明,第二段是规则段,第三段是c代码。
(2) 第一段的c代码要用%{和%}括起来,第三段的c代码不用。
(3) 第二段是规则段,[a-zA-Z]+ \n . 是正则表达式,表示匹配的内容,{}内的是c编写的动作。
上面程序中yytext是lex变量,匹配模式的文本存储在这一变量中。yylex()这一函数开始分析,它由lex自动生成。关于lex变量和函数后续介绍,这里只是通过简单的lex程序来认识lex.
Lex 的运行
flex test.l
gcc lex.yy.c –lfl
./a.out
lex demo2.l
%{
enum yytokentype
{
ADD = 259,
SUB = 260,
};
%}
myadd "+"
mysub "-"
myother .
%%
{myadd} { return ADD; }
{mysub} { return SUB; }
{myother} { printf("Mystery character\n"); }
%%
main(int argc, char **argv)
{
int tok;
while (tok = yylex())
{
if (tok == ADD || tok == SUB)
{
printf("meet + or -\n");
}
else
{
printf("this else statement will not be printed, \
because if yylex return,the retrun value must be ADD or SUB.");
}
}
}
Yacc
部分函数简单介绍
yyparse()
yacc生成的语法分析程序的入口点是yyparse(),当程序调用yyparse()时,语法分析程序就试图分析输入流。如果分析成功,语法分析程序就返回一个零值,反之,则返回一个非零值。
每次调用该函数,语法分析程序就重新开始进行分析,而忘记上次返回的状态,这与lex扫描程序十分不同,它能够获得调用后的每一次状态。
————————————————
版权声明:本文为CSDN博主「逆風的薔薇」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/fly_yr/article/details/43019601
其实这个函数是yacc生成的,所以你在代码里面可以直接使用。这个时候 你可能会问:“yacc生成了yyparse函数,那么lex是不是也生成了什么函 数呢?”,是的,lex生成的函数为yylex函数。实际上yyparse还间接调用 了yylex函数,可以在生成的c源文件中去核实。
1、yacc语法规则部分和BNF类同,先来看BNF巴克斯范式。
(1)<> 内包含的内容为必选项;
(2)[] 内的包含的内容为可选项;
(3){ } 内包含的为可重复0至无数次的项;
(4) | 表示在其左右两边任选一项,相当于"OR"的意思;
(5)::= 是“被定义为”的意思;
(6)双引号“”内的内容代表这些字符本身;而double _quote用来表示双引号。
(7)BNF范式举例,下面的例子用来定义java中的for语句:
FOR_STATEMENT ::=
"for" "(" ( variable_declaration |
( expression ";" ) | ";" )
[ expression ] ";"
[ expression ]
")" statement
yacc 语法
result: components { } ;
编译运行yacc代码
yacc -d tiny.y
Tiny Compiler
运行方式
./build.sh
yychar = yylex ();
把yylex换乘getTokenmake
./tiny.out sample.tny
文件介绍
终结符的define
是在y.tab.h
而globals.h
中包含了y.tab.h
所以要先lex,yacc 生成lex.yy.c 和 y.tab.h
然后用个globals.h 去include这些
然后开始自己编译器的创作
-
util.c :
- 产生语法树节点
- 输出Token
- 一些基本字符串操作
-
parse.h
- 声明了parse方法
-
scan.h
- 声明了tokenString 数组 和 getToken方法(实现在lex.yy.c) 源于tiny.l getToken方法 实际上只是对yylex的一层封装 parse是对yyparse的封装
-
tiny.l
(Lex specification for TINY)
- lex 词法分析
-
gobals.h
- 数据类型的声明
-
tiny.c
- 打印语法树
-
symtab.h
- st_insert
- st_lookup
- printSymTab
-
analyze.c
- 语义分析
-
tm.c
- TM虚拟机
代码分析
函数介绍
static TreeNode * stmt_sequence(void);
static TreeNode * statement(void);
static TreeNode * if_stmt(void);
static TreeNode * repeat_stmt(void);
static TreeNode * assign_stmt(void);
static TreeNode * read_stmt(void);
static TreeNode * write_stmt(void);
static TreeNode * exp(void);
static TreeNode * simple_exp(void);
static TreeNode * term(void);
static TreeNode * factor(void);
另外还有6个重要函数:
1)-打印语法树void printTree( TreeNode * tree )
2)-分配该类的新语句节点TreeNode * newStmtNode(StmtKind kind)
3)-分配该类新表达式节点TreeNode * newExpNode(ExpKind kind)
4)-为拷贝分配足够的空间,并拷贝串char * copyString(char * s)
5)-保存向前看记号的静态变量token和检测输入的记号是否和预期相同 static void match(TokenType expected)
6)- 显示出错信息static void syntaxError(char * message)
功能配置
#define NO_PARSE FALSE
#define NO_ANALYZE TRUE
#define NO_CODE TRUE
具体实现
listing = stdout;
fprintf(listing, "\nTINY COMPILATION: %s\n", pgm);
#if NO_PARSE
while (getToken()!=ENDFILE);
#else
syntaxTree = parse();
if (TraceParse) {
fprintf(listing, "\nSyntax tree:\n");
printTree(syntaxTree);
}
#if !NO_ANALYZE
功能测试
语法分析模块测试
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)