1. 文法

1.1 概念辨析

语法（syntax）：是语言的结构规则，规定了语言中各个构造的规范形式

语义（semantics）：是语言的构造含义

  • 静态语义：确保程序本身是有意义的
  • 动态语义：确保程序的工作和输出是有意义的

错误类型

  • 词法错误：非法字符、字符串未闭合、标识符起名违规、数字字面量写错、关键字拼写错误（部分程序在一开始就有关键字表）

  • 语法错误：缺少必要符号、错误语句结构、关键字拼写错误

  • 语义错误：运算类型不匹配、未声明变量、未定义函数、作用域不匹配、参数不匹配、非法内存操作

int 1^^2 = 2; ➡️ 变量名不符合规范，词法错误

int x = a ➡️ 缺少分号，语法错误

int x = “a”; ➡️ 语法正确，但是将字符串赋给整型，静态语义错误

int x = a / 0; ➡️ 语法和静态语义正确，但是运行时会除以0，动态语义错误

字母表（alphabet）：是一门语言中有穷的元素/符号集合，通常用Σ\Sigma 表示

  • ΣEnglish={a,b,…,z}\Sigma_\text{English} = \{a,b,\ldots,z\}
  • Σ程序语言={字母,数字,专用符号}\Sigma_\text{程序语言} = \{\text{字母,数字,专用符号}\}
  • Σ机器语言={0,1}\Sigma_\text{机器语言} = \{0, 1\}

终结符：是会出现在最终生成的句子中的基本符号，无法再被替换或推导为其他符号，是源语言中的最小可识别单元

非终结符：也称为变量、语法实体，是在文法中可被规则进一步替换的符号，用于构造句型，但不会直接出现在最终生成的句子中

符号串：是由字母表中的符号按一定顺序组成的有穷序列

  • 符号串的长度是符号串中含有的符号个数
  • 不含任何符号的符号串称为空串，记作ϵ\epsilon
  • 符号串的连接：xy 是把 y 的符号写在 x 的符号之后得到的符号串
  • 符号串的方幂：ana^n 是把自身连接 n 次得到的字符串，如a0=ϵ,a1=a,a2=aaa^0 = \epsilon, a^1=a, a^2=aa

符号集：字母表的子集

  • 乘积：AB={ab∣a∈A, b∈B}AB = \{ ab \mid a \in A,\, b \in B \}，如 {a,b}{c,d} = {ac,ad,bc,bd}
  • 方幂：A0=ϵ,A1=A,Ak=AA…AAA^0 = {\epsilon}, A^1 = A, A^k = AA \ldots AA，如若A={a,b}A = \{a, b\}，则A0={ϵ},A1={a,b},A2={aa,ab,ba,bb}A^0 = \{\epsilon\},A^1 = \{a, b\}, A^2 = \{aa, ab, ba, bb\}
  • Kleene 闭包：A∗=A0∪A1∪A2∪…=⋃i=0∞AiA^* = A^0 \cup A^1 \cup A^2 \cup \ldots = \bigcup_{i=0}^\infty A^i，如若Σ={0,1}\Sigma = \{0, 1\}，则Σ∗={ϵ,0,1,00,01,10,11,000,001,…}\Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, \ldots\}，即空串以及所有由 0 和 1 构成的任意长度的字符串
  • 正闭包：A+=A1∪A2∪…=⋃i=1∞AiA^+ = A^1 \cup A^2 \cup \ldots = \bigcup_{i=1}^\infty A^i，实际上就是 Kleene 闭包去掉了空串

文法：形式化描述语法的工具，规定如何从符号推导出合法句子，实现用有穷的规则集和有穷的符号集来描述无穷的句子集

语言：本质上就是一个符号串集合，是从给定字母表Σ\Sigma 的 Kleene 闭包Σ∗\Sigma^* 中选出的、满足文法的一个子集，记作L⊆Σ∗L \subseteq \Sigma^*

1.2 例子

