Pwn进你的心
0%

CMPT379编译器Lab1：decaflex

Posted on In 15k 14 mins.

decaflex

本作业的目标是为 Decaf 编程语言编写一个词法分析器

Decaf 中词汇元素的详细信息在 Decaf 规范中：Decaf Programming Language Specification

词法分析器为给定的 Decaf 程序生成令牌流

  • 输入取自标准输入 stdin，将输出令牌流发送到标准输出 stdout
  • 并在标准错误 stderr 流上发出错误

在 /compilers-class-hw/decaflex/testcases/dev 目录中包含了提供给词法分析器的输入样例

实验描述

使用 Decaf 规范作为指导，完成一个 lex 程序，该程序是 Decaf 语言的词法分析器

请务必遵守以下要求：

  • 如果程序成功解析输入，则应使用 exit(EXIT_SUCCESS) 退出程序，如果您的程序发现词法错误，则应使用 exit(EXIT_FAILURE)
  • 请注意，标记名称和词法值应与目录 testcases 中提供给您的示例输出相同
  • 您必须使用 Decaf 规范的令牌列表部分中提供的令牌名称
  • 必须包含特殊的空格和注释标记：
    • 空格标记应具有包含所有空格字符的词法值
    • 空格和注释词素应将换行符 \n 转换为文本字符串，以便可以从词法分析器输出中恢复每个标记的行号和字符号
  • 提供适当的错误报告，包括检测到错误的行中的行号和位置请注意，它不会检查错误消息的内容，check.py 只会检查词法分析器的返回值

使用 Python 程序在测试用例上运行 zipout.py 解决方案程序，您的解决方案必须在目录 answer 中编译，并且必须调用 decaflex，针对所有测试用例运行，如下所示：

1
python3 zipout.py
  • 这将创建一个名为 output 的目录和一个可以根据参考输出文件进行检查的文件 output.zip
1
python3 check.py
  • 这将检查您解决方案的准确性

实验步骤

一开始会得到如下的 default.lex 文件：（不完整的解决方案）

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
%{

#include <iostream>
#include <cstdlib>

using namespace std;

%}

%%
  /*
    Pattern definitions for all tokens
  */
func                       { return 1; }
int                        { return 2; }
package                    { return 3; }
\{                         { return 4; }
\}                         { return 5; }
\(                         { return 6; }
\)                         { return 7; }
[a-zA-Z\_][a-zA-Z\_0-9]*   { return 8; }
[\t\r\a\v\b ]+             { return 9; }
\n                         { return 10; }
.                          { cerr << "Error: unexpected character in input" << endl; return -1; }

%%

int main () {
  int token;
  string lexeme;
  while ((token = yylex())) {
    if (token > 0) {
      lexeme.assign(yytext);
      switch(token) {
        case 1: cout << "T_FUNC " << lexeme << endl; break;
        case 2: cout << "T_INT " << lexeme << endl; break;
        case 3: cout << "T_PACKAGE " << lexeme << endl; break;
        case 4: cout << "T_LCB " << lexeme << endl; break;
        case 5: cout << "T_RCB " << lexeme << endl; break;
        case 6: cout << "T_LPAREN " << lexeme << endl; break;
        case 7: cout << "T_RPAREN " << lexeme << endl; break;
        case 8: cout << "T_ID " << lexeme << endl; break;
        case 9: cout << "T_WHITESPACE " << lexeme << endl; break;
        case 10: cout << "T_WHITESPACE \\n" << endl; break;
        default: exit(EXIT_FAILURE);
      }
    } else {
      if (token < 0) {
        exit(EXIT_FAILURE);
      }
    }
  }
  exit(EXIT_SUCCESS);
}

实验的目标就是根据 Decaf 规范来补充上述文件中缺失的正则表达式

在补充 default.lex 之前我们可以先编译一下，然后看看它有什么功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
➜  answer git:(master) ✗ ./decaflex
package Test { func main() int { } }
T_PACKAGE package
T_WHITESPACE  
T_ID Test
T_WHITESPACE  
T_LCB {
T_WHITESPACE  
T_FUNC func
T_WHITESPACE  
T_ID main
T_LPAREN (
T_RPAREN )
T_WHITESPACE  
T_INT int
T_WHITESPACE  
T_LCB {
T_WHITESPACE  
T_RCB }
T_WHITESPACE  
T_RCB }
T_WHITESPACE \n
  • 可以发现：字符串 package Test { func main() int { } } 的每个元素都被拆解为了 token（词法分析器就是这个功能）

