企业官网建设流程全解析

软考软件设计师上午题一共75道选择题，涉及的知识面铺得非常广。很多人复习到“程序设计语言基础知识”这一章时，都会有同样的感觉：内容不难，但概念太细，编译原理相关的几个阶段总是看完就混，文法那四种类型更是容易在考场上突然卡壳。这一章在试卷中的分值不算高，历年一般稳定在2到4分左右，但它是少有的“投入产出比”比较高的章节——只要把几个核心概念梳理清楚，这几分的到手难度远低于数据结构里的算法题，也低于设计模式里的代码辨析题。

这篇文章，我把自己备考时整理的程序设计语言基础笔记做一个系统的输出，重点讲清楚编译过程的六个阶段怎么区分、四种文法怎么判断、中间代码几种形式怎么转换这些核心考点，同时补充一些真题里反复出现的陷阱。不管你是第一次考还是二战冲刺，这一篇吃透，这一章的选择题基本就稳了。

1. 考情定位：这几分到底值不值得花时间

先说结论：值得，而且性价比极高。软考软件设计师上午题的知识模块大概有十几个，像软件工程、数据库、操作系统这些章节，每一章的分值都很高，但对应的复习量也大。程序设计语言基础这章虽然分值不高，可它的核心考点是非常收敛的——翻十年真题就能发现，翻来覆去也就那么几个点：语言分类，编译和解释的区别，编译各阶段的职能，文法类型判断，正规式，后缀式和四元式。这些内容一旦理解了，基本不会忘，比死记硬背各种协议端口稳得多。

这一章适合花的时间，我的建议是3到4个小时左右。第1个小时过一遍教材上的基础概念，第2个小时重点吃透编译过程的六个阶段和文法判断，第3个小时刷历年真题中所有涉及本章的题目。如果基础比较好，大学期间学过《编译原理》的课程，哪怕已经忘得差不多，捡起来也很快。如果是零基础的非科班考生，这部分也完全不用担心——软考考的是基础概念，不是让你真去写一个编译器，不需要啃晦涩的算法推导。

有一点要提前说清楚，这一章的知识点之间是有内在逻辑链条的。程序语言从高级语言写出来到能在机器上运行，中间必须经过“翻译”这一步，而翻译的过程拆开来看，就是词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成这六个阶段。理解了这条主线，后面所有的零散考点其实都可以串起来，不需要死记。

2. 程序设计语言核心概念：从机器码到高级语言

这一节的内容在真题中通常以概念辨析的形式出现，难度不大，但偶尔会挖一些细节坑。

2.1 语言层次：机器语言、汇编语言与高级语言

机器语言是计算机硬件直接识别和执行的指令，由0和1组成的二进制代码构成。不同的CPU体系结构对应不同的机器指令集，所以机器语言是特定于硬件的，几乎没有可移植性。机器语言程序可以直接被CPU执行，不需要任何翻译，这也是它执行效率最高的原因，但写程序的难度也最高。

汇编语言是对机器指令的符号化表示，比如用MOV、ADD这样的助记符代替操作码，用变量名代替内存地址。汇编语言仍然面向具体的机器，每条汇编指令基本对应一条机器指令。它比机器语言好写、好读，但在不同平台之间依然无法直接移植。汇编程序写完后，需要一个“汇编程序”来把它翻译成机器语言，这个翻译过程基本是“一对一”的，相对简单。

高级语言则是面向问题、面向过程的描述语言，跟具体的机器结构解耦。C、C++、Java、Python都属于高级语言。高级语言的一条语句往往对应多条机器指令，所以不能再直接翻译，而需要一个更复杂的翻译系统，也就是编译程序或解释程序。高级语言的优势在于可移植性强、表达能力强、开发效率高，代价是执行效率相对汇编语言低一些，且翻译过程更复杂。

真题里偶尔会考一个比较冷的知识点：汇编语言实质上是机器语言的符号化表示，低级语言包括机器语言和汇编语言。这个说法要记住，很多人在“低级语言”和“高级语言”之间只记得后者，但低级语言判断题也会出现。

2.2 程序语言的基本成分

教材上把程序语言的基本成分归纳为四类：数据成分、运算成分、控制成分和传输成分。

