谈谈形式语言与编译课程

2018-04-25赵银亮戴慧珺

计算机教育 2018年4期

赵银亮，戴慧珺，李昊，李波

（西安交通大学电子与信息工程学院，陕西西安 710049）

1 背景

编译原理课程由来已久，至今仍然是计算机专业主干课程。笔者经过长期的教学实践，观察到与本课程有关的教学问题，概括为以下四个。

问题一：现有的编译原理课程在内容上存在理论完整性不足，使学生产生“知其然不知其所以然”的困惑。编译原理课程中介绍程序分析变换和优化技术的部分，涉及程序语言理论和大量具体方法，从教学方法上有强调理论性和强调技术实现两个极端[1]。为了降低课程难度，授课教师一般直接使用形式语言理论的相关结论来解决词法和语法分析问题，课程并不覆盖形式语言理论，结果造成课程所包含的理论内容不够完整。

问题二：对于编译原理课程在课程体系中的地位存在着不同观点，让课程体系设计者陷入决策困境。这里罗列一些观点：编译原理是最有价值的课程之一[2]，课程太抽象、难度太大[3]，对开设该课程的必要性存在质疑[4-5]，该课程是其他课程的综合练习[2]，等。这些观点导致编译原理课程的开设与不开设都在两可之间，且实际情况也是如此。

问题三：编译原理课程虽然属于计算机科学基础理论范畴，但一般没有在大学前两个学年的课程中出现，影响了计算机专业学生对于基础理论的掌握。通常认为，大学前两年是基础理论学习和综合素质培养阶段，如西安交通大学的“2+4+X”模式等。在课程体系设计中，前两年的候选课程很多，但没有编译原理课程，导致计算机专业学生基础理论的掌握减弱，不利于后续专业课程的学习和能力培养。

问题四：在学科快速发展和课程学时数被压缩这一背景下，与其他课程内容重叠问题变得日益明显。目前，计算机学科知识构成呈现多样化趋势，这就要求许多新的课程加入到课程体系中来，必然造成已有课程总学时数呈现下降趋势。III型和II型语言理论作为编译原理课程与形式语言与自动机课程的共同相关部分，自然面临合并和优化设计问题。

2 对存在问题的分析与求解

2.1 课程的理论完整性

现有编译原理课程的理论完整性不足表现在几个方面：①在词法分析器设计中使用了有限状态自动机，但没有完整包括正则语言的判定性理论；②介绍的语法分析框架，没有明确给出理论依据；③语义分析使用的是语法制导翻译方法，仅在方法学上将属性文法与分析框架进行了集成；④基于工具自动生成词法与语法分析器，没有生成原理的介绍；⑤选择性介绍类型检查、类型推理的具体实现，没有类型理论的系统介绍；⑥介绍运行环境的实现，没有介绍程序语义支持。

为了有助于学生融会贯通课程知识，在课程中阐明理论依据是必要的。解决的方法是完整引入相应理论，并将原有内容与这些理论结合起来。此外，由于课时的限制和降低课程难度的要求，谨慎选择较复杂的理论（如类型理论和语义学等），转而求助于课程体系层面的解决方法。

2.2 课程定位与作用

引起课程定位与作用模糊问题是有客观原因的：一方面，经过计算机系统的早期发展，编译器技术已经相对成熟稳定，尽管随着体系结构演变也在缓慢发展，但与计算机技术整体快速发展相比，可以认为处于相对停滞状态，因而直接相关的工作岗位需求也少；另一方面，几乎所有软件和计算系统都由程序构成，程序决定计算机应用的几乎所有方面，所以，编译原理课程所介绍的程序分析变换和优化是计算机科学与技术的基础。此外，编译技术还是软硬件协同设计的组成部分，也是计算机系统发展的支撑技术，其重要意义不言而喻。另外，从人才培养模式的角度也能找到存在这种问题的原因。一般观点认为大学“2+2”模式分别注重基础培养和专业培养，但编译原理课程一般在大三开设，因而不能归为基础理论环节，从而错过对学生进行相关抽象思维能力培养的最佳时间节点。

