語義分析較困難的根本原因在於語法的可遞歸性，深層次的遞歸使得問題的分解看起來變得相當地復雜。但是如果能將遞歸問題轉化為迭代問題，便能很大程度地簡化此問題模型。遞歸轉化為迭代的關鍵在於——找到最深層遞歸結構的全部特征，迭代化之，問題便迎刃而解。
一般情況下，人們在面對復雜的遞歸問題時時，亦是依據其語法規則，找到其遞歸深層的結構，化解之，步步迭代，如此，問題便得到解決。人類的思維很是擅長將遞歸問題轉化為迭代問題，而學習知識的過程，則可以看成是對各種各樣語法規則的理解與掌握。
一元操作符、二元操作符的遞歸問題，可以很簡單的轉化為迭代，多元操作符的情況稍復雜些。
所有的操作符及其優先級如下圖：
如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
>>>
復制代碼
