Step1: String -> Scanning (DFA) -> Tokens Scanner又叫Lexical analyzer或Lexer.

其目的在于, 将需要compile的源代码逐字读入compiler, 并将每一个符合"词汇命名规则(Lexical Syntax)"的字段转换成token存储.
换句话说, 就是一遍读, 一遍看每一个单词的拼写对不对. 对的就转成token, 拼错了就输出error.

作业中对应: A6 P4
(某些语言的compiler在Scanning之后还包含Preprocessing, 因为不在241讨论范围内, 不做解释)

Step2: Tokens -> Parsing(LL/LR) -> Intermediate Format (WLI)

Parsing又叫Syntactic Analysis.
其目的在于, 将token与token联系在一起, 并将他们的转换成符合一定规范的"中间格式", 一般是某种树状结构, 例如241中定义的WLI.

在Parsing过程中, 如果遇到不符合某种语言的"语法规则(Grammar)"时, 则输出error. 如果语法正确, 则输出对应格式.
简单说, 就是看的说的话是不是人话, 有没有缺个标点少个括号.
如果不是人话那就说明你该重新学语法去了.

作业中对应: A8 P4

Step3: Intermediate Format -> Semantic Analysis(Context-Sensitive Analysis) ->

Semantic Analysis的目的在于, 检查程序是否存在语义上的冲突. 或者说, 上下文是不是相符.

比如在C中, 如果没有declare过变量int a;, 则a = 3;就不合法.
再比如, 如果a declare为int, 则a = 'b';就不合法, 因为a不能为char.

作业中对应: A9 A10
(Optimization为代码优化, 241没有涉及, 知道即可)

Step4: -> Code Generation -> Code Fragment

将Intermediate Format转换为另一种格式, 比如MIPS或者二进制文件, 可与上一步同步进行.

作业中对应: A9 A10, A3, A4

Step5: Code Fragements -> Linking -> Executable File(Single File)

将多个compile好的多个文件链接在一起, 生成一个可执行的二进制文件(或仅生成合并以后的单个文件, 但文件本身可能无法执行)

作业中对应: A5 P1, P2

附: 09FALL 第二题答案

1. Scanning
2. Parsing
3. Semantic Analysis
4. Parsing
5. Semantic Analysis
6. Linking
7. Semantic Analysis
8. Parsing
9. 1A@#SR%$#
10. + foo
11. x