编程原理学习笔记(一)

有空学习一下编程语言与编译原理相关知识。看的是《自制编程语言这本书》

环境搭建

开发语言是C,工具使yacc和lex,环境为Ubuntu子系统。

先安装gcc make cmake ,然后是bison(yacc)和flex(lex)

1
2
sudo apt update
sudo apt install gcc make cmake bison flex

语法处理

分为4个阶段: 1. 词法分析 将源代码分为若干个记号(token)。 2. 语法分析 从记号构建分析树,或称之为语法树/抽象语法树。 3. 语义分析 检查是否含有语法正确但存在逻辑问题的错误。还会进行数据类型的检查。 4. 生成代码 进入代码生成阶段

执行词法分析的程序,称为词法分析器。lex是编写词法分析器的工具 执行语法分析的程序,称为解析器。yacc是编写语法分析器的工具

yacc是Yet Another Compiler Compiler的缩写,即又一个生成编译器的编译器。实际上只是解析器部分。

lex则是lexical analyzer的缩写。

由于词法分析是早于语法分析的,所以就能解释i+++++j这句编译报错的原因了。i+++++j被词法分析拆分成了i ++ ++ + j,从而导致语法分析时出错。

使用lex+yacc编写一个简单计算器程序

最终的效果需要输入任何一个式子,得到式子的结果,如:

1
2
3
4
1+2
>> 3.000000
1+2*3
>> 7.000000

词法分析

lex是生成一个词法分析器的工具。我们需要编写.l文件,lex输入.l文件,输出词法分析器的C语言代码。flex则是增强版的lex。

词法分析器将输入的字符串分割为记号,因此先要想好我们都使用哪些记号。简单的计算器程序应当至少包含这些记号:

  • 运算符。基本的四则运算运算符,即+-*/
  • 实数。包含整数和小数。小数先忽略包含e的浮点数表示法。
  • 换行符。输入换行符就会执行计算,因此换行符应设置为记号。
  • 空白符。空格和制表符应当被略过。

为简单起见,先不考虑括号

一个.l文件由定义区块,规则区块,用户代码区块组成。区块间用%%分隔。

定义区块

1
2
3
4
5
6
7
8
9
10
%{
#include <stdio.h>
#include "y.tab.h"

int
yywrap()
{
return 1;
}
%}

定义区块内可以定义初始状态或为正则表达式命名(以方便直接调用)等。

使用%{}%包裹的部分,词法分析器会将之原样输出:

这里原样输出了一些代码,作为最终代码的起始部分,包括包含头文件。其中y.tab.h是之后yacc自动生成的头文件,等之后可以回过头来再看。

yywrap函数直接返回了1。如果没有这个函数就必须手动链接lex库文件,在不同编译环境时比较麻烦,因此最好写上。

When the scanner receives an end-of-file indication from YY_INPUT, it then checks the yywrap() function. If yywrap() returns false (zero), then it is assumed that the function has gone ahead and set up yyin to point to another input file, and scanning continues. If it returns true (non-zero), then the scanner terminates, returning 0 to its caller. Note that in either case, the start condition remains unchanged; it does not revert to INITIAL.

If you do not supply your own version of yywrap(), then you must either use %option noyywrap (in which case the scanner behaves as though yywrap() returned 1), or you must link with -lfl to obtain the default version of the routine, which always returns 1.

规则区块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"+"     return ADD;
"-" return SUB;
"*" return MUL;
"/" return DIV;
"\n" return CR;
(0|([1-9][0-9]*))(\.[0-9]*)? {
double temp;
sscanf(yytext, "%lf", &temp);
yylval.double_value = temp;
return DOUBLE_LITERAL;
}
[ \t] ;
. {
fprintf(stderr, "lexical error, value: %s", yytext);
exit(1);
}

规则区块使用正则表达式描述记号。

记号一般包含三部分含义,分别是: 1. 记号的原始字符串 一个记号包含输入的原始字符串,比如123.456的原始字符串"123.456",内存中应当用8字节保存(包括结尾的\0) 2. 记号的种类 描述一个记号的种类,一般用大写字母表示,比如123.456的种类为实常量(DOUBLE_LITERAL) 3. 记号的值 记号代表具体的数值,比如123.456代表double类型的双精度浮点数123.456,在内存中应当用8字节保存。