综上分析，可以使用如下判据解决问题：①课程的类型归属：强调理论性的课程还是技术基础课程？②课程内容选择范围：作为系统软件关注设计方法还是软硬件实现细节？③本课程对于专业课程的作用：作为理论基础课程还是专业技术课程？④课程的难易程度：偏重抽象的形式化描述还是实现细节？⑤与其他课程的关系：是独立的有内涵的课程还是其它课程的综合练习？

事实上，对这些判据的不同回答就构成了各自特色的编译原理课程，本文的形式语言与编译课程在构建过程中选择每个判据中的第一个选项，由此明晰了课程定位和作用。

2.3 课程内容重叠

编译原理课程与形式语言理论、语言范型和类型系统等先修课程发生重叠，前者涉及该课程核心，后者是编译需求。编译原理课程也与系统类课程发生重叠，如指令系统、程序映像、优化技术等，属于技术细节层面重叠。

为了消除与其他课程重叠，可采用多种方法：第一种是课程体系设计层面的解决方法，结合课程进度和侧重点，分别落实客观的重叠知识点，分配给相应课程，这种方法对解决课程群间的内容重叠有效，比如采用课程之间互相兼顾、优化系统类课程群等方法。第二种方法是避免重复先修课程的内容，该方法适用于解决人为造成的与离散数学和数据结构课程的重叠，比如不要试图将编译原理课程设计为先修课程的综合练习。最后一类方法是将其他课程内容合并到本课程中，该方法适用于消除和形式语言与自动机、程序设计等课程的重叠，该方法的副作用是容易导致课程名称和内涵发生重构。

运用以上三种消除重叠的方法，编译原理课程内容的合理性得到优化，优化后的内容涵盖了完整的形式语言理论，所以其名称也必将发生变更，形成了形式语言与编译课程，就是本文标题所指。考虑到程序设计语言也是形式语言，将原有的程序设计语言的编译原理课程改名为形式语言与编译课程并不会破坏一致性，反而更有普遍适用性。

3 课程内容与教学过程设计

课程内容与教学过程设计本着简单的设计原则：控制课程难度，将原理与实现分开，由课时数限定理论内容的选择。课程内容选择如图1所示。

在图1中，形式语言与编译课程的内容一部分取自形式语言与自动机课程，另一部分为重新设计的编译原理课程的词法分析、语法分析和语义分析部分，所形成的形式语言与编译课程可以看作是对原有两门课程的合并。

形式语言与自动机课程中余下的内容属于计算导论中的高级内容，必要时可以作为高年级选修课程独立设课；编译原理课程中的代码优化和代码生成也是专业重要内容，也可以作为选修课单独设课或编译原理高级专题讲座内容。

图1 课程设计方案

这个设计方案突出了课程的理论性，另外从专业技术内容角度考虑，编译原理核心部分中的编译器设计与实现仍然作为实验教学单独设课，即编译器设计专题实验课程，以此训练学生阅读编译源代码并进行词法分析、语法分析、语义分析和代码生成方面的动手能力，达到对编译器技术层面的掌握。

3.1 形式语言与编译课程的内容设计

1）完整引入III型和II型语言理论。

III型语言理论包括DFA、NFA、ε-NFA、GNFA、r、文法、正则语言、等价性；II型语言理论包括CFG、推导、归约、语法树、PDA、PDA与CFG等价性、CFL性质、范式等。这部分内容移自形式语言与自动机课程。

2）更新词法分析。

利用正则语言判定性从输入流中识别单词符号，只需很少保留编译原理的词法分析内容。更新后的内容包括词法分析器框架、单词符号设计、多DFA集成设计、词法分析器自动生成等。