数据成分描述的是程序中涉及的数据对象，包括数据的类型（整型、实型、字符型、布尔型）和数据的组织形式（常量、变量、数组、结构体、指针等）。变量就是内存中有名字的存储单元，变量名实际上是对存储地址的符号化引用。常量的值在程序运行期间不会改变，包括直接写的字面量，也包括用名字定义的符号常量。

运算成分描述的是程序中允许执行的运算操作。不同的程序设计语言支持的运算符集合不同，但一般都包括算术运算、关系运算、逻辑运算、位运算和赋值运算。表达式中运算符的优先级和结合性是考点之一，比如乘除优先于加减，括号优先级最高，赋值运算符是右结合的。

控制成分用来控制程序执行的流程。三种基本控制结构是顺序、选择和循环。顺序结构就是按照语句出现的先后顺序依次执行；选择结构根据条件判断执行不同的分支，比如if-else和switch-case；循环结构在满足条件时重复执行一段代码，比如while循环、for循环、do-while循环。这里注意，程序设计理论里一个经典结论是：任何程序都可以用顺序、选择、循环三种基本结构组合来实现，不需要额外的控制手段。

传输成分用于处理数据的输入输出以及程序之间的数据传递。在C语言中就是printf、scanf这些输入输出函数，在面向对象语言中还包括函数调用时的参数传递。参数传递有值传递和引用传递（地址传递）之分——按值传递时，形参拿到的是实参的一个副本，函数内修改形参不影响实参；按地址传递时，形参和实参指向同一个存储单元，函数内修改形参，实参也会跟着变。这是程序语言基础里少有的能够结合编程实践出选择题的点。

2.3 常见考查方式

这一小节在选择题里出题方式比较直白。一种是题干给出一个描述，问属于哪一种语言层次，比如“能够被计算机硬件直接识别并执行的语言是”，答案是机器语言。另一种是问程序语言的基本成分有哪些，选项里混入“算法成分”或者“数据结构成分”这类干扰项。还有一种就是把参数传递方式结合代码片段来考，给出一个简单的程序，问某个变量在调用前后的值。

复习这一部分的时间不用太长，关键是把概念搞清楚，看到选项能立刻判断正误就行。

3. 语言处理程序三兄弟：汇编、编译与解释

高级语言程序写出来之后，计算机无法直接执行，必须经过某种“翻译”变成机器指令。完成翻译工作的程序统称为语言处理程序，主要包括汇编程序、解释程序和编译程序。这三者之间的区别是本章的高频考点，几乎每年都考一次。

3.1 汇编程序：1对1的符号翻译

汇编程序的作用是把汇编语言源程序翻译成可执行的机器语言程序。汇编语言的指令与机器指令基本一一对应，所以翻译过程比较简单。它主要做两件事：一是把助记符操作码翻译成对应的机器操作码，二是把符号地址（也就是变量名、标号）转换成具体的存储地址。

汇编过程中会产生一个很重要的表，叫符号表，用来记录源程序中的符号及其对应的地址。这部分知识在后面编译原理部分还会出现，可以先留个印象。

考试中对汇编程序的考查不会太深，主要是区分汇编程序和编译程序的对象不同——汇编处理的是汇编语言，编译处理的是高级语言。

3.2 编译程序：整体翻译再执行

编译程序的高级语言处理方式是“整体翻译，然后执行”。它的输入是高级语言写的源程序，输出是等价的机器语言程序（目标程序）。翻译的过程是完整的、一次性完成的，翻译结果可以在之后反复多次运行，每次运行不再需要重新翻译。

正因为是先整体翻译再运行，编译方式执行的程序运行效率相对较高。程序的执行过程分成了“编译期”和“运行期”两个阶段，编译期内做一些静态的检查和分析，比如语法检查、类型检查，这些错误会在编译阶段就能被发现并报告给程序员。

典型的编译型语言包括C、C++、Java（Java其实是半编译半解释的，先编译成字节码，再由虚拟机解释执行，这个特例偶尔也考）、Pascal等。C语言的源程序经过编译生成.obj目标文件，然后链接成.exe可执行文件，整个过程就是典型的编译方式。

3.3 解释程序：边翻译边执行