可以认为，汉语是句子的排列组合，而句子是汉字或词语的排列组合，因此汉语可以看作为句子的无穷集，但汉字和词语是有穷集，我们需要定义一些规则，来说明如何用有穷集来刻画无穷集，即规定一个句子是怎样由汉字和词语组成的

例如“苹果十分打安全香蕉我是手机”就不是一个合法的句子，而“我是大学生”就是一个合法的句子。

在汉语中可以认为句子的其中一种合法形式是“主语+谓语”，而“谓语”的其中一种合法形式是“动词+直接宾语”，因此可以写出如下规则

1
2
3
4
5
6
7
<句子> ::= <主语> <谓语>
<主语> ::= <代词> | <名词>
<代词> ::= 我 | 你 | 他
<名词> ::= 王明 | 大学生 | 工人 | 英语
<谓语> ::= <动词> | <直接宾语>
<动词> ::= 是 | 学习
<直接宾语> ::= <代词> | <名词>

因此可以利用规则产生如“我是大学生”这样的句子，流程如下

1
2
3
4
5
6
7
8
<句子> 
=> <主语> <谓语>
=> <代词> <谓语>
=> 我 <谓语>
=> 我 <动词> <直接宾语>
=> 我 是 <直接宾语>
=> 我 是 <名词>
=> 我 是 大学生

2. 形式语言

2.1 产生式与文法

产生式：形如α→β\alpha \to \beta 或α::=β\alpha ::= \beta 的有序对，读作“α\alpha 定义为β\beta”

文法：定义为四元组G=(VN,VT,P,S)G = (V_N, V_T, P, S)

  • G：文法（Grammar）
  • VNV_N：非终结符集（Nonterminal），通常用大写字母表示
  • VTV_T：终结符集（Terminal），通常用小写字母表示
  • PP：产生式集（Production）
  • SS：起始符 / 识别符（Start）
  • V=VN∪VTV = V_N \cup V_T：文法的字母表（Variable）

加减表达式的文法 G[式子]：

  • <式子> -> <数字串> | <式子><运算符><数字串>
  • <数字串> -> <数字> | <数字><数字串>
  • <数字> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  • <运算符> -> + | -

2.2 推导与归约

直接推导和直接归约：如果存在产生式A→γA \to \gamma，且有v=αAβ,w=αγβv = \alpha A \beta, w = \alpha \gamma \beta，那么称 v 直接推导到 w，w 直接归约到 v，记作v⇒wv \Rightarrow w

推导和归约：若存在v=w0⇒w1⇒…⇒wn=wv = w_0 \Rightarrow w_1 \Rightarrow \ldots \Rightarrow w_n = w，即 v 经过多步（可以是 0 步）产生式推到 w，那么称 v 推导出 w，w 归约到 v，记作v⇒∗wv \Rightarrow^* w

image-20250622132830233

2.3 句型和句子

句型：从识别符推出的符号串α\alpha，即S⇒∗αS \Rightarrow^* \alpha

句子：是只由终结符组成的句型，即α∈VT∗\alpha \in V_T^*

语言：文法 G 从开始符 S 所可以得到的所有句子的集合，记作L(G)L(G)

文法等价：两个文法所定义的语言是一样的，例如G1[A]:A→0R,A→01,R→A1G_1[A]: A \to 0R, A \to 01, R \to A1 和G2[S]:S→0S1,S→01G_2[S]: S \to 0S1, S \to 01 定义的语言都是0n1n0^n1^n

image-20250622133110937

3. 文法类型

