编译原理课程实践1报告

发表于

一、环境

项目 内容
系统 Ubuntu 18.04 (Windows Subsystem for Linux), Windows 10 Home, version 1809
GCC Ubuntu 7.3.0-27ubuntu1~18.04
Python Python 2.7.15 [GCC 7.3.0] :: Anaconda, Inc. on linux2
flex flex 2.6.4

二、功能实现

1、指数转换

首先，分析Python中指数的可能形式。

由于题目中的Python 版本为2.7，通过查询Python 2.7相关文档（ https://docs.python.org/2.7/reference/lexical_analysis.html ），获得浮点数的相关词法定义。

1
2
3
4
5
6
floatnumber   ::=  pointfloat | exponentfloat
pointfloat    ::=  [intpart] fraction | intpart "."
exponentfloat ::=  (intpart | pointfloat) exponent
intpart       ::=  digit+
fraction      ::=  "." digit+
exponent      ::=  ("e" | "E") ["+" | "-"] digit+

如下为一些浮点数的形式：

1
3.14    10.    .001    1e100    3.14e-10    0e0

可以看出，Python中指数的形式可以描述为：(整数部分|浮点数)(e|E)[-+]?整数部分。其中，整数部分允许前导0，浮点数允许省略0.X开头的0和 X.0结尾的0，e可以为大写也可以为小写，e之后可以或者省略紧跟+和-表示指数次数的正负，而后的次数只能为整数，整个数字中间不存在空格。

下面给出单个数字、整数部分、浮点数和指数在LEX中的规则：

1
digit [0-9]
1
intpart {digit}+
1
pointfloat ({intpart}?[.]{intpart})|({intpart}[.])
1
exponentfloat ({intpart}|{pointfloat})(e|E)([-+]?){intpart}

当匹配到exponentfloat时，将其转换为小数并写入输出流。下面给出匹配到exponentfloat时的程序操作：

1
2
3
4
5
{exponentfloat} {
    int precision = 0;
    double decimal = str2double(yytext, 0, yyleng, &precision);
    printByPrecision(decimal, precision);
}

str2double是把字符串中st到ed范围内的子串转换成浮点数并返回其小数位数的函数。函数原型如下，具体实现见附录：

1
double str2double(const char *str, int st, int ed, int * precision);

printByPrecision是给出浮点数及其精度，去掉小数点后多余的0后输出的函数，最少有一位小数。函数定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void printByPrecision(double x, int precision)
{
    char buffer[20] = {0};
    sprintf(buffer, "%.*lf", precision, x);
    int len = strlen(buffer);
    for (int i = len - 1; i >= 0; i--)
    {
        if (buffer[i] == '0')
            precision--;
        else
            break;
    }
    if (precision == 0)
        precision++;
    printf("%.*lf", precision, x);
}

将程序作用到题目所给的test.py，执行结果如下：

1
2
3
4
5
6
7
> flex flex.l
> gcc lex.yy.c -lfl
> ./a.out <test.py >result.py
> python ./test.py
10000000000.0 0.05 579 3399.95 45.73
> python ./result.py
10000000000.0 0.05 579 3399.95 45.73

result.py内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/env python 
      
def  main():
    a = 10000000000.0
    b = 0.05
    c = 123+456
    d = 3400.0-0.05
    e = 34+800.0+0.73-789
    print a,b,c,d,e

if   __name__  ==  '__main__':
    main()

2、加减法计算

在上一问的基础上，只需要识别加减表达式即可。在这里我考虑了变量与常量混合的情况，并且忽略+-连续出现而没有运算数的情况。

在只考虑十进制的情况下，表达式可以用描述为，以-+符号或者-+符号连接上数字或者变量开头，随后紧跟0个或者若干个由-+符号连接上数字或者变量的算式。在LEX中的规则可以定义为：

1
decimalinteger ([1-9][0-9]*)|0
1
numeric {decimalinteger}|{pointfloat}|{exponentfloat}
1
alphabet [a-zA-Z]
1
variable ({alphabet}|_)+({numeric}|{alphabet}|_)*
1
expression [-+]?({numeric}|{variable})([-+]({numeric}|{variable}))*