解释程序处理高级语言的方式是“逐句翻译，逐句执行”，整个过程不生成独立的目标程序。解释程序读取一行源代码，翻译成机器指令，然后立刻执行，执行完再去读下一行。就像同声传译一样，翻译和内容是同步推进的。

解释方式的好处是灵活性高，跨平台性好，程序出错时能立刻定位到出错的行，便于调试。缺点是执行效率低，因为每运行一次程序，都要重新把每一行源代码重新翻译一遍。典型的解释型语言有Python、JavaScript、Ruby等。

这个区别要记住一个非常贴切的类比：编译方式就像先把整本书翻译成中文再阅读，解释方式就像请了一个翻译，你说一句他翻一句。

3.4 编译与解释的对比速查

真题里关于这个对比的设问方式很灵活，有的直接问“下列哪个语言采用的是解释执行方式”，有的给出一段描述让考生判断说的是编译还是解释。特别注意Java这个特例，它介于两者之间：源程序先编译成平台无关的字节码，字节码再由Java虚拟机解释执行。出题人偶尔在这种特例上做文章，题干会写“既编译又解释”、“先编译后解释”之类的话。

4. 编译过程逐段拆解：六个阶段各自干什么

编译原理是这一章最核心的内容，也是很多考生觉得难的地方。但软考对编译原理的要求并不高，不需要你会构造自动机，也不需要懂LR(1)分析表怎么生成，只需要你把六个阶段各自的输入、输出和主要职能搞清楚，能判断某个具体的编译动作属于哪个阶段。

一个编译程序的工作过程，可以分为六大阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。此外，还有符号表管理和出错处理这两个贯穿整个过程的辅助工作。

4.1 词法分析：把字符流拆成单词流

词法分析是编译过程的第一个阶段，它的输入是源程序的字符序列，也就是一个一个的字符；输出是单词符号序列。单词符号是程序语言的最小语义单位，包括关键字（如if、while、return）、标识符（变量名、函数名）、常数、运算符（+、-、*、/）和分界符（括号、逗号、分号）等。

词法分析做的事情，本质上就是“从左到右扫描源程序，按照语言的词法规则识别出每一个单词”。比如源代码里出现了一个字符串“int count = 10;”，词法分析器会把“int”识别为关键字，把“count”识别为标识符，把“=”识别为赋值运算符，把“10”识别为整型常数，把“;”识别为分号。

描述词法规则的数学工具是什么？是正规式（正则表达式）。正规式可以用来表示程序设计语言的单词结构，比如标识符的正规式通常可以写成“字母开头的字母数字串”，用一个正规式描述出来，再用有限自动机来识别它。这里要注意，词法分析阶段用的是正规式和有限自动机，语法分析阶段用的是上下文无关文法——这两者不能搞混，是真题的常客。

需要记住的典型词法错误包括：非法字符出现在源码里、标识符写法不符合规则、数字常量格式错误等。比如在C语言里写一个“123abc”当作标识符使用，这就是词法层面的错误。

4.2 语法分析：检查单词组合是否符合语法规则

词法分析把字符流变成了单词流，但单词怎么组合成合法的句子，就得靠语法分析。语法分析的任务是在词法分析的基础上，根据语言的语法规则（文法），把单词符号串分解成各类语法单位，比如表达式、语句、函数定义等，并检查这些单词的组合是否合乎语法。

简单说，词法分析回答的是“这些字符能否组成一个合法的单词”，语法分析回答的是“这些单词能否组成一个合法的句子”。语法分析通常以语法树（推导树）的形式来体现句子的结构。比如表达式“a + b * c”，根据乘法优先级高于加法的语法规则，语法分析树中b和c会先生成一棵子树，再和a组成加法结构。

描述语法规则的数学工具是上下文无关文法。上下文无关文法这个概念后面单独讲，这里先记住结论。

典型的语法错误有：缺少分号、括号不匹配、if语句的条件缺少括号、变量声明语句结构不完整等。这些错误不是单词本身写错了，而是单词的排列组合不符合语言规定的形式。

语法分析的主要方法分为两类：自上而下的分析法和自下而上的分析法。自上而下就是从文法的开始符号出发，尝试用产生式推导出给定的输入串；自下而上则是从输入串出发，尝试归约到文法的开始符号。记住名词和基本思想即可，软考很少考到具体的算法构造。

