語義分析較困難的根本原因在於語法的可遞歸性，深層次的遞歸使得問題的分解看起來變得相當地復雜。但是如果能將遞歸問題轉化為迭代問題，便能很大程度地簡化此問題模型。遞歸轉化為迭代的關鍵在於——找到最深層遞歸結構的全部特征，迭代化之，問題便迎刃而解。 一般情況下，人們在面對復雜的遞歸問題時時，亦是依據其語法規則，找到其遞歸深層的結構，化解之，步步迭代，如此，問題便得到解決。人類的思維很是擅長將遞歸問題轉化為迭代問題，而學習知識的過程，則可以看成是對各種各樣語法規則的理解與掌握。 一元操作符、二元操作符的遞歸問題，可以很簡單的轉化為迭代，多元操作符的情況稍復雜些。 所有的操作符及其優先級如下圖： 如typeof、取地址、指針指向等，在這裡並未實現。實現的包括有算數運算式、邏輯運算式、函數調用與括號。對於理解語義分析的過程，已足夠。 對於不包含括號與函數的簡單表達式，我們語義分析演算過程如下： 我們的數據結構： 復制代碼 1 ''' 2 ____________________________ Syntax Tree 3 Parenthesis: 4 ["(",None] 5 [")",None] 6 Operators(grouped by precedence): 7 Unary : 8 1 + - ! ~ ["+",None] ["-",None] ["!",None] ["~",None] 9 Binary : 10 2 * / % ["*",None] ["/",None] ["%",None] 11 3 + - ["+",None] ["-",None] 12 4 << >> ["<<",None] [">>",None] 13 5 > >= < <= [">",None] [">=",None] ["<",None] ["<=",None] 14 6 == != ["==",None] ["!=",None] 15 7 & ["&",None] 16 8 ^ ["^",None] 17 9 | ["|",None] 18 10 && ["&&",None] 19 11 || ["||",None] 20 Ternary : 21 12 expr ? expr : expr ["?",None] [":",None] ["@expr","?:",listPtr0,listPtr1,listPtr2] 22 13 expr , expr , expr... 23 Var,Num,Expr,Function: 24 ["@var","varName"] 25 ["@num","num_string"] 26 ["@expr","Operator",listPtr,...] 27 ["@func","funcName",listPtr1,...] 28 ["@expr_list",["@var"|"@num"|"@expr"|"@func",...],...] 29 ''' 復制代碼 這是我們最終的代碼模塊圖： 其中形如 module_x_y 的函數，x表示此運算符的優先級，y表示橫向序號，從零開始。代碼注釋已經寫得很詳細了，請看源代碼： View Code 上面的代碼雖然很大，卻是最簡單的一部分了，其實可以采取一些方法顯著地壓縮代碼量，但是時間有限。 下面給出一元運算符、二元運算符、三元運算符及逗號分隔符的語義分析過程，這是本文的核心代碼之一： 復制代碼 1 ######################################## global list 2 # construct a module dictionary 3 # module_dic_tuple[priority]['Operator'](lis,i) 4 module_dic_tuple=({}, { '+':module_1_0,'-':module_1_1,'!':module_1_2,'~':module_1_3 },\ 5 { '*':module_2_0,'/':module_2_1,'%':module_2_2 }, \ 6 { '+':module_3_0,'-':module_3_1 },\ 7 { '<<':module_4_0,'>>':module_4_1 },\ 8 { '>':module_5_0,'>=':module_5_1,'<':module_5_2,'<=':module_5_3 },\ 9 { '==':module_6_0,'!=':module_6_1 },\ 10 { '&':module_7_0 },\ 11 { '^':module_8_0 },\ 12 { '|':module_9_0 },\ 13 { '&&':module_10_0 },\ 14 { '||':module_11_0 },\ 15 { '?:':module_12_0 },\ 16 { ',':module_13_0 } ) 17 18 operator_priority_tuple=( () , ('+', '-', '!', '~') , ('*','/','%'),\ 19 ('+','-'),('<<','>>'),\ 20 ('>','>=','<','<='),('==','!='),\ 21 ('&'),('^'),('|'),('&&'),('||'),('?',':'),(',') ) 22 23 ############################# parse:unary,binary,ternary,comma expr 24 ########### return value : 25 ############# 0 parsed sucessfully 26 ############# 1 syntax error 27 def parse_simple_expr(lis): 28 if len(lis)==0: 29 return 1 30 #if lis[len(lis)-1][0][0]!='@': 31 # return 1 32 #if lis[0][0][0]!='@' and lis[0][0] not in ('+','-','!','~'): 33 # return 1 34 for pri in range(1,12): # pri 1,2,3,4,5,6,7,8,9,10,11 35 i=0 36 while 1: 37 if len(lis)==1 and lis[0][0][0]=='@': 38 return 0 39 if i>=len(lis): 40 break 41 if lis[i][0] in operator_priority_tuple[pri]: 42 if module_dic_tuple[pri][lis[i][0]](lis,i)==0: 43 i=0 44 continue 45 else: 46 i=i+1 47 continue 48 else: 49 i=i+1 50 for pri in range(12,13): # pri 12 # parse ...A?A:A... 51 i=0 52 while 1: 53 if len(lis)==1 and lis[0][0][0]=='@': 54 return 0 55 if i>=len(lis): 56 break 57 if lis[i][0]==':': 58 if module_dic_tuple[pri]['?:'](lis,i)==0: 59 i=0 60 continue 61 else: 62 i=i+1 63 continue 64 else: 65 i=i+1 66 return module_dic_tuple[13][','](lis,0) 67 return 1 復制代碼 上面代碼中，使用了函數引用的詞典鏈表來簡化此部分的代碼數量。 這一部分就不進行驗證展示了，具體過程與前面的文章《一個簡單的語義分析算法：單步算法——Python實現》中的描述類似。 實現了 parse_simple_expr 功能之後，剩下的函數與括號的語義分析變得簡單些，演算過程如下： 代碼實現： 復制代碼 1 ########### return value :[intStatusCode,indexOf'(',indexOf')'] 2 ############# intStatusCode 3 ############# 0 sucessfully 4 ############# 1 no parenthesis matched 5 ############# 2 list is null :( 6 def module_parenthesis_place(lis): 7 length=len(lis) 8 err=0 9 x=0 10 y=0 11 if length==0: 12 return [2,None,None] 13 try: 14 x=lis.index([")",None]) 15 except: 16 err=1 17 lis.reverse() 18 try: 19 y=lis.index(["(",None],length-x-1) 20 except: 21 err=1 22 lis.reverse() 23 y=length-y-1 24 if err==1: 25 return [1,None,None] 26 else: 27 return [0,y,x] 28 29 30 ############################# parse:unary binary ternary prenthesis function expr 31 ########### return value : 32 ############# 0 parsed sucessfully 33 ############# 1 syntax error 34 ############################# find first ')' 35 def parse_comp_expr(lis): 36 while 1: 37 if len(lis)==0: 38 return 1 39 if len(lis)==1: 40 if lis[0][0][0]=='@': 41 return 0 42 else: 43 return 1 44 place=module_parenthesis_place(lis) 45 if place[0]==0: 46 mirror=lis[(place[1]+1):place[2]] 47 if parse_simple_expr(mirror)==0: 48 if place[1]>=1 and lis[place[1]-1][0]=='@var': 49 '''func''' 50 funcName=lis[place[1]-1][1] 51 del lis[place[1]-1:(place[2]+1)] 52 lis.insert(place[1]-1,["@func",funcName,mirror[0]]) 53 else: 54 del lis[place[1]:(place[2]+1)] 55 lis.insert(place[1],mirror[0]) 56 else: 57 return 1 58 else: 59 return parse_simple_expr(lis) 60 return 1 復制代碼 如此，代碼到此結束。 下面給出實驗結果： 復制代碼 >>> ls=[['(',None],['@var','f'],['(',None],['@num','1'],[',',None],['@num','2'],[',',None],['@num','3'],[',',None],['!',None],['-',None],['@var','x'],['?',None],['@var','y'],[':',None],['~',None],['@var','z'],[')',None],['-',None],['@num','3'],[')',None],['/',None],['@num','4']] >>> ls [['(', None], ['@var', 'f'], ['(', None], ['@num', '1'], [',', None], ['@num', '2'], [',', None], ['@num', '3'], [',', None], ['!', None], ['-', None], ['@var', 'x'], ['?', None], ['@var', 'y'], [':', None], ['~', None], ['@var', 'z'], [')', None], ['-', None], ['@num', '3'], [')', None], ['/', None], ['@num', '4']] >>> len(ls) 23 >>> parse_comp_expr(ls);ls 0 [['@expr', '/', ['@expr', '-', ['@func', 'f', ['@expr_list', ['@num', '1'], ['@num', '2'], ['@num', '3'], ['@expr', '?:', ['@expr', '!', ['@expr', '-', ['@var', 'x']]], ['@var', 'y'], ['@expr', '~', ['@var', 'z']]]]], ['@num', '3']], ['@num', '4']]] >>> len(ls) 1 >>> 復制代碼