从源程序中识别词法单位的方法涉及一个通用的框架（见图2），图2中的判定框是框架的核心，用形式语言的方法决定输入串所属的词法单位。图中附加处理框表示对接受的输入串进行额外处理，包括将识别出的符号串转换为内部表示或者插入符号表，并对不接受的输入串进行错误处理。框架中的前处理部分也叫预处理，是对源程序文本进行一定程度的清洗（如删除注解、规范空白字符等），之后才提供给判定框处理。框架中的后处理是将判定结果和附加处理结果构造成单词符号并按照某种方式呈现出来，如保存在文件中或者返回给语法分析等。这个识别框架体现了词法分析的原理与通用性。

多DFA集成设计解决了同时识别源程序中多个词法单位的问题，具体方法是构造判定词法单位的自动机，将识别每个词法单位的DFA集成为一个DFA。算法[6]的输入是需要识别的单词符号，它们属于那些由序列中的正则表达式r0, ...,rn-1定义的词法单位（种属），而输出就是集成后的DFA。

3）更新语法分析。

这个算法正确工作的条件是∩iL(ri)=ϕ；如果x∈L(ri)且xy∈L(rj)，那么x优先被识别为单词符号，当然这个条件还可以放松，将识别更灵活的语言如Lisp词法单位。这部分最主要的改变是增加了项目下推自动机IPDA作为自上而下分析和自下而上分析统一的理论依据。