4.3 语义分析：检查程序的含义是否合法

语义分析是六个阶段中最容易和语法分析混淆的一个。语法分析只关心形式，不关心含义，比如“int a = 'hello';”在语法上完全没问题——它符合“类型+变量+赋值+值+分号”的语法结构，但在语义上就是非法的：把一个字符串赋给了整型变量。

语义分析的主要工作是检查程序中各种语法成分的含义是否合法，包括静态语义检查。最重要的静态语义检查就是类型检查，除此之外还有声明检查（变量是否先声明后使用）、控制流检查和一致性检查等。语义分析的结果是给每个语法单位标注上语义信息，比如变量的类型、表达式的类型。

举个经典的例子，在C语言中：

int a; float b; a = b + "str";

这里把字符串类型和float类型做加法再赋给int变量，语法上没有任何问题，但语义分析阶段会发现类型不匹配的错误。语义错误的本质是程序“看起来语法正确，但含义不对”。

区分词法错误、语法错误和语义错误，是考得最多的点之一。给你一段出错的代码，问错误发生在编译的哪个阶段被检出。记一个口诀：字符级错误多半是词法错误，结构级错误是语法错误，含义级错误是语义错误。

4.4 中间代码生成：让翻译过程有中间站

源程序经过词法、语法、语义分析之后，语义正确性已经确认，接下来需要生成目标代码。但直接从语法树生成机器代码会很复杂，因为机器代码的平台相关性太强。编译程序的处理方式是先生成一种与具体机器无关的中间表示形式，也就是中间代码。

中间代码的作用是：一方面便于后续的代码优化，另一方面屏蔽掉目标机器的差异，使编译程序的后续阶段可以独立于具体硬件来设计。中间代码的常见形式有后缀式（逆波兰式）、三元式、四元式、树形表示等。软考主要考后缀式和四元式，这个在后面专门展开。

以表达式“a + b * c”为例，它的后缀式是“a b c * + ”，四元式则表示为：

其中T1、T2是编译程序生成的临时变量。

4.5 代码优化：让目标代码更高效

中间代码生成之后，如果直接翻译成目标代码，程序能跑，但效率往往不高。代码优化的任务就是对中间代码进行等价变换，使得生成的目标代码运行时间更短、占用的存储空间更少。

代码优化依据优化范围可以分为三类：局部优化、循环优化和全局优化。局部优化是在基本块内（一段顺序执行的语句）进行的优化，比如删除公共子表达式、删除无用赋值、合并已知量等。循环优化是优化中最重要的部分，因为循环中的代码会被反复执行，哪怕减少一条指令，总体收益都很大。循环优化的主要技术包括代码外提（把循环体内不随循环变化的计算提到循环外）、强度削减（把代价高的运算替换成代价低的运算，比如把乘法变成加法）、删除归纳变量等。全局优化则是跨基本块的优化，涉及控制流和数据流分析。

这一节的考查形式比较浅，通常是问“下列哪项属于循环优化的方法”或者“局部优化的基本单位是什么”。记住基本块、循环优化三大技术这几个关键词就够了。

4.6 目标代码生成：形成机器指令

目标代码生成的输入是优化后的中间代码，输出是目标机器上的机器语言代码或汇编代码。这个阶段要完成指令的选择、寄存器的分配和调度等工作。

目标代码生成与具体的机器密切相关，所以不同硬件平台上的编译器，目标代码生成部分是不同的。这也是为什么同一个编译器在不同平台上需要分别实现的原因。目标代码可以是立即执行的机器语言代码，也可以是可重定位的机器代码（需要进一步链接和加载），还可以是汇编语言代码（还需要汇编程序再转换成机器代码）。

这个阶段的考点非常少，理解一句话就行：目标代码生成阶段把中间代码变换成特定机器上的机器指令序列。

4.7 符号表管理与出错处理

除了上面六大阶段，编译过程中还有两个贯穿始终的工作，一个是符号表管理，一个是出错处理。

