适合读者软考中级备考同学阅读时间5分钟内容文法、有限自动机、语法分析三大板块的核心对比表、易错点、记忆口诀汇总一、板块内容概览“程序语言与编译”板块共覆盖以下核心内容文法基础终结符/非终结符、产生式、乔姆斯基文法分类0-3型词法分析正规式与正规集、有限自动机DFA/NFA、NFA转DFA、正规式与FA等价转换语法分析自上而下推导最左/最右、自下而上归约规范归约、短语/直接短语/句柄、语法树与二义性中间代码逆波兰、三元式、四元式运行时环境符号表、静态/栈/堆存储错误处理与参数传递错误分类、传值与传址二、核心对比表2.1 乔姆斯基文法分类0-3型类型名称产生式形式对应自动机典型应用0型短语结构文法α→β\alpha \rightarrow \betaα→β无限制图灵机理论计算机1型上下文有关文法αAβ→αγβ\alpha A \beta \rightarrow \alpha \gamma \betaαAβ→αγβγ≠ε\gamma \neq \varepsilonγε线性有界自动机自然语言处理2型上下文无关文法A→γA \rightarrow \gammaA→γAAA为单个非终结符下推自动机程序设计语言语法3型正则文法A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a右线性有限自动机词法规则包含关系3型⊂\subset⊂2型⊂\subset⊂1型⊂\subset⊂0型越往上描述能力越强2.2 语法分析自上而下 vs 自下而上对比项自上而下推导自下而上归约起始点开始符号输入符号串操作替换非终结符展开替换子串为非终结符归约对应推导最左推导最右推导规范推导的逆核心概念非终结符句柄分析方法递归下降、LLLR、LALR2.3 词法分析DFA vs NFA对比项DFANFA下一状态唯一多个或零个ε\varepsilonε转移不允许允许状态数较多较少模拟运行快无回溯慢需回溯构造难度较难容易直观识别能力相同相同等价2.4 短语、直接短语、句柄概念定义语法树对应短语某非终结符推导出的子串以某非终结符为根的子树的所有叶节点串直接短语一步推导得到的短语深度为1的子树父节点直接生出终结符的叶节点串句柄最左边的直接短语最左直接短语三、易错点汇总易错点正确理解文法类型判断错误左部单个非终结符且无上下文限制 → 2型上下文无关右部只有单非终结符在末尾 → 3型正则NFA与DFA识别能力不同识别能力相同可相互转换最左推导对应自下而上最左推导对应自上而下最右推导规范推导对应自下而上归约句柄是任意可归约子串句柄是最左边的直接短语不是任意短语二义性是语言的属性二义性是文法的属性不是语言的属性同一语言可有不同文法符号表仅用于语义分析符号表在词法、语法、语义、代码生成各阶段都使用静态变量在栈区静态变量在静态数据区普通局部变量在栈区传值与传址混淆传值复制副本不影响实参传址传递地址修改影响实参四、记忆口诀汇总文法分类0型无限制图灵机最强1型上下文线性有界忙2型无关文下推自动掌3型正则规有限自动行。推导与归约自上而下开始符最左替换展开树自下而上从串起规范归约最右逆。短语句柄短语是非终结符的叶串直接一步出终结句柄是最左直接短语归约之时先找它。DFA/NFADFA确定唯一路NFA多路可空跳子集构造换等价识别能力一样高。中间代码逆波兰后缀写栈式计算最快捷三元式三字段序号引用结果来四元式多一结果临时变量显式排。存储与传参静态全局生命长栈上局部自动亡堆由手动管生死内存分配要成双。传值复制不影响传址修改同地址。五、板块总结程序语言与编译板块板块2共完成16篇文章覆盖知识模块篇数核心内容语言基础2篇语言分类、编译vs解释文法与自动机7篇文法定义与分类、正规式、DFA/NFA、NFA转DFA、等价转换语法分析5篇自上而下推导、自下而上归约、短语/句柄、语法树与二义性中间代码与运行时2篇中间代码形式、符号表与存储组织、错误处理与传参至此“程序语言与编译”板块全部更新完毕。该板块是理解编译器工作原理的基础也是软考选择题的稳定得分区。六、下期预告板块3 – 操作系统主要内容进程管理进程状态、PCB、上下文切换进程同步与互斥PV操作、前驱图、经典同步问题死锁必要条件、银行家算法、死锁预防与检测存储管理分区、分页、分段、虚拟存储、页面置换文件管理文件结构、目录、磁盘空间管理设备管理I/O软件层次、设备独立性从下一篇文章开始我们将进入操作系统板块这是软考下午题编程填空的高频出题区请持续关注本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新板块内容#软考中级 #软件设计师 #文法 #有限自动机 #语法分析 #板块总结 #操作系统