CUCU:一个你能理解的编译器(1/3)

2020-07-19 10:50:59

我会试着告诉你这有多简单。第一部分很有理论性,所以要有耐心。

CUCU是玩具语言的玩具编译器。我希望它尽可能接近ANSI CA,这样每个有效的CUCU程序都可以用C编译器编译,没有任何错误。当然,整个ANSI C标准的支持非常困难,所以我选择了一个非常小的C语言子集。

Int cucu_strlen(char*s){int i=0;而(s[i]){i=i+1;}return i;}。

我们即将为我们的语言定义一个语法。这是重要的一步,因为我们编译器设计中的一切都依赖于它。

那么,让我们从上到下。我们的源文件包含一个程序。什么是程序?我们知道它是变量声明、函数声明和函数定义的列表,例如:

Int func(char*s,int len);/*函数声明*/int i;/*变量声明*/int func(char*s,int len){/*函数定义*/...}。

让我们试着用EBNF的形式把它写下来(如果你不知道什么是EBNF,这是绝对可以的,它真的很直观):

这个符号说:“程序是变量声明、函数声明和函数定义的重复序列。但是所有这些描述和定义是什么呢?好的,让我们再深入一点:

<;var-decl>;::=<;type>;<;ident>;";;";<;func-decl>;::=<;type>;<;ident>;";(";<;func-args>;";)";";;";";&。Ident>;";(";<;func-args>;";)";<;func-body>;<;func-args>;::={<;type>;<;ident>;";,";}<;type>;::==";int";|"。

因此,变量声明很简单:它是一个类型名称,后跟标识符,再跟一个分号,就像我们在C中通常做的那样,例如:

函数声明稍微复杂一些。它是一个“类型+标识符”,以及大括号内的函数参数<;func-args>;的可选列表。

反过来,函数参数列表是一系列逗号分隔的“类型+标识符”,如下所示:

实际上,CUCU中的尾随逗号仍然允许,但不是必需的。它只会简化我们的解析器代码。

支持的数据类型仅为int和char*。标识符是由字母、数字和下划线符号组成的序列。

只剩下<;Func-Body>;了。但让我们先来谈谈语句和表达式。

语句是语言中最小的独立元素。以下是OUT语言中的有效语句:

/*这些是简单语句*/i=2+3;/*赋值语句*/my_func(I);/*函数调用语句*/return i;/*return语句*//*这些是复合语句*/if(x>;0){..。}其他{.。}While(x>;0){..。}。

表达式是语句的较小部分。与语句相反,表达式始终返回值。通常,这只是一个算术问题。例如,在语句func(x[2],i+j)中,表达式为x[2]和i+j。

那么,回过头来看看<;Funcc-Body>;。它只是一个有效的语句(通常是块语句)。

<;Funcc-body>;::=<;语句>;<;语句>;::=";{";{<;语句>;}";}";/*块语句*/|[<;type>;]<;ident>;[";=";<;expr>;]";;&。返回";<;expr&>;";;|";IF";";(";<;expr&>;)";<;语句>;[";Else&34;<;语句>;]|";While";";(";<;expr>;<;语句>;|<;表达式>;";;";

<;expr&>;::=<;bit-expr>;|<;bit-expr>;=<;expr&>;<;bit-expr>;::=<;eq-expr>;|<;bitwise-expr>;&;<;eq-expr>;|<;bit-expr>;Eq-expr>;==<;rel-expr&>;|<;eq-expr&>;!=<;rel-expr&>;<;rel-expr>;::=<;Shift-expr&>>;|<;rel-expr&>;<;Shift-expr&>;<;Shift-expr>;:Add-expr>;|<;Shift-expr&>;>;>;<;add-expr>;<;add-expr>;::=<;Postfix-expr>;|<;add-expr>;+<;Postfix-expr>;|<;add-expr>;-<;postfix-expr>&。[<;expr&>]|<;后缀-expr&>;(<;expr&>;{";,<;expr>;})<;prim-expr>;:==<;number>;|<;ident>;|<;string>;|";(";<;expr。

就这样。您注意到表达式表示法中的递归了吗?基本上,上面的符号向我们显示了运算符从下到上的优先顺序:首先计算括号和方括号,最后进行赋值。

例如,根据此语法,表达式8>;>;1+1将被求值为2(如8>;>;(1+1)),而不是5(如(8>;>;1)+1),因为>;>;的优先级低于+。

现在我们学完了语法,准备开始了。第一件要做的事就是艾拉·莱克瑟。我们的编译器接受字节流作为输入,而lexer允许将该流拆分成更小的标记,以便稍后处理。它为我们提供了一定程度的抽象,并简化了解析器。

例如,字节序列“int i=2+31;”将被拆分成标记:

在正常的成人词法分析器中,每个词位(标记)都有一个类型和一个值,因此我们将得到一个配对列表,而不是上面的列表:<;type:int&>;,<;ID:i<;,<;Assign:=&>;,<;NUM:2>;,<;plus:+&>;,<;NUM:31>;,<;Semi:;>。我们要通过它的值来检测lexemetype,这根本不是学术性的!

词法分析器的主要问题是,一旦从流中读取了一个字节,它就不能“不可读”。如果我们读取了一个不能添加到当前令牌中的字节,该怎么办呢?在处理当前令牌之前,我们应该将其存储在哪里?

几乎每个词法分析器都需要提前阅读。我们的语法非常简单,所以我们只需要一个单字节的缓冲区-nextc。它存储一个字节,该字节是从流中读取的,但尚未推送到令牌字符串。

另外,我需要警告您-我在CUCU代码中经常使用全局变量。我知道这是一种糟糕的风格,但是如果我把所有的值都作为函数参数传递,编译器就会失去它的简单性。

如果不是标识符-请尝试读取一系列特殊运算符,如&;、|、<;、>;、=、!。

如果不是运算符-请尝试读取字符串文字“&;mldr”。或者“&;mldr.”

如果再次失败-只需读取单个字节。它可能是另一个单字节字符,如“(”或“[";。

#include<;stdio.h>;/*对于vpritnf*/#include<;stdarg.h>;/*对于va_list*/#include<;stdlib.h>;/*对于exit()*/#include<;ctype.h>;/*对于isspace,isalpha...。*/#定义MAXTOKSZ 256静态文件*f;/*输入文件*/static char tok[MAXTOKSZ];static int tokpos;static int nextc;void readchr(){if(tokpos==MAXTOKSZ-1){tok[tokpos]=';\0';;fprintf(stderr,";标记太长:%s\n";,Nextc=fgetc(F);}void readtok(){for(;;){While(isspace(Nextc)){nextc=fgetc(F);}tokpos=0;While(isalnum(Nextc)||nextc==';_';){readchr();}if(tokpos==0){While(nextc==';<;'。||nextc==';>;';||nextc==';!';||nextc==';|';){readchr();}}if(tokpos==0){if(nextc==';\';';||nextc=='){char c=nextc;Readchr();While(nextc!=c){readchr();}readchr();}false if(nextc==';/';){readchr();if(nextc==';*';){nextc=fgetc(F);While(nextc!=';/';){While(下一个!=';*';){nextc=fgetc(F);}}Else if(nextc!=EOF){readchr();}}Break;}tok[tokpos]=';\0';;}int main(){f=stdin;nextc=fgetc(F);对于(;;){readtok();printf(";内标识:%s\n";,tok);如果(tok[0]==';\0';)Break;}返回0;}。

如果我们将一个C文件作为编译器输入-它将打印一个令牌列表,每行一个。

我希望你喜欢这篇文章。你可以在Github、Twitter或通过RSS订阅,并向其投稿。