程序设计语言与编译原理是上午题里弃考率最高的模块文法产生式像天书、自动机图看着眼晕、前后缀表达式一转换就乱。真相是这块每年 2~4 分的题目套路比任何模块都死——自动机题就是走迷宫表达式题就是画二叉树文法题就是套规则硬推。零数学门槛全是手工活。一、编译与解释先分清两种翻译官编译程序把源程序一次性整体翻译成目标代码机器语言之后运行目标代码。像翻译公司译整本书解释程序逐句翻译、逐句执行不产生目标代码。像同声传译。编译的六个阶段顺序要记词法分析 → 语法分析 → 语义分析 → 中间代码生成 → 代码优化 → 目标代码生成前三个阶段是考点各管一类错误词法分析把字符流切成一个个合法单词记号。3.5.2这种不合法数字、乱拼的关键字归它管语法分析按文法规则把单词组装成结构语法树。括号不匹配、语句结构残缺归它管语义分析检查含义合不合理。类型不匹配把字符串赋给整型变量、变量未声明归它管。二、文法语言的生产规则文法就是一组替换规则产生式。两类符号终结符小写最终出现在句子里的字符不可再分解非终结符大写中间符号可以被产生式右部替换。推导 从开始符号 S 出发不断把非终结符替换成产生式右部直到串里全是终结符。能推出来的串就属于这个文法描述的语言。例文法 GS→aAA→bS | b。它能产生哪些串S → aA → ab A 取 b → ab S → aA → abS → abaA → abab A 取 bS 再展开 → abab 再循环一轮 → ababab ……规律一目了然(ab)ⁿ。考场上给你四个候选串问哪个推不出来就挨个试推——推不出来就是答案不需要任何理论。三、有限自动机就是走迷宫自动机图就两个记号单箭头指入的是初态双圆圈是终态。识别规则一句话从初态出发按输入串逐字符走边串走完的那一刻停在终态上就接受否则拒绝。做题方法就是笨办法每个候选串都在图上走一遍。比如初态 AA 读 0 到 BB 读 1 到 CC 是终态——串01从 A 出发读 0 到 B读 1 到 C串尽人终接受。其余10、00、11走一遍要么无路可走要么停在非终态都拒绝。DFA确定的和 NFA不确定的区别一句话DFA 每个状态对同一个输入只有一条出路NFA 可能有多条或 ε 空转移。软考识别题大多是 DFA走迷宫即可。四、表达式画棵树三种遍历给三种答案三种记法中缀ab运算符在中间、前缀ab、后缀ab逆波兰式编译器最爱因为算它不用括号不用管优先级。转换神器表达式树。建树规则优先级高的运算先算、做子树最后算的运算做根。例a b*c——先算b*c乘号做子树的根最后算做总根 / \ a * / \ b c然后三种遍历对应三种记法前序遍历根左右 a * b c → 前缀 a*bc 中序遍历左根右a b * c → 中缀 ab*c 后序遍历左右根a b c * → 后缀 abc*后缀表达式求值用栈遇操作数入栈遇运算符弹出栈顶两个计算结果压回栈。例3 4 5 *3 入栈 [3] 4 入栈 [3, 4] 遇 弹 4、3算 347压栈 [7] 5 入栈 [7, 5] 遇 * 弹 5、7算 7×535压栈 [35] → 结果 35五、传值与传址函数调用的最后一考传值调用形参是实参的副本函数里怎么改实参纹丝不动传址调用引用调用形参是实参的别名函数里改的就是实参本身。f(x){ xx1; }a5调用f(a)传值则 a 还是 5传址则 a 变 6。软考喜欢给一段小程序问输出本质就考这一句。六、10 道练习题基础题1~51.编译程序与解释程序的区别在于 。A. 编译程序产生目标代码后再执行解释程序逐句翻译执行、不产生目标代码 B. 解释程序执行速度更快 C. 编译程序不产生任何代码 D. 两者没有本质区别2.词法分析阶段的主要任务是 。A. 检查括号是否匹配 B. 将字符流识别为一个个单词记号 C. 进行类型检查 D. 生成目标代码3.某确定有限自动机初态为 AA 读入 0 转到 BB 读入 1 转到 CC 为终态则下列串中被该自动机接受的是 。A. 10 B. 00 C. 01 D. 114.中缀表达式 ab 的后缀表达式是 。A. ab B. ab C. ba D. ab5.函数f(x){ xx1; }主程序中a5以传值方式调用f(a)后a 的值为 。A. 6 B. 不确定 C. 编译错误 D. 5进阶题6~10带坑6.编译时发现某语句中出现了3.5.2这样不合法的数字形式该错误应由 阶段发现。A. 词法分析 B. 语法分析 C. 语义分析 D. 目标代码生成7.中缀表达式 ab*c 的后缀表达式为 。A. abc* B. abc C. abc* D. abc*8.后缀表达式3 4 5 *的值为 。A. 23 B. 60 C. 35 D. 179.函数f(x){ xx1; }主程序中a5以传址引用方式调用f(a)后a 的值为 。A. 5 B. 6 C. 不变 D. 编译错误10.文法 GS→aAA→bS|b下列串中不能由该文法推导出的是 。A. ab B. abab C. ababab D. aabb七、答案与详解1. A编译 整体翻译出目标代码再运行解释 逐句翻译逐句执行不落目标代码。Java/C 是编译路线传统 Python/Basic 是解释路线。2. B词法分析管切单词字符流 → 记号流。括号匹配是语法分析C 的结构问题类型检查是语义分析。3. C走迷宫A—0→B—1→C终态串01走完正好停在终态接受。其余三个要么第一步就没路A 读 1 无转移要么停在非终态。4. B后缀 运算符跟在两个操作数后面ab。5. D传值调用形参 x 是副本x1 改的是副本实参 a 纹丝不动仍为5。6. A3.5.2是造不出来的单词——词法分析阶段就无法把它识别成合法记号错误暴露在第一关。注意和括号不匹配语法、类型不符语义区分三者正好对应三个阶段。7. D画树先算b*c子树做根后序遍历 →abc*。选 A 的是按先加后乘的错误顺序建的树——先算的做子树、后算的做根顺序一错全错。8. C栈模拟3、4 入栈遇 弹出算得 7 压回5 入栈遇 * 弹出算 7×5 35。选 B60的是把3 4当成了3×4…… 按步骤走栈就不会错。9. B传址调用形参是实参的别名x1 直接改在 a 身上 → a 6。和第 5 题对照记忆传值 5、传址 6这一对是软考的固定节目。10. D试推该文法从 S 出发只能生成(ab)ⁿ形式的串ab、abab、ababab……。aabb中出现了aa——S 第一个产生式 S→aA 决定了 a 后面只能跟 A而 A 只能产生 b 开头的内容两个 a 永远不可能相邻。八、五句话带走编译出目标代码解释逐句执行编译六阶段顺序词法→语法→语义→中间码→优化→目标码错误归口造不出的单词归词法结构残缺归语法类型不对归语义文法题 试推能推出来的就是合法串自动机题 走迷宫初态出发逐字符走串尽人终即接受表达式题 画树先算的做子树、后算的做根前序前缀、中序中缀、后序后缀后缀求值用栈数入栈运算符弹二算一。下一篇预告上午题的压轴模块——数据结构二叉树的三个遍历前中后序怎么互相还原、完全二叉树的编号规律、堆为什么是顶最大却整体无序。这块正是你算法系列博客的体——分治、动规是招式数据结构是内功。