程序设计语言与编译原理

快拿分：文法类型与自动机对应、句柄在分析树的位置、编译各阶段任务、传值/传址/静态动态作用域、FIRST/FOLLOW 概念题——偏记准定义，大计算较少。

一、知识与应试（考点·难点·知识点合一）

1.1 文法与自动机

• Chomsky 分层：0 短语结构、1 上下文有关、2 CFG、3 正则；2 型对应下推自动机，3 型对应有限自动机。
• 句柄：最左直接短语（分析树叶子向上找）。
• 〔真题〕：「配对括号」语言不能用仅正则描述（需栈）。

1.2 语法分析

• LL(1)：左递归消除、FIRST/FOLLOW、预测分析表无多重入口。
• LR 族：LR0/SLR/LR1/LALR 冲突类型（移进-归约、归约-归约）。
• 〔难点〕：FIRST/FOLLOW 含 (\varepsilon) 时的迭代至不动点。

1.3 编译过程与优化

• 阶段：词法（正则/DFA）→ 语法 → 语义（类型检查等）→ 中间代码 → 优化 → 目标代码；符号表多遍使用。
• 中间表示：四元式、三元式、间接三元式——可修改性对比。
• 优化：局部（常量合并、公共子表达式）、循环不变外提；与机器无关/有关划分。

1.4 语言机制（常接 C）

• 传值/传址：形参是否影响实参。
• 作用域：静态看词法块，动态看调用链（题设默认多为静态）。
• static 局部：生存期贯穿程序，只初始化一次。

1.4.1 程序内存区域

区域	存放内容	易错点
代码区	编译后的机器指令	通常只读
静态存储区	全局变量、静态变量、常量、字符串常量	生命周期贯穿程序运行期
堆区	动态分配对象/内存	由程序员或运行时管理，泄漏常出在这里
栈区	函数参数、局部变量、返回地址	由编译器自动分配释放

上午题常把 static、全局变量、局部变量、动态分配对象混在一起考，先按生命周期和谁分配释放区分。

二、速记与背诵

文法	自动机
3 型 正则	有限自动机 NFA/DFA
2 型 CFG	下推自动机 PDA

• 编译前端：词法+语法+语义；后端：代码生成+（目标级）优化。

三、考场检查

• 问「某阶段错误」：词法错多为非法字符；语义错多为类型不匹配。
• 逆波兰/后缀：运算符顺序紧跟操作数，不手懒按栈模拟一遍。