我想学习编写parser。

cs900601

输入是源文件，输出…… 还没想好，总之要先parse完才行罢。
词法分析和预处理器是之前某个公开课的作业中留下的，这回就接着用。
所以这里输入已经是带有Token类型的Token流了。

完全不讲运行效率，只是个学习过程。
本来应该在大学就学会的，现在还不会。唉

用的是递归下降语法分析方法。语法是拉瓦语言。也就是LavaX。也就是GVMaker。
没系统地看过书，现在我觉得最后产生的语法树是决策树的子集。不知道这个想法是否正确。
暴力枚举法就是每次将决策树「往前进一格」，然后顺延下去。
但正常的解析不需要枚举整个解空间，而只需要在搜索解空间时尽快地将符合语法规则的结果输出来就好了。

为了学习的目的，就暂且尝试遍历整个解空间。对于下面这段很短的代码就尝试了46000多次（解空间的大小是 K的N次方 ，其中N为Token数。嗯很快就会爆炸。

1. char GGV[] = "Golden Global View";
   
2. int i, j = 2;
   
3. struct FUN_LINK fun;
   
4. void foo() {
   
5.     label1: {}
   
6.     "assignment" = "expression";
   
7.     ;
   
8.     1;
   
9.     "哈哈";
   
10. }

复制代码

最后解析出来的结果是：

1. root
   
2.   translation_unit  (4 children)
   
3.     declaration
   
4.       simple_declaration  (3 children)
   
5.         decl_specifier_seq
   
6.           decl_specifier
   
7.             type_specifier
   
8.               trailing_type_specifier
   
9.                 simple_type_specifier
   
10.                   char
    
11.         init_declarator_list
    
12.           init_declarator  (2 children)
    
13.             declarator
    
14.               ptr_declarator
    
15.                 noptr_declarator  (2 children)
    
16.                   noptr_declarator_root
    
17.                     declarator_id
    
18.                       id_expression
    
19.                         GGV
    
20.                   noptr_declarator_suffix  (2 children)
    
21.                     [
    
22.                     ]
    
23.             initializer
    
24.               brace_or_equal_initializer  (2 children)
    
25.                 =
    
26.                 initializer_clause
    
27.                   assignment_expression
    
28.                     conditional_expression
    
29.                       logical_or_expression
    
30.                         logical_and_expression
    
31.                           inclusive_or_expression
    
32.                             exclusive_or_expression
    
33.                               and_expression
    
34.                                 equality_expression
    
35.                                   relational_expression
    
36.                                     shift_expression
    
37.                                       additive_expression
    
38.                                         multiplicative_expression
    
39.                                           pm_expression
    
40.                                             cast_expression
    
41.                                               unary_expression
    
42.                                                 postfix_expression
    
43.                                                   postfix_root
    
44.                                                     primary_expression
    
45.                                                       "Golden Global View"
    
46.         ;
    
47.     declaration
    
48.       simple_declaration  (3 children)
    
49.         decl_specifier_seq
    
50.           decl_specifier
    
51.             type_specifier
    
52.               trailing_type_specifier
    
53.                 simple_type_specifier
    
54.                   int
    
55.         init_declarator_list  (3 children)
    
56.           init_declarator
    
57.             declarator
    
58.               ptr_declarator
    
59.                 noptr_declarator
    
60.                   noptr_declarator_root
    
61.                     declarator_id
    
62.                       id_expression
    
63.                         i
    
64.           ,
    
65.           init_declarator  (2 children)
    
66.             declarator
    
67.               ptr_declarator
    
68.                 noptr_declarator
    
69.                   noptr_declarator_root
    
70.                     declarator_id
    
71.                       id_expression
    
72.                         j
    
73.             initializer
    
74.               brace_or_equal_initializer  (2 children)
    
75.                 =
    
76.                 initializer_clause
    
77.                   assignment_expression
    
78.                     conditional_expression
    
79.                       logical_or_expression
    
80.                         logical_and_expression
    
81.                           inclusive_or_expression
    
82.                             exclusive_or_expression
    
83.                               and_expression
    
84.                                 equality_expression
    
85.                                   relational_expression
    
86.                                     shift_expression
    
87.                                       additive_expression
    
88.                                         multiplicative_expression
    