符号表用来记录源程序中出现的每个标识符（变量名、函数名、类型名）的属性信息，包括名字、类型、作用域、存储分配信息等。符号表是编译过程中不可或缺的数据结构，词法分析阶段遇到新标识符时要登记，语义分析阶段要查表进行类型检查，目标代码生成阶段要查表确定存储位置。符号表管理的内容包括符号表的建立、查找和更新。

出错处理是当编译过程中发现源程序错误时，诊断错误、报告错误的位置和性质，并尽可能从错误中恢复，继续编译下去，一次编译发现尽可能多的错误。错误分为两类：一类是编译时能够发现的错误，包括词法错误、语法错误和静态语义错误；另一类是运行时错误，比如除数为0、数组越界访问、空指针引用，这类错误要到程序运行的时候才能暴露出来。

5. 形式语言与文法：最难啃但也是必拿分

形式语言理论这一节，很多人第一次看的时候一头雾水，什么终结符非终结符，什么0型1型2型3型，感觉像在看天书。但实际真题考得非常浅，主要就是给一个文法，让你判断它属于乔姆斯基分类中的哪一类。把四种文法的定义吃透，这类题就是送分题。

5.1 文法的基本定义

文法是形式语言的核心概念。文法G通常表示为一个四元组：G = (V_N, V_T, P, S)。其中：

• V_N是非终结符集合，这些符号代表语法成分，可以被进一步推导展开，习惯上用大写字母表示，比如S、A、B。
• V_T是终结符集合，这些符号是语言中不可再分割的基本符号，是最终出现在句子中的符号，习惯上用小写字母表示，比如a、b、c，或者数字、运算符。
• P是产生式（规则）的集合，形如 α → β，意思是α可以被替换成β。产生式是文法中最重要的部分。
• S是开始符号，它必须属于非终结符集合，是文法推导的起点。

推导就是从开始符号S出发，反复应用产生式中的规则，把非终结符逐步替换，直到最后得到的符号串完全由终结符组成。最终得到的这个终结符串就是该文法生成的一个句子。

整个语言，就是文法能够生成的所有句子的集合，记为L(G)。

5.2 乔姆斯基文法分类

乔姆斯基按产生式的形式限制，把文法分为四类：

0型文法（短语文法，PSG）对产生式没有任何限制，形式为 α → β，只要求α中至少含有一个非终结符，且α、β都属于符号串的集合。0型文法生成的语言称为0型语言，能力最强，能被图灵机识别。

1型文法（上下文有关文法，CSG）产生式形如 αAβ → αγβ，其中γ不能为空串。本质含义是：只有当非终结符A出现在上下文α和β之间时，才能被替换成γ。比如“aSb → aaSbb”这种形式，S的替换取决于它前后的符号，所以叫上下文有关。1型文法生成的语言能被子线性界限自动机识别。

2型文法（上下文无关文法，CFG）产生式形如 A → β，也就是左部必须是一个单独的非终结符，右部可以是任意符号串，但不能为空串（有些教材允许空串产生式，软考一般不涉及这个细节）。它的特点是替换一个非终结符时，不需要考虑这个符号出现的上下文，所以叫上下文无关。程序设计语言中大多数语法结构都是用上下文无关文法来描述的，比如表达式、赋值语句、循环结构的语法规则。2型文法生成的语言能被下推自动机识别。

3型文法（正规文法，RG）限制最严格，产生式形式只能是 A → aB 或 A → a，其中A和B都是非终结符，a是终结符（也可以包含空串）。这种形式叫右线性文法。还有一种左线性文法，形式为 A → Ba 或 A → a。左线性和右线性合称正规文法。3型文法生成的语言叫正规语言，能被有限自动机识别，也正好是词法分析阶段描述单词结构所使用的文法类型。

判断口诀：0型无限制，1型左长右短看上下文，2型左部单个非终结符，3型左部单个且右部最多一个非终结符且在末尾（右线性）或在开头（左线性）。

5.3 文法类型判断实操

拿到一个文法，怎么快速判断类型？按顺序从严格到宽松判断：

第一步，看所有产生式是否都满足3型文法的形式。每条产生式的左部都是单个非终结符，右部是“一个终结符”或者“一个终结符加一个非终结符”。如果全部满足，就是3型。

