编译原理:flex与bison–从0到1完成一个编译器(sample语言)
文章目录
- 前言
- 一、Sample语言简介
- 二、项目内容
- 三、原理与实现过程
- 1.词法分析
- 2.步骤
- 四、项目演示
- 总结
- 源代码
前言
本系列文章共三部分，记述了我完成编译器的过程，供后来的学弟学妹参考借鉴。
本项目是我的编译原理作业，文章是由实验报告整理而来的，重在阐述，如果没有编译原理的相关知识，还要结合一些教程来看。
本项目实现的编译器包括词法分析，语法分析，语义分析与中间代码生成，目标代码生成共四个阶段，能将sample语言翻译成可执行的汇编语言。使用flex与bison工具辅助，通过C语言实现。本人能力有限，项目有许多不足和值得改进的地方，也请读者多多指正。
本文为本系列的第一部分，介绍sample语言的词法分析。
一、Sample语言简介
Sample语言是PASCAL语言的简化版本。具有一般高级语言的共同特征：它的字符集包括所有的大小写字母、数字和一些界符；有多种数据类型：整型、实型、字符型等；有变量说明和常量说明；包括顺序、条件和循环三种语句结构。
Sample语言的词法、语法定义见这里 需要注明的是，本项目中，八进制和十六进制数字并没有写在词法中，需要自己定义。
二、项目内容
本项目编写了一个对于Sample语言源代码的词法分析，并打印分析结果。使用词法分析工具Flex，并结合C语言完成。根据Sample语言文档写出了所有单词的正则表达式，利用Flex工具和C语言进行判断和分析，输出单词的行号、种别码，并能够给出错误信息。
- 单词识别
扫描源程序，根据词法规则，识别单词，填写相应的 token 表。 - 错误处理
如果产生词法错误，则输出出错的位置（源程序行号）以及相关的说明文字。本程序能够查出源代码中可能包含的词法错误，即出现 Sample 词法中未定义的字符以及任何不符合 Sample 词法单元定义的字符。 - 常量和注释识别要求
a. 识别八进制数和十六进制数。若输入文件中包含符合词法定义的八进制数（如 0123）和十六进制数（如 0x3F），本程序能够得出相应的词法单元；若输入文件中包含不符合 词法定义的八进制数（如 09）和十六进制数（如 0x1G），本程序需要给出输入文件有词法错误的提示信息。
b.识别指数形式的浮点数。若输入文件中包含符合词法定义的指数形式的浮点数 （如 1.05e-4），本程序需要得出相应的词法单元；若输入文件中包含不符合词法定义的指数形式的浮点数（如 1.05e），本程序需要给出输入文件有词法错误的提示信息。
c.识别“/…/”和“//”形式的注释。若输入文件中包含符合定义的“/…/” 和“//”形式的注释，本程序能够滤除这样的注释；若输入文件中包含不符合定义的注释 （如“/…/”注释中缺少“/*”），程序需要给出由不符合定义的注释所引发的错误的提示信息。
三、原理与实现过程
1.词法分析
词法分析是编译的第一个阶段，它的主要任务是从左至右地逐个字符地对源程序进行扫描，产生一个个单词序列，用于词法分析。执行词法分析的程序称为词法分析程序或扫描程序。
2.步骤
首先在计算机上安装flex和tcc，将其添加到环境变量中。
根据Sample语言文档中语言单词的定义，写出标识符、整数、实数等的正则表达式。并为保留字、运算符等进行编号。
根据正则表达式和文档编写flex程序，识别单词并输出对应的编号和行号。统计其中的错误和无法识别的单词，与结尾输出。
对于要求一，本程序优先匹配’\n’来统计行数，每识别到一个’\n’就对行号加1。每一个单词，输出其行号。
对于要求二，本程序对文档中所有单词进行匹配，对于无法进行匹配的单词将其记录并报错。需要特别判断的是，如果一个单词以数字开头，并含有字母，这个单词会被错误地识别成一个数字和一个标识符。解决办法是对以数字开头的单词进行特判，记录并报错。
部分单词的正则表达式及操作如下：
单词 |
正则表达式 |
操作 |
换行 |
\n |
行号加1 |
标识符 |
[a-zA-Z][a-zA-Z0-9]* |
/ |
注释 |
“/"(.|\n)”*/" |
记录注释的行数 |
注释 |
“//”.* |
/ |
特殊判断 |
[0-9]+[a-zA-Z]+[a-zA-Z0-9]* |
报错 |
部分常数的正则表达式如下。
数字类别 |
正则表达式 |
八进制数 |
0[0-7]+ |
十六进制数 |
0x[0-9A-F]* |
指数形式的浮点数 |
{DIGIT}+"."{DIGIT}+“e”(""|"-"){DIGIT}+ |
对于要求三，本程序写出了八进制数、十六进制数、指数形式浮点数的正则表达式。对于注释“//”，本程序匹配以“//”开头、以’\n’结尾的所有字符串并只输出“//”。对于注释“/……/”，本程序匹配以“/”开头以“/”结尾的所有字符串。值得提出的是，当此类注释只有“/”或只有“/”时，程序会识别成运算符“/”和“”。解决方案为对“/”和“*/”进行单独匹配，若能够单独匹配到这两个单词，说明该注释缺失符号。
关于本程序的出错处理，本程序将无法识别的单词和它的行号记录下来，词法分析完成后一起输出。
四、项目演示
下面是对几个Sample语言片段的词法分析输出
片段1
program example;
var
a:integer;
begin
x:=3+3.5+3.5e4;
end
片段2(对于单词α，由于激活了中文显示，α不能正常输出)
program example;
var
3a:real;
3a=0x1G;
α:integer;
片段3（注释缺失）
/*aaabbcd
adfaf
*/
/*balabala
//asdfo
总结
本实验中完成了一个对于Sample语言源代码的词法分析，并打印分析结果。使用词法分析工具Flex，并结合C语言完成。根据Sample语言文档写出了所有单词的正则表达式，利用Flex工具和C语言进行判断和分析，输出单词的行号、种别码，并能够给出错误信息。
当时完成这样一个词法分析程序还是蛮有成就感的，第一次使用flex工具进行编程，我也感受到了编译原理这门课程的魅力。当时我就想一定要完成自己的编译器。
源代码
%{
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include<string.h>
int row=1;
char faults[100][100];
int cnt_fault=0;
%}
HDIGIT [1-9]
DIGIT [0-9]
ID [a-zA-Z][a-zA-Z0-9]*
EIGIT [0-7]
SDIGIT [0-9A-F]
BAOLIUZI and|begin|bool|char|const|do|else|end|for|if|input|integer|not|or|output|program|read|real|repeat|then|to|until|var|while|write
DANJIEFU [+|\-|*|/|=|<|>|\||:|,|_|.]
SHUANGJIEFU "/*"|"*/"|"<="|">="|"<>"|":="
BOOL true|false
FENHAO ;
%%
\n {row++;}
"/*"(.|\n)*"*/" {
int len=strlen(yytext);
int num=0;
for(int i=0;i<len;i++)
if(yytext[i]=='\n')
num++;
printf("%4d\t45\t注释: /*\n",row);
row+=num;
printf("%4d\t46\t注释: */\n",row);
}
"/*" { sprintf(faults[cnt_fault++],"%4d\t缺少注释\n", row); }
"*/" { sprintf(faults[cnt_fault++],"%4d\t缺少注释\n", row); }
{DIGIT}|{HDIGIT}{DIGIT}+ { printf("%4d\t53\t整数：%s(%d)\n",row, yytext, atoi(yytext)); }
{DIGIT}+"."{DIGIT}+ { printf("%4d\t53\t实数：%s(%g)\n", row,yytext, atof(yytext)); }
0[0-7]+ { printf("%4d\t53\t八进制数：%s(%g)\n",row, yytext, atof(yytext)); }
0x[0-9A-F]* { printf("%4d\t53\t十六进制数：%s\n",row, yytext); }
{DIGIT}+"."{DIGIT}+"e"(""|"-"){DIGIT}+ { printf("%4d\t53\t指数形式的浮点数：%s(%g)\n",row, yytext, atof(yytext)); }
'.*' { printf("%4d\t53\t字符常数：%s\n",row, yytext); }
program { printf("%4d\t 1\t保留字: %s\n",row,yytext); }
var { printf("%4d\t 2\t保留字: %s\n",row,yytext); }
integer { printf("%4d\t 3\t保留字: %s\n",row,yytext); }
bool { printf("%4d\t 4\t保留字: %s\n",row,yytext); }
real { printf("%4d\t 5\t保留字: %s\n",row,yytext); }
char { printf("%4d\t 6\t保留字: %s\n",row,yytext); }
const { printf("%4d\t 7\t保留字: %s\n",row,yytext); }
begin { printf("%4d\t 8\t保留字: %s\n",row,yytext); }
if { printf("%4d\t 9\t保留字: %s\n",row,yytext); }
then { printf("%4d\t10\t保留字: %s\n",row,yytext); }
else { printf("%4d\t11\t保留字: %s\n",row,yytext); }
while { printf("%4d\t12\t保留字: %s\n",row,yytext); }
do { printf("%4d\t13\t保留字: %s\n",row,yytext); }
repeat { printf("%4d\t14\t保留字: %s\n",row,yytext); }
until { printf("%4d\t15\t保留字: %s\n",row,yytext); }
for { printf("%4d\t16\t保留字: %s\n",row,yytext); }
to { printf("%4d\t17\t保留字: %s\n",row,yytext); }
of { printf("%4d\t18\t保留字: %s\n",row,yytext); }
input { printf("%4d\t19\t保留字: %s\n",row,yytext); }
output { printf("%4d\t20\t保留字: %s\n",row,yytext); }
not { printf("%4d\t21\t保留字: %s\n",row,yytext); }
and { printf("%4d\t22\t保留字: %s\n",row,yytext); }
or { printf("%4d\t23\t保留字: %s\n",row,yytext); }
true { printf("%4d\t24\t保留字: %s\n",row,yytext); }
false { printf("%4d\t25\t保留字: %s\n",row,yytext); }
end { printf("%4d\t26\t保留字: %s\n",row,yytext); }
case { printf("%4d\t27\t保留字: %s\n",row,yytext); }
read { printf("%4d\t28\t保留字: %s\n",row,yytext); }
write { printf("%4d\t29\t保留字: %s\n",row,yytext); }
"+" { printf("%4d\t30\t运算符: %s\n",row,yytext); }
"-" { printf("%4d\t31\t运算符: %s\n",row,yytext); }
"*" { printf("%4d\t32\t运算符: %s\n",row,yytext); }
"/" { printf("%4d\t33\t运算符: %s\n",row,yytext); }
"<" { printf("%4d\t34\t运算符: %s\n",row,yytext); }
">" { printf("%4d\t35\t运算符: %s\n",row,yytext); }
"<=" { printf("%4d\t36\t运算符: %s\n",row,yytext); }
">=" { printf("%4d\t37\t运算符: %s\n",row,yytext); }
"=" { printf("%4d\t38\t运算符: %s\n",row,yytext); }
":=" { printf("%4d\t39\t运算符: %s\n",row,yytext); }
"<>" { printf("%4d\t40\t运算符: %s\n",row,yytext); }
":" { printf("%4d\t41\t运算符: %s\n",row,yytext); }
"," { printf("%4d\t42\t运算符: %s\n",row,yytext); }
"//".* { printf("%4d\t44\t注释: //\n",row); }
";" { printf("%4d\t47\t分号：%s\n",row, yytext); }
"(" { printf("%4d\t48\t界符：%s\n",row, yytext); }
")" { printf("%4d\t49\t界符：%s\n",row, yytext); }
"." { printf("%4d\t50\t界符：%s\n",row, yytext); }
"{" { printf("%4d\t51\t界符：%s\n",row, yytext); }
"}" { printf("%4d\t52\t界符：%s\n",row, yytext); }
"[" { printf("%4d\t53\t界符：%s\n",row, yytext); }
"]" { printf("%4d\t54\t界符：%s\n",row, yytext); }
{ID} { printf("%4d\t58\t标识符：%s\n", row,yytext); }
[0-9]+[a-zA-Z]+[a-zA-Z0-9]* { sprintf(faults[cnt_fault++],"%4d\t不能识别的字符：%s\n", row,yytext); }
[\t\x20]+ /*删除多余的空格*/
. { sprintf(faults[cnt_fault++],"%4d\t不能识别的字符：%s\n", row,yytext); }
%%
int main(int argc, char *argv[])
{
system("chcp 65001");
++argv; --argc;
if (argc>0) yyin = fopen(argv[0],"r");
//else yyin = stdin;
else
{
char file[100];
printf("输入你的文件:\n");
scanf("%s",file);
yyin=fopen(file,"r");
}
yylex();
if(cnt_fault>0)
{
printf("错误\n");
for(int i=0;i<cnt_fault;i++)
printf("%s",faults[i]);
}
system("pause");
return 0;
}
int yywrap()
{ return 1; }