当匹配到expression时，需要将其计算出结果，并写入到输出流中。考虑到实际代码中整数和浮点数的内存占用不同，这里需要将整数与浮点数区别开考虑。表达式参与计算的值如果全部为整数，得到的结果也应该是整数，如果有浮点数参与运算，那么结果就应该是浮点数。对于整数，这里假设其范围在-2147483648~2147483647之间，即C语言中int类型的范围。

下面给出匹配到expression时的程序操作：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
{expression} {
    int st = 0, flag = 1; //st：当前数字的在字符串中开始的位置，flag：需要加还是减

    int hasVar = 0;
    //判断是否有变量
    for (int i = 0; i < yyleng; i++)
    {
        if ((yytext[i] == '+' || yytext[i] == '-') && !(yytext[i + 1] >= '0' && yytext[i + 1] <= '9' || yytext[i + 1] == '.'))
        {
            ECHO;
            hasVar = 1;
            break;
        }
    }

    if (!hasVar)
    {
        int isfloat = 0; //是否作为浮点数进行计算
        for (int i = 0; i < yyleng; i++)
        {
            if (yytext[i] == '.' || yytext[i] == 'e' || yytext[i] == 'E')
            {
                isfloat = 1;
                break;
            }
        }
        if (isfloat)
        {
            int maxprecision = 0, precision = 0;
            double sum = 0; //运算结果
            for (int i = 0; i < yyleng; i++)
            {
                //遇到+-号就可以判断数字的起止位置
                if (yytext[i] == '+' || yytext[i] == '-')
                {
                    //如果是第一个符号，那么不进行计算，只更改符号
                    if (i == 0)
                    {
                        flag = (yytext[i] == '+') ? 1 : -1;
                        st = i + 1;
                    }
                    //如果前面不是E，那么进行计算，如果是E的话，认为是数字的一部分，交给str2double处理
                    else if (yytext[i - 1] != 'E' && yytext[i - 1] != 'e')
                    {
                        double tmp = str2double(yytext, st, i, &precision);
                        if (precision > maxprecision)
                            maxprecision = precision;
                        sum += tmp * flag;
                        flag = (yytext[i] == '+') ? 1 : -1;
                        st = i + 1;
                    }
                }
                //遇到匹配末尾
                if (i == yyleng - 1)
                {
                    double tmp = str2double(yytext, st, yyleng, &precision);
                    if (precision > maxprecision)
                        maxprecision = precision;
                    sum += tmp * flag;
                }
            }
            printByPrecision(sum, maxprecision);
        }
        else
        {
            int sum = 0; //运算结果
            for (int i = 0; i < yyleng; i++)
            {
                //遇到+-号就可以判断数字的起止位置
                if (yytext[i] == '+' || yytext[i] == '-')
                {
                    //如果不是第一个符号，进行计算
                    if (i != 0)
                    {
                        int tmp = str2int(yytext, st, i);
                        sum += tmp * flag;
                    }
                    //整数情况下不存在E
                    flag = (yytext[i] == '+') ? 1 : -1;
                    st = i + 1;
                }
                //遇到匹配末尾了
                if (i == yyleng - 1)
                {
                    int tmp = str2int(yytext, st, yyleng);
                    sum += tmp * flag;
                }
            }
            printf("%d", sum);
        }
    }
}

str2int是把字符串中st到ed范围内的子串转换成整数的函数。函数原型如下，具体实现见附录：

1
int str2int(const char *str, int st, int ed);

将程序作用到题目所给的test.py，执行结果如下：

1
2
3
4
5
6
7
> flex flex.l
> gcc lex.yy.c -lfl
> ./a.out <test.py >result.py
> python ./test.py
10000000000.0 0.05 579 3399.95 45.73
> python ./result.py
10000000000.0 0.05 579 3399.95 45.73

result.py内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/env python 
      
def  main():
    a = 10000000000.0
    b = 0.05
    c = 579
    d = 3399.95
    e = 45.73
    print a,b,c,d,e