上下文无关文法G 的IPDA 为 (itemG,T,itemG,Δ, [S'→·S], [S'→·S], {[S'→S·]})，其中迁移函数分为 (E)Δ([A→α·Nη],ε)={[A→α·Nη][N→·γ]| (N,γ)∈Ρ}、(S)Δ([A→α·aη], c)={[A→αa·η]}和 (R)Δ([A→α·Nη][N→·γ],ε)={[A→αN·η]} 三类（IPDA 中状态与栈顶符号相同）[6]。

自上而下分析是E-迁移对应于推导。自下而上分析使用了IPDA的栈作为状态栈，当前栈顶元素为当前状态，对于IPDA的三种迁移，符号栈进行相应地操作：(E)符号栈没有动作；(S)符号栈压入a；(R)符号栈弹出|γ|个符号, 然后压入N。

形式语言与编译课程的理论完整性体现在III型和II型语言理论完整。词法分析基于III型语言的判定性，自上而下和自下而上的语法分析被统一在项目下推自动机上，而语义分析仍采用语法制导的翻译原理，并与IPDA结合起来，中间代码生成和运行时环境归属到语义分析中，本身是完整的形式化代码变换和优化设计。

图2 词法单位的识别框架

4）更新语义分析。

沿用编译原理中语法制导的语义分析，具体基于IPDA 来描述，假定当前项目为[A→α·Xη],当X=a时采用 S-迁移，Δ(-,a,ρ[A→α·aη])={(-,ρ[A→αa·η])}，相应的属性求值工作是，将词法分析器返回的结果作为a的综合属性的值。当X=B时采用 E-迁移，Δ([A→α·Bη],ε,ρ)={(-,ρ[B→·γ]) | (B,γ)∈Ρ}，对于新栈顶 [B→·γ]根据规则γ中所有符号的综合属性已经算出值，同时B的继承属性也已经求过值。

对于完全项目 [B→γ·]采用 R-迁移，Δ(-,ε,ρ[A→α·Bη][B→γ·])={(-,ρ[A→αB·η])}，这时γ中所有符号的综合属性已经算出，同时B的继承属性也已经求出。所以，B的综合属性的值应根据该产生式的语义规则进行计算作为该项目A→αBη中B的属性值。

3.2 形式语言与编译课程的教学过程设计

教学过程见表1。

表1 形式语言与编译课程的教学过程

4 效果评价

采用两种方法评价该课程效果，一种是分析的方法，另一种是实现并通过学生成绩进行评价。

4.1 方案分析

1）涵盖完整的理论和原理。

编译原理课程使用形式语言的有关结论解决词法语法分析的问题，但没有完整描述为什么这么做以及这样做为什么可以，使教学内容变成为一种技术要求学生掌握或记住，既会引起有用无用的疑问，也容易造成学生不知道所以然。本方案试图改变这一状况。以有穷自动机为例，编译中介绍的NFA映射函数δ是一个从 S×Σ*至2S的映射，这种表示给引入NFA接受串、扩展迁移函数、DFA等价性的概念显著增加了复杂度。往往最基本的形式是最有用的，也是最重要的，所以III型语言理论包含最基本的NFA（δ为从 S×Σ至2S的映射）和ε-NFA（δ为从S×Σ{ε}至2S的映射），并包括一般化的GNFA（弧上标记为正则表达式）。更重要的是，组成该理论的定理及其证明建立了计算的模型，这些理论不仅用于解决编译中的问题，也用于解决计算机科学中的其他问题，具有广泛意义，借此在教学过程中培养学生观察现象、认识规律和发现规律的能力。

2）在正确的时间节点上培养学生抽象思维能力。

抽象是计算的基本属性，抽象思维能力是计算机专业人才培养的重点之一。学习抽象知识是培养抽象思维能力的途径。

形式语言与编译课程的内容有很高的抽象性：首先，来自于编译原理的部分，因为它是关于程序分析变换和优化的，相比程序设计属于元级处理，其抽象性在教学实践中也已有共识；其次，就是形式化计算模型，包括III型和II型语言理论、类型系统、还包括形式语义学。形式语言与编译课程的抽象性表现在上述两个方面，单纯的理论性课程和专业核心课程最多包括一个抽象性方面，因此，该课程是培养计算机专业学生抽象思维能力的主要课程之一。

能力培养的重点在大学4年各阶段有所不同，从培养方案可以看出有多种模式：典型的“1+3”方案，即1年通识教育加上3年专业教育；另一种是“2+4”，即2年基础教育加上4年专业教育。大一大二是理论基础建立的黄金时段，过后由于专业课程加重且课程更关注方法论和技术层面的知识，导致理论基础变得没有弥补和扩展的空间，而且，后期也到了理论知识发挥潜在作用的时候。

培养方案的设计者面临将部分课程作为前2年课程的选择，他们往往站在学校的高度做决策，因此像电工实习、金工实习、工程制图、生命科学基础、数学建模等课程被选中，在这种情况下，也需要选择计算机理论基础课程。形式语言与编译课程在大二下学期开始，就提供了这类选择性。

表2是计算机专业2015级学生第4学期课表（2016—2017学年第2学期），从中可以看出通识课程占比情况。一般情况下，传统编译原理课程在大三作为专业课开设。本方案只是在时间上往前提前了一个学期，但课程性质发生了变化，即从专业课变成作为理论基础课，实现了在正确的时间节点上培养学生抽象思维能力的教学目标。

4.2 形式语言与编译课程的实现效果

该课程设计结果列入西安交通大学最新版培养计划，面向2015级计算机班、少年班（选修）和钱学森班（选修），于2016—2017学年第2学期开课。

期末笔试试题共有9道题，全面覆盖课程内容。各题描述及得分情况如表3所述。

在表3中，除了第8题外，各题平均得分和分数分布正常。第4题平均得分较高，说明形式语言部分掌握较好，与学生反馈也吻合。第8题失分原因归结为方案多、教材不配套和时间紧3点，其中方案多是指要求掌握多个活动记录方案（如fp-sp活动记录格式[7]和sp-top格式[8]），并学会栈式存储的设计原理，相比以往提高了要求。笔者计划通过提供配套教材并放弃sp-top格式来解决。表4、表5、表6是各班级成绩汇总，其中只包括计算机2个班。

从各班成绩来看，分布基本合理，总体上达到成绩良好。

与此课程配套的专题实验课采用引进斯坦福大学COOL实验平台以及题目，结果得分情况正常，而少年班完成效果最好，平均分在90分以上。表明从编译器设计角度来看，本课程设计合理，能够为大二学生所接受。