Liping Zou bio photo

Liping Zou

An Android Developer

Email Twitter Instagram Github

Overview

词法分析器的功能是输入源程序,输出单词符号。当初定义Token(单词种别,属性值)序列的时候,是将单词种别用数字来表示,后来再做语法分析的时候,发现用数字时不太合理的,所以又对单词的种别码进行了一番修改。

我的程序的总体思路是先对源程序进行一遍扫描,将多余的空格和注释去除,然后再读一遍已经进行过预处理的源程序,进行单词的识别,转换成二元组,保存到token文件中,并建立符号表对标识符进行管理,如果发现了错误,对其的位置和错误信息进行打印。

在对单词的识别部分,我采用了有穷自动机的理论来进行识别。这样就可以根据现在的状态和输入符号决定其后继行为。因此在对单词的识别中,我画了很多的状态图来识别不同的单词,如字符串、数字等等。状态图的绘制中,本来想用visio来画的,后来的后来觉得太麻烦了,还是用了最快的手画的方法。

image

image

image

image

image

image

关于错误处理的方面,我对于词法分析阶段所能遇到的几种错误,如下图所示中的四种中的前三种都进行了相应的处理。但是对于第三点做的不太好,对字符常数中可以出现的字符限制的有点过于厉害,例如分号等在我的词法分析器中是不能再字符串中出现的。