对于运算符,只需关注记号种类。而数值类的记号还需关心记号的值。

规则区块的书写方式:一个正则表达式,后面接C代码(如果多于一行应用大括号包裹)。如果输入的字符串匹配正则表达式,则执行后面的C代码。这部分C代码称为动作。

前5行负责处理四则运算字符和回车。注意这里的双引号是正则的转义字符(这种风格的正则表达式支持这种转义的方式),也可以写成\+\-\*\/ 后面接了一句C语言语句,直接返回了对应的标识符。现在可能无法理解具体含义,后面继续学。

接下来是处理浮点数值的部分。前面的略复杂的正则表示负责匹配所有的实数,包括123123.456。这里的正则可能并非最优,暂时无法匹配1e10.2这种C风格的浮点数,不过暂且够用。不太清楚这里的正则具体的规则,会不会和其他的不一样,找了篇资料以后慢慢研究。“记号的原始字符串”会被全局变量yytext引用。接下来sscanf函数解析这个字符串,并将解析的结果存放在yylaval这个全局变量中。yylval是一个联合体(union),可以存放各种类型记号的值。此变量的定义写在yacc的定义文件calc.y中,具体见下文。

用户代码区块

这一部分可以编写任意C代码,并且不用%{%}包裹。本例中没有用户代码区块。

lex中的正则表达式

书上的匹配实数的正则表达式似乎有点问题,待之后运行起来测试。

这是一个匹配C风格浮点数的正则表达式

1
[-+]?(([1-9][0-9]*)|0)(\.[0-9]*)?([eE][-+]?(([1-9][0-9]*)|0))?

待补充

语法分析

yacc则是生成解析器的工具。我们需要编写yacc的.y文件。向yacc程序输入.y文件,就会输出语法分析器的C语言代码。bison则是yacc的增强版。

yacc的.y文件同样也由区块组成,也分别为定义区块,规则区块,用户代码区块,区块间用%%分隔

定义区块

1
2
3
4
5
6
7
8
9
10
11
12
%{
#include <stdio.h>
#include <stdlib.h>
#define YYDEBUG 1
%}
%union {
int int_value;
double double_value;
}
%token <double_value> DOUBLE_LITERAL
%token ADD SUB MUL DIV CR
%type <double_value> expression term primary_expression

与lex相同开头先用%{%}包裹了一部分C代码,负责包含头文件,并且用预处理定义了YYDEBUG的值为1,这样能开启调试模式,方便调试查看程序运行中语法分析的状态。调试部分之后学习。

接下来声明了记号以及非终结符的种类。记号可能会有很多类型,这些类型都声明在这个联合体中。本例其实只用到double类型。为方便说明多定义了一个int类型没有用到。

非终结符由记号组成,最后以一个特殊记号终结符组成。

接下来是声明记号。第一种记号DOUBLE_LITERAL是实常量,用尖括号<>包裹指定类型为double_value,即上文定义的记号的种类。对于不关心数值的记号即ADD SUB MUL DIV CR ,无需指定类型。

最后声明这些非终结符的类型,指明为double_value

非终结符

我的理解是一个句子由若干个非终结符和一个终结符组成。非终结符由若干个记号组成。这些记号组合起来可能也代表着数值。比如3+5这句话,3,+,5都是几号,35具有具体的数值,+不具有数值,代表着相加,于是3+5这个非终结符应当表示8的数值,即所谓的非终结符的数值和类型。

规则区块

定义区块之后是规则区块:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
line_list
: line
| line_list line
;
line
: expression CR
{
printf(">>%lf\n", $1);
}
;
expression
: term
| expression ADD term
{
$$ = $1 + $3;
}
| expression SUB term
{
$$ = $1 - $3;
}
;
term
: primary_expression
| term MUL primary_expression
{
$$ = $1 * $3;
}
| term DIV primary_expression
{
$$ = $1 / $3;
}
;
primary_expression
: DOUBLE_LITERAL
;

规则区块的每一条规则由语法规则和C语言编写的动作两部分组成。在yacc中使用BNF(巴科斯范式,Backus Normal Form)规范来编写规则。