非完整代码如下：

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
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
%{

#include <iostream>
#include <cstdlib>

using namespace std;

const char *node_map[]={
  "T_AND"            ,
  "T_ASSIGN"         ,
  "T_BOOLTYPE"       ,
  "T_BREAK"          ,
  "T_CHARCONSTANT"   ,
  "T_COMMA"          ,
  "T_COMMENT"        ,
  "T_CONTINUE"       ,
  "T_DIV"            ,
  "T_DOT"            ,
  "T_ELSE"           ,
  "T_EQ"             ,
  "T_EXTERN"         ,
  "T_FALSE"          ,
  "T_FOR"            ,
  "T_FUNC"           ,
  "T_GEQ"            ,
  "T_GT"             ,
  "T_ID"             ,
  "T_IF"             ,
  "T_INTCONSTANT"    ,
  "T_INTTYPE"        ,
  "T_LCB"            ,
  "T_LEFTSHIFT"      ,
  "T_LEQ"            ,
  "T_LPAREN"         ,
  "T_LSB"            ,
  "T_LT"             ,
  "T_MINUS"          ,
  "T_MOD"            ,
  "T_MULT"           ,
  "T_NEQ"            ,
  "T_NOT"            ,
  "T_NULL"           ,
  "T_OR"             ,
  "T_PACKAGE"        ,
  "T_PLUS"           ,
  "T_RCB"            ,
  "T_RETURN"         ,
  "T_RIGHTSHIFT"     ,
  "T_RPAREN"         ,
  "T_RSB"            ,
  "T_SEMICOLON"      ,
  "T_STRINGCONSTANT" ,
  "T_STRINGTYPE"     ,
  "T_TRUE"           ,
  "T_VAR"            ,
  "T_VOID"           ,
  "T_WHILE"          ,
  "T_WHITESPACE"     ,
  "T_WHITESPACE \\n"
};

enum node_kind
{
  T_AND            ,
  T_ASSIGN         ,
  T_BOOLTYPE       ,
  T_BREAK          ,
  T_CHARCONSTANT   ,
  T_COMMA          ,
  T_COMMENT        ,
  T_CONTINUE       ,
  T_DIV            ,
  T_DOT            ,
  T_ELSE           ,
  T_EQ             ,
  T_EXTERN         ,
  T_FALSE          ,
  T_FOR            ,
  T_FUNC           ,
  T_GEQ            ,
  T_GT             ,
  T_ID             ,
  T_IF             ,
  T_INTCONSTANT    ,
  T_INTTYPE        ,
  T_LCB            ,
  T_LEFTSHIFT      ,
  T_LEQ            ,
  T_LPAREN         ,
  T_LSB            ,
  T_LT             ,
  T_MINUS          ,
  T_MOD            ,
  T_MULT           ,
  T_NEQ            ,
  T_NOT            ,
  T_NULL           ,
  T_OR             ,
  T_PACKAGE        ,
  T_PLUS           ,
  T_RCB            ,
  T_RETURN         ,
  T_RIGHTSHIFT     ,
  T_RPAREN         ,
  T_RSB            ,
  T_SEMICOLON      ,
  T_STRINGCONSTANT ,
  T_STRINGTYPE     ,
  T_TRUE           ,
  T_VAR            ,
  T_VOID           ,
  T_WHILE          ,
  T_WHITESPACE     ,
  T_WHITESPACE2
};

%}

escaped_char '(\\n|\\r|\\t|\\v|\\f|\\a|\\b|\\)'
normal_char  '(a-z|A-Z|0-9)'
arith_char   '(\+|\-|\*|\/|\%|\<|\>|\=|\!|\||\&)'
blank_char   '(\(|\)|\[|\]|\{|\})'
other_char   '(\ |\@|\#|\$|\^|\"|\'|\:|\;|\.|\,|\?|\_|\`|\~)'

all_char     {escaped_char}|{normal_char}|{arith_char}|{blank_char}|{other_char}

