软考软件设计师上午题一共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、JavaJava其实是半编译半解释的先编译成字节码再由虚拟机解释执行这个特例偶尔也考、Pascal等。C语言的源程序经过编译生成.obj目标文件然后链接成.exe可执行文件整个过程就是典型的编译方式。3.3 解释程序边翻译边执行解释程序处理高级语言的方式是“逐句翻译逐句执行”整个过程不生成独立的目标程序。解释程序读取一行源代码翻译成机器指令然后立刻执行执行完再去读下一行。就像同声传译一样翻译和内容是同步推进的。解释方式的好处是灵活性高跨平台性好程序出错时能立刻定位到出错的行便于调试。缺点是执行效率低因为每运行一次程序都要重新把每一行源代码重新翻译一遍。典型的解释型语言有Python、JavaScript、Ruby等。这个区别要记住一个非常贴切的类比编译方式就像先把整本书翻译成中文再阅读解释方式就像请了一个翻译你说一句他翻一句。3.4 编译与解释的对比速查对比维度编译程序解释程序翻译时机全部翻译完成后统一执行边翻译边执行目标程序生成独立的机器代码文件不生成目标代码文件执行效率相对较高无需重复翻译相对较低逐次运行都要重新翻译跨平台性编译生成的程序与平台绑定通常跨平台性更好错误发现时机编译期能发现大量静态错误运行到出错行才能发现典型语言C、C、PascalPython、JavaScript真题里关于这个对比的设问方式很灵活有的直接问“下列哪个语言采用的是解释执行方式”有的给出一段描述让考生判断说的是编译还是解释。特别注意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 * ”四元式则表示为序号oparg1arg2result(1)*bcT1(2)aT1T2其中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 非终结符SS → bA符合A → a符合A → aB符合B → b符合。所以这是一个3型文法。再看一个稍微复杂的S → aA A → aA | ε这里产生式左部都是单个非终结符但右部“ε”不是终结符软考语境下如果允许空产生式这个文法有时会被单独讨论。在实际考题中如果出现ε你大概率要做特殊处理。题目给的选项通常会故意拿这一点区分人。稳妥的记忆方式是正规文法中空产生式一般是允许作为特例存在的判断类型时主要看“非空”产生式的形式。再比如S → AB A → a B → bS → 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 高频考点汇总考点考法优先级编译与解释的区别判断某语言或描述属于编译方式还是解释方式必考编译各阶段的职能给出某编译动作或错误判断属于哪个阶段必考文法类型判断给出产生式集合判断属于0/1/2/3型哪种文法高频后缀式/四元式中缀表达式转后缀式或四元式或反向还原高频正规式描述给语言规则选正规式或给正规式选语言中频词法/语法/语义错误区分给错误代码描述判断编译哪个阶段报错中频程序语言成分判断某描述属于数据成分、运算成分还是控制成分中低频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左边一个N3右边最多一个N”。注意“N”指非终结符。正规文法等价链正规文法和正规式以及有限自动机是“三兄弟”。后缀式本质“运算符右移括号消除”。多题练习后自然熟练。8. 冲刺建议这一章应该怎么刷题最后的这部分给大家一点我实际复习过程中的经验。我建议把这一章放在软考复习的第二个星期来做。原因很简单程序设计语言基础的知识点和上午题其他模块相对独立不需要前置知识但又需要一定的时间用真题来巩固概念记忆。如果放在后面往往时间紧张只能草草过一遍考场上碰到文法判断全靠蒙的状态太危险了。具体刷题顺序我推荐三步走。第一步把教材章节正文完整读一遍里面的例题全部自己动手做一遍尤其是后缀式转换和文法判断一定要自己推导一遍别直接看答案。第二步做近十年的真题中所有涉及本章的选择题做完之后不只看对错把每个选项为什么对、为什么错都弄清楚。第三步考前一周把做错的题重新回顾一遍重点看那些概念混淆类的错题。关于是否需要看扩展的编译原理内容我的建议是明确划清界限。软考设计题里曾经出现过判断正规式和有限自动机等价、补全四元式这类题但深度仅限于此。不要花时间去学LL(1)分析表的构造不要学SLR、LALR的详细算法也不要自己真的去写一个编译器的Demo。软考的命题风格是广度优先把时间花在不常考的深水区性价比太低。如果这一章的错题率一直在50%左右徘徊问题大概率出在文法类型判断和后缀式转换上。这两个分项都是可以通过短期强化突破的文法判断题找20道左右的专项练习把每道题的产生式类型都标注出来做完一遍判断思路会非常清晰后缀式题找15道左右从头到尾手动模拟转换不用工具做完基本就形成了肌肉记忆。每次模拟考试的时候上午题中如果出现这章的题我会刻意控制在1分钟内做完不给它留太多纠结时间。因为概念类题目需要的是第一反应的准确率纠结来纠结去反而容易落入出题人的干扰项陷阱。碰到一时拿不准的文法判断我一般会立即在草稿纸上把产生式列出来按0、1、2、3的顺序逐条核对比在脑子里空想要可靠得多。最后说一个我自己踩过的坑千万不要按照大学的《编译原理》教材难度去准备这一章。软考上午题是“覆盖广、深度浅”的风格程序设计语言基础更是如此。你不需要知道怎么构造LR分析器不需要证明某个文法是LL(1)的也不需要实现词法分析器生成器。你只需要把这张卷子里那2到4分拿到手把有限的时间投入到下午题那些分值密集的大题上才是正确的应试策略。