89.                                           pm_expression
    
90.                                             cast_expression
    
91.                                               unary_expression
    
92.                                                 postfix_expression
    
93.                                                   postfix_root
    
94.                                                     primary_expression
    
95.                                                       2
    
96.         ;
    
97.     declaration
    
98.       simple_declaration  (3 children)
    
99.         decl_specifier_seq
    
100.           decl_specifier
     
101.             type_specifier
     
102.               trailing_type_specifier
     
103.                 elaborated_type_specifier  (2 children)
     
104.                   class_key
     
105.                     struct
     
106.                   FUN_LINK
     
107.         init_declarator_list
     
108.           init_declarator
     
109.             declarator
     
110.               ptr_declarator
     
111.                 noptr_declarator
     
112.                   noptr_declarator_root
     
113.                     declarator_id
     
114.                       id_expression
     
115.                         fun
     
116.         ;
     
117.     declaration
     
118.       function_definition  (3 children)
     
119.         decl_specifier_seq
     
120.           decl_specifier
     
121.             type_specifier
     
122.               trailing_type_specifier
     
123.                 simple_type_specifier
     
124.                   void
     
125.         declarator
     
126.           ptr_declarator
     
127.             noptr_declarator  (2 children)
     
128.               noptr_declarator_root
     
129.                 declarator_id
     
130.                   id_expression
     
131.                     foo
     
132.               noptr_declarator_suffix
     
133.                 parameters_and_qualifiers  (3 children)
     
134.                   (
     
135. 
     
136. （中间省略，因为有帖子字数限制）
     
137.                                         multiplicative_expression
     
138.                                           pm_expression
     
139.                                             cast_expression
     
140.                                               unary_expression
     
141.                                                 postfix_expression
     
142.                                                   postfix_root
     
143.                                                     primary_expression
     
144.                                                       "哈哈"
     
145.                 ;
     
146.             }

复制代码

还有好多好多地方没做完的，不知道几时能做完了。是件很忧伤的事情

[ 本帖最后由 cs900601 于 2016-9-11 17:00 编辑 ]

dragon_

这代码，猛一看还以为是json。。。

cs900601

嗯，可能是因为括号比较多吧

我刚才把Yan的编译器中的“函数生成器.txt”丢进这个parser了。

预处理器的结果

1. simple void KW_VOID
   
2. emit_simple_directly push void
   
3. identifier FunSeek
   
4. emit_identifier push FunSeek
   
5. simple ( OP_LPAREN
   
6. emit_simple_directly push (
   
7. simple ) OP_RPAREN
   
8. emit_simple_directly push )
   