测试程序如下,内包含主要的C语言的各种语句,含有少量的错误:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    int _a;
         char ch = 'f;
    floatb,centigrade,fahrj@enheit;
         char fd = '\n';
 
    printf("please inputa);
   scanf("%d",&a); /*mycomment1or***2*/
    printf("please inputb");
   scanf("%f",&b);
    if (a==8.1.6)
    {
       centigrade=095*(b-32)/9; /*itismyc5435omment*/
        printf("TheCentigrade is ",centigrade);  /*mess/age*/
    }
    else if (a!=0)
    {
       fahrenheit=(9/5.0)*b++32; /*mycontent*/
        printf("TheFahrenheit is fahrenheit);   /*hello****/
    }
    return 0;
}

运行结果如下图所示:

image

这是用Python写的第一个稍微像点样的东西,所以很多地方写的不大好,代码结构也是有点混乱。总而言之,就是在这样的条件下把编译原理的第一次实验给写完了。接下来是我的水水的代码了。

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
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
# -*- coding: utf-8 -*- 
'''
Created on 2012-10-18

@author: zouliping
'''
import string

_key = ("auto","break","case","char","const","continue","default",

"do","double","else","enum","extern","float","for",

"goto","if","int","long","register","return","short",

"signed","static","sizeof","struct","switch","typedef","union",

"unsigned","void","volatile","while")  # c语言的32个关键字

_abnormalChar = '@#$%^&*~' #标识符中可能出现的非法字符

_syn = ''  #单词的种别码
_p = 0  #下标
_value = ''  #存放词法分析出的单词
_content = '' #程序内容
_mstate = 0 #字符串的状态
_cstate = 0 #字符的状态
_dstate = 0 #整数和浮点数的状态
_line = 1 #代码的第几行
_mysymbol = [] #符号表

def outOfComment():
    '''去除代码中的注释'''
    global _content
    state = 0
    index = -1
    
    for c in _content:
        index = index + 1
        
        if state == 0:
            if c == '/':
                state = 1
                startIndex = index
            
        elif state == 1:
            if c == '*':
                state = 2
            else:
                state = 0
                
        elif state == 2:
            if c == '*':
                state = 3
            else:
                pass
            
        elif state == 3:
            if c == '/':
                endIndex = index + 1
                comment = _content[startIndex:endIndex]
                _content = _content.replace(comment,'') #将注释替换为空,并且将下标移动
                index = startIndex - 1
                state = 0
                
            elif c == '*':
                pass
            else:
                state = 2
                
def getMyProm():
    '''从文件中获取代码片段'''
    global _content
    myPro = open(r'E://test.txt','r')

    for line in myPro:
        if line != '\n':
            _content = "%s%s" %(_content,line.lstrip()) #效率更高的字符串拼接方法
        else:
            _content = "%s%s" %(_content,line)
    myPro.close()

def analysis(mystr):
    '''分析目标代码,生成token'''
    global _p,_value,_syn,_mstate,_dstate,_line,_cstate
    
    _value = ''
    ch = mystr[_p]
    _p += 1
    while ch == ' ':
        ch = mystr[_p]
        _p += 1
    if ch in string.letters or ch == '_':    ###############letter(letter|digit)*
        while ch in string.letters or ch in string.digits or ch == '_' or ch in _abnormalChar:
            _value += ch
            ch = mystr[_p]
            _p += 1
        _p -= 1
        
        for abnormal in _abnormalChar:
            if abnormal in _value:
                _syn = '@-6' #错误代码,标识符中含有非法字符
                break
            else:
                _syn = 'ID'
        
        for s in _key:
            if cmp(s,_value) == 0:
                _syn = _value.upper()               #############关键字
                break
        if _syn == 'ID':
            inSymbolTable(_value)
            
    elif ch == '\"':                        #############字符串
        while ch in string.letters or ch in '\"% ' :
            _value += ch
            if _mstate == 0:
                if ch == '\"':
                    _mstate = 1
            elif _mstate == 1:
                if ch == '\"':
                    _mstate = 2

            ch = mystr[_p]
            _p += 1
            
        if _mstate == 1:
            _syn = '@-2'     #错误代码,字符串不封闭
            _mstate = 0
            
        elif _mstate == 2:
            _mstate = 0
            _syn = 'STRING'
            
        _p -= 1    
        
    elif ch in string.digits:
        while ch in string.digits or ch == '.' or ch in string.letters:
            _value += ch
            if _dstate == 0:
                if ch == '0':
                    _dstate = 1
                else:
                    _dstate = 2
                    
            elif _dstate == 1:
                if ch == '.':
                    _dstate = 3
                else:
                    _dstate = 5
                    
            elif _dstate == 2:
                if ch == '.':
                    _dstate = 3
                
            ch = mystr[_p]
            _p += 1
        
        for char in string.letters:
            if char in _value:
                _syn = '@-7' #错误代码,数字和字母混合,如12AB56等
                _dstate = 0
                
                
        if _syn != '@-7':
            if _dstate == 5:
                _syn = '@-3' #错误代码,数字以0开头
                _dstate = 0
            else:    
                _dstate = 0
                if '.' not in _value:
                    _syn = 'DIGIT'               ##################digit digit*
                else:
                    if _value.count('.') == 1:
                        _syn = 'FRACTION'           ################## 浮点数    
                    else:
                        _syn = '@-5' #错误代码,浮点数中包含多个点,如1.2.3                
        _p -= 1
            
                
    elif ch == '\'':                    ################## 字符
        while ch in string.letters or ch in '@#$%&*\\\'\"':
            _value += ch
            if _cstate == 0:
                if ch == '\'':
                    _cstate = 1
                    
            elif _cstate == 1:
                if ch == '\\':
                    _cstate = 2
                elif ch in string.letters or ch in '@#$%&*':
                    _cstate = 3
                    
            elif _cstate == 2:
                if ch in 'nt':
                    _cstate = 3
                    
            elif _cstate == 3:
                if ch == '\'':
                    _cstate = 4
            ch = mystr[_p]
            _p += 1
        
        _p -= 1
        if _cstate == 4:
            _syn = 'CHARACTER'
            _cstate = 0
        else:
            _syn = '@-4'   #错误代码,字符不封闭
            _cstate = 0
                    
    elif ch == '<': 
        _value = ch
        ch = mystr[_p]
        
        if ch == '=':           ###########  '<='
            _value += ch
            _p += 1
            _syn = '<='
        else:                   ###########  '<'
            _syn = '<'
        
    elif ch == '>': 
        _value = ch
        ch = mystr[_p]
        
        if ch == '=':           ########### '>='
            _value += ch
            _p += 1
            _syn = '>='
        else:                   ########## '>'
            _syn = '>'
            
    elif ch == '!': 
        _value = ch
        ch = mystr[_p]
        
        if ch == '=':           ########## '!='
            _value += ch
            _p += 1
            _syn = '!='
        else:                   ########## '!'
            _syn = '!'
            
        
    elif ch == '+': 
        _value = ch
        ch = mystr[_p]
        
        if ch =='+':            ############ '++'
            _value += ch
            _p += 1
            _syn = '++'
        else :                  ############ '+'
            _syn = '+'
        
    elif ch == '-': 
        _value = ch
        ch = mystr[_p]
        
        if ch =='-':            ########### '--'
            _value += ch
            _p += 1
            _syn = '--'
        else :                  ########### '-'
            _syn = '-'
            
    elif ch == '=':  
        _value = ch
        ch = mystr[_p]
        
        if ch =='=':            ########### '=='
            _value += ch
            _p += 1
            _syn = '=='
        else :                  ########### '='
            _syn = '='
    
    elif ch == '&':
        _value = ch 
        ch = mystr[_p]
        
        if ch == '&':           ########### '&&'
            _value += ch
            _p += 1
            _syn = '&&'
        else:                   ########### '&'
            _syn = '&'
            
    elif ch == '|':
        _value = ch
        ch = mystr[_p]
        
        if ch == '|':           ########## '||'       
            _value += ch
            _p += 1
            _syn = '||'
        else:                   ########## '|'
            _syn = '|'
            
    elif ch == '*':             ########## '*'
        _value = ch
        _syn = '*'
        
    elif ch == '/':             ########## '/'
        _value = ch
        _syn = '/'
        
    elif ch ==';':              ########## ';'
        _value = ch
        _syn = ';'
        
    elif ch == '(':             ##########  '('
        _value = ch
        _syn = '('
        
    elif ch == ')':             ########### ')'
        _value = ch
        _syn = ')'
        
    elif ch == '{':             ########### '{'
        _value = ch
        _syn = '{'
        
    elif ch == '}':             ########### '}'    
        _value = ch
        _syn = '}'       
        
    elif ch == '[':             ########### '['    
        _value = ch
        _syn = '['   
        
    elif ch == ']':             ########### ']'    
        _value = ch
        _syn = ']'  
        
    elif ch == ',':             ########## ','    
        _value = ch
        _syn = ','   
    elif ch == '\n':
        _syn = '@-1'
         
def inSymbolTable(token):
    '''将关键字和标识符存进符号表'''
    global _mysymbol
    if token not in _mysymbol:
        _mysymbol.append(token)

if __name__ == '__main__': 
    getMyProm()
    outOfComment()
    
    symbolTableFile = open(r'E://symbol_table.txt','w')
    tokenFile = open(r'E://token.txt','w')
    while _p != len(_content):
        analysis(_content)
        if _syn == '@-1':
            _line += 1 #记录程序的行数
        elif _syn == '@-2':
            print '字符串 ' + _value + ' 不封闭! Error in line ' + str(_line)
        elif _syn == '@-3':
            print '数字 ' + _value + ' 错误,不能以0开头! Error in line ' + str(_line)
        elif _syn == '@-4':
            print '字符 ' + _value + ' 不封闭! Error in line ' + str(_line)
        elif _syn == '@-5':
            print '数字 ' + _value + ' 不合法! Error in line ' + str(_line)
        elif _syn == '@-6':
            print '标识符' + _value + ' 不能包含非法字符!Error in line ' + str(_line)
        elif _syn == '@-7':
            print '数字 ' + _value + ' 不合法,包含字母! Error in line ' + str(_line)
        else: #若程序中无词法错误的情况
            #print (_syn,_value)
            tokenFile.write(str(_syn)+'@'+_value+'\n')
        
    tokenFile.close()
    symbolTableFile.write('入口地址\t变量名\n')
    i = 0
    for symbolItem in _mysymbol:
        symbolTableFile.write(str(i)+'\t\t\t'+symbolItem+'\n')
        i += 1
    symbolTableFile.close()