escaped_str  \"[\\n|\\r|\\t|\\v|\\f|\\a|\\b|\\]+\"
normal_str   \"[a-z|A-Z|0-9]+\"
arith_str    \"[\+|\-|\*|\/|\%|\<|\>|\=|\!|\||\&]+\"
blank_str    \"[\(|\)|\[|\]|\{|\}]+\"
other_str    \"[\ |\@|\#|\$|\^|\"|\'|\:|\;|\.|\,|\?|\_|\`|\~]+\"

all_str      {escaped_str}|{normal_str}|{arith_str}|{blank_str}|{other_str}

decimal_num  [0-9]+
hex_num      0(x|X)[0-9a-fA-F]+    

normal_id    [a-zA-Z\_][a-zA-Z\_0-9]*

%%
  /*
    Pattern definitions for all tokens
  */

"&&"                       { return T_AND; }
"="                        { return T_ASSIGN; }
"bool"                     { return T_BOOLTYPE; }
"break"                    { return T_BREAK; }
{all_char}                 { return T_CHARCONSTANT; }
{all_str}                  { return T_STRINGCONSTANT; }
","                        { return T_COMMA; }
"comment"                  { return T_COMMENT; }
"continue"                 { return T_CONTINUE; }
"/"                        { return T_DIV; }
"."                        { return T_DOT; }
"else"                     { return T_ELSE; }
"=="                       { return T_EQ; }
"extern"                   { return T_EXTERN; }
"false"                    { return T_FALSE; }
"for"                      { return T_FOR; }
"func"                     { return T_FUNC; }
">="                       { return T_GEQ; }
">"                        { return T_GT; }
"if"                       { return T_IF; }
{decimal_num}|{hex_num}    { return T_INTCONSTANT; }
"int"                      { return T_INTTYPE; }
"{"                        { return T_LCB; }
"<<"                       { return T_LEFTSHIFT; }
"<="                       { return T_LEQ; }
"("                        { return T_LPAREN; }
"["                        { return T_LSB; }
"<"                        { return T_LT; }
"-"                        { return T_MINUS; }
"%"                        { return T_MOD; }
"*"                        { return T_MULT; }
"!="                       { return T_NEQ; }
"!"                        { return T_NOT; }
"null"                     { return T_NULL; }
"||"                       { return T_OR; }
"package"                  { return T_PACKAGE; }
"+"                        { return T_PLUS; }
"}"                        { return T_RCB; }
"return"                   { return T_RETURN; }
">>"                       { return T_RIGHTSHIFT; }
")"                        { return T_RPAREN; }
"]"                        { return T_RSB; }
";"                        { return T_SEMICOLON; }
"string"                   { return T_STRINGTYPE; }
"true"                     { return T_TRUE; }
"var"                      { return T_VAR; }
"void"                     { return T_VOID; }
"while"                    { return T_WHILE; }
[\t\r\a\v\b ]+             { return T_WHITESPACE; }
\n                         { return T_WHITESPACE2; }
{normal_id}                { return T_ID; }
.                          { cerr << "Error: unexpected character in input" << endl; return -1; }

%%

int main () {
  int token,key=0;
  string lexeme;

  while ((token = yylex())) {
    if (token > 0) {
      lexeme.assign(yytext);
      if(token < sizeof(node_map)/sizeof(char*)){
        if(token == T_WHITESPACE2){
          if(key == 1){
            cout << "T_WHITESPACE \\n\\n" << endl;
            key = 2;
          }
          else if(key == 0){
            key = 1;
          }
        }
        else if(token == T_WHITESPACE){
          if(key == 1){
            cout << "T_WHITESPACE \\n" << lexeme << endl;
            key = 0;
          }
          else if(key == 2){
            cout << lexeme << endl;
            key = 0;
          }
          else{
            cout << "T_WHITESPACE " << lexeme << endl;
            key = 0;
          }
        }
        else{
          if(key == 2){
            key = 0;
          }
          if(key == 1){
            cout << "T_WHITESPACE \\n" << endl;
            key = 0;
          }
          cout << node_map[token] << " " << lexeme << endl;
        }
      }
      else{
        exit(EXIT_FAILURE);
      }
    } else {
      if (token < 0) {
        exit(EXIT_FAILURE);
      }
    }
  }
  if(key == 1){
    cout << "T_WHITESPACE \\n" << endl;
    key = 0;
  }
  exit(EXIT_SUCCESS);
}
  • 由于原实验的检查机制过于严格，我为了提高分数而做了不少特殊处理（这导致了代码的可读性下降，但大体上的功能是实现了的）
  • 改来改去还是发现不理想，最终得分如下：