9. simple { OP_LBRACE
   
10. emit_simple_directly push {
    
11. simple int KW_INT
    
12. emit_simple_directly push int
    
13. identifier i
    
14. emit_identifier push i
    
15. simple , OP_COMMA
    
16. emit_simple_directly push ,
    
17. identifier p
    
18. emit_identifier push p
    
19. simple ; OP_SEMICOLON
    
20. emit_simple_directly push ;
    
21. simple char KW_CHAR
    
22. emit_simple_directly push char
    
23. identifier n
    
24. emit_identifier push n
    
25. simple ; OP_SEMICOLON
    
26. emit_simple_directly push ;
    
27. identifier FunInsert
    
28. emit_identifier push FunInsert
    
29. simple ( OP_LPAREN
    
30. emit_simple_directly push (
    
31. literal "define" array of 7 char 646566696E6500
    
32. simple , OP_COMMA
    
33. emit_simple_directly push ,
    
34. literal 0 int 00000000
    
35. simple | OP_BOR
    
36. emit_simple_directly push |
    
37. identifier SK_BLANK
    
38. emit_identifier push SK_BLANK
    
39. simple << OP_LSHIFT
    
40. emit_simple_directly push <<
    
41. literal 4 int 04000000
    
42. simple ) OP_RPAREN
    
43. emit_simple_directly push )
    
44. simple ; OP_SEMICOLON
    
45. emit_simple_directly push ;
    
46. identifier FunInsert
    
47. emit_identifier push FunInsert
    
48. simple ( OP_LPAREN
    
49. emit_simple_directly push (
    
50. literal "include" array of 8 char 696E636C75646500
    
51. simple , OP_COMMA
    
52. emit_simple_directly push ,
    
53. literal 0 int 00000000
    
54. simple | OP_BOR
    
55. emit_simple_directly push |
    
56. identifier SK_BAO
    
57. emit_identifier push SK_BAO
    
58. simple << OP_LSHIFT
    
59. emit_simple_directly push <<
    
60. literal 4 int 04000000
    
61. simple ) OP_RPAREN
    
62. emit_simple_directly push )
    
63. simple ; OP_SEMICOLON
    
64. emit_simple_directly push ;
    
65. identifier FunInsert
    
66. emit_identifier push FunInsert
    
67. simple ( OP_LPAREN
    
68. emit_simple_directly push (
    
69. literal "undef" array of 6 char 756E64656600
    
70. simple , OP_COMMA
    
71. emit_simple_directly push ,
    
72. literal 0 int 00000000
    
73. simple | OP_BOR
    
74. emit_simple_directly push |
    
75. identifier SK_BLANK
    
76. emit_identifier push SK_BLANK
    
77. simple << OP_LSHIFT
    
78. emit_simple_directly push <<
    
79. literal 4 int 04000000
    
80. simple ) OP_RPAREN
    
81. emit_simple_directly push )
    
82. simple ; OP_SEMICOLON
    
83. emit_simple_directly push ;
    
84. identifier FunInsert
    
85. emit_identifier push FunInsert
    
86. simple ( OP_LPAREN
    
87. emit_simple_directly push (
    
88. literal "ifdef" array of 6 char 696664656600
    
89. simple , OP_COMMA
    
90. emit_simple_directly push ,
    
91. literal 0 int 00000000
    
92. simple | OP_BOR
    
93. emit_simple_directly push |
    
94. identifier SK_BLANK
    
95. emit_identifier push SK_BLANK
    
96. simple << OP_LSHIFT
    
97. emit_simple_directly push <<
    
98. literal 4 int 04000000
    
99. simple ) OP_RPAREN
    
100. emit_simple_directly push )
     
101. simple ; OP_SEMICOLON
     
102. emit_simple_directly push ;
     
103. identifier FunInsert
     
104. emit_identifier push FunInsert
     
105. simple ( OP_LPAREN
     
106. emit_simple_directly push (
     
107. literal "ifndef" array of 7 char 69666E64656600
     
108. simple , OP_COMMA
     
109. emit_simple_directly push ,
     
110. literal 0 int 00000000
     
111. simple | OP_BOR
     
112. emit_simple_directly push |
     
113. identifier SK_BLANK
     
114. emit_identifier push SK_BLANK
     
115. simple << OP_LSHIFT
     
116. emit_simple_directly push <<
     
117. literal 4 int 04000000
     
118. simple ) OP_RPAREN
     
119. emit_simple_directly push )
     
120. simple ; OP_SEMICOLON
     
121. emit_simple_directly push ;
     
122. identifier FunInsert
     
123. emit_identifier push FunInsert
     
124. simple ( OP_LPAREN
     
125. emit_simple_directly push (
     
126. literal "endif" array of 6 char 656E64696600
     
127. simple , OP_COMMA
     
128. emit_simple_directly push ,
     
129. literal 0 int 00000000
     
130. simple ) OP_RPAREN
     
131. emit_simple_directly push )
     
132. simple ; OP_SEMICOLON
     
133. emit_simple_directly push ;
     
134. identifier FunInsert
     
135. emit_identifier push FunInsert
     
136. simple ( OP_LPAREN
     
137. 
     
138. （因为长度限制略去）
     
139. 
     
140. emit_simple_directly push }
     
141. simple } OP_RBRACE
     
142. emit_simple_directly push }
     
143. eof
     
144. We have 589 tokens.
     
145. 0: void
     
146. 1: FunSeek
     
147. 2: (
     
148. 3: )
     