初步看起来有点复杂,实际上每条规则书写方式都是这样的格式:

1
2
3
4
5
6
7
A
: B /* A 产生 B / B 规约成A ,可不执行动作 */
| C D /* 或,A 产生C D / C D 规约成 A*/
{
/* A产生C D / C D规约成A 时执行的动作 */
}
; /* 分号表示一条规则结束 */

文中A、B、C、D都是非终结符,即表示A的定义是B或是C与D的结合。

巴科斯范式是一种上下文无关文法,足够简单且容易构造分析算法来分析句子。如果将上述例子写成产生式规则是这样的: \[ A\to B | CD \] 我们的简单计算机程序的文法应该是这样的: \[ \begin{align} &G =(N,\Sigma,P,S)\\ &N =\{line\_list, line, expression, term, primary\_expression\}\\ &\Sigma =\{DOUBLE\_LITERAL, ADD, SUB, MUL, DIV, CR\}\\ &S =line\_list\\ &P由以下产生式规则组成:\\ &1.line\_list\to line|line\_list\ line\\ &2.line\to expression\ CR\\ &3.expression\to term|expression\ ADD\ term|expression\ SUB\ term\\ &4.term\to primary\_expression|term\ MUL\ primary\_expression|term\ DIV\ primary\_expression\\ &5.primary\_expression\to DOUBLE\_LITERAL\\ \end{align} \] 可能这样看比较接近我们形式语言与自动机中学的理论了。BNF的书写规则有些许不同,大体上相似。

下面解释一下这些产生式规则的含义。

line_listline是用来表示一句话可能出现一句以上。在本例中,我们需要循环输入表达式以得到结果,所以需要设计成支持出现一次以上的模式。line_list产生line_list line这种形式以实现无穷多句话。

每一行line产生expression和CR,即一个表达式和换行符。输入回车后,表示这句话结束了,应当输出结果,所以动作是将表达式的值输出。同时没有对$$赋值,则数据没有保留。

表达式可以是单独的一个项,也可以是表达式加项或表达式减项

一开始我对这里有些异或,表达式也可以是项加减项啊,为什么不包括这一条呢?后续探讨这个问题

项可以是单独的一元表达式,或是项乘以一元表达式或除以。

一元表达式则是实常量。

此外,在语法规则中包含了运算符的优先级顺序以及结合规律,即先乘除后加减。具体是为何能实现的需要更多理论知识。

每条规则被触发时,可以执行一定的动作,即每条规则后的C语言语句。比如乘法对应执行的规则:

1
2
3
4
5
term
: term MUL primary_expression
{
$$ = $1 * $3;
}

产生式中的非终结符的值被以此保存在$1,$2,$3等变量中。$$表示当前栈的值,可以理解为规约后的term的值。

同时,如果书写动作时,yacc会补全一个{$$ = $1;}的动作:

1
2
primary_expression
: DOUBLE_LITERAL

等价于

1
2
3
4
5
primary_expression
: DOUBLE_LITERAL
{
$$ = $1;
}

因此本例中的所有非终结符都是有具体数值的,类型为double_vale(在定义区块中定义)

用户代码区块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int
yyerror(char const* str)
{
extern char* yytext;
fprintf(stderr, "parser error near %s\n", yytext);
return 0;
}

int main()
{
extern int yyparse();
extern FILE* yyin;

yyin = stdin;
if (yyparse()) {
fprintf(stderr, "ERROR! ERROR! ERROR!\n");
exit(1);
}
}

在此处编写我们的程序的main函数。全局变量yyin设定输入,然后调用yyparse()函数解析。

还要定义一个回调函数yyerror,当解析失败时会调用并给出回显。

语法分析器的执行过程

语法分析执行时回实现一个栈,所有的记号会按顺序在中依次移进,并根据产生式规则进行规约并执行动作。

1+2*3为例,图解详细的分析过程。

首先字符串被词法分析器分割成了一个个记号。

这里词法分析器分析完后就已经变成记好了,对应着1,+,2,*,3这些字符。同样这些DOUBLE_LITERAL也有具体的数值了。

然后按顺序记号依次入栈,成为移进(shift)。