1
2
3
Correct(dev): 30 / 59
Score(dev): 30.00
Total Score: 30.00

大体上遇到如下的问题：

  • 除了莫名其妙的 \n 和空格会干扰结果以外，报错处理的问题还没有解决
  • 字符串处理也没有到位，特别是带有 \ 的字符串
  • 程序要求错误的语义直接输出 -1，但我的程序是一边检查一边打印数据的，要想直接输出 -1 就必须提前把数据存储在缓冲区中

最后对着那几个错误的案例进行修改，写了个满分的分析器

完整代码如下：

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
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
%{

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <iostream>

using namespace std;

const char *node_map[]={
  "T_AND"            ,
  "T_ASSIGN"         ,
  "T_BOOLTYPE"       ,
  "T_BREAK"          ,
  "T_CHARCONSTANT"   ,
  "T_COMMA"          ,
  "T_COMMENT"        ,
  "T_CONTINUE"       ,
  "T_DIV"            ,
  "T_DOT"            ,
  "T_ELSE"           ,
  "T_EQ"             ,
  "T_EXTERN"         ,
  "T_FALSE"          ,
  "T_FOR"            ,
  "T_FUNC"           ,
  "T_GEQ"            ,
  "T_GT"             ,
  "T_ID"             ,
  "T_IF"             ,
  "T_INTCONSTANT"    ,
  "T_INTTYPE"        ,
  "T_LCB"            ,
  "T_LEFTSHIFT"      ,
  "T_LEQ"            ,
  "T_LPAREN"         ,
  "T_LSB"            ,
  "T_LT"             ,
  "T_MINUS"          ,
  "T_MOD"            ,
  "T_MULT"           ,
  "T_NEQ"            ,
  "T_NOT"            ,
  "T_NULL"           ,
  "T_OR"             ,
  "T_PACKAGE"        ,
  "T_PLUS"           ,
  "T_RCB"            ,
  "T_RETURN"         ,
  "T_RIGHTSHIFT"     ,
  "T_RPAREN"         ,
  "T_RSB"            ,
  "T_SEMICOLON"      ,
  "T_STRINGCONSTANT" ,
  "T_STRINGTYPE"     ,
  "T_TRUE"           ,
  "T_VAR"            ,
  "T_VOID"           ,
  "T_WHILE"          ,
  "T_WHITESPACE"     ,
  "T_WHITESPACE \\n"
};

enum node_kind
{
  T_AND            ,
  T_ASSIGN         ,
  T_BOOLTYPE       ,
  T_BREAK          ,
  T_CHARCONSTANT   ,
  T_COMMA          ,
  T_COMMENT        ,
  T_CONTINUE       ,
  T_DIV            ,
  T_DOT            ,
  T_ELSE           ,
  T_EQ             ,
  T_EXTERN         ,
  T_FALSE          ,
  T_FOR            ,
  T_FUNC           ,
  T_GEQ            ,
  T_GT             ,
  T_ID             ,
  T_IF             ,
  T_INTCONSTANT    ,
  T_INTTYPE        ,
  T_LCB            ,
  T_LEFTSHIFT      ,
  T_LEQ            ,
  T_LPAREN         ,
  T_LSB            ,
  T_LT             ,
  T_MINUS          ,
  T_MOD            ,
  T_MULT           ,
  T_NEQ            ,
  T_NOT            ,
  T_NULL           ,
  T_OR             ,
  T_PACKAGE        ,
  T_PLUS           ,
  T_RCB            ,
  T_RETURN         ,
  T_RIGHTSHIFT     ,
  T_RPAREN         ,
  T_RSB            ,
  T_SEMICOLON      ,
  T_STRINGCONSTANT ,
  T_STRINGTYPE     ,
  T_TRUE           ,
  T_VAR            ,
  T_VOID           ,
  T_WHILE          ,
  T_WHITESPACE     ,
  T_WHITESPACE2    
};

%}