149. 4: {
     
150. 5: int
     
151. 6: i
     
152. 7: ,
     
153. 8: p
     
154. 9: ;
     
155. 10: char
     
156. 11: n
     
157. 12: ;
     
158. 13: FunInsert
     
159. 14: (
     
160. 15: "define"
     
161. 16: ,
     
162. 17: 0
     
163. 18: |
     
164. 19: SK_BLANK
     
165. 20: <<
     
166. 21: 4
     
167. 22: )
     
168. 23: ;
     
169. 24: FunInsert
     
170. 25: (
     
171. 26: "include"
     
172. 27: ,
     
173. 28: 0
     
174. 29: |
     
175. 30: SK_BAO
     
176. 31: <<
     
177. 32: 4
     
178. 33: )
     
179. 34: ;
     
180. 35: FunInsert
     
181. 36: (
     
182. 37: "undef"
     
183. 38: ,
     
184. 39: 0
     
185. 40: |
     
186. 41: SK_BLANK
     
187. 42: <<
     
188. 43: 4
     
189. 44: )
     
190. 45: ;
     
191. 46: FunInsert
     
192. 47: (
     
193. 48: "ifdef"
     
194. 49: ,
     
195. 50: 0
     
196. 51: |
     
197. 52: SK_BLANK
     
198. 53: <<
     
199. 54: 4
     
200. 55: )
     
201. 56: ;
     
202. 57: FunInsert
     
203. 58: (
     
204. 59: "ifndef"
     
205. 60: ,
     
206. 61: 0
     
207. 62: |
     
208. 63: SK_BLANK
     
209. 64: <<
     
210. 65: 4
     
211. 66: )
     
212. 67: ;
     
213. 68: FunInsert
     
214. 69: (
     
215. 70: "endif"
     
216. 71: ,
     
217. 72: 0
     
218. 73: )
     
219. 74: ;
     
220. 75: FunInsert
     
221. 76: (
     
222. 77: "loadall"
     
223. 78: ,
     
224. 79: 0
     
225. 80: |
     
226. 81: SK_CR
     
227. 82: <<
     
228. 83: 4
     
229. 84: )
     
230. 85: ;
     
231. 86: FunInsert
     
232. 87: (
     
233. 88: "secret"
     
234. 89: ,
     
235. 90: 0
     
236. 91: |
     
237. 92: SK_BLANK
     
238. 93: <<
     
239. 94: 4
     
240. 95: )
     
241. 96: ;
     
242. 97: FunInsert
     
243. 98: (
     
244. 99: "code"
     
245. 100: ,
     
246. 101: 0
     
247. 102: |
     
248. 103: SK_NULL
     
249. 104: <<
     
250. 105: 4
     
251. 106: )
     
252. 107: ;
     
253. 108: FunInsert
     
254. 109: (
     
255. 110: "loaddata"
     
256. 111: ,
     
257. 112: 0
     
258. 113: |
     
259. 114: SK_BLANK
     
260. 115: <<
     
261. 116: 4
     
262. 117: )
     
263. 118: ;
     
264. 119: FunInsert
     
265. 120: (
     
266. 121: "begin"
     
267. 122: ,
     
268. 123: 0
     
269. 124: |
     
270. 125: SK_BLANK
     
271. 126: <<
     
272. 127: 4
     
273. 128: )
     
274. 129: ;
     
275. 130: FunInsert
     
276. 131: (
     
277. 132: "end"
     
278. 133: ,
     
279. 134: 0
     
280. 135: |
     
281. 136: SK_CR
     
282. 137: <<
     
283. 138: 4
     
284. 
     
285. （因为长度限制略去）
     
286. 
     
287. 571: )
     
288. 572: n
     
289. 573: =
     
290. 574: 1
     
291. 575: ;
     
292. 576: FunInsert
     
293. 577: (
     
294. 578: p
     
295. 579: ,
     
296. 580: n
     
297. 581: |
     
298. 582: SK_FUN
     
299. 583: <<
     
300. 584: 4
     
301. 585: )
     
302. 586: ;
     
303. 587: }
     
304. 588: }

复制代码

[ 本帖最后由 cs900601 于 2016-9-11 00:01 编辑 ]

cs900601

修理了一些语法分析和词法分析的错误，现在用19秒可以解析完 Yan 的编译器的 “编译器.txt”。这个文件有一些 #include 命令，结果就是它总共包含了81000多个 tokens。


螢幕快照_2016-09-12_19-51-21.jpeg (27.32 KB, 下载次数: 577)

2016-9-13 08:55 上传

点击文件名下载附件

[ 本帖最后由 cs900601 于 2016-9-13 11:16 编辑 ]