-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathREADME.zh.html
More file actions
360 lines (359 loc) · 116 KB
/
Copy pathREADME.zh.html
File metadata and controls
360 lines (359 loc) · 116 KB
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
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<meta name="generator" content="VuePress 2.0.0-rc.14">
<script>
(function() {
const userMode = localStorage.getItem('vuepress-reco-color-scheme') || 'auto';
const systemDarkMode = window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches;
if (userMode === 'dark' || (userMode === 'auto' && systemDarkMode)) {
document.documentElement.classList.toggle('dark', true);
}
})();
</script>
<title>SysY 编译器 | Yunge Hu 's Blog</title><meta name="description" content="Just playing around">
<link rel="preload" href="/assets/style-DFiSfBVn.css" as="style"><link rel="stylesheet" href="/assets/style-DFiSfBVn.css">
<link rel="modulepreload" href="/assets/app-B51tXhJU.js"><link rel="modulepreload" href="/assets/README.zh.html-C95KaJWV.js"><link rel="modulepreload" href="/assets/SymbolTableTree-BQyaxW6o.js">
<link rel="prefetch" href="/assets/timeline.html-CDRCyYXN.js" as="script"><link rel="prefetch" href="/assets/posts.html-Cm3Bj9S1.js" as="script"><link rel="prefetch" href="/assets/friendship-link.html-CPYWbDf2.js" as="script"><link rel="prefetch" href="/assets/1.html-BvGA5exa.js" as="script"><link rel="prefetch" href="/assets/1.html-CQiPtbSY.js" as="script"><link rel="prefetch" href="/assets/1.html-B91OJGi4.js" as="script"><link rel="prefetch" href="/assets/1.html-Tfqc0eqa.js" as="script"><link rel="prefetch" href="/assets/1.html-DkR1aWCw.js" as="script"><link rel="prefetch" href="/assets/1.html-9JnLqyKk.js" as="script"><link rel="prefetch" href="/assets/2.html-Bgp2cdo4.js" as="script"><link rel="prefetch" href="/assets/3.html-BrEt4hPg.js" as="script"><link rel="prefetch" href="/assets/index.html-BKyJy_kV.js" as="script"><link rel="prefetch" href="/assets/Install-Neo4j-in-Ubuntu-and-Use-Gremlin.html-D3zJqoKu.js" as="script"><link rel="prefetch" href="/assets/Neo4j.html-RU17f5ie.js" as="script"><link rel="prefetch" href="/assets/index.html-DTD_Tf27.js" as="script"><link rel="prefetch" href="/assets/Javajibenchengxushejijiegou.html-Cop84p5k.js" as="script"><link rel="prefetch" href="/assets/Javamianxiangduixiangchengxusheji——duixiangyulei.html-RHrWrJ8D.js" as="script"><link rel="prefetch" href="/assets/Javamianxiangduixiangchengxusheji——jiekou、lambdabiaodashiyunabulei.html-B4BIhUeh.js" as="script"><link rel="prefetch" href="/assets/Javamianxiangduixiangchengxusheji——jicheng.html-CDNHmPwq.js" as="script"><link rel="prefetch" href="/assets/bingfa.html-BObwH6f-.js" as="script"><link rel="prefetch" href="/assets/yichangduanyanherizhi.html-Bw2Q646T.js" as="script"><link rel="prefetch" href="/assets/fanxingyujihe.html-ChyCepcN.js" as="script"><link rel="prefetch" href="/assets/index.html-B_tI2L4g.js" as="script"><link rel="prefetch" href="/assets/suoyincaozuo.html-M9SgPFiv.js" as="script"><link rel="prefetch" href="/assets/lab0.html-DQt1B-xd.js" as="script"><link rel="prefetch" href="/assets/lab1.html-Dvm30kLN.js" as="script"><link rel="prefetch" href="/assets/lab2.html-gAWXyUFt.js" as="script"><link rel="prefetch" href="/assets/lab3.html-LQVGolsr.js" as="script"><link rel="prefetch" href="/assets/lab4.html-CF_2B461.js" as="script"><link rel="prefetch" href="/assets/lab5.html-2WxLf5I9.js" as="script"><link rel="prefetch" href="/assets/lab6.html-ueb45YH9.js" as="script"><link rel="prefetch" href="/assets/index.html-CjBzVZj0.js" as="script"><link rel="prefetch" href="/assets/404.html-Dk0UZDtj.js" as="script"><link rel="prefetch" href="/assets/Valine.min-Dm4Ijz6H.js" as="script"><link rel="prefetch" href="/assets/giscus-2a044aea-CdPDkb7_.js" as="script">
</head>
<body>
<div id="app"><!--[--><div class="theme-container series--no show-catalog"><header class="navbar-container not-open"><div class="navbar-inner"><div class="site-brand nav-item"><img class="logo" src="/logo.png" alt="Yunge Hu 's Blog"><a href="/" class="site-name can-hide">Yunge Hu 's Blog</a></div><div class="nav-item navbar-links-wrapper" style=""><div><form class="search-box" role="search"><input type="search" autocomplete="off" spellcheck="false" value><!----></form></div><nav class="navbar-links"><!--[--><div class="navbar-links__item"><a href="/" class="link router-link-active" aria-label="Home"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->Home<!--]--></span></span><!--[--><!--]--></a></div><div class="navbar-links__item"><a class="link" href="https://github.com/gitDebuger/gitdebuger.github.io" target="_blank" rel="noopener noreferrer" aria-label="GitHub"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->GitHub<!--]--></span></span><span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!--[--><!--]--></a></div><!--]--></nav><span class="xicon-container btn-toggle-dark-mode btn--dark-mode"><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 32 32" style="width:20px;height:20px;font-size:20px;color:inherit;"><path d="M15 2h2v3h-2z" fill="currentColor"></path><path d="M27 15h3v2h-3z" fill="currentColor"></path><path d="M15 27h2v3h-2z" fill="currentColor"></path><path d="M2 15h3v2H2z" fill="currentColor"></path><path d="M5.45 6.884l1.414-1.415l2.121 2.122l-1.414 1.414z" fill="currentColor"></path><path d="M23 7.58l2.121-2.12l1.414 1.414l-2.121 2.121z" fill="currentColor"></path><path d="M23.002 24.416l1.415-1.414l2.12 2.122l-1.413 1.414z" fill="currentColor"></path><path d="M5.47 25.13L7.59 23L9 24.42l-2.12 2.12l-1.41-1.41z" fill="currentColor"></path><path d="M16 8a8 8 0 1 0 8 8a8 8 0 0 0-8-8zm0 14a6 6 0 0 1 0-12z" fill="currentColor"></path></svg></span><span class="xicon-container btn-toggle-menus"><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 32 32" style="width:20px;height:20px;font-size:20px;color:inherit;"><circle cx="16" cy="8" r="2" fill="currentColor"></circle><circle cx="16" cy="16" r="2" fill="currentColor"></circle><circle cx="16" cy="24" r="2" fill="currentColor"></circle></svg></span></div></div></header><!----><!----><!----><!--[--><main class="page-container"><aside class="series-container"><!--[--><!--]--></aside><div class="page-content"><h1 class="page-title">SysY 编译器</h1><div class="page-info"><span class="xicon-container left"><!--[--><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 32 32" class="xicon-icon" style="width:18px;height:18px;font-size:18px;color:inherit;"><path d="M16 4a5 5 0 1 1-5 5a5 5 0 0 1 5-5m0-2a7 7 0 1 0 7 7a7 7 0 0 0-7-7z" fill="currentColor"></path><path d="M26 30h-2v-5a5 5 0 0 0-5-5h-6a5 5 0 0 0-5 5v5H6v-5a7 7 0 0 1 7-7h6a7 7 0 0 1 7 7z" fill="currentColor"></path></svg><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->Yunge Hu<!--]--></span></span><!----><span class="xicon-container left"><!--[--><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 32 32" class="xicon-icon" style="width:18px;height:18px;font-size:18px;color:inherit;"><path d="M11.17 6l3.42 3.41l.58.59H28v16H4V6h7.17m0-2H4a2 2 0 0 0-2 2v20a2 2 0 0 0 2 2h24a2 2 0 0 0 2-2V10a2 2 0 0 0-2-2H16l-3.41-3.41A2 2 0 0 0 11.17 4z" fill="currentColor"></path></svg><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[--><!--[--><a href="/categories/Compiler/1.html" class="">Compiler</a><!--]--><!--]--></span></span><!----><!----></div><div class="theme-reco-md-content"><div><h1 id="sysy-编译器" tabindex="-1"><a class="header-anchor" href="#sysy-编译器"><span>SysY 编译器</span></a></h1><h2 id="_1-项目概述" tabindex="-1"><a class="header-anchor" href="#_1-项目概述"><span>1. 项目概述</span></a></h2><h3 id="_1-1-这是什么项目" tabindex="-1"><a class="header-anchor" href="#_1-1-这是什么项目"><span>1.1 这是什么项目？</span></a></h3><p>北京航空航天大学的《编译技术》课程实验要求设计并编写一个编译器，该项目即对该编译器的设计开发。</p><h3 id="_1-2-需要翻译什么语言" tabindex="-1"><a class="header-anchor" href="#_1-2-需要翻译什么语言"><span>1.2 需要翻译什么语言？</span></a></h3><p>该编译器可以将 <em><strong>SysY</strong></em> 语言 ( C 语言的子集 ) 编写的代码翻译成<em><strong>中间代码</strong></em>或<em><strong>目标代码</strong></em>。</p><h3 id="_1-3-源代码将被翻译成什么语言" tabindex="-1"><a class="header-anchor" href="#_1-3-源代码将被翻译成什么语言"><span>1.3 源代码将被翻译成什么语言？</span></a></h3><p>源代码需要翻译成<em><strong>中间代码 ( LLVM IR Code 或 P-code )</strong></em> 或<em><strong>目标代码 ( MIPS )</strong></em> 。</p><h2 id="_2-参考编译器介绍" tabindex="-1"><a class="header-anchor" href="#_2-参考编译器介绍"><span>2. 参考编译器介绍</span></a></h2><p>课程组提供了两个编译器 ( Pascal-Compiler 和 Pl0-Compiler ) 以供参考，我们需要阅读分析其源代码，然后在此基础上完成我们自己的编译器的整体架构设计。</p><p>在本节中，我将总结其中一个编译器的设计思想，包括但不限于其总体结构、接口设计和文件组织。具体内容如下。</p><h2 id="_3-sysy-编译器总体设计" tabindex="-1"><a class="header-anchor" href="#_3-sysy-编译器总体设计"><span>3. SysY 编译器总体设计</span></a></h2><p>项目仓库：<a href="https://github.com/gitDebuger/sysy-compiler" target="_blank" rel="noopener noreferrer">SysY Compiler<span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span></a></p><h3 id="_3-1-目录结构" tabindex="-1"><a class="header-anchor" href="#_3-1-目录结构"><span>3.1 目录结构</span></a></h3><p>该编译器使用 Java 语言开发，当前源代码目录结构如下 ( 目录结构将随开发过程不断更新 ) 。</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line">src</span>
<span class="line">├── Compiler.java</span>
<span class="line">├── config.json</span>
<span class="line">├── exception</span>
<span class="line">│ ├── CompilationException.java</span>
<span class="line">│ └── ExceptionCategory.java</span>
<span class="line">├── lexer</span>
<span class="line">│ ├── ILexer.java</span>
<span class="line">│ ├── impl</span>
<span class="line">│ │ ├── DefaultLexerImpl.java</span>
<span class="line">│ │ └── StateTransitionLexerImpl.java</span>
<span class="line">│ ├── token</span>
<span class="line">│ │ ├── Assistant.java</span>
<span class="line">│ │ ├── CharConst.java</span>
<span class="line">│ │ ├── Identifier.java</span>
<span class="line">│ │ ├── IntConst.java</span>
<span class="line">│ │ ├── Keyword.java</span>
<span class="line">│ │ ├── Operator.java</span>
<span class="line">│ │ ├── StringConst.java</span>
<span class="line">│ │ ├── Token.java</span>
<span class="line">│ │ └── TokenCategory.java</span>
<span class="line">│ └── utils</span>
<span class="line">│ ├── State.java</span>
<span class="line">│ └── StateConverter.java</span>
<span class="line">├── parser</span>
<span class="line">│ ├── IParser.java</span>
<span class="line">│ ├── impl</span>
<span class="line">│ │ └── DefaultParserImpl.java</span>
<span class="line">│ └── node</span>
<span class="line">│ ├── BlockNode.java</span>
<span class="line">│ ├── ParseTreeLeafNode.java</span>
<span class="line">│ └── ParseTreeNode.java</span>
<span class="line">├── semantic</span>
<span class="line">│ ├── ISemanticAnalyzer.java</span>
<span class="line">│ ├── env</span>
<span class="line">│ │ ├── ArrayItem.java</span>
<span class="line">│ │ ├── Env.java</span>
<span class="line">│ │ ├── EnvItem.java</span>
<span class="line">│ │ ├── FunctionItem.java</span>
<span class="line">│ │ └── ItemCategory.java</span>
<span class="line">│ └── impl</span>
<span class="line">│ └── DefaultSemanticAnalyzerImpl.java</span>
<span class="line">├── symbol</span>
<span class="line">│ ├── BlankCategory.java</span>
<span class="line">│ ├── Category.java</span>
<span class="line">│ └── NonTerminalCategory.java</span>
<span class="line">└── tools</span>
<span class="line"> ├── FirstFollowCalculator.java</span>
<span class="line"> ├── Grammar.java</span>
<span class="line"> ├── PredictiveParsingTableBuilder.java</span>
<span class="line"> └── ToolMain.java</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h3 id="_3-2-根目录" tabindex="-1"><a class="header-anchor" href="#_3-2-根目录"><span>3.2 根目录</span></a></h3><p>根目录下的 <code>Compiler</code> 类是整个编译器的入口，配置文件 <code>config.json</code> 为评测所需的配置文件，与编译器程序本身无关。</p><h3 id="_3-3-目录-exception" tabindex="-1"><a class="header-anchor" href="#_3-3-目录-exception"><span>3.3 目录 <code>exception</code></span></a></h3><p>该目录下的两个类分别为异常类和枚举类。</p><p>异常类 <code>CompilationException</code> 意为编译错误，当编译器遇到源程序的错误时，可以抛出该异常。</p><p>枚举类 <code>ExceptionCategory</code> 作为上述异常类的一个字段，代表不同类型的编译错误，包括词法错误、语法错误、语义错误。</p><h3 id="_3-4-目录-lexer" tabindex="-1"><a class="header-anchor" href="#_3-4-目录-lexer"><span>3.4 目录 <code>lexer</code></span></a></h3><p>该目录包含词法分析子程序的相关文件。</p><p>接口 <code>ILexer</code> 为词法分析器接口，对外暴露词法分析器功能，其可以拥有不同的实现。</p><p>子目录 <code>impl</code> 包含不同的词法分析器实现，当前拥有两个实现类，实现思路不同。另外，实现类 <code>DefaultLexerImpl</code> 不保证在词法分析阶段之后的阶段正常工作，当前仅使用 <code>StateTransitionLexerImpl</code> 类作为词法分析器实现。</p><p>子目录 <code>token</code> 定义词法单元。抽象类 <code>Token</code> 作为所有词法单元的基类，枚举类 <code>TokenCategory</code> 作为该类的一个字段标记该词法单元的类型，其余的类均为 <code>Token</code> 类的子类，用于更好地对词法单元进行分类。</p><p>子目录 <code>utils</code> 中的文件用于词法分析器的状态转换。枚举类 <code>State</code> 定义不同的状态，接口 <code>StateConverter</code> 为函数式接口，用于在词法分析器中实现不同状态之间的转换。</p><h3 id="_3-5-目录-parser" tabindex="-1"><a class="header-anchor" href="#_3-5-目录-parser"><span>3.5 目录 <code>parser</code></span></a></h3><p>该目录包含语法分析子程序的相关文件。</p><p>接口 <code>IParser</code> 为语法分析器接口，对外暴露语法分析器功能，其可以拥有不同的实现。</p><p>子目录 <code>impl</code> 包含不同类型的语法分析器实现，当前仅有一个实现类。</p><p>子目录 <code>node</code> 定义语法分析树节点。类 <code>ParseTreeNode</code> 为语法分析树节点类，包含中间节点和叶子节点共有的属性和方法；类 <code>ParseTreeLeafNode</code> 继承自 <code>ParseTreeNode</code> 类，包含叶子节点特有的属性和方法。</p><h3 id="_3-6-目录-semantic" tabindex="-1"><a class="header-anchor" href="#_3-6-目录-semantic"><span>3.6 目录 <code>semantic</code></span></a></h3><p>该目录包含语义分析子程序的相关文件。</p><p>接口 <code>ISemanticAnalyzer</code> 为语义分析器接口，对外暴露语义分析器功能，其可以拥有不同的实现。</p><p>子目录 <code>impl</code> 包含不同类型的语义分析器实现，当前仅有一个实现类。</p><p>子目录 <code>env</code> 包含符号表相关类。类 <code>Env</code> 为符号表树节点类，类 <code>EnvItem</code> 为符号表项，其拥有两个子类，分别是 <code>ArrayItem</code> 类和 <code>FunctionItem</code> 类，代表数组和函数，其中包含一些数组和函数特有的属性和方法。枚举类 <code>ItemCategory</code> 可作为 <code>EnvItem</code> 类的一个字段，标记符号表项的类型。</p><h3 id="_3-7-目录-symbol" tabindex="-1"><a class="header-anchor" href="#_3-7-目录-symbol"><span>3.7 目录 <code>symbol</code></span></a></h3><p>该目录中的文件定义语法分析过程中需要用到的类型信息。</p><p>接口 <code>Category</code> 拥有三个实现类，这三个类均为枚举类，分别是上文提到的 <code>TokenCategory</code> 以及该目录下的 <code>BlankCategory</code> 和 <code>NonterminalCategory</code> 。</p><p>枚举类 <code>BlankCategory</code> 定义文法中的空产生式。</p><p>枚举类 <code>NonterminalCategory</code> 定义文法中的非终结符类型。</p><p>上文中的 <code>TokenCategory</code> 定义文法中的终结符类型，特别的，其中还包含终止符，用于语法分析器识别词法单元流的结尾。</p><h3 id="_3-8-目录-tools" tabindex="-1"><a class="header-anchor" href="#_3-8-目录-tools"><span>3.8 目录 <code>tools</code></span></a></h3><p>该目录下的文件用于处理文法并产生语法分析所需的预测分析表。</p><p>枚举类 <code>Grammar</code> 定义所有的文法。</p><p>类 <code>FirstFollowCalculator</code> 根据文法计算每个非终结符的 FIRST 集和 FOLLOW 集，并将集合内容输出到输出流中。</p><p>类 <code>PredictiveParsingTableBuilder</code> 根据文法及刚才计算出的 FIRST 集和 FOLLOW 集生成预测分析表，并可以将预测分析表信息输出到输出文件中。</p><p>类 <code>ToolMain</code> 启动整个预测分析表生成流程，将上述两个类的计算结果输出到文件中，并将预测分析表的数据结构返回给调用者。</p><h2 id="_4-词法分析设计" tabindex="-1"><a class="header-anchor" href="#_4-词法分析设计"><span>4. 词法分析设计</span></a></h2><p>词法分析器包含两个实现类，实现类 <code>DefaultLexerImpl</code> 由于结构混乱现已被标记为弃用。</p><p>实现类 <code>StateTransitionLexerImpl</code> 使用状态转换图实现词法分析，对外暴露的方法 <code>nextToken</code> 从给定输入流中读取下一个词法单元并返回给调用者。</p><p>根据给定的词法，我们可以绘制出如下的状态转换图：</p><p><img src="/assets/StateInLexer-B2wzFAmX.svg" alt="StateInLexer"></p><p>在构造词法分析器类时，会将状态初始化为 <code>Start</code> 。</p><p>每次调用 <code>nextToken</code> 方法，都会根据当前状态找到对应的状态转换处理器，然后根据读入的字符执行对应的状态转换逻辑；这个转换过程将不断进行，直到可以返回下一个词法单元或者抛出异常为止。</p><p>除了普通的状态转换处理器外，词法分析器还包含一个特殊的错误状态处理器，当发现词法错误或到达文件尾时便会进入错误状态。如果是由于发现词法错误进入错误状态，该处理器会抛出词法错误异常；如果是由于到达文件尾进入错误状态，处理器会将词法分析器状态永久置为 <code>FileEnd</code> 用以标记文件读入结束。</p><p>如果词法分析器状态为 <code>FileEnd</code> 即文件读入结束之后再次调用 <code>nextToken</code> 方法，该方法只会返回 <code>null</code> 。</p><h2 id="_5-语法分析设计" tabindex="-1"><a class="header-anchor" href="#_5-语法分析设计"><span>5. 语法分析设计</span></a></h2><p>语法分析器设计的基本思想：预测分析表驱动，非递归，自顶向下分析。</p><h3 id="_5-1-改造文法" tabindex="-1"><a class="header-anchor" href="#_5-1-改造文法"><span>5.1 改造文法</span></a></h3><p>为了满足设计需求，我们首先要对原文法进行改造，使之基本符合 LL(1) 文法的规定。改造过程如下，其中 <code>\epsilon</code> 代表空串：</p><p><em><strong>编译单元</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <CompUnit> -> {<Decl>} {<FuncDef>} <MainFuncDef></span></span>
<span class="line"><span class="token operator"><</span>CompUnit<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>DeclList<span class="token operator">></span> <span class="token operator"><</span>FuncDefList<span class="token operator">></span> <span class="token operator"><</span>MainFuncDef<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>DeclList<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>Decl<span class="token operator">></span> <span class="token operator"><</span>DeclList<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"><span class="token operator"><</span>FuncDefList<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>FuncDef<span class="token operator">></span> <span class="token operator"><</span>FuncDefList<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>声明</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <Decl> -> <ConstDecl> | <VarDecl></span></span>
<span class="line"><span class="token operator"><</span>Decl<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>ConstDecl<span class="token operator">></span> <span class="token operator">|</span> <span class="token operator"><</span>VarDecl<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>常量声明</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <ConstDecl> -> CONSTTK <BType> <ConstDef> { COMMA <ConstDef> } SEMICN</span></span>
<span class="line"><span class="token operator"><</span>ConstDecl<span class="token operator">></span> <span class="token operator">-></span> CONSTTK <span class="token operator"><</span>BType<span class="token operator">></span> <span class="token operator"><</span>ConstDef<span class="token operator">></span> <span class="token operator"><</span>ConstDefList<span class="token operator">></span> SEMICN</span>
<span class="line"><span class="token operator"><</span>ConstDefList<span class="token operator">></span> <span class="token operator">-></span> COMMA <span class="token operator"><</span>ConstDef<span class="token operator">></span> <span class="token operator"><</span>ConstDefList<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>基本类型</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <BType> -> INTTK | CHARTK</span></span>
<span class="line"><span class="token operator"><</span>BType<span class="token operator">></span> <span class="token operator">-></span> INTTK <span class="token operator">|</span> CHARTK</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>常量定义</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <ConstDef> -> IDENFR [ LBRACK <ConstExp> RBRACK ] ASSIGN <ConstInitVal></span></span>
<span class="line"><span class="token operator"><</span>ConstDef<span class="token operator">></span> <span class="token operator">-></span> IDENFR <span class="token operator"><</span>ArrSym<span class="token operator">></span> ASSIGN <span class="token operator"><</span>ConstInitVal<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>ConstArrSym<span class="token operator">></span> <span class="token operator">-></span> LBRACK <span class="token operator"><</span>ConstExp<span class="token operator">></span> RBRACK <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>常量初值</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <ConstInitVal> -> <ConstExp> | LBRACE [ <ConstExp> { COMMA <ConstExp> } ] RBRACE | STRCON</span></span>
<span class="line"><span class="token operator"><</span>ConstInitVal<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>ConstExp<span class="token operator">></span> <span class="token operator">|</span> LBRACE <span class="token operator"><</span>ConstExpListOpt<span class="token operator">></span> RBRACE <span class="token operator">|</span> STRCON</span>
<span class="line"><span class="token operator"><</span>ConstExpListOpt<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>ConstExp<span class="token operator">></span> <span class="token operator"><</span>ConstExpTail<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"><span class="token operator"><</span>ConstExpTail<span class="token operator">></span> <span class="token operator">-></span> COMMA <span class="token operator"><</span>ConstExp<span class="token operator">></span> <span class="token operator"><</span>ConstExpTail<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>变量声明</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <VarDecl> -> <BType> <VarDef> { COMMA <VarDef> } SEMICN</span></span>
<span class="line"><span class="token operator"><</span>VarDecl<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>BType<span class="token operator">></span> <span class="token operator"><</span>VarDef<span class="token operator">></span> <span class="token operator"><</span>VarDefList<span class="token operator">></span> SEMICN</span>
<span class="line"><span class="token operator"><</span>VarDefList<span class="token operator">></span> <span class="token operator">-></span> COMMA <span class="token operator"><</span>VarDef<span class="token operator">></span> <span class="token operator"><</span>VarDefList<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>变量定义</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <VarDef> -> IDENFR [ LBRACK <ConstExp> RBRACK ] | IDENFR [ LBRACK <ConstExp> RBRACK ] ASSIGN <InitVal></span></span>
<span class="line"><span class="token operator"><</span>VarDef<span class="token operator">></span> <span class="token operator">-></span> IDENFR <span class="token operator"><</span>ConstArrSym<span class="token operator">></span> <span class="token operator">|</span> IDENFR <span class="token operator"><</span>ArrSym<span class="token operator">></span> ASSIGN <span class="token operator"><</span>InitVal<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p>提取左公因子：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><VarDef> -> IDENFR <ArrSym> <_VarDef></span>
<span class="line"><_VarDef> -> ASSIGN <InitVal> | \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>变量初值</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <InitVal> -> <Exp> | LBRACE [ <Exp> { COMMA <Exp> } ] RBRACE | STRCON</span></span>
<span class="line"><span class="token operator"><</span>InitVal<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>Exp<span class="token operator">></span> <span class="token operator">|</span> LBRACE <span class="token operator"><</span>ExpListOpt<span class="token operator">></span> RBRACE <span class="token operator">|</span> STRCON</span>
<span class="line"><span class="token operator"><</span>ExpListOpt<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>Exp<span class="token operator">></span> <span class="token operator"><</span>ExpTail<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"><span class="token operator"><</span>ExpTail<span class="token operator">></span> <span class="token operator">-></span> COMMA <span class="token operator"><</span>Exp<span class="token operator">></span> <span class="token operator"><</span>ExpTail<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>函数定义</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <FuncDef> -> <FuncType> IDENFR LPARENT [ <FuncFParams> ] RPARENT <Block></span></span>
<span class="line"><span class="token operator"><</span>FuncDef<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>FuncType<span class="token operator">></span> IDENFR LPARENT <span class="token operator"><</span>FuncFParamsList<span class="token operator">></span> RPARENT <span class="token operator"><</span>Block<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>FuncFParamsList<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>FuncFParams<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>主函数定义</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <MainFuncDef> -> INTTK MAINTK LPARENT RPARENT <Block></span></span>
<span class="line"><span class="token operator"><</span>MainFuncDef<span class="token operator">></span> <span class="token operator">-></span> INTTK MAINTK LPARENT RPARENT <span class="token operator"><</span>Block<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>函数类型</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <FuncType> -> VOIDTK | INTTK | CHARTK</span></span>
<span class="line"><span class="token operator"><</span>FuncType<span class="token operator">></span> <span class="token operator">-></span> VOIDTK <span class="token operator">|</span> INTTK <span class="token operator">|</span> CHARTK</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>函数形参表</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <FuncFParams> -> <FuncFParam> { COMMA <FuncFParam> }</span></span>
<span class="line"><span class="token operator"><</span>FuncFParams<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>FuncFParam<span class="token operator">></span> <span class="token operator"><</span>FuncFParamList<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>FuncFParamList<span class="token operator">></span> <span class="token operator">-></span> COMMA <span class="token operator"><</span>FuncFParam<span class="token operator">></span> <span class="token operator"><</span>FuncFParamList<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>函数形参</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <FuncFParam> -> <BType> IDENFR [ LBRACK RBRACK ]</span></span>
<span class="line"><span class="token operator"><</span>FuncFParam<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>BType<span class="token operator">></span> IDENFR <span class="token operator"><</span>BracketPair<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>BracketPair<span class="token operator">></span> <span class="token operator">-></span> LBRACK RBRACK <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>语句块</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <Block> -> LBRACE { <BlockItem> } RBRACE</span></span>
<span class="line"><span class="token operator"><</span>Block<span class="token operator">></span> <span class="token operator">-></span> LRACE <span class="token operator"><</span>BlockItemList<span class="token operator">></span> RBRACE</span>
<span class="line"><span class="token operator"><</span>BlockItemList<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>BlockItem<span class="token operator">></span> <span class="token operator"><</span>BlockItemList<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>语句块项</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <BlockItem> -> <Decl> | <Stmt></span></span>
<span class="line"><span class="token operator"><</span>BlockItem<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>Decl<span class="token operator">></span> <span class="token operator">|</span> <span class="token operator"><</span>Stmt<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>语句</strong></em></p><p>原文法：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><Stmt> -> <Lval> ASSIGN <Exp> SEMICN</span>
<span class="line">| [ <Exp> ] SEMICN</span>
<span class="line">| <Block></span>
<span class="line">| IFTK LPARENT <Cond> RPARENT <Stmt> [ ELSETK <Stmt> ]</span>
<span class="line">| FORTK LPARENT [ <ForStmt> ] SEMICN [ <Cond> ] SEMICN [ <ForStmt> ] RPARENT <Stmt></span>
<span class="line">| BREAKTK SEMICN</span>
<span class="line">| CONTINUETK SEMICN</span>
<span class="line">| RETURNTK [ <Exp> ] SEMICN</span>
<span class="line">| <Lval> ASSIGN GETINTTK LPARENT RPARENT SEMICN</span>
<span class="line">| <Lval> ASSIGN GETCHARTK LPARENT RPARENT SEMICN</span>
<span class="line">| PRINTFTK LPARENT STRCON { COMMA <Exp> } RPARENT SEMICN</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>改写后文法：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><Stmt> -> <Lval> ASSIGN <Exp> SEMICN</span>
<span class="line"> | <ExpOpt> SEMICN</span>
<span class="line"> | <Block></span>
<span class="line"> | IFTK LPARENT <Cond> RPARENT <Stmt> <ElseOpt></span>
<span class="line"> | FORTK LPARENT <ForStmtOpt> SEMICN <CondOpt> SEMICN <ForStmtOpt> RPARENT <Stmt></span>
<span class="line"> | BREAKTK SEMICN</span>
<span class="line"> | CONTINUETK SEMICN</span>
<span class="line"> | RETURNTK <ExpOpt> SEMICN</span>
<span class="line"> | <Lval> ASSIGN GETINTTK LPARENT RPARENT SEMICN</span>
<span class="line"> | <Lval> ASSIGN GETCHARTK LPARENT RPARENT SEMICN</span>
<span class="line"> | PRINTFTK LPARENT STRCON <ExpListTailOpt> RPARENT SEMICN</span>
<span class="line"></span>
<span class="line"><ExpOpt> -> <Exp> | \epsilon</span>
<span class="line"><ElseOpt> -> ELSETK <Stmt> | \epsilon</span>
<span class="line"><ForStmtOpt> -> <ForStmt> | \epsilon</span>
<span class="line"><CondOpt> -> <Cond> | \epsilon</span>
<span class="line"><ExpListTailOpt> -> COMMA <Exp> <ExpListTailOpt> | \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>提取左公因子：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><Stmt> -> <LVal> ASSIGN <ReadOrOther></span>
<span class="line"> | <ExpOpt> SEMICN</span>
<span class="line"> | <Block></span>
<span class="line"> | IFTK LPARENT <Cond> RPARENT <Stmt> <ElseOpt></span>
<span class="line"> | FORTK LPARENT <ForStmtOpt> SEMICN <CondOpt> SEMICN <ForStmtOpt> RPARENT <Stmt></span>
<span class="line"> | BREAKTK SEMICN</span>
<span class="line"> | CONTINUETK SEMICN</span>
<span class="line"> | RETURNTK <ExpOpt> SEMICN</span>
<span class="line"> | PRINTFTK LPARENT STRCON <ExpListTailOpt> RPARENT SEMICN</span>
<span class="line"><ReadOrOther> = <Exp> SEMICN | <GetFunc> LPARENT RPARENT SEMICN</span>
<span class="line"><GetFunc> -> GETINTTK | GETCHARTK</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>For循环语句</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <ForStmt> -> <Lval> ASSIGN <Exp></span></span>
<span class="line"><span class="token operator"><</span>ForStmt<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>Lval<span class="token operator">></span> ASSIGN <span class="token operator"><</span>Exp<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <Exp> -> <AddExp></span></span>
<span class="line"><span class="token operator"><</span>Exp<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>AddExp<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>条件表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <Cond> -> <LOrExp></span></span>
<span class="line"><span class="token operator"><</span>Cond<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>LOrExp<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>左值表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <LVal> -> IDENFR [ LBRACK <Exp> RBRACK ]</span></span>
<span class="line"><span class="token operator"><</span>LVal<span class="token operator">></span> <span class="token operator">-></span> IDENFR <span class="token operator"><</span>ArrSym<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>ArrSym<span class="token operator">></span> <span class="token operator">-></span> LBRACK <span class="token operator"><</span>Exp<span class="token operator">></span> RBRACK <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>基本表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <PrimaryExp> -> LPARENT <Exp> RPARENT | <LVal> | <Number> | <Character></span></span>
<span class="line"><span class="token operator"><</span>PrimaryExp<span class="token operator">></span> <span class="token operator">-></span> LPARENT <span class="token operator"><</span>Exp<span class="token operator">></span> RPARENT <span class="token operator">|</span> <span class="token operator"><</span>LVal<span class="token operator">></span> <span class="token operator">|</span> <span class="token operator"><</span>Number<span class="token operator">></span> <span class="token operator">|</span> <span class="token operator"><</span>Character<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>数值</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <Number> -> INTCON</span></span>
<span class="line"><span class="token operator"><</span>Number<span class="token operator">></span> <span class="token operator">-></span> INTCON</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>字符</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <Character> -> CHRCON</span></span>
<span class="line"><span class="token operator"><</span>Character<span class="token operator">></span> <span class="token operator">-></span> CHRCON</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>一元表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <UnaryExp> -> <PrimaryExp> | IDENFR LPARENT [ <FuncRParams> ] RPARENT | <UnaryOp> <UnaryExp></span></span>
<span class="line"><span class="token operator"><</span>UnaryExp<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>PrimaryExp<span class="token operator">></span> <span class="token operator">|</span> IDENFR LPARENT <span class="token operator"><</span>FuncRParamsList<span class="token operator">></span> RPARENT <span class="token operator">|</span> <span class="token operator"><</span>UnaryOp<span class="token operator">></span> <span class="token operator"><</span>UnaryExp<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>FuncRParamsList<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>FuncRParams<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>单目运算符</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <UnaryOp> -> PLUS | MINU | NOT</span></span>
<span class="line"><span class="token operator"><</span>UnaryOp<span class="token operator">></span> <span class="token operator">-></span> PLUS <span class="token operator">|</span> MINU <span class="token operator">|</span> NOT</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>函数实参表</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <FuncRParams> -> <Exp> { COMMA <Exp> }</span></span>
<span class="line"><span class="token operator"><</span>FuncRParams<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>Exp<span class="token operator">></span> <span class="token operator"><</span>ExpListTail<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>ExpListTail<span class="token operator">></span> <span class="token operator">-></span> COMMA <span class="token operator"><</span>Exp<span class="token operator">></span> <span class="token operator"><</span>ExpListTail<span class="token operator">></span> <span class="token operator">|</span> \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>乘除模表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <MulExp> -> <UnaryExp> | <MulExp> ( MULT | DIV | MOD ) <UnaryExp></span></span>
<span class="line"><span class="token operator"><</span>MulExp<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>UnaryExp<span class="token operator">></span> <span class="token operator">|</span> <span class="token operator"><</span>MulExp<span class="token operator">></span> <span class="token operator"><</span>MultDivModOp<span class="token operator">></span> <span class="token operator"><</span>UnaryExp<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>MultDivModOp<span class="token operator">></span> <span class="token operator">-></span> MULT <span class="token operator">|</span> DIV <span class="token operator">|</span> MOD</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>消除左递归：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><MulExp> -> <UnaryExp> <_MulExp></span>
<span class="line"><_MulExp> -> <MultDivModOp> <MulExp> | \epsilon</span>
<span class="line"><MultDivModOp> -> MULT | DIV | MOD</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>加减表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <AddExp> -> <MulExp> | <AddExp> ( PLUS | MINU ) <MulExp></span></span>
<span class="line"><span class="token operator"><</span>AddExp<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>MulExp<span class="token operator">></span> <span class="token operator">|</span> <span class="token operator"><</span>AddExp<span class="token operator">></span> <span class="token operator"><</span>PlusMinuOp<span class="token operator">></span> <span class="token operator"><</span>MulExp<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>PlusMinuOp<span class="token operator">></span> <span class="token operator">-></span> PLUS <span class="token operator">|</span> MINU</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>消除左递归：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><AddExp> -> <MulExp> <_AddExp></span>
<span class="line"><_AddExp> -> <PlusMinuOp> <AddExp> | \epsilon</span>
<span class="line"><PlusMinuOp> -> PLUS | MINU</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>关系表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <RelExp> -> <AddExp> | <RelExp> ( GRE | LSS | GEQ | LEQ ) <AddExp></span></span>
<span class="line"><span class="token operator"><</span>RelExp<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>AddExp<span class="token operator">></span> <span class="token operator">|</span> <span class="token operator"><</span>RelExp<span class="token operator">></span> <span class="token operator"><</span>GreLssGeqLeqOp<span class="token operator">></span> <span class="token operator"><</span>AddExp<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>GreLssGeqLeqOp<span class="token operator">></span> <span class="token operator">-></span> GRE <span class="token operator">|</span> LSS <span class="token operator">|</span> GEQ <span class="token operator">|</span> LEQ</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>消除左递归：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><RelExp> -> <AddExp> <_RelExp></span>
<span class="line"><_RelExp> -> <GreLssGeqLeqOp> <RelExp> | \epsilon</span>
<span class="line"><GreLssGeqLeqOp> -> GRE | LSS | GEQ | LEQ</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>相等性表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <EqExp> -> <RelExp> | <EqExp> ( EQL | NEQ ) <RelExp></span></span>
<span class="line"><span class="token operator"><</span>EqExp<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>RelExp<span class="token operator">></span> <span class="token operator">|</span> <span class="token operator"><</span>EqExp<span class="token operator">></span> <span class="token operator"><</span>EqlNeqOp<span class="token operator">></span> <span class="token operator"><</span>RelExp<span class="token operator">></span></span>
<span class="line"><span class="token operator"><</span>EqlNeqOp<span class="token operator">></span> <span class="token operator">-></span> EQL <span class="token operator">|</span> NEQ</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>消除左递归：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><EqExp> -> <RelExp> <_EqExp></span>
<span class="line"><_EqExp> -> <EqlNeqOp> <EqExp> | \epsilon</span>
<span class="line"><EqlNeqOp> -> EQL | NEQ</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>逻辑与表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <LAndExp> -> <EqExp> | <LAndExp> AND <EqExp></span></span>
<span class="line"><span class="token operator"><</span>LAndExp<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>EqExp<span class="token operator">></span> <span class="token operator">|</span> <span class="token operator"><</span>LAndExp<span class="token operator">></span> AND <span class="token operator"><</span>EqExp<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p>消除左递归：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><LAndExp> -> <EqExp> <_LAndExp></span>
<span class="line"><_LAndExp> -> AND <LAndExp> | \epsilon</span>
<span class="line"><LAndExp> -> <EqExp> | <LAndExp> AND <EqExp></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>逻辑或表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <LOrExp> -> <LAndExp> | <LOrExp> OR <LAndExp></span></span>
<span class="line"><span class="token operator"><</span>LOrExp<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>LAndExp<span class="token operator">></span> <span class="token operator">|</span> <span class="token operator"><</span>LOrExp<span class="token operator">></span> OR <span class="token operator"><</span>LAndExp<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p>消除左递归：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><LOrExp> -> <LAndExp> <_LOrExp></span>
<span class="line"><_LOrExp> -> OR <LOrExp> | \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p><em><strong>常量表达式</strong></em></p><div class="language-c line-numbers-mode" data-highlighter="prismjs" data-ext="c" data-title="c"><pre class="language-c"><code><span class="line"><span class="token comment">// <ConstExp> -> <AddExp></span></span>
<span class="line"><span class="token operator"><</span>ConstExp<span class="token operator">></span> <span class="token operator">-></span> <span class="token operator"><</span>AddExp<span class="token operator">></span></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p>虽然这个文法不完全符合 LL(1) 文法的规定，但已经足够使用了。</p><h3 id="_5-2-计算-first-集和-follow-集" tabindex="-1"><a class="header-anchor" href="#_5-2-计算-first-集和-follow-集"><span>5.2 计算 FIRST 集和 FOLLOW 集</span></a></h3><p>我们将改造完的文法以程序源码的形式在编译器中表示，这样做是为了当文法发生变化时，这两个集合可以随之更新。</p><p>接下来我们使用伪代码描述这两个集合计算过程，符号定义如下：</p><ul><li><code>G</code> ：文法</li><li><code>N</code> ：非终结符集合</li><li><code>T</code> ：终结符集合</li><li><code>P</code> ：产生式集合</li></ul><p>按照如下算法计算每个非终结符的 FIRST 集：</p><div class="language-pseudocode line-numbers-mode" data-highlighter="prismjs" data-ext="pseudocode" data-title="pseudocode"><pre class="language-pseudocode"><code><span class="line">function ComputeFIRST(G):</span>
<span class="line"> initialize FIRST(A) = {} for each non-terminal A in N</span>
<span class="line"></span>
<span class="line"> repeat</span>
<span class="line"> for each production A -> α in P:</span>
<span class="line"> for each symbol X in α:</span>
<span class="line"> if X in T:</span>
<span class="line"> add X to FIRST(A)</span>
<span class="line"> break</span>
<span class="line"> else if x not in T:</span>
<span class="line"> add all elements of (FIRST(X) - {ε}) to FIRST(A)</span>
<span class="line"> </span>
<span class="line"> if ε in FIRST(X):</span>
<span class="line"> continue</span>
<span class="line"> else break</span>
<span class="line"> if all Xi (1 <= i <= n) contain ε in their FIRST sets:</span>
<span class="line"> add ε to FIRST(A)</span>
<span class="line"></span>
<span class="line"> until no changes to any FIRST set</span>
<span class="line"></span>
<span class="line"> return FIRST</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>或者我们也可以利用 FIRST 集的传递性，递归地进行 FIRST 集计算：</p><div class="language-pseudocode line-numbers-mode" data-highlighter="prismjs" data-ext="pseudocode" data-title="pseudocode"><pre class="language-pseudocode"><code><span class="line">function ComputeFIRST(G):</span>
<span class="line"> initialize FIRST(A) = {} for each non-terminal A in N</span>
<span class="line"> initialize visited(A) = false for each non-terminal A in N</span>
<span class="line"></span>
<span class="line"> for each non-terminal A in N:</span>
<span class="line"> if not visited(A):</span>
<span class="line"> FIRST(A) = ComputeFIRSTRecursive(A)</span>
<span class="line"></span>
<span class="line"> return FIRST</span>
<span class="line"></span>
<span class="line">function ComputeFIRSTRecursive(A):</span>
<span class="line"> if visited(A):</span>
<span class="line"> return FIRST(A)</span>
<span class="line"></span>
<span class="line"> visited(A) = true</span>
<span class="line"></span>
<span class="line"> for each production A -> α in P:</span>
<span class="line"> for each symbol X in α:</span>
<span class="line"> if X in T:</span>
<span class="line"> add X to FIRST(A)</span>
<span class="line"> break</span>
<span class="line"> else if X not in T:</span>
<span class="line"> add all elements of (ComputeFIRSTRecursive(X) - {ε}) to FIRST(A)</span>
<span class="line"></span>
<span class="line"> if ε not in FIRST(X):</span>
<span class="line"> break</span>
<span class="line"></span>
<span class="line"> if all symbols in α can derive ε:</span>
<span class="line"> add ε to FIRST(A)</span>
<span class="line"></span>
<span class="line"> return FIRST(A)</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>按照如下算法计算每个非终结符的 FOLLOW 集：</p><div class="language-pseudocode line-numbers-mode" data-highlighter="prismjs" data-ext="pseudocode" data-title="pseudocode"><pre class="language-pseudocode"><code><span class="line">function ComputeFOLLOW(G):</span>
<span class="line"> initialize FOLLOW(A) = {} for each non-terminal A in N</span>
<span class="line"> initialize FOLLOW(S) = { $ }</span>
<span class="line"></span>
<span class="line"> repeat</span>
<span class="line"> for each production A -> α in P:</span>
<span class="line"> for each symbol B in α:</span>
<span class="line"> if B in T:</span>
<span class="line"> add all elements of (FIRST(β) - {ε}) to FOLLOW(B)</span>
<span class="line"></span>
<span class="line"> if ε in FIRST(β) or B is the last symbol in α:</span>
<span class="line"> add all elements of FOLLOW(A) to FOLLOW(B)</span>
<span class="line"></span>
<span class="line"> until no changes to any FOLLOW set</span>
<span class="line"></span>
<span class="line"> return FOLLOW</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>我们可以将计算结果输出到本地文件用以监测程序运行情况。</p><h3 id="_5-3-生成预测分析表" tabindex="-1"><a class="header-anchor" href="#_5-3-生成预测分析表"><span>5.3 生成预测分析表</span></a></h3><p>计算完 FIRST 集和 FOLLOW 集后，我们可以利用这两个集合生成预测分析表。</p><p>对于文法 <code>G</code> 中的每个产生式 <code>A->α</code> 进行如下处理：</p><ol><li>对于 <code>FIRST(α)</code> 中的每个终结符号 <code>a</code> 将 <code>A->α</code> 加入到 <code>M[A,a]</code> 中。</li><li>如果 <code>ε</code> 在 <code>FIRST(α)</code> 中，那么对于 <code>FOLLOW(A)</code> 中的每个终结符号 <code>b</code> 将 <code>A->α</code> 加入到 <code>M[A,b]</code> 中。如果 <code>ε</code> 在 <code>FIRST(α)</code> 中，且 <code>$</code> 在 <code>FOLLOW(A)</code> 中，将 <code>A->α</code> 加入到 <code>M[A,$]</code> 中。</li></ol><p>完成上面的操作后，如果 <code>M[A,a]</code> 中没有产生式，那么将 <code>M[A,a]</code> 设置为错误，我们通常在表中用一个空条目表示。</p><p>同样的，我们可以将预测分析表打印到本地的 <code>.csv</code> 文件监控运行结果。</p><h3 id="_5-4-语法分析主程序" tabindex="-1"><a class="header-anchor" href="#_5-4-语法分析主程序"><span>5.4 语法分析主程序</span></a></h3><p>语法分析主程序采用预测分析表驱动的预测分析算法，算法伪代码如下：</p><div class="language-pseudocode line-numbers-mode" data-highlighter="prismjs" data-ext="pseudocode" data-title="pseudocode"><pre class="language-pseudocode"><code><span class="line">function PredictiveParser(input, parseTable, startSymbol):</span>
<span class="line"> initialize stack = [ $, startSymbol ]</span>
<span class="line"> initialize pointer = 0</span>
<span class="line"> input = input + $</span>
<span class="line"></span>
<span class="line"> while stack is not empty:</span>
<span class="line"> top = stack.pop()</span>
<span class="line"></span>
<span class="line"> currentInput = input[pointer]</span>
<span class="line"></span>
<span class="line"> if top is a terminal or top == $:</span>
<span class="line"> if top == currentInput:</span>
<span class="line"> pointer = pointer + 1</span>
<span class="line"> else:</span>
<span class="line"> return "Error: Unexpected input symbol"</span>
<span class="line"></span>
<span class="line"> else if top is a non-terminal:</span>
<span class="line"> production = parseTable[top, currentInput]</span>
<span class="line"> if production is empty:</span>
<span class="line"> return "Error: No matching production"</span>
<span class="line"></span>
<span class="line"> else:</span>
<span class="line"> for symbol in reverse(production):</span>
<span class="line"> if symbol != ε:</span>
<span class="line"> stack.push(symbol)</span>
<span class="line"></span>
<span class="line"> else:</span>
<span class="line"> return "Error: Invalid symbol on stack"</span>
<span class="line"></span>
<span class="line"> if pointer == len(input):</span>
<span class="line"> return "Success: Input is parsed successfully"</span>
<span class="line"> else:</span>
<span class="line"> return "Error: Input is not fully parsed"</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>但是，由于我们的文法不是完全的 LL(1) 文法，所以预测分析表的某些条目会存在两个产生式，我们需要对这些情况单独处理。</p><p>存在问题的条目有下面几个：</p><table><thead><tr><th style="text-align:center;">非终结符\终结符</th><th style="text-align:center;"><code>IDENFR</code></th><th style="text-align:center;"><code>ELSETK</code></th><th style="text-align:center;"><code>INTTK</code></th><th style="text-align:center;"><code>CHARTK</code></th></tr></thead><tbody><tr><td style="text-align:center;"><code><UnaryExp></code></td><td style="text-align:center;">√</td><td style="text-align:center;"></td><td style="text-align:center;"></td><td style="text-align:center;"></td></tr><tr><td style="text-align:center;"><code><Stmt></code></td><td style="text-align:center;">√</td><td style="text-align:center;"></td><td style="text-align:center;"></td><td style="text-align:center;"></td></tr><tr><td style="text-align:center;"><code><ElseOpt></code></td><td style="text-align:center;"></td><td style="text-align:center;">√</td><td style="text-align:center;"></td><td style="text-align:center;"></td></tr><tr><td style="text-align:center;"><code><DeclList></code></td><td style="text-align:center;"></td><td style="text-align:center;"></td><td style="text-align:center;">√</td><td style="text-align:center;">√</td></tr><tr><td style="text-align:center;"><code><FuncDefList></code></td><td style="text-align:center;"></td><td style="text-align:center;"></td><td style="text-align:center;">√</td><td style="text-align:center;"></td></tr></tbody></table><p>我们接下来对这些条目逐一进行分析。</p><p><em><strong><code><UnaryExp>,IDENFR</code></strong></em></p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><UnaryExp> -> <PrimaryExp></span>
<span class="line"> | IDENFR LPARENT <FuncRParamsList> RPARENT</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p>相关产生式如下：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><PrimaryExp> -> LPARENT <Exp> RPARENT | <LVal> | <Number> | <Character></span>
<span class="line"><LVal> -> IDENFR <ArrSym></span>
<span class="line"><ArrSym> -> LBRACK <Exp> RBRACK | \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>这个问题很好解决。向前读取一个终结符，如果下一个终结符为 <code>LPARENT</code> 则说明为第二个产生式，否则为第一个产生式。</p><p><em><strong><code><Stmt>,IDENFR</code></strong></em></p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><Stmt> -> <ExpOpt> SEMICN</span>
<span class="line"> | <LVal> ASSIGN <ReadOrOther></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p>相关产生式如下：</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><ExpOpt> -> <Exp> | \epsilon</span>
<span class="line"><Exp> -> <AddExp></span>
<span class="line"><AddExp> -> <MulExp> <_AddExp></span>
<span class="line"><MulExp> -> <UnaryExp> <_MulExp></span>
<span class="line"><UnaryExp> -> <PrimaryExp> | IDENFR LPARENT <FuncRParamsList> RPARENT | <UnaryOp> <UnaryExp></span>
<span class="line"><PrimaryExp> -> LPARENT <Exp> RPARENT | <LVal> | <Number> | <Character></span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>这个问题比较复杂，我们可以这样做：</p><ol><li>向前读取一个终结符，如果为 <code>LPARENT</code> 则说明为第一个产生式。</li><li>如果不符合第一步的条件，则先分析出 <code><LVal></code> 的语法成分，然后判断 <code><LVal></code> 之后的下一个终结符，如果为 <code>ASSIGN</code> 说明为第二个产生式，否则为第一个产生式。</li></ol><p><em><strong><code><ElseOpt>,ELSETK</code></strong></em></p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><ElseOpt> -> ELSETK <Stmt></span>
<span class="line"> | \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p>这是很经典的悬空 <code>else</code> 问题，我们按照惯例让每个 <code>else</code> 和最近的尚未匹配的 <code>if</code> 匹配即可。</p><p><em><strong><code><DeclList>,INTTK</code> 和 <code><FuncDefList>,INTTK</code></strong></em></p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><DeclList> -> <Decl> <DeclList></span>
<span class="line"> | \epsilon;</span>
<span class="line"><FuncDefList> -> <FuncDef> <FuncDefList></span>
<span class="line"> | \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>相关产生式较多，所以这里不再罗列。</p><p>解决方法很简单，对于 <code><DeclList></code> 的情况，我们向前读取两个终结符，如果第二个终结符为 <code>LPARENT</code> 说明为第二个产生式，否则为第一个产生式；对于 <code><FuncDefList></code> 的情况，我们向前读取一个终结符，如果为 <code>MAINTK</code> 说明为第二个产生式，否则为第一个产生式。</p><p><em><strong><code><DeclList>,CHARTK</code></strong></em></p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre class="language-text"><code><span class="line"><DeclList> -> <Decl> <DeclList></span>
<span class="line"> | \epsilon</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div></div></div><p>这种情况的处理方式和上一种情况的处理方式相同，向前读取两个终结符，如果第二个终结符为 <code>LPARENT</code> 说明为第二个产生式，否则为第一个产生式。</p><h3 id="_5-5-错误处理" tabindex="-1"><a class="header-anchor" href="#_5-5-错误处理"><span>5.5 错误处理</span></a></h3><p>按照评测要求，源程序中会出现缺少 <code>SEMICN</code> <code>RPARENT</code> <code>RBRACK</code> 的情况，我们只需要在缺少该种终结符时，创建一个终结符添加到语法分析树中即可，新创建的终结符行号与上一个终结符的行号相同，完成处理后将报错信息打印到错误输出流。</p><h3 id="_5-6-评测说明" tabindex="-1"><a class="header-anchor" href="#_5-6-评测说明"><span>5.6 评测说明</span></a></h3><p>语法分析器的输出为语法分析树，编译器主程序将后序遍历该语法分析树，输出需要输出的终结符和非终结符。</p><p>考虑到我们改写了文法，语法分析树的结构会与原文法的语法分析树结构不同，从而导致输出结果不同，我们可以如下处理：</p><ol><li>对于新添加的非终结符以及不要求输出的已有非终结符，在遍历过程中不输出其分析信息。</li><li>对于改写的左递归文法，将输出根节点的操作放在输出左子树和输出右子树的操作中间。</li></ol><p>伪代码描述如下：</p><div class="language-pseudocode line-numbers-mode" data-highlighter="prismjs" data-ext="pseudocode" data-title="pseudocode"><pre class="language-pseudocode"><code><span class="line">function ParseAndPrint(node):</span>
<span class="line"> if node is <MulExp> or <AddExp> or <RelExp> or <EqExp> or <LAndExp> or <LOrExp>:</span>
<span class="line"> ParseAndPrint(node.left)</span>
<span class="line"> print(node)</span>
<span class="line"> ParseAndPrint(node.right)</span>
<span class="line"> return</span>
<span class="line"> else:</span>
<span class="line"> for child in node.children:</span>
<span class="line"> ParseAndPrint(child)</span>
<span class="line"> print(node)</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>为了方便监测输出结果以进行调试，可以使用如下算法将语法分析树输出到文件中：</p><div class="language-pseudocode line-numbers-mode" data-highlighter="prismjs" data-ext="pseudocode" data-title="pseudocode"><pre class="language-pseudocode"><code><span class="line">function PrintTree(tree, prefix, isLast):</span>
<span class="line"> print(prefix + (isLast ? "└── " : "├── ") + tree)</span>
<span class="line"> for child in tree.children:</span>
<span class="line"> set newPrefix = prefix + (isLast ? " " : "│ ")</span>
<span class="line"> PrintTree(child, newPrifix, whether child is the last)</span>
<span class="line"></span>
<span class="line">PrintTree(SyntaxTree, "", true)</span>
<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h2 id="_6-语义分析设计" tabindex="-1"><a class="header-anchor" href="#_6-语义分析设计"><span>6. 语义分析设计</span></a></h2><h3 id="_6-1-主要设计思想" tabindex="-1"><a class="header-anchor" href="#_6-1-主要设计思想"><span>6.1 主要设计思想</span></a></h3><p>语义分析的主要任务就是生成符号表，并检查源代码中的语义错误。</p><p>虽然语义分析可以合并到语法分析过程中，但是为了避免对原有语法分析代码的大范围修改，也为了方便语义分析的编写工作，此次任务中，语义分析将被放置在语法分析之后。语义分析器将利用语法分析输出的语法树，遍历语法树生成符号表并检查其中的语义错误。</p><h3 id="_6-2-符号表管理" tabindex="-1"><a class="header-anchor" href="#_6-2-符号表管理"><span>6.2 符号表管理</span></a></h3><p>本次编译器设计中使用的符号表将体现为一棵符号表树，树的根节点代表全局作用域，其余节点代表不同嵌套深度的局部作用域。</p><p>在语义分析过程中，我们还会使用一个指针指向当前作用域对应的符号表树节点，该指针指向的节点即为顶层作用域节点，该指针也可被称为顶层作用域指针。初始状态下顶层作用域指针指向符号表树的根节点，代表当前作用域为全局作用域。</p><p>每当进入一个新的作用域，我们会创建一个新的符号表树节点，同时更新顶层作用域指针指向这个新创建的节点；每当离开一个作用域，我们需要更新顶层作用域指针，使其指向原作用域的外层作用域对应的符号表树节点。为了达成这个目的，每个符号表树节点除存储其对应作用域的符号表项外，还需要存储指向其上层节点的指针，以及指向其下层节点的指针列表。自然，根节点的上层节点指针为空。</p><p>最终形成的符号表将如下图所示：</p><p><img src="/assets/SymbolTableTree-DztgUMYk.svg" alt="SymbolTableTree"></p><p>在语义分析过程中，如果需要处理的是变量声明或者函数声明语句，我们将查找当前顶层作用域符号表树节点，检查是否已存在同名表项，如果已存在应当报错处理；否则，应当填入新的符号表项。如果需要处理的是对符号的调用，我们将从当前顶层作用域符号表树节点出发，一路查找到符号表树的根节点，直到查找到对应的符号表项为止；如果一直查找到根节点都没有找到对应的符号表项，应当报错处理。</p><h3 id="_6-3-评测说明" tabindex="-1"><a class="header-anchor" href="#_6-3-评测说明"><span>6.3 评测说明</span></a></h3><p>在已经拥有完整的语法树的情况下，语义分析工作就非常容易了。所以需要注意的其实就是评测要求了。</p><p>对于正确的源程序，需要按作用域顺序输出符号表信息，我们只需要对符号表树进行前序深度优先搜索即可，遍历过程中输出每个节点的表项信息。为了便于查找，节点中的表项使用哈希表存储，但是评测要求按照插入顺序输出符号名称。如果使用Java语言编写编译器，可以利用Java集合框架提供的 <code>LinkedHashMap</code> 类，它是可以记录元素插入顺序的哈希表结构，恰好可以满足我们的需求。</p><p>对于错误的源程序，由于我们的语义分析工作是在语法分析完成之后进行，所以之前的词法错误和语法错误，以及新的语义错误，不能在分析过程中输出了。所以说，我们需要使用一定的数据结构存储分析过程中检查到的错误，分析结束之后，将所有的错误合并到一起后排序输出。</p><h2 id="附录" tabindex="-1"><a class="header-anchor" href="#附录"><span>附录</span></a></h2><h3 id="a-词法单元定义" tabindex="-1"><a class="header-anchor" href="#a-词法单元定义"><span>A. 词法单元定义</span></a></h3><table><thead><tr><th style="text-align:center;">终结符名称</th><th style="text-align:center;">类别码</th></tr></thead><tbody><tr><td style="text-align:center;"><strong>Ident</strong></td><td style="text-align:center;">IDENFR</td></tr><tr><td style="text-align:center;"><strong>IntConst</strong></td><td style="text-align:center;">INTCON</td></tr><tr><td style="text-align:center;"><strong>StringConst</strong></td><td style="text-align:center;">STRCON</td></tr><tr><td style="text-align:center;"><strong>CharConst</strong></td><td style="text-align:center;">CHRCON</td></tr><tr><td style="text-align:center;">main</td><td style="text-align:center;">MAINTK</td></tr><tr><td style="text-align:center;">const</td><td style="text-align:center;">CONSTTK</td></tr><tr><td style="text-align:center;">int</td><td style="text-align:center;">INTTK</td></tr><tr><td style="text-align:center;">char</td><td style="text-align:center;">CHARTK</td></tr><tr><td style="text-align:center;">break</td><td style="text-align:center;">BREAKTK</td></tr><tr><td style="text-align:center;">continue</td><td style="text-align:center;">CONTINUETK</td></tr><tr><td style="text-align:center;">if</td><td style="text-align:center;">IFTK</td></tr><tr><td style="text-align:center;">else</td><td style="text-align:center;">ELSETK</td></tr><tr><td style="text-align:center;">!</td><td style="text-align:center;">NOT</td></tr><tr><td style="text-align:center;">&&</td><td style="text-align:center;">AND</td></tr><tr><td style="text-align:center;">||</td><td style="text-align:center;">OR</td></tr><tr><td style="text-align:center;">for</td><td style="text-align:center;">FORTK</td></tr><tr><td style="text-align:center;">getint</td><td style="text-align:center;">GETINTTK</td></tr><tr><td style="text-align:center;">gerchar</td><td style="text-align:center;">GETCHARTK</td></tr><tr><td style="text-align:center;">printf</td><td style="text-align:center;">PRINTFTK</td></tr><tr><td style="text-align:center;">return</td><td style="text-align:center;">RETURNTK</td></tr><tr><td style="text-align:center;">+</td><td style="text-align:center;">PLUS</td></tr><tr><td style="text-align:center;">-</td><td style="text-align:center;">MINU</td></tr><tr><td style="text-align:center;">void</td><td style="text-align:center;">VOIDTK</td></tr><tr><td style="text-align:center;">*</td><td style="text-align:center;">MULT</td></tr><tr><td style="text-align:center;">/</td><td style="text-align:center;">DIV</td></tr><tr><td style="text-align:center;">%</td><td style="text-align:center;">MOD</td></tr><tr><td style="text-align:center;"><</td><td style="text-align:center;">LSS</td></tr><tr><td style="text-align:center;"><=</td><td style="text-align:center;">LEQ</td></tr><tr><td style="text-align:center;">></td><td style="text-align:center;">GRE</td></tr><tr><td style="text-align:center;">>=</td><td style="text-align:center;">GEQ</td></tr><tr><td style="text-align:center;">==</td><td style="text-align:center;">EQL</td></tr><tr><td style="text-align:center;">!=</td><td style="text-align:center;">NEQ</td></tr><tr><td style="text-align:center;">=</td><td style="text-align:center;">ASSIGN</td></tr></tbody></table><h3 id="b-错误类型" tabindex="-1"><a class="header-anchor" href="#b-错误类型"><span>B. 错误类型</span></a></h3><table><thead><tr><th style="text-align:center;">错误类型</th><th style="text-align:center;">类别码</th><th style="text-align:center;">描述</th></tr></thead><tbody><tr><td style="text-align:center;">非法符号</td><td style="text-align:center;">a</td><td style="text-align:center;">词法错误，出现 & 或 | 符号，应当作 && 或 || 处理。</td></tr><tr><td style="text-align:center;">符号重定义</td><td style="text-align:center;">b</td><td style="text-align:center;">符号名称在当前作用域下重复定义</td></tr><tr><td style="text-align:center;">符号未定义</td><td style="text-align:center;">c</td><td style="text-align:center;">使用未定义标识符</td></tr><tr><td style="text-align:center;">函数参数个数不匹配</td><td style="text-align:center;">d</td><td style="text-align:center;">调用函数时，传递的实参个数和函数定义的形参个数不符</td></tr><tr><td style="text-align:center;">函数参数类型不匹配</td><td style="text-align:center;">e</td><td style="text-align:center;">调用函数时，传递的实参类型和函数定义的形参类型不符</td></tr><tr><td style="text-align:center;">不匹配的 <code>return</code> 语句</td><td style="text-align:center;">f</td><td style="text-align:center;">在无返回值函数中使用了带返回值的 <code>return</code> 语句</td></tr><tr><td style="text-align:center;">缺少 <code>return</code> 语句</td><td style="text-align:center;">g</td><td style="text-align:center;">有返回值函数的末尾缺少 <code>return</code> 语句</td></tr><tr><td style="text-align:center;">试图改变常量的值</td><td style="text-align:center;">h</td><td style="text-align:center;">试图修改常量左值的值</td></tr><tr><td style="text-align:center;">缺少分号</td><td style="text-align:center;">i</td><td style="text-align:center;">语法错误</td></tr><tr><td style="text-align:center;">缺少右圆括号</td><td style="text-align:center;">j</td><td style="text-align:center;">语法错误</td></tr><tr><td style="text-align:center;">缺少右方括号</td><td style="text-align:center;">k</td><td style="text-align:center;">语法错误</td></tr><tr><td style="text-align:center;">格式字符数量和表达式数量不匹配</td><td style="text-align:center;">l</td><td style="text-align:center;">打印语句的控制字符串中的格式字符数量和传递的表达式数量不匹配</td></tr><tr><td style="text-align:center;">违规的循环控制语句</td><td style="text-align:center;">m</td><td style="text-align:center;">在非循环块中使用 <code>continue</code> 或 <code>break</code> 语句</td></tr></tbody></table></div></div><footer class="page-meta"><div class="meta-item edit-link"><span class="xicon-container left meta-item-label"><!--[--><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 32 32" class="xicon-icon" style="width:20px;height:20px;font-size:20px;color:inherit;"><path d="M2 26h28v2H2z" fill="currentColor"></path><path d="M25.4 9c.8-.8.8-2 0-2.8l-3.6-3.6c-.8-.8-2-.8-2.8 0l-15 15V24h6.4l15-15zm-5-5L24 7.6l-3 3L17.4 7l3-3zM6 22v-3.6l10-10l3.6 3.6l-10 10H6z" fill="currentColor"></path></svg><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->Edit this page<!--]--></span></span></div><div class="meta-item last-updated"><span class="xicon-container left meta-item-label"><!--[--><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 32 32" class="xicon-icon" style="width:20px;height:20px;font-size:20px;color:inherit;"><path d="M26 4h-4V2h-2v2h-8V2h-2v2H6c-1.1 0-2 .9-2 2v20c0 1.1.9 2 2 2h20c1.1 0 2-.9 2-2V6c0-1.1-.9-2-2-2zm0 22H6V12h20v14zm0-16H6V6h4v2h2V6h8v2h2V6h4v4z" fill="currentColor"></path></svg><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->Last Updated 2024/10/22 18:15:58<!--]--></span></span></div></footer><!----><!----></div><div class="page-catalog-container"><h5 class="tip">ON THIS PAGE</h5><ul><!--[--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_1-项目概述" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="1. 项目概述"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->1. 项目概述<!--]--></span></span><!--[--><!--]--></a></li><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_1-1-这是什么项目" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="1.1 这是什么项目？"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->1.1 这是什么项目？<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_1-2-需要翻译什么语言" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="1.2 需要翻译什么语言？"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->1.2 需要翻译什么语言？<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_1-3-源代码将被翻译成什么语言" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="1.3 源代码将被翻译成什么语言？"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->1.3 源代码将被翻译成什么语言？<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_2-参考编译器介绍" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="2. 参考编译器介绍"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->2. 参考编译器介绍<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_3-sysy-编译器总体设计" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3. SysY 编译器总体设计"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3. SysY 编译器总体设计<!--]--></span></span><!--[--><!--]--></a></li><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_3-1-目录结构" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.1 目录结构"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.1 目录结构<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_3-2-根目录" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.2 根目录"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.2 根目录<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_3-3-目录-exception" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.3 目录 exception"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.3 目录 exception<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_3-4-目录-lexer" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.4 目录 lexer"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.4 目录 lexer<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_3-5-目录-parser" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.5 目录 parser"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.5 目录 parser<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_3-6-目录-semantic" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.6 目录 semantic"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.6 目录 semantic<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_3-7-目录-symbol" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.7 目录 symbol"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.7 目录 symbol<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_3-8-目录-tools" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.8 目录 tools"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.8 目录 tools<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_4-词法分析设计" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="4. 词法分析设计"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->4. 词法分析设计<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_5-语法分析设计" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5. 语法分析设计"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5. 语法分析设计<!--]--></span></span><!--[--><!--]--></a></li><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_5-1-改造文法" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.1 改造文法"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.1 改造文法<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_5-2-计算-first-集和-follow-集" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.2 计算 FIRST 集和 FOLLOW 集"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.2 计算 FIRST 集和 FOLLOW 集<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_5-3-生成预测分析表" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.3 生成预测分析表"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.3 生成预测分析表<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_5-4-语法分析主程序" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.4 语法分析主程序"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.4 语法分析主程序<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_5-5-错误处理" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.5 错误处理"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.5 错误处理<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_5-6-评测说明" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.6 评测说明"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.6 评测说明<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_6-语义分析设计" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="6. 语义分析设计"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->6. 语义分析设计<!--]--></span></span><!--[--><!--]--></a></li><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_6-1-主要设计思想" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="6.1 主要设计思想"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->6.1 主要设计思想<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_6-2-符号表管理" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="6.2 符号表管理"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->6.2 符号表管理<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#_6-3-评测说明" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="6.3 评测说明"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->6.3 评测说明<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/README.zh.html#附录" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="附录"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->附录<!--]--></span></span><!--[--><!--]--></a></li><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#a-词法单元定义" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="A. 词法单元定义"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->A. 词法单元定义<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/README.zh.html#b-错误类型" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="B. 错误类型"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->B. 错误类型<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--]--><!--]--></ul></div></main><!--]--></div><!--[--><!----><!----><!--]--><!--]--></div>
<script type="module" src="/assets/app-B51tXhJU.js" defer></script>
</body>
</html>