if   __name__  ==  '__main__':
    main()

3、更多case

下面是一个考虑了更多情况的测试文件test2.py。

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python 
      
def  main():
    a = 1e+2+3
    b = .53e3+100.
    c = 1+2+a
    d = +1+2+3-4-2e-1
    e = a+3+b+1e5
    print 1+5
    print a,b,c,d,e

if   __name__  ==  '__main__':
    main()

终端中执行结果如下：

1
2
3
4
5
6
7
8
9
> flex flex.l
> gcc lex.yy.c -lfl
> ./a.out <test2.py >result2.py
> python ./test2.py
6
103.0 630.0 106.0 1.8 100736.0
> python ./result2.py
6
103.0 630.0 106.0 1.8 100736.0

result2.py内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python 
      
def  main():
    a = 103.0
    b = 630.0
    c = 1+2+a
    d = 1.8
    e = a+3+b+1e5
    print 6
    print a,b,c,d,e

if   __name__  ==  '__main__':
    main()

三、感想

本次大作业利用LEX进行代码预处理。在实际操作中我先是简单的执行了书上给出的样例，观察了输出和匹配串的行为，然后再设计题目要求的功能。在处理浮点数时，最开始考虑的是在Python中进行尝试，然后总结出指数的正规式，基于自己总结的正规式完成了整个功能。后来在和同学交流中发现Python官网的文档里面有写指数的词法定义，于是对规则进行了完善。

在我的代码中，我对输入做了一定的假设。比如，假设输入的整数只能是C语言int类型的范围，不支持输入l表示长整型等。在输出的时候，由于double的精度问题，输出的小数默认都是6位，而题目样例中给的输出参考是1位或者2位的自适应长度。为了解决这个问题，特意在提取数值的时候求出浮点数的小数位数，并在表达式中取最大的一个精度，然后利用这个精度将求出的结果重新转换为字符串，最后删去末尾多余的0即可。

附：完整的flex.l代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
%{
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int str2int(const char *str, int st, int ed)
{
    int num = 0;
    int base = 10;
    for (int i = st; i < ed; i++)
    {
        num = num * base + str[i] - '0';
    }
    return num;
}

double str2double(const char *str, int st, int ed, int *precision)
{
    int isfloat = 0; //是否作为浮点数进行计算
    for (int i = st; i < ed; i++)
    {
        if (str[i] == '.' || str[i] == 'e' || str[i] == 'E')
        {
            isfloat = 1;
            break;
        }
    }
    if (!isfloat)
    {
        *precision = 0;
        return str2int(str, st, ed);
    }

    double num1 = 0;          //e之前的数值
    int num2 = 0;             //e之后的数值
    int flag1 = 0, flag2 = 0; //flag1：是否在小数点后，flag2：是否在e之后
    double e = 1;             //小数点之后的权重
    for (int i = st; i < ed; i++)
    {
        if (str[i] >= '0' && str[i] <= '9')
        {
            if (!flag1 && !flag2) //e以前，小数点前
                num1 = num1 * 10 + (str[i] - '0');
            else if (flag1 && !flag2) //e以前，小数点后
            {
                e = e / 10.0;
                (*precision)++;
                num1 = num1 + (str[i] - '0') * e;
            }
            else if (flag2) //e以后
                num2 = num2 * 10 + (str[i] - '0');
        }
        else if (str[i] == '.')
        {
            flag1 = 1;
            (*precision)++;
        }
        else if (str[i] == 'e' || str[i] == 'E')
            flag2 = 1;
        else if (str[i] == '-')
            flag2 = 2;
    }

    if (e != 1)
        (*precision)--;

    double k = 1;   //10的num2次方
    if (flag2 == 1) //e之后是正幂次
    {
        (*precision) -= num2;
        for (int i = 0; i < num2; i++)
            k = k * 10;
    }
    else if (flag2 == 2) //e之后是负幂次
    {
        (*precision) += num2;
        for (int i = 0; i < num2; i++)
            k = k / 10;
    }
    if (*precision <= 0)
        *precision = 1;
    num1 = num1 * k;
    return num1;
}

void printByPrecision(double x, int precision)
{
    char buffer[20] = {0};
    sprintf(buffer, "%.*lf", precision, x);
    int len = strlen(buffer);
    for (int i = len - 1; i >= 0; i--)
    {
        if (buffer[i] == '0')
            precision--;
        else
            break;
    }
    if (precision == 0)
        precision++;
    printf("%.*lf", precision, x);
}

%}
digit [0-9]
intpart {digit}+
pointfloat ({intpart}?[.]{intpart})|({intpart}[.])
exponentfloat ({intpart}|{pointfloat})(e|E)[-+]?{intpart}
decimalinteger ([1-9][0-9]*)|0
numeric {decimalinteger}|{pointfloat}|{exponentfloat}
alphabet [a-zA-Z]
variable ({alphabet}|_)+({numeric}|{alphabet}|_)*
expression [-+]?({numeric}|{variable})([-+]({numeric}|{variable}))*
%%