all_char     \'([\x20-\x26\x28-\x2e\x30-\x5b\x5d-\x7e]|\\n|\\r|\\t|\\v|\\f|\\a|\\b|\\\\|\\'|\\\")\'
all_str      \"([\x20-\x21\x23-\x2e\x30-\x5b\x5d-\x7e]*(\\n|\\r|\\t|\\v|\\f|\\a|\\b|\\'|\\\"|\\\\)*)+\"

decimal_num  [0-9]+
hex_num      0(x|X)[0-9a-fA-F]+    

normal_id    [a-zA-Z\_][a-zA-Z\_0-9]*

%%
  /*
    Pattern definitions for all tokens
  */

"&&"                       { return T_AND; }
"="                        { return T_ASSIGN; }
"bool"                     { return T_BOOLTYPE; }
"break"                    { return T_BREAK; }
{all_char}                 { return T_CHARCONSTANT; }
{all_str}                  { return T_STRINGCONSTANT; }
","                        { return T_COMMA; }
\/\/(.*?)\n                { return T_COMMENT; }
"continue"                 { return T_CONTINUE; }
"/"                        { return T_DIV; }
"."                        { return T_DOT; }
"else"                     { return T_ELSE; }
"=="                       { return T_EQ; }
"extern"                   { return T_EXTERN; }
"false"                    { return T_FALSE; }
"for"                      { return T_FOR; }
"func"                     { return T_FUNC; }
">="                       { return T_GEQ; }
">"                        { return T_GT; }
"if"                       { return T_IF; }
{decimal_num}|{hex_num}    { return T_INTCONSTANT; }
"int"                      { return T_INTTYPE; }
"{"                        { return T_LCB; }
"<<"                       { return T_LEFTSHIFT; }
"<="                       { return T_LEQ; }
"("                        { return T_LPAREN; }
"["                        { return T_LSB; }
"<"                        { return T_LT; }
"-"                        { return T_MINUS; }
"%"                        { return T_MOD; }
"*"                        { return T_MULT; }
"!="                       { return T_NEQ; }
"!"                        { return T_NOT; }
"null"                     { return T_NULL; }
"||"                       { return T_OR; }
"package"                  { return T_PACKAGE; }
"+"                        { return T_PLUS; }
"}"                        { return T_RCB; }
"return"                   { return T_RETURN; }
">>"                       { return T_RIGHTSHIFT; }
")"                        { return T_RPAREN; }
"]"                        { return T_RSB; }
";"                        { return T_SEMICOLON; }
"string"                   { return T_STRINGTYPE; }
"true"                     { return T_TRUE; }
"var"                      { return T_VAR; }
"void"                     { return T_VOID; }
"while"                    { return T_WHILE; }
[\t\r\a\v\b ]+             { return T_WHITESPACE; }
[\n]+[\t\ ]*               { return T_WHITESPACE2; }
{normal_id}                { return T_ID; }             
.                          { cerr << "Error: unexpected character in input" << endl; return -1; }

%%

int main () {
  int token;
  string line;
  string lexeme;

  ofstream fin;
  fin.open("1");

  while ((token = yylex())) {
    if (token >= 0) {
      lexeme.assign(yytext);
      if(token < sizeof(node_map)/sizeof(char*)){
        if(token == T_WHITESPACE2){
          fin << "T_WHITESPACE ";
          for(auto &c : lexeme){
            if(c == '\n'){
              fin << "\\n";
            }
            else{
              fin << c;
            }
          }
          fin << endl;
        }
        else if(token == T_COMMENT){
          fin << "T_COMMENT ";
          for(auto &c : lexeme){
            if(c == '\n'){
              fin << "\\n";
            }
            else{
              fin << c;
            }
          }
          fin << endl;  
        }
        else{
          fin << node_map[token] << " " << lexeme << endl;
        }
      }
      else{
        cout << 1 << endl;
        exit(EXIT_FAILURE);
      }
    } else {
      cout << 1 << endl;
      exit(EXIT_FAILURE);
    }
  }

  fstream fout("1",ios::in|ios::out);
  while(getline(fout,line)){
    cout << line << endl;
  }

  exit(EXIT_SUCCESS);
}

实验结果：

1
2
3
Correct(dev): 59 / 59
Score(dev): 59.00
Total Score: 59.00