论文部分内容阅读
[摘要]编译原理课程是高校计算机类专业的重要的基础和骨干课程。而语义分析又是编译原理课程重点中的难点。它设计了抽象机模型，使用抽象机的操作行为描述程序设计语言的语义。针对传统的分支和循环语句，分析了控制结构的抽象，提出了分支和循环控制语句的语义模型。在编译原理课程的教学中，有效地帮助学生理解了语义分析的原理和技术。
[关键词]编译原理 控制结构 语法制导翻译 语义模型
一、引言
编译原理是计算机学科中少有的从实践到理论，再从理论到实践的一门专业课程。编译技术不断进步，已经成为计算机科学中发展最迅速、最成熟的一个重要分支。编译技术集中体现了计算机科学发展的重要成果与精华。程序语言及其编译的研究在计算机科学中始终处于非常重要的地位。
在语言及编译理论中，文法(BNF)和语法图已成为语言语法描述的典型工具，但语义描述至今尚无人们普遍接受的典型描述工具。采用操作语义学的方法来描述语义，即以一个抽象机的行为来描述语言的各个结构的作用和含义。
二、抽象机
抽象机由一个指令指针ip、一个存储器、一个控制器和一个运算器组成。
抽象机一旦启动，由专门的装入程序将一个要运行的程序装入代码存储器中，并置ip指向该程序的第一条指令。然后依次完成下述工作：
(1）执行ip所指向的指令。
(2）修改ip的内容。
若所执行的指令已修改过ip，则不再修改ip；若所执行的指令未修改ip，那么修改ip使之指向下一条指令，即 ip:=ip+1。
(3）若ip指向特殊的STOP指令，则终止执行，否则转回执行（1）。
假设抽象机对各种程序设计语言所常用的运算符（如＋，-，*，/，＞,＜,>=等）都有相应的指令与之对应。因此，只要知道抽象机操作的语义，也就知道了语言结构的语义。
为了显示修改ip的内容，抽象机提供两种特殊的转移指令：无条件转移指令（goto L）和条件转移指令（if B goto L）。
三、语法制导翻译
源程序的句子经过词法分析和语法分析后，已将词法错误和语法错误检查出来，并由程序员进行了修正，得到语法上正确的句子，下一步对这些语法上正确的句子，按照句子的语义规则进行语义分析，其目的是生成代码并实现其语义。因此，语义分析与代码生成是紧密相关的。为便于移植和优化，将句子翻译成抽象机的指令形式，称为中间代码，经过优化后再翻译成目标代码。最终的目标代码质量较高，并可以提高执行效率。
在语法分析过程中，根据每个产生式所对应的语义子程序（语义动作）进行翻译（生成中间代码）的方法称为语法制导翻译。
四、控制结构的抽象
顺序、选择和重复可以帮助程序员组织语句的控制流程，是基本控制工具。顺序是按计算机程序计数器提供的顺序获得指令的一种抽象。选择和重复是对硬件显式修改程序计数器的值，实现无条件转移和条件转移的抽象，这样的控制既简单又有效。抽象控制结构比显式控制转移修改指令计数器的低级控制机制更好些，它更面向问题，有利于程序设计。程序员通过使用顺序、选择和重复的一般模式就能较好地表达他们的意图。
高级语言结构最终还是要翻译成传统计算机的条件转移和无条件转移机器代码。将由编译程序生成有效的中间代码，而编译程序必须利用转移指令将控制抽象进行具体化。
分支控制结构允许程序员在某些可选择的语句中做出一种选择来执行。有两种基本的分之控制结构：单选控制（if…then…）和二选一控制（if…then…else…）。
循环控制结构允许程序员控制某些语句可以执行0次或多次。
五、语义模型
（1）单选控制结构语句 if B then S
对应的控制可以表示为（中间代码形式）
if B goto B.T
goto S. next
B.T:
┇//语句S对应的中间代码段
S.next:
表示为语义模型如图1所示。
其中，曲线表示语句S1对应的可能的中间出口转移。
（2）二选一控制结构语句if B S1else S2
图2 if B S1else S2语句的语义模型
对应的控制可以表示为（中间代码形式）
if B goto B.T
goto B.F
B.T:
┇//语句S1对应的中间代码段
goto S. next
B.F:
┇//语句S2对应的中间代码段
S.next:
表示为语义模型如图2所示。
其中，曲线表示语句S1和S1对应的可能的中间出口转移。
（3）循环控制结构语句 while B do S
图3while B do S 语句的语义模型
对应的控制可以表示为（中间代码形式）
again: if B goto B.T
goto S. next
B.T:
┇//语句S对应的中间代码段
goto again
S.next:
表示为语义模型如图3所示。
六、语义子程序
根据控制语句的语义模型，容易得到分支、循环控制语句的语义子程序。以二选一控制结构语句为例。
(1)M→if B then{backpatch（B.T，ip)； M.CHAIN=B.F；}
(2)N→M S1 else{q=ip； emit（goto 0）；backpatch（M.CHAIN，ip）；
N.CHAIN=merge（S1.CHAIN，q）；}
(3)S→N S2{S.CHAIN=merge（S2.CHAIN,N.CHAIN）；}
七、总结
编译原理中的语义分析是难以理解和掌握的，语义描述的传统方法是流程图，但没有对控制转移部分进行显示的标注，单凭流程图进行语义子程序的构造，学生普遍难以接收。而采用语义模型的表示，直观地表达了控制转移，对文法产生式的改写和语义子程序的构造提供了清晰的思路，实践表明，在编译原理课程的教学中，有效地帮助学生理解了语义分析的原理和技术。
参考文献：
[1]蒋宗礼，姜守旭.形式语言与自动机理论[M].北京:清华大学出版社，2007.
[2] 龚天富.语言及编译[M].北京:电子工业出版社，2003．
[3]Andrew W.Apple.现代编译器的Java实现[M].北京:电子工业出版社，2004.
[4]Dick Grune etc.Modern Compiler Design[M].JOHN WILEY&SONS，LTD，2002.
[5]余胜泉，张建伟.信息时代的教学与实践[M].北京:高等教育出版社，2005.
（作者单位：四川电子科技大学）
[关键词]编译原理 控制结构 语法制导翻译 语义模型
一、引言
编译原理是计算机学科中少有的从实践到理论，再从理论到实践的一门专业课程。编译技术不断进步，已经成为计算机科学中发展最迅速、最成熟的一个重要分支。编译技术集中体现了计算机科学发展的重要成果与精华。程序语言及其编译的研究在计算机科学中始终处于非常重要的地位。
在语言及编译理论中，文法(BNF)和语法图已成为语言语法描述的典型工具，但语义描述至今尚无人们普遍接受的典型描述工具。采用操作语义学的方法来描述语义，即以一个抽象机的行为来描述语言的各个结构的作用和含义。
二、抽象机
抽象机由一个指令指针ip、一个存储器、一个控制器和一个运算器组成。
抽象机一旦启动，由专门的装入程序将一个要运行的程序装入代码存储器中，并置ip指向该程序的第一条指令。然后依次完成下述工作：
(1）执行ip所指向的指令。
(2）修改ip的内容。
若所执行的指令已修改过ip，则不再修改ip；若所执行的指令未修改ip，那么修改ip使之指向下一条指令，即 ip:=ip+1。
(3）若ip指向特殊的STOP指令，则终止执行，否则转回执行（1）。
假设抽象机对各种程序设计语言所常用的运算符（如＋，-，*，/，＞,＜,>=等）都有相应的指令与之对应。因此，只要知道抽象机操作的语义，也就知道了语言结构的语义。
为了显示修改ip的内容，抽象机提供两种特殊的转移指令：无条件转移指令（goto L）和条件转移指令（if B goto L）。
三、语法制导翻译
源程序的句子经过词法分析和语法分析后，已将词法错误和语法错误检查出来，并由程序员进行了修正，得到语法上正确的句子，下一步对这些语法上正确的句子，按照句子的语义规则进行语义分析，其目的是生成代码并实现其语义。因此，语义分析与代码生成是紧密相关的。为便于移植和优化，将句子翻译成抽象机的指令形式，称为中间代码，经过优化后再翻译成目标代码。最终的目标代码质量较高，并可以提高执行效率。
在语法分析过程中，根据每个产生式所对应的语义子程序（语义动作）进行翻译（生成中间代码）的方法称为语法制导翻译。
四、控制结构的抽象
顺序、选择和重复可以帮助程序员组织语句的控制流程，是基本控制工具。顺序是按计算机程序计数器提供的顺序获得指令的一种抽象。选择和重复是对硬件显式修改程序计数器的值，实现无条件转移和条件转移的抽象，这样的控制既简单又有效。抽象控制结构比显式控制转移修改指令计数器的低级控制机制更好些，它更面向问题，有利于程序设计。程序员通过使用顺序、选择和重复的一般模式就能较好地表达他们的意图。
高级语言结构最终还是要翻译成传统计算机的条件转移和无条件转移机器代码。将由编译程序生成有效的中间代码，而编译程序必须利用转移指令将控制抽象进行具体化。
分支控制结构允许程序员在某些可选择的语句中做出一种选择来执行。有两种基本的分之控制结构：单选控制（if…then…）和二选一控制（if…then…else…）。
循环控制结构允许程序员控制某些语句可以执行0次或多次。
五、语义模型
（1）单选控制结构语句 if B then S
对应的控制可以表示为（中间代码形式）
if B goto B.T
goto S. next
B.T:
┇//语句S对应的中间代码段
S.next:
表示为语义模型如图1所示。
其中，曲线表示语句S1对应的可能的中间出口转移。
（2）二选一控制结构语句if B S1else S2
图2 if B S1else S2语句的语义模型
对应的控制可以表示为（中间代码形式）
if B goto B.T
goto B.F
B.T:
┇//语句S1对应的中间代码段
goto S. next
B.F:
┇//语句S2对应的中间代码段
S.next:
表示为语义模型如图2所示。
其中，曲线表示语句S1和S1对应的可能的中间出口转移。
（3）循环控制结构语句 while B do S
图3while B do S 语句的语义模型
对应的控制可以表示为（中间代码形式）
again: if B goto B.T
goto S. next
B.T:
┇//语句S对应的中间代码段
goto again
S.next:
表示为语义模型如图3所示。
六、语义子程序
根据控制语句的语义模型，容易得到分支、循环控制语句的语义子程序。以二选一控制结构语句为例。
(1)M→if B then{backpatch（B.T，ip)； M.CHAIN=B.F；}
(2)N→M S1 else{q=ip； emit（goto 0）；backpatch（M.CHAIN，ip）；
N.CHAIN=merge（S1.CHAIN，q）；}
(3)S→N S2{S.CHAIN=merge（S2.CHAIN,N.CHAIN）；}
七、总结
编译原理中的语义分析是难以理解和掌握的，语义描述的传统方法是流程图，但没有对控制转移部分进行显示的标注，单凭流程图进行语义子程序的构造，学生普遍难以接收。而采用语义模型的表示，直观地表达了控制转移，对文法产生式的改写和语义子程序的构造提供了清晰的思路，实践表明，在编译原理课程的教学中，有效地帮助学生理解了语义分析的原理和技术。
参考文献：
[1]蒋宗礼，姜守旭.形式语言与自动机理论[M].北京:清华大学出版社，2007.
[2] 龚天富.语言及编译[M].北京:电子工业出版社，2003．
[3]Andrew W.Apple.现代编译器的Java实现[M].北京:电子工业出版社，2004.
[4]Dick Grune etc.Modern Compiler Design[M].JOHN WILEY&SONS，LTD，2002.
[5]余胜泉，张建伟.信息时代的教学与实践[M].北京:高等教育出版社，2005.
（作者单位：四川电子科技大学）