第二步，如果3型不满足，看是否满足2型。只要所有产生式的左部都是单个非终结符，就是2型。

第三步，如果2型不满足，看是否所有产生式的左部长度都不大于右部长度，且左部至少含一个非终结符，就是1型（注意空产生式特例）。

第四步，如果以上都不满足，就是0型。

举个例子，给定文法：

S → aS S → bA A → a A → aB B → b

逐条检查，所有产生式都符合 A → a 或 A → 终结符+非终结符的形式——S → aS符合（S → 终结符a + 非终结符S），S → bA符合，A → a符合，A → aB符合，B → b符合。所以这是一个3型文法。

再看一个稍微复杂的：

S → aA A → aA | ε

这里产生式左部都是单个非终结符，但右部“ε”不是终结符，软考语境下如果允许空产生式，这个文法有时会被单独讨论。在实际考题中，如果出现ε，你大概率要做特殊处理。题目给的选项通常会故意拿这一点区分人。稳妥的记忆方式是：正规文法中，空产生式一般是允许作为特例存在的，判断类型时主要看“非空”产生式的形式。

再比如：

S → AB A → a B → b

S → AB的左部是单个非终结符S，右部是AB两个非终结符，不符合3型（右部只能有一个非终结符），但左部是单个非终结符，所以是2型。请注意，虽然它推导出的语言只是{ab}这个有限集合，但文法类型判断只看产生式形式，不看生成的语言，这一点很多人会弄混。

5.4 正规式与有限自动机

与3型文法紧密相关的是正规式（正则表达式）。正规式是一种用来描述正规语言的表达式表示法。

常见的正规式运算符有三个：连接、选择（|）、闭包（*）。比如正规式ab|cd表示的语言是{ab, cd}；正规式a*表示由零个或多个a组成的串的集合；正规式(a|b)*表示由a和b组成的任意串的集合。

正规式描述的是语言的“规则”，而有限自动机是识别这个语言的“机器”。从正规式可以构造出有限自动机，从有限自动机也可以反过来得到正规式，两者描述能力等价。3型文法、正规式、有限自动机，三者是等价的描述工具。

软考对这个知识点的考查方式：给一个正规式，问它描述的是哪个字符串集合；或者给几个语言的描述，问哪个正规式能正确表达它。比如“以字母开头，后跟字母或数字的标识符”的正规式可以表示为letter (letter|digit)*，其中letter代表字母集合，digit代表数字集合。

在基础阶段，把三种等价关系记清楚就够了：正规文法 = 正规式 = 有限自动机。这句话几乎是原封不动地出现在很多年真题里。

6. 语法分析与中间代码：理解比死记更重要

语法分析的方法和中间代码的形式，是本章后半部分的两个重点。这部分内容理解起来不难，但需要动手做几道转换题才能熟练。

6.1 自上而下分析与自下而上分析

语法分析的核心任务是按照文法规则，判断一个单词串是否属于该文法定义的语言。对于同一个文法，可以选择不同的分析策略，主要分为自上而下分析和自下而上分析两大类。

自上而下分析是从文法的开始符号出发，用产生式进行推导，试图推导出与输入串完全匹配的句子。好比你知道故事开头和结尾，然后一步步填补中间的情节，看看能不能正好拼成完整的故事。自上而下分析的代表方法是递归下降分析法、LL(1)分析法。

自下而上分析是从输入串出发，试图通过归约（把右部符号串替换成左部的非终结符），最终归约到文法的开始符号。好比从故事的结尾倒着向前寻找逻辑关系，最终回到开头。自下而上分析的代表方法是算符优先分析法、LR分析法。

考试对分析方法的考查，一般就是判断某个方法属于自上而下还是自下而上，或者在词法/语法分析之间做选择。这里记忆关键词：递归下降和LL是自顶向下，“算符优先”和“LR”是自底向上。

6.2 后缀式（逆波兰式）

后缀式也叫逆波兰式，是一种把运算符写在操作数之后的表达式表示法。传统的中缀表达式“a + b”，写成后缀式是“ab+”。后缀式的最大特点是运算顺序完全确定，不需要括号，也不需要运算符优先级规则。

