CSCI3130 L05 Part 3 程序语言

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核本讲：L05 Part 3 程序语言 · 原件 L05-上下文无关文法-资料包.pdf（本地课件） p.80–90 定位：把抽象文法放进编译器的数据流，区分结构检查与语义检查。前后：上一份 L05-P2-解析与歧义.md

p.80 Outline，进入 CFG 与程序语言。

编译器中 parser 的位置（p.81–83）

p.81 把程序与机器指令并列，目标是将结构化源程序变成低层执行步骤。图（p.82）：source file→lexer→token流→parser→parse tree→codegen→object code。看什么：词法分析先把字符分成记号，语法分析再判断记号组合结构，代码生成消费该结构。图底部人名是原课件背景，不用于推导算法。

p.83 parser 必须知道语言文法。它不能只靠“这个字母出现过”来确认整个程序合法，因为合法性涉及记号之间的嵌套和顺序。

p.81 的程序与指令示意全文：

源程序                         指令示意
v = 5;                         Add v,v,0
if (v>5)                       cmp v,5
    x = 12 + v;                jmplt ELSE
while (x !=3) {                THEN:
    x = x - 3;                   add x,12,v
    v = 10;                    ELSE:
}                              WHILE:
......                         cmp x,3
                               ...

这一页是阶段关系示意，并非完整可执行编译结果。特别是右侧首行并不能在一般指令语义下实现左侧 v=5，跳转与循环也不完整；应从中理解“高级语句被拆为计算、比较、跳转”，不能拿它当逐条正确的汇编模板。p.82 图底部列 Ken Thompson（UNIX/grep/vi 中的正则表达式）、Eric E. Schmidt、Mike Lesk（lex）、Stephen C. Johnson（yacc），这些是原课件的工具背景标注，不是本次独立历史考证。

从程序规则到表达式树（p.84–86）

p.84 的 PROGRAM 展开为语句列表，列表递归地产生分号分隔的语句，STMT 可以是表达式、if、while 或花括号块。这里的文法是演示结构，不承诺已消除前面讲过的算术及 else 歧义。

p.84 的全部规则（保留演示文法的原形）：

PROGRAM → STMT_LIST
STMT_LIST → STMT ; STMT_LIST | STMT ;
STMT → EXPR | IF_STMT | WHILE_STMT | { STMT_LIST }
EXPR → EXPR + EXPR | EXPR - EXPR | ID
IF_STMT → if ( EXPR ) then STMT
        | if ( EXPR ) then STMT else STMT
WHILE_STMT → while ( EXPR ) do STMT

分号、括号、花括号和关键字是终结符；PROGRAM 等大写名是变量；ID 表示标识符记号。列表没有空规则，因此至少一条语句且最后也带分号；递归选第一条可继续加语句，选第二条结束。它只演示列出的语言片段，不能据此声称 p.81 中的赋值、比较等全部已被定义。

p.85 输入 10 + 2 * 5，文法 $E\to E+E\mid E\ast E\mid INT$ 给出 $E\Rightarrow E+E\Rightarrow E+E\ast E\Rightarrow10+E\ast E\Rightarrow10+2\ast E\Rightarrow10+2\ast5$ 。INT 表示词法得到的整数记号，具体10、2、5由记号携带。p.86 对应树根为加，右子树为乘。原推导不是严格最左推导，但仍是合法一般推导；不要因展开了右变量就说它无效。

结构决定代码生成顺序（p.87–89）

p.87 图先生成 mult a, 2, 5，再 add b, 10, a：临时变量 a=10，b=20。乘法子树先产生可供父加法使用的结果，正是依赖关系而非版面顺序决定执行次序。

p.88 BNF 用 ::= 写产生式、尖括号写非终结符，表达能力仍沿用文法思想；LL、LR 是可线性解析的受限文法类，不能由此推出任意 CFG 都线性可解析。p.89 区分语法与语义：赋值语句可符合结构规则，却可能在类型或含义层面不合要求。页面把“given CFG is inherently ambiguous”并列为难题；术语上固有歧义属于语言，文法本身谈歧义，两者不要混用。本页没有给判定算法，因此不能把“难”误读成已有可运行的慢算法。

p.88 的两个 BNF 例子为：

<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>

它们对应上一部分 E、T 两层；本页没有再给 factor 的完整规则，应沿用上一部分的“括号表达式或原子”的解释理解示例。p.89 还明确提出“两份 CFG 是否等价”的问题，并用 Char a, b, c; c = 3.2; 说明语法与语义的差别。是否允许把3.2赋给字符类型，要由具体语言的类型及转换规则决定，不能只凭这两行断言每种语言都拒绝。

p.90 Questions 结束页。

考试角度：（C 级通识）常见考法是解释 token、语法树与代码生成的分工，或按树的依赖顺序求表达式值。

同一输入沿编译数据流走到底（补充）

继续用正文的 10 + 2 * 5。lexer 先把两个字符 1、0 合成一个整数 token，它的种类为 INT，附带值为10；后面依次为 PLUS、INT(2)、TIMES、INT(5)。parser 读取的是这些 token 的种类与顺序，建立加法根、整数10左子树和乘法右子树。树中的 INT 并不是运行时值本身，词法附带的数值才让后续计算知道是10而不是任意整数。

codegen 按子树依赖产生临时结果：先令 t1=2×5=10，再令 t2=10+t1=20。t1 从乘法完成开始有效，直到加法使用后才不再需要；若优化器复用保存 t1 的位置，必须在它最后一次被读取之后，不能提前覆盖。这是临时值的生命周期，不是要求源程序一定声明这两个变量。

排查失败也按接口定位：10 + * 5 的字符和记号都可能合法，但记号组合缺操作数，parser 可拒绝；x + 5 可能语法合法，却需后续查 x 是否声明、类型是否支持加法。若树正确但结果成60，检查是否误用了“先加后乘”的执行结构，不能只归咎于 lexer。每一阶段的输入、输出和保证不同，分开检查才知道错误在哪里。

自检：一段程序通过 CFG 语法检查，能否保证运行不出错？

CFG 检查的是结构，哪些事实还没由它检查？

展开推理与答案

不能。变量绑定、类型约束、数组越界或除零等通常不由这里的 CFG 单独保证；有些由静态语义检查处理，有些取决于运行数据。语法树可作为后续检查的输入，但它不是程序安全或正确性的全部证明。

本讲核心考点

lexer、parser、codegen 的输入输出（p.81–83，C 级）。
表达式树决定计算顺序（p.85–87，C 级）。
BNF、受限文法与语义边界（p.88–89，C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

原件：L05-上下文无关文法-资料包.pdf（本地课件），PDF p.80–90。
本次独立学习修订：核对本讲90页的文本，视觉复核 p.36、58、76、78、81–82、84、88–90；补全原规则、程序示意、推导树结构和搜索候选。