文法类型定义限制理解
无限制文法α→β,α∈V+,β∈V∗\alpha \to \beta, \alpha \in V^+, \beta \in V^*产生式的右边可以是任意符号串符号可以随便变换
上下文有关文法α A β  →  α γ β,γ∈V+\alpha\,A\,\beta \;\to\; \alpha\,\gamma\,\beta, \gamma \in V^+产生式的右部长度必须大于左部长度，即不会收缩符号串能不能替换 A，要看它前面后面是什么符号
上下文无关文法A→γ,A∈VN,γ∈V∗A \to \gamma, A \in V_N, \gamma \in V^*产生式的左部必须是单一非终结符无论A周围跟什么符号，都可以独立替换成任意符号
正规文法A→aBA \to aB 或A→aA \to a 或A→εA \to \varepsilon，且A,B∈VN,a∈VTA, B \in V_N, a \in V_T右侧最多只能带一个非终结符，并且要么在开头（左线性）要么在结尾（右线性）虽然不管A周围跟什么符号，但是需要右侧只拖一个非终结符

4 种文法类型的定义是逐步增加限制的，因此每一型文法都包含前一型文法

4. 文法使用

4.1 规范推导与规范句型

最左推导：在每一步推导中，总是优先替换最左边的非终结符

最右推导 / 规范推导：在每一步推导中，总是优先替换最右边的非终结符

规范句型：由规范推导所得的句型

image-20250622134059278

4.2 语法树

推导树/语法树（Parse Tree）：表示一个符号串根据文法规则的推导过程的树形结构

  • 根节点：起始符
  • 内部节点：产生式中被替换的非终结符
  • 叶子节点：最终得到的符号串中的各个终结符
  • 直接子节点从左到右的顺序必须与产生式右部一致，内部节点 A 的直接子结点从左到右构成了一个推导A→A1A2…AnA \to A_1A_2 \ldots A_n
  • 叶子节点从左到右的顺序必须与符号串一致

二义性：如果一个文法存在某个句子对应两棵不同的语法树，也就是存在两个推导，则说这个文法是二义的

4.3 句型分析

句型分析：识别一个符号串是否为某文法的句型，等价于识别是否能根据文法构造出该符号串的语法树，等价于识别当前符号串是否在语法上正确

  • 自上而下（Top-Down）
    • 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导
    • 将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串
  • 自下而上（Bottom-Up）
    • 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号
    • 从输入符号串开始，以它作为语法树的末端结点符号串，自底向上的构造语法树

考虑文法G[S]: S->cAd, A->ab, A->a，对于输入串 w = cabd

  • 自顶向下：先对起始符号 S 利用产生式得到 S=>cAd，此时 c 已经匹配，考虑下一节点 A，利用产生式得到 cAd=>cabd，此时与输入串完全匹配，因此认为 w 是文法 G 的句子

  • 自底向上：先对符号串 cabd 分析，发现 a 和 ab 都可以归约，考虑对 a 进行归约得到 cAbd，此时没有产生式可以用于归约，因此回溯到上一步对 ab 进行归约得到 cAd，然后再对 cAd 进行归约可以得到 S

4.4 短语与句柄

短语：对于给定的文法 G 和句型αβδ\alpha\beta\delta，如果存在某个非终结符 A 使得S⇒∗αAδS \Rightarrow^* \alpha A \delta 且A⇒+βA \Rightarrow^+ \beta，则称β\beta 是句型αβδ\alpha\beta\delta 相对于非终结符 A 的短语

直接短语：特别的，对上述定义如果有A→βA \to \beta，则称β\beta 是句型αβδ\alpha\beta\delta 相对于非终结符 A 的直接短语

句柄：是自底向上分析中当前句型的最左直接短语，是可以立即归约为非终结符的短语，又称为可归约串

语法树和句型

  • 短语：以某个非终结符为根节点的子树下，所有叶子节点拼起来的串

  • 直接短语：两层子树的所有叶子节点拼起来的串

  • 句柄：位于最左边的直接短语

image-20250622135614688

4.5 限制

有害规则：虽然形式上符合文法，但是对语言的推导产生负面影响，如引起文法的二义性或增加解析复杂度

多余规则：在文法中存在但实际上对于生成语言没有任何贡献或可以被其他规则替代

  • 不可到达：非终结符不在任何规则的右部出现
  • 不可终止：不能推导出终结符的非终结符

image-20250622135839784