-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
360 lines (359 loc) · 120 KB
/
Copy pathindex.html
File metadata and controls
360 lines (359 loc) · 120 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 Compiler | 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/index.html-DTD_Tf27.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/README.zh.html-C95KaJWV.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 Compiler</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-compiler" tabindex="-1"><a class="header-anchor" href="#sysy-compiler"><span>SysY Compiler</span></a></h1><h2 id="_1-project-overview" tabindex="-1"><a class="header-anchor" href="#_1-project-overview"><span>1. Project Overview</span></a></h2><h3 id="_1-1-what-is-this-project" tabindex="-1"><a class="header-anchor" href="#_1-1-what-is-this-project"><span>1.1 What is this project?</span></a></h3><p>This project is designed and developed as part of the "Compiler Technology" course experiment at Beihang University, which requires the design and implementation of a compiler.</p><h3 id="_1-2-what-language-needs-to-be-translated" tabindex="-1"><a class="header-anchor" href="#_1-2-what-language-needs-to-be-translated"><span>1.2 What language needs to be translated?</span></a></h3><p>The compiler is expected to translate code written in <em><strong>SysY</strong></em> language (a subset of C language) into <em><strong>intermediate code</strong></em> or <em><strong>target code</strong></em>.</p><h3 id="_1-3-what-language-will-source-code-be-translated-into" tabindex="-1"><a class="header-anchor" href="#_1-3-what-language-will-source-code-be-translated-into"><span>1.3 What language will source code be translated into?</span></a></h3><p>The source code needs to be translated into <em><strong>intermediate code (LLVM IR Code or P-code)</strong></em> or <em><strong>target code (MIPS)</strong></em>.</p><h2 id="_2-introduction-to-reference-compilers" tabindex="-1"><a class="header-anchor" href="#_2-introduction-to-reference-compilers"><span>2. Introduction to Reference Compilers</span></a></h2><p>The course group provided two compilers (Pascal-Compiler and Pl0-Compiler) for reference. We need to read and analyze their source code, and then complete the overall architecture design of our own compiler based on this.</p><p>In this section, I will summarize the design philosophy of one of the compilers, including but not limited to its overall structure, interface design, and file organization. The specific content is as follows.</p><h2 id="_3-overall-design-of-sysy-compiler" tabindex="-1"><a class="header-anchor" href="#_3-overall-design-of-sysy-compiler"><span>3. Overall Design of SysY Compiler</span></a></h2><p>Project Repository: <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-directory-structure" tabindex="-1"><a class="header-anchor" href="#_3-1-directory-structure"><span>3.1 Directory Structure</span></a></h3><p>The compiler is developed in Java language, and the current source code directory structure is as follows (the directory structure will be updated continuously during the development process).</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-root-directory" tabindex="-1"><a class="header-anchor" href="#_3-2-root-directory"><span>3.2 Root Directory</span></a></h3><p>The <code>Compiler</code> class under the root directory is the entry point of the entire compiler, and the configuration file <code>config.json</code> is a configuration file required for evaluation, which is unrelated to the compiler program itself.</p><h3 id="_3-3-directory-exception" tabindex="-1"><a class="header-anchor" href="#_3-3-directory-exception"><span>3.3 Directory <code>exception</code></span></a></h3><p>The two classes under this directory are the exception class and the enumeration class.</p><p>The exception class <code>CompilationException</code> means a compilation error, which can be thrown when the compiler encounters an error in the source program.</p><p>The enumeration class <code>ExceptionCategory</code> serves as a field of the above exception class, representing different types of compilation errors, including lexical errors, syntax errors, and semantic errors.</p><h3 id="_3-4-directory-lexer" tabindex="-1"><a class="header-anchor" href="#_3-4-directory-lexer"><span>3.4 Directory <code>lexer</code></span></a></h3><p>This directory contains files related to the lexical analysis subroutine.</p><p>The interface <code>ILexer</code> is the interface for the lexical analyzer, which exposes the functionality of the lexical analyzer and can have different implementations.</p><p>The subdirectory <code>impl</code> contains different implementations of the lexical analyzer. Currently, there are two implementation classes with different implementation ideas. In addition, the implementation class <code>DefaultLexerImpl</code> is not guaranteed to work properly after the lexical analysis phase, and the class <code>StateTransitionLexerImpl</code> is currently used as the only implementation of the lexical analyzer.</p><p>The subdirectory <code>token</code> defines lexical units. The abstract class <code>Token</code> serves as the base class for all lexical units, and the enumeration class <code>TokenCategory</code> serves as a field of this class to mark the type of the lexical unit. The remaining classes are subclasses of <code>Token</code> and are used to better classify lexical units.</p><p>The files in the subdirectory utils are used for state transitions in the lexical analyzer. The enumeration class <code>State</code> defines different states, and the interface <code>StateConverter</code> is a functional interface used to implement the transition between different states in the lexical analyzer.</p><h3 id="_3-5-directory-parser" tabindex="-1"><a class="header-anchor" href="#_3-5-directory-parser"><span>3.5 Directory <code>parser</code></span></a></h3><p>This directory contains files related to the syntax analysis subroutine.</p><p>The interface <code>IParser</code> is the interface for the syntax analyzer, which exposes the functionality of the syntax analyzer and can have different implementations.</p><p>The subdirectory impl contains different types of syntax analyzer implementations, and currently there is only one implementation class.</p><p>The subdirectory node defines syntax analysis tree nodes. The class <code>ParseTreeNode</code> is the class for syntax analysis tree nodes, which includes attributes and methods common to intermediate nodes and leaf nodes; the class <code>ParseTreeLeafNode</code> inherits from the <code>ParseTreeNode</code> class and includes attributes and methods unique to leaf nodes.</p><h3 id="_3-6-directory-semantic" tabindex="-1"><a class="header-anchor" href="#_3-6-directory-semantic"><span>3.6 Directory <code>semantic</code></span></a></h3><p>This directory contains files related to the semantic analysis subroutines.</p><p>The interface <code>ISemanticAnalyzer</code> serves as the interface for the semantic analyzer, exposing the functionality of the semantic analyzer, which can have different implementations.</p><p>The subdirectory <code>impl</code> contains implementations of different types of semantic analyzers, with only one implementation class currently available.</p><p>The subdirectory <code>env</code> contains classes related to the symbol table. The class <code>Env</code> is a symbol table tree node class, and the class <code>EnvItem</code> is a symbol table item, which has two subclasses, namely the <code>ArrayItem</code> class and the <code>FunctionItem</code> class, representing arrays and functions, respectively. These classes include attributes and methods specific to arrays and functions. The enumeration class <code>ItemCategory</code> can serve as a field of the <code>EnvItem</code> class, marking the type of symbol table items.</p><h3 id="_3-7-directory-symbol" tabindex="-1"><a class="header-anchor" href="#_3-7-directory-symbol"><span>3.7 Directory <code>symbol</code></span></a></h3><p>The files in this directory define the type information needed during the syntax analysis process.</p><p>The interface <code>Category</code> has three implementation classes, all of which are enumeration classes, namely the <code>TokenCategory</code> mentioned earlier and the <code>BlankCategory</code> and <code>NonterminalCategory</code> in this directory.</p><p>The enumeration class <code>BlankCategory</code> defines the empty production in the grammar.</p><p>The enumeration class <code>NonterminalCategory</code> defines the types of non-terminals in the grammar.</p><p>The <code>TokenCategory</code> mentioned above defines the terminal symbols in the grammar, and in particular, it also includes the end-of-input symbol, which is used by the syntax analyzer to recognize the end of the lexical unit stream.</p><h3 id="_3-8-directory-tools" tabindex="-1"><a class="header-anchor" href="#_3-8-directory-tools"><span>3.8 Directory <code>tools</code></span></a></h3><p>The files in this directory are used to process the grammar and generate the predictive parsing table required for syntax analysis.</p><p>The enumeration class <code>Grammar</code> defines all the grammars.</p><p>The class <code>FirstFollowCalculator</code> calculates the FIRST set and FOLLOW set for each non-terminal based on the grammar and outputs the set content to the output stream.</p><p>The class <code>PredictiveParsingTableBuilder</code> generates the predictive parsing table based on the grammar and the FIRST set and FOLLOW set just calculated, and can output the predictive parsing table information to the output file.</p><p>The class <code>ToolMain</code> starts the entire predictive parsing table generation process, outputs the calculation results of the above two classes to the file, and returns the data structure of the predictive parsing table to the caller.</p><h2 id="_4-lexical-analysis-design" tabindex="-1"><a class="header-anchor" href="#_4-lexical-analysis-design"><span>4. Lexical Analysis Design</span></a></h2><p>The lexical analyzer includes two implementation classes. The implementation class <code>DefaultLexerImpl</code> is now deprecated due to structural confusion.</p><p>The implementation class <code>StateTransitionLexerImpl</code> implements lexical analysis using a state transition diagram, exposing the method <code>nextToken</code> to read the next lexical unit from the given input stream and return it to the caller.</p><p>Based on the given lexicon, we can draw the following state transition diagram:</p><p><img src="/assets/StateInLexer-B2wzFAmX.svg" alt="StateInLexer"></p><p>When constructing the lexical analyzer class, the state is initialized to <code>Start</code>.</p><p>Each call to the <code>nextToken</code> method will find the corresponding state transition handler based on the current state, and then perform the corresponding state transition logic according to the character read; this transition process will continue until the next lexical unit can be returned or an exception is thrown.</p><p>In addition to the normal state transition handlers, the lexical analyzer also includes a special error state handler, which enters the error state when a lexical error is found or when the end of the file is reached. If it enters the error state due to a lexical error, the handler will throw a lexical error exception; if it enters the error state due to reaching the end of the file, the handler will permanently set the lexical analyzer state to <code>FileEnd</code> to mark the end of file reading.</p><p>If the lexical analyzer state is <code>FileEnd</code>, that is, after the file reading is finished, and the <code>nextToken</code> method is called again, the method will only return null.</p><h2 id="_5-syntax-analysis-design" tabindex="-1"><a class="header-anchor" href="#_5-syntax-analysis-design"><span>5. Syntax Analysis Design</span></a></h2><p>The basic idea of the syntax analyzer design: driven by the predictive parsing table, non-recursive, top-down analysis.</p><h3 id="_5-1-grammar-transformation" tabindex="-1"><a class="header-anchor" href="#_5-1-grammar-transformation"><span>5.1 Grammar Transformation</span></a></h3><p>To meet the design requirements, we must first transform the original grammar to conform to the LL(1) grammar rules as much as possible. The transformation process is as follows, where <code>\epsilon</code> represents an empty string:</p><p><em><strong>Compilation Unit</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>Declarations</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>Constant Declaration</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>Basic Type</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>Constant Definition</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>Constant Initial Value</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>Variable Declaration</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>Variable Definition</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>Extracting Left Common Factors:</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>Variable Initial Value</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>Function Definition</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>Main Function Definition</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>Function Type</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>Function Parameter List</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>Function Parameter</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>Statement Block</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>Statement Block Item</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>Statements</strong></em></p><p>Original Grammar:</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>Rewritten Grammar:</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>Extracting Left Common Factors:</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 Loop Statement</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>Experiment</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>Conditional Experiment</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>Left Value Statement</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>Primary Experiment</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>Number</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>Character</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>Unary Experiment</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>Unary Operator</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>Function Real Parameters</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>Multiply and Divide and Mod Experiment</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>Extracting Left Common Factors:</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>Add and Minus Experiment</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>Extracting Left Common Factors:</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>Relationship Experiment</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>Extracting Left Common Factors:</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>Equation Experiment</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>Extracting Left Common Factors:</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>Logic And Experiment</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>Extracting Left Common Factors:</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>Logic Or Experiment</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>Extracting Left Common Factors:</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>Constant Experiment</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>Although this grammar is not entirely compliant with LL(1) grammar rules, it is sufficient for use.</p><h3 id="_5-2-calculation-of-first-and-follow-sets" tabindex="-1"><a class="header-anchor" href="#_5-2-calculation-of-first-and-follow-sets"><span>5.2 Calculation of FIRST and FOLLOW sets</span></a></h3><p>We represent the transformed grammar in the form of program source code within the compiler so that when the grammar changes, these two sets can be updated accordingly.</p><p>Next, we use pseudocode to describe the calculation process of these two sets, with the following symbol definitions:</p><ul><li><code>G</code> : Grammar</li><li><code>N</code> : Set of non-terminals</li><li><code>T</code> : Set of terminals</li><li><code>P</code> : Set of productions</li></ul><p>According to the following algorithm, calculate the FIRST set for each non-terminal:</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>Alternatively, we can also use the transitivity of the FIRST set to recursively calculate the FIRST set:</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>According to the following algorithm, calculate the FOLLOW set for each non-terminal:</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>We can output the calculation results to a local file to monitor the program's operation.</p><h3 id="_5-3-generation-of-predictive-parsing-table" tabindex="-1"><a class="header-anchor" href="#_5-3-generation-of-predictive-parsing-table"><span>5.3 Generation of Predictive Parsing Table</span></a></h3><p>After calculating the FIRST and FOLLOW sets, we can use these two sets to generate a predictive parsing table.</p><p>For each production <code>A->α</code> in grammar <code>G</code> , do the following:</p><ul><li>For each terminal symbol <code>a</code> in <code>FIRST(α)</code>, add <code>A->α</code> to <code>M[A,a]</code> .</li><li>If <code>ε</code> is in <code>FIRST(α)</code> , then for each terminal symbol <code>b</code> in <code>FOLLOW(A)</code> , add <code>A->α</code> to <code>M[A,b]</code> . If <code>ε</code> is in <code>FIRST(α)</code> , and <code>$</code> is in <code>FOLLOW(A)</code> , add <code>A->α</code> to <code>M[A,$]</code> .</li></ul><p>After completing the above operations, if there are no productions in <code>M[A,a]</code> , set <code>M[A,a]</code> to an error, which we usually represent with an empty entry in the table.</p><p>Similarly, we can print the predictive parsing table to a local <code>.csv</code> file to monitor the results.</p><h3 id="_5-4-syntax-analysis-main-program" tabindex="-1"><a class="header-anchor" href="#_5-4-syntax-analysis-main-program"><span>5.4 Syntax Analysis Main Program</span></a></h3><p>The syntax analysis main program uses a predictive analysis table-driven predictive analysis algorithm, with pseudocode as follows:</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>However, since our grammar is not entirely an LL(1) grammar, some entries in the predictive analysis table will have two productions, and we need to handle these cases individually.</p><p>The problematic entries are as follows:</p><table><thead><tr><th style="text-align:center;">Non- Terminal\Terminal</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>We will analyze each of these entries one by one.</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>The relevant productions are as follows:</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>This problem is easy to solve; read one terminal symbol forward, if the next terminal symbol is <code>LPARENT</code> , it indicates the second production, otherwise, it is the first production.</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>The relevant productions are as follows:</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>This problem is more complex; we can do the following:</p><ol><li>Read one terminal symbol forward, if it is <code>LPARENT</code> , it indicates the first production.</li><li>If it does not meet the conditions of the first step, first analyze the syntax component of <code><LVal></code> , then judge the next terminal symbol after <code><LVal></code> , if it is <code>ASSIGN</code> , it indicates the second production, otherwise, it is the first production.</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>This is a classic dangling <code>else</code> problem; we can follow the convention to match each <code>else</code> with the nearest unmatched <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>There are many relevant productions, so they are not listed here.</p><p>The solution is simple; for the case of <code><DeclList></code> , read two terminal symbols forward, if the second terminal symbol is <code>LPARENT</code> , it indicates the second production, otherwise, it is the first production; for the case of <code><FuncDefList></code> , read one terminal symbol forward, if it is <code>MAINTK</code> , it indicates the second production, otherwise, it is the first production.</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>The handling of this situation is the same as the previous one; read two terminal symbols forward, if the second terminal symbol is <code>LPARENT</code> , it indicates the second production, otherwise, it is the first production.</p><h3 id="_5-5-error-handling" tabindex="-1"><a class="header-anchor" href="#_5-5-error-handling"><span>5.5 Error Handling</span></a></h3><p>According to the evaluation requirements, the source program will have missing <code>SEMICN</code> <code>RPARENT</code> <code>RBRACK</code> situations, and we just need to create a terminal symbol and add it to the syntax analysis tree when this kind of terminal symbol is missing. The newly created terminal symbol has the same line number as the previous terminal symbol, and after the processing is completed, the error message is printed to the error output stream.</p><h3 id="_5-6-evaluation-instructions" tabindex="-1"><a class="header-anchor" href="#_5-6-evaluation-instructions"><span>5.6 Evaluation Instructions</span></a></h3><p>The output of the syntax analyzer is the syntax analysis tree, and the compiler main program will post-order traverse this syntax analysis tree to output the required terminal and non-terminal symbols.</p><p>Considering that we have rewritten the grammar, the structure of the syntax analysis tree will be different from the structure of the syntax analysis tree of the original grammar, which will lead to different output results. We can handle it as follows:</p><ol><li>For the newly added non-terminal symbols and the existing non-terminal symbols that are not required to be output, do not output their analysis information during the traversal process.</li><li>For the rewritten left-recursive grammar, place the operation of outputting the root node in the middle of the operations of outputting the left subtree and the right subtree.</li></ol><p>Pseudocode description is as follows:</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>To facilitate monitoring of the output results for debugging, the following algorithm can be used to output the syntax analysis tree to a file:</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-semantic-analysis-design" tabindex="-1"><a class="header-anchor" href="#_6-semantic-analysis-design"><span>6. Semantic Analysis Design</span></a></h2><h3 id="_6-1-main-design-philosophy" tabindex="-1"><a class="header-anchor" href="#_6-1-main-design-philosophy"><span>6.1 Main Design Philosophy</span></a></h3><p>The primary task of semantic analysis is to generate a symbol table and check for semantic errors in the source code.</p><p>Although semantic analysis can be integrated into the syntax analysis process, to avoid extensive modifications to the existing syntax analysis code and to facilitate the writing of semantic analysis, semantic analysis in this task will be placed after syntax analysis. The semantic analyzer will use the syntax tree output by the syntax analyzer, traverse the syntax tree to generate a symbol table, and check for semantic errors within it.</p><h3 id="_6-2-symbol-table-management" tabindex="-1"><a class="header-anchor" href="#_6-2-symbol-table-management"><span>6.2 Symbol Table Management</span></a></h3><p>In this compiler design, the symbol table used will be represented as a symbol table tree, with the root node representing the global scope and the other nodes representing local scopes of different nesting depths.</p><p>During the semantic analysis process, we will also use a pointer to point to the symbol table tree node corresponding to the current scope. This pointer points to the top-level scope node, which can also be referred to as the top-level scope pointer. Initially, the top-level scope pointer points to the root node of the symbol table tree, representing the current scope as the global scope.</p><p>Whenever we enter a new scope, we will create a new symbol table tree node and update the top-level scope pointer to point to this newly created node. Whenever we exit a scope, we need to update the top-level scope pointer so that it points to the symbol table tree node corresponding to the outer scope of the original scope. To achieve this, each symbol table tree node, in addition to storing the symbol table items corresponding to its scope, also needs to store a pointer to its upper node and a list of pointers to its lower nodes. Naturally, the upper node pointer of the root node is null.</p><p>The final symbol table will be shown in the figure below:</p><p><img src="/assets/SymbolTableTree-DztgUMYk.svg" alt="SymbolTableTree"></p><p>During the semantic analysis process, if we are dealing with variable declarations or function declarations, we will look up the current top-level scope symbol table tree node to check if there is already an entry with the same name. If there is, an error should be reported; otherwise, a new symbol table entry should be added. If we are dealing with a call to a symbol, we will start from the current top-level scope symbol table tree node and search all the way to the root node of the symbol table tree until we find the corresponding symbol table entry. If we search all the way to the root node and still do not find the corresponding symbol table entry, an error should be reported.</p><h3 id="_6-3-evaluation-instructions" tabindex="-1"><a class="header-anchor" href="#_6-3-evaluation-instructions"><span>6.3 Evaluation Instructions</span></a></h3><p>With a complete syntax tree already available, the semantic analysis work becomes quite straightforward. What really needs attention are the evaluation requirements.</p><p>For correct source programs, the symbol table information needs to be output in the order of scopes. We simply need to perform a pre-order depth-first search on the symbol table tree, outputting the entry information of each node during the traversal. For easy lookup, the entries in the nodes are stored using a hash table, but the evaluation requires that the symbol names be output in the order they were inserted. If writing a compiler in Java, we can utilize the <code>LinkedHashMap</code> class provided by the Java collection framework. It is a hash table structure that can record the order of element insertion, which perfectly meets our needs.</p><p>For erroneous source programs, since our semantic analysis is conducted after syntax analysis is complete, lexical errors, syntactic errors, and new semantic errors cannot be output during the analysis process. Therefore, we need to use a certain data structure to store the errors detected during the analysis. After the analysis is finished, all errors should be combined and sorted before being output together.</p><h2 id="appendix" tabindex="-1"><a class="header-anchor" href="#appendix"><span>Appendix</span></a></h2><h3 id="a-lexical-unit-definition" tabindex="-1"><a class="header-anchor" href="#a-lexical-unit-definition"><span>A. Lexical Unit Definition</span></a></h3><table><thead><tr><th style="text-align:center;">Name of Nonterminal Symbol</th><th style="text-align:center;">Category Code</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-error-category" tabindex="-1"><a class="header-anchor" href="#b-error-category"><span>B. Error Category</span></a></h3><table><thead><tr><th style="text-align:center;">Error Category</th><th style="text-align:center;">Category Code</th><th style="text-align:center;">Description</th></tr></thead><tbody><tr><td style="text-align:center;">Illegal Symbol</td><td style="text-align:center;">a</td><td style="text-align:center;">Lexical error, appear & or | symbol, which should be treated as && or || .</td></tr><tr><td style="text-align:center;">Symbol Redefinition</td><td style="text-align:center;">b</td><td style="text-align:center;">The symbol name is redefined within the current scope.</td></tr><tr><td style="text-align:center;">Undefined Symbol</td><td style="text-align:center;">c</td><td style="text-align:center;">Using an undefined identifier.</td></tr><tr><td style="text-align:center;">Mismatched Function Params</td><td style="text-align:center;">d</td><td style="text-align:center;">The number of actual arguments passed to a function does not match the number of formal parameters defined.</td></tr><tr><td style="text-align:center;">Function Params Type Mismatch</td><td style="text-align:center;">e</td><td style="text-align:center;">The type of actual arguments passed to a function does not match the type of formal parameters defined.</td></tr><tr><td style="text-align:center;">Mismatched <code>return</code> Statement</td><td style="text-align:center;">f</td><td style="text-align:center;">A <code>return</code> statement with a return value is used in a function that does not return a value.</td></tr><tr><td style="text-align:center;">Missing <code>return</code> Statement</td><td style="text-align:center;">g</td><td style="text-align:center;">A function that returns a value is missing a <code>return</code> statement at the end.</td></tr><tr><td style="text-align:center;">Attempt to Modify Constant Value</td><td style="text-align:center;">h</td><td style="text-align:center;">Attempting to modify the value of a constant left value.</td></tr><tr><td style="text-align:center;">Missing Semicolon</td><td style="text-align:center;">i</td><td style="text-align:center;">Syntax Error</td></tr><tr><td style="text-align:center;">Missing Right Parenthesis</td><td style="text-align:center;">j</td><td style="text-align:center;">Syntax Error</td></tr><tr><td style="text-align:center;">Missing Right Bracket</td><td style="text-align:center;">k</td><td style="text-align:center;">Syntax Error</td></tr><tr><td style="text-align:center;">Format Characters and Expressions Mismatch</td><td style="text-align:center;">l</td><td style="text-align:center;">The number of format characters in the control string of a print statement does not match the number of expressions passed.</td></tr><tr><td style="text-align:center;">Illegal Loop Control Statement</td><td style="text-align:center;">m</td><td style="text-align:center;">Using <code>continue</code> or <code>break</code> statements within a non-loop block.</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/#_1-project-overview" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="1. Project Overview"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->1. Project Overview<!--]--></span></span><!--[--><!--]--></a></li><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_1-1-what-is-this-project" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="1.1 What is this project?"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->1.1 What is this project?<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_1-2-what-language-needs-to-be-translated" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="1.2 What language needs to be translated?"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->1.2 What language needs to be translated?<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_1-3-what-language-will-source-code-be-translated-into" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="1.3 What language will source code be translated into?"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->1.3 What language will source code be translated into?<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/#_2-introduction-to-reference-compilers" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="2. Introduction to Reference Compilers"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->2. Introduction to Reference Compilers<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/#_3-overall-design-of-sysy-compiler" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3. Overall Design of SysY Compiler"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3. Overall Design of SysY Compiler<!--]--></span></span><!--[--><!--]--></a></li><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_3-1-directory-structure" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.1 Directory Structure"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.1 Directory Structure<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_3-2-root-directory" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.2 Root Directory"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.2 Root Directory<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_3-3-directory-exception" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.3 Directory exception"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.3 Directory exception<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_3-4-directory-lexer" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.4 Directory lexer"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.4 Directory lexer<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_3-5-directory-parser" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.5 Directory parser"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.5 Directory parser<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_3-6-directory-semantic" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.6 Directory semantic"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.6 Directory semantic<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_3-7-directory-symbol" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.7 Directory symbol"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.7 Directory symbol<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_3-8-directory-tools" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="3.8 Directory tools"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->3.8 Directory tools<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/#_4-lexical-analysis-design" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="4. Lexical Analysis Design"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->4. Lexical Analysis Design<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/#_5-syntax-analysis-design" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5. Syntax Analysis Design"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5. Syntax Analysis Design<!--]--></span></span><!--[--><!--]--></a></li><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_5-1-grammar-transformation" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.1 Grammar Transformation"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.1 Grammar Transformation<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_5-2-calculation-of-first-and-follow-sets" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.2 Calculation of FIRST and FOLLOW sets"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.2 Calculation of FIRST and FOLLOW sets<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_5-3-generation-of-predictive-parsing-table" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.3 Generation of Predictive Parsing Table"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.3 Generation of Predictive Parsing Table<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_5-4-syntax-analysis-main-program" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.4 Syntax Analysis Main Program"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.4 Syntax Analysis Main Program<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_5-5-error-handling" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.5 Error Handling"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.5 Error Handling<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_5-6-evaluation-instructions" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="5.6 Evaluation Instructions"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->5.6 Evaluation Instructions<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/#_6-semantic-analysis-design" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="6. Semantic Analysis Design"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->6. Semantic Analysis Design<!--]--></span></span><!--[--><!--]--></a></li><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_6-1-main-design-philosophy" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="6.1 Main Design Philosophy"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->6.1 Main Design Philosophy<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_6-2-symbol-table-management" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="6.2 Symbol Table Management"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->6.2 Symbol Table Management<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#_6-3-evaluation-instructions" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="6.3 Evaluation Instructions"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->6.3 Evaluation Instructions<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--]--><!--[--><li class="page-catalog-menu-depth_2"><a aria-current="page" href="/blogs/Compiler/#appendix" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="Appendix"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->Appendix<!--]--></span></span><!--[--><!--]--></a></li><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#a-lexical-unit-definition" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="A. Lexical Unit Definition"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->A. Lexical Unit Definition<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--[--><li class="page-catalog-menu-depth_3"><a aria-current="page" href="/blogs/Compiler/#b-error-category" class="router-link-active router-link-exact-active link page-catalog-item page-catalog-item" aria-label="B. Error Category"><!--[--><!--]--><span class="xicon-container left"><!--[--><!----><!--]--><span class="xicon-content" style="color:inherit;font-size:14px;"><!--[-->B. Error Category<!--]--></span></span><!--[--><!--]--></a></li><!--]--><!--]--><!--]--></ul></div></main><!--]--></div><!--[--><!----><!----><!--]--><!--]--></div>
<script type="module" src="/assets/app-B51tXhJU.js" defer></script>
</body>
</html>