转换规则并不复杂。中缀转后缀时，从左到右扫描表达式，按运算符的优先级调整位置。最简单的方法是给表达式加括号，然后逐步把运算符移到右括号的位置，最后去掉所有括号。但考场上一层层套括号太慢，更实用的方式是使用一个操作符栈来手动模拟。

举个例子，把中缀表达式a + b * c转后缀式：

扫描到a，直接输出a；扫描到+，因为栈为空，+入栈；扫描到b，输出b；扫描到*，优先级高于栈顶的+，所以入栈；扫描到c，输出c；扫描结束，把栈中剩余的运算符依次弹出输出。最终后缀式是a b c * +。

再看一个带括号的例子：(a + b) * c。扫描到(入栈；扫描到a输出；扫描到+，栈顶是(，+入栈；扫描到b输出；扫描到)，把栈中运算符直到(为止全部弹出，得到+输出，弹出(不输出；扫描到入栈（此时栈空或栈顶优先级低于）；扫描到c输出；结束，弹出*。最终得到a b + c *。

后缀式的计算也非常简单：从左到右扫描，遇到操作数就压栈，遇到运算符就弹出两个操作数，计算结果压回栈中。最终栈中剩下的数就是表达式的值。

6.3 三元式与四元式

三元式和四元式是编译程序中常用的中间代码表示形式。

三元式的形式是(op, arg1, arg2)，用一个三元组表示一个运算，第三个分量有时省略（单目运算）。三元式的编号可以被其他三元式引用，引用方式就是指向该三元式的编号。表达式a + b * c可以表示为：

(1) (*, b, c)

(2) (+, a, (1))

四元式的形式是(op, arg1, arg2, result)，其中result是存放运算结果的临时变量。同一个表达式用四元式表示就是：

(1) (*, b, c, T1)

(2) (+, a, T1, T2)

三元式的特点是引用结果时用的是编号而不是临时变量名，四元式的特点是显式地引入了临时变量。两者在表达能力和用途上有所不同，四元式更接近三地址指令，在代码优化阶段使用更广泛。

真题的常见考法是：给一个表达式，要求选择正确的四元式序列或后缀式；或者给一个后缀式，让考生还原成中缀表达式。这类题属于“熟能生巧”的题，考前刷十几道题基本就能全对。

6.4 语法树与二义性

语法树（推导树）是语法分析过程的可视化表示，它展示了文法是如何推导出一个句子的。语法树的根节点是文法的开始符号，叶子节点组成的序列就是被分析的句子，内部节点是推导过程中用到的非终结符。

二义性是语法分析中的一个重要概念。如果一个文法的某个句子可以构造出两棵不同的语法树，就称这个文法是二义性的。二义性意味着同一个句子在语法结构上存在两种不同的解释，这会让编译程序无法确定该句子对应的语义。

经典的二义性例子是悬空else问题。“if x then if y then s1 else s2”这个句子，在有些文法规则下可以理解为嵌套结构，也可以理解为序列结构。解决悬空else的常用规则是：else与最近的if匹配。

考试对二义性的考查一般集中在判断某个文法是否具有二义性，或者问二义性文法会导致什么问题。记住结论：二义性文法在编译程序中是不可取的，因为同一个句子对应多棵语法树，程序含义不确定。

7. 高频考法与避坑指南：真题里反复出现的陷阱

这一章的知识点数量有限，历年真题反复在几个固定的坑上做文章。总结一下高频陷阱和记忆方法，能帮你快速避开失分点。

7.1 高频考点汇总

7.2 避坑要点

第一个要避的坑：语法分析和语义分析混淆。记住一条判断经验——如果错误关注的是“形式”是否正确（比如括号匹配、语句序列完整），属于语法分析；如果错误关注的是“含义”是否合法（比如类型不匹配、变量未声明），属于语义分析。

第二个要避的坑：词法分析和语法分析混淆。词法分析处理的对象是字符，粒度是“单词”；语法分析处理的对象是单词流，粒度是“句子”。举个例子，“inta”这个字符串如果被当作关键字“int”和标识符“a”直接连在一起没有分隔符，有些词法分析器会把“inta”识别成一个非法标识符，这属于词法错误；而“int a 10;”这种单词排列组合不合规，属于语法错误。

第三个要避的坑：文法类型判断只看产生式形式，不看生成的语言。有的文法生成的语言很简单，比如上面的S → AB / A → a / B → b，但它明明只是2型而不是3型。反过来，有些文法形式上是2型，但生成的语言恰好是正规语言，文法类型仍然是2型。判断依据永远是产生式的形式限制，不是语言本身。

第四个要避的坑：正规文法的左右线性区别。正规文法包含右线性和左线性两类。右线性是A → aB，左线性是A → Ba。有些题目会问“该文法属于左线性还是右线性，还是两者兼有”。注意一个文法允许同时包含左线性和右线性产生式时，整体仍然属于正规文法（因为它们描述的语言仍然可以用一个合适的正规文法来描述），但题目可能会用“左线性”“右线性”的术语做选项区分。

第五个要避的坑：表达式中运算符优先级影响后缀式。很多人转后缀式容易犯的错是忽略了优先级直接按中缀顺序输出。核心保证是：转换时用栈顶运算符和当前扫描到的运算符做优先级比较，栈顶优先级不低于当前运算符时，先弹出栈顶。真正动手模拟几遍，这个坑就彻底绕开了。

7.3 记忆口诀

• 编译过程六个阶段，可以记成“词法语法语义，中间优化目标”，前三个负责“看懂”，后三个负责“翻译”。
• 文法类型判断，“0无限制，1看上下文，2左边一个N，3右边最多一个N”。注意“N”指非终结符。
• 正规文法等价链：正规文法和正规式以及有限自动机是“三兄弟”。
• 后缀式本质：“运算符右移，括号消除”。多题练习后自然熟练。

8. 冲刺建议：这一章应该怎么刷题

最后的这部分，给大家一点我实际复习过程中的经验。

我建议把这一章放在软考复习的第二个星期来做。原因很简单，程序设计语言基础的知识点和上午题其他模块相对独立，不需要前置知识，但又需要一定的时间用真题来巩固概念记忆。如果放在后面，往往时间紧张，只能草草过一遍，考场上碰到文法判断，全靠蒙的状态太危险了。

具体刷题顺序，我推荐三步走。第一步，把教材章节正文完整读一遍，里面的例题全部自己动手做一遍，尤其是后缀式转换和文法判断，一定要自己推导一遍，别直接看答案。第二步，做近十年的真题中所有涉及本章的选择题，做完之后不只看对错，把每个选项为什么对、为什么错都弄清楚。第三步，考前一周把做错的题重新回顾一遍，重点看那些概念混淆类的错题。

关于是否需要看扩展的编译原理内容，我的建议是明确划清界限。软考设计题里曾经出现过判断正规式和有限自动机等价、补全四元式这类题，但深度仅限于此。不要花时间去学LL(1)分析表的构造，不要学SLR、LALR的详细算法，也不要自己真的去写一个编译器的Demo。软考的命题风格是广度优先，把时间花在不常考的深水区，性价比太低。

如果这一章的错题率一直在50%左右徘徊，问题大概率出在文法类型判断和后缀式转换上。这两个分项都是可以通过短期强化突破的：文法判断题，找20道左右的专项练习，把每道题的产生式类型都标注出来，做完一遍，判断思路会非常清晰；后缀式题，找15道左右，从头到尾手动模拟转换，不用工具，做完基本就形成了肌肉记忆。

每次模拟考试的时候，上午题中如果出现这章的题，我会刻意控制在1分钟内做完，不给它留太多纠结时间。因为概念类题目需要的是第一反应的准确率，纠结来纠结去反而容易落入出题人的干扰项陷阱。碰到一时拿不准的文法判断，我一般会立即在草稿纸上把产生式列出来，按0、1、2、3的顺序逐条核对，比在脑子里空想要可靠得多。

最后说一个我自己踩过的坑：千万不要按照大学的《编译原理》教材难度去准备这一章。软考上午题是“覆盖广、深度浅”的风格，程序设计语言基础更是如此。你不需要知道怎么构造LR分析器，不需要证明某个文法是LL(1)的，也不需要实现词法分析器生成器。你只需要把这张卷子里那2到4分拿到手，把有限的时间投入到下午题那些分值密集的大题上，才是正确的应试策略。