{exponentfloat} {
    int precision = 0;
    double decimal = str2double(yytext, 0, yyleng, &precision);
    printByPrecision(decimal, precision);
}

{variable} {
    ECHO;
}

{expression} {
    int st = 0, flag = 1; //st：当前数字的在字符串中开始的位置，flag：需要加还是减

    int hasVar = 0;
    //判断是否有变量
    for (int i = 0; i < yyleng; i++)
    {
        if ((yytext[i] == '+' || yytext[i] == '-') && !(yytext[i + 1] >= '0' && yytext[i + 1] <= '9' || yytext[i + 1] == '.'))
        {
            ECHO;
            hasVar = 1;
            break;
        }
    }

    if (!hasVar)
    {
        int isfloat = 0; //是否作为浮点数进行计算
        for (int i = 0; i < yyleng; i++)
        {
            if (yytext[i] == '.' || yytext[i] == 'e' || yytext[i] == 'E')
            {
                isfloat = 1;
                break;
            }
        }
        if (isfloat)
        {
            int maxprecision = 0, precision = 0;
            double sum = 0; //运算结果
            for (int i = 0; i < yyleng; i++)
            {
                //遇到+-号就可以判断数字的起止位置
                if (yytext[i] == '+' || yytext[i] == '-')
                {
                    //如果是第一个符号，那么不进行计算，只更改符号
                    if (i == 0)
                    {
                        flag = (yytext[i] == '+') ? 1 : -1;
                        st = i + 1;
                    }
                    //如果前面不是E，那么进行计算，如果是E的话，认为是数字的一部分，交给str2double处理
                    else if (yytext[i - 1] != 'E' && yytext[i - 1] != 'e')
                    {
                        double tmp = str2double(yytext, st, i, &precision);
                        if (precision > maxprecision)
                            maxprecision = precision;
                        sum += tmp * flag;
                        flag = (yytext[i] == '+') ? 1 : -1;
                        st = i + 1;
                    }
                }
                //遇到匹配末尾
                if (i == yyleng - 1)
                {
                    double tmp = str2double(yytext, st, yyleng, &precision);
                    if (precision > maxprecision)
                        maxprecision = precision;
                    sum += tmp * flag;
                }
            }
            printByPrecision(sum, maxprecision);
        }
        else
        {
            int sum = 0; //运算结果
            for (int i = 0; i < yyleng; i++)
            {
                //遇到+-号就可以判断数字的起止位置
                if (yytext[i] == '+' || yytext[i] == '-')
                {
                    //如果不是第一个符号，进行计算
                    if (i != 0)
                    {
                        int tmp = str2int(yytext, st, i);
                        sum += tmp * flag;
                    }
                    //整数情况下不存在E
                    flag = (yytext[i] == '+') ? 1 : -1;
                    st = i + 1;
                }
                //遇到匹配末尾了
                if (i == yyleng - 1)
                {
                    int tmp = str2int(yytext, st, yyleng);
                    sum += tmp * flag;
                }
            }
            printf("%d", sum);
        }
    }
}    
%%

int main(void)
{
    yylex();
    return 0;
}