首先是记号1移进,记号ADD为下一个等待移进:

    Next: 
    <button>ADD</button>
</div>
<button>DOUBLE_LITERAL</button> ......

记号1触发规则:

1
2
primary_expression
: DOUBLE_LITERAL

归约成primary_expression:

Next: <button>ADD</button>
</div>
<button>primary_expression</button> ......

primary_expression不会和ADD触发规则。而自身触发规则:

1
2
term
: primary_expression

归约成term

Next: <button>SUB</button>
</div>
<button>term</button> ......

term还是不会和ADD触发规则,自身继续触发规则:

1
2
expression
: term

归约成expression

Next: <button>ADD</button>
</div>
<button>expression</button> ......

此时单独的expression似乎不能继续触发规则而归约了。

接下来记号+移进:

    Next: <button>DOUBLE_LITERAL</button>
</div>
<button>expression</button> 
<button>ADD</button> ......

此时不能触发任何规则,于是继续移进下一个记号:

    Next: <button>MUL</button>
</div>
<button>expression</button> 
<button>ADD</button> 
<button>DOUBLE_LITERAL</button> ......

单独的DOUBLE_LITERAL还是归约成primary_expression

    Next: <button>MUL</button>
</div>
<button>expression</button> 
<button>ADD</button> 
<button>primary_expression</button> ......

还是继续归约为term

    Next: <button>MUL</button>
</div>
<button>expression</button> 
<button>ADD</button> 
<button>term</button> ......

接下来就有些不一样的地方了。expression ADD term可以触发规则:

1
2
expression
: expression ADD term

然而下一个记号是MUL,由于有规则

1
2
term
: term MUL primary_expression

所以这里不能归约,要接下来的归约情况,因此不做归约,继续移进下一个记号:

    Next: <button>DOUBLE_LITERAL</button>
</div>
<button>expression</button> 
<button>ADD</button> 
<button>term</button> 
<button>MUL</button> ......

此时还不能归约,继续移进

    Next: 
</div>
<button>expression</button> 
<button>ADD</button> 
<button>term</button> 
<button>MUL</button> 
<button>DOUBLE_LITERAL</button> ......

此时,前三个匹配一个规则,后三个记号匹配一个规则。这里会将后三个记号归约成term(为什么不会产生冲突暂时不清楚):

    Next: 
</div>
<button>expression</button> 
<button>ADD</button> 
<button>term</button>  ......

同时归约的时候执行动作,计算2*3的值,并存入栈中规约后的非终结符term

继续触发规则,归约成expression:

    Next: 
</div>
<button>expression</button> ......

同样计算$1+$3,得到结果7。

生成可执行文件

接下来就可以使用lex和yacc生成源代码,然后编译并链接生成可执行文件:

首先用lex或flex生成词法分析器的C代码lex.yy.c

1
2
$ flex calc.l
# 或者用 lex calc.l

然后使用yacc或bison生成语法分析器的C代码y.tab.cy.tab.h

1
2
$ bison -dv --yacc calc.y
# 或者用 yacc -dv calc.y

选项--yacc是为了使生成的文件名为y.tab.cy.tab.h,lex.yy.ccalc.l中需要正确包含这个头文件。如果不加--yacc生成的文件名为calc.tab.ccalc.tab.h

-d会生成头文件,共lex.yy.c包含-v会生成一个.output文件,它会包含所有的语法规则,解析器,所有可能的分支状态以及编译器启动信息。

之后可以用gcc编译成可执行文件

1
$ gcc -o calc y.tab.c lex.yy.c

程序执行最终效果:

1
2
3
4
5
$ ./calc
3*3+1
>>10.000000
1.2*5
>>6.000000

总结

简单了解了编译器的组成,了解了使用lex+yacc书写一个编译器前端的过程。初步了解lex与yacc的使用方法,编写了一个简单的计算器程序。

编写过程中对词法分析和语法分析有了初步的了解。

参考资料

The Flex Manual Page: http://dinosaur.compilertools.net/flex/manpage.html LEX regular expressions: http://www.csd.uwo.ca/~moreno/CS447/Lectures/Lexical.html/node11.html Formal grammar: https://en.wikipedia.org/wiki/Formal_grammar Backus–Naur form: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form