【计算理论】上下文无关语法 ( 语法组成 | 规则 | 语法 | 语法示例 | 约定的简写形式 | 语法分析树 )

I . 语法组成

---

上下文无关语法 组成 : 由 $\{ \quad V , \Sigma , R , S \quad \}${V,Σ,R,S} 四部分组成 ;

变量集 $V$V : 有限的变量集合 ;

终端字符集 $\Sigma$Σ : 有限的终端字符组成的集合 ; 相当于常量的含义 , 与变量相对 ;

规则集 $R$R : 有限的规则组成的集合 , 规则规定如何进行代换操作 , 规定 变量 , 终端字符 , 字符串变量 等 ;

开始变量 $S$S : 该变量作为开始变量 ;

II . 规则

---

规则 简介 :

① 已知条件 : 假设 $u, v , w$u,v,w 是 变量 ( 变元 ) 或 终端字符集 ( 常量 / 常元 ) ;

② 规则描述 : 规则是一个箭头 , $A \to w$A→w , $A$A 是变元 , $w$w 是 变元 和 常元 组成的终端字符 ;

③ 规则用法 : 在字符串中 , 根据 $A \to w$A→w 规则进行替换 , 只需要将 $A$A 变元替换成 $w$w 字符串即可 ;

④ 规则示例 : $uAv$uAv 中使用上述规则进行替换 , 将 $A$A 替换成 $w$w , 替换结果是得到新字符串 $uwv$uwv ;

$uAv \Rightarrow uwv$uAv⇒uwv

III . 语法

---

1 . 有限次规则替换 : $u \Rightarrow *v$u⇒∗v 表示有限多次替换后 , 每一步替换的临时结果序列组成集合 $\{u_1 , u_2 , \cdots , u_k\}${u1​,u2​,⋯,uk​} , 最终结果是 终端字符 ;

2 . 有限次规则替换 步骤 :

• $u$u 根据某规则进行替换得到 $u_1$u1​ ;
• $u_1$u1​ 根据某规则进行替换得到 $u_2$u2​ ;
• $\vdots$⋮
• $u_k$uk​ 根据某规则进行替换得到 $v$v ;

3 . 最终规则替换结果要求 : $v$v 中不包含变元 , 全部由 终端字符 ( 常元 ) 组成的 字符串 ;

$v$v 是由 $u$u 生成的 ;

4 . 语法定义 : 从开始变元 , 使用规则逐步替换 , 替换到最后 , 将所有 终端字符组成字符串 放在一个集合中 , 称为语法生成的语言 ;

$L(G) = \{ w \in \Sigma^* : S \Rightarrow *w \}$L(G)={w∈Σ∗:S⇒∗w}

IV . 语法示例

---

1 . 语法组成部分 : $G3 =( \; \{ S \}, \{ a, b \}, R , S \; )$G3=({S},{a,b},R,S) 其组成如下 :

• 变量集 $\{ S \}${S} ;

• 终端字符集 $\{ a, b \}${a,b} ;

• 规则 $R$R ;

• 开始变量 $S$S ;

2 . 规则 $R$R 描述 :

$S \to aSb \; | \; SS \; | \; \varepsilon$S→aSb∣SS∣ε

• $S$S 变量 可以使用 $aSb$aSb 字符串替换 ;
• $S$S 变量 可以使用 $SS$SS 字符串替换 ;
• $S$S 变量 可以使用 $\varepsilon$ε 字符串替换 ;

3 . 规则替换过程 :

① $S$S 是开始变量 , 可以使用 $aSb$aSb 替换 :

$S \Rightarrow aSb$S⇒aSb

② 使用 $aSb$aSb 替换 $S$S :

$S \Rightarrow aSb \Rightarrow aaSbb$S⇒aSb⇒aaSbb

③ 使用 $SS$SS 替换 $S$S :

$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaSSbb$S⇒aSb⇒aaSbb⇒aaSSbb

④ 使用 $aSb$aSb 替换第一个 $S$S :

$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaSSbb \Rightarrow aaaSbSbb$S⇒aSb⇒aaSbb⇒aaSSbb⇒aaaSbSbb

⑤ 使用 $\varepsilon$ε 替换第一个 $S$S :

$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaSSbb \Rightarrow aaaSbSbb \Rightarrow aaabSbb$S⇒aSb⇒aaSbb⇒aaSSbb⇒aaaSbSbb⇒aaabSbb

⑥ 使用 $aSb$aSb 替换 $S$S :

$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaSSbb \Rightarrow aaaSbSbb \Rightarrow aaabSbb \Rightarrow aaabaSbbb$S⇒aSb⇒aaSbb⇒aaSSbb⇒aaaSbSbb⇒aaabSbb⇒aaabaSbbb

⑦ 使用 $\varepsilon$ε 替换 $S$S :

$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaSSbb \Rightarrow aaaSbSbb \Rightarrow aaabSbb \Rightarrow aaabaSbbb \Rightarrow aaababbb$S⇒aSb⇒aaSbb⇒aaSSbb⇒aaaSbSbb⇒aaabSbb⇒aaabaSbbb⇒aaababbb

最终得到 $aaababbb$aaababbb 字符串 , 该字符串全部由终端字符构成 , 是从 $S$S 开始状态出发 , 按照 $R$R 规则替换得来的 ;

称该字符串由 语法 $G3$G3 生成的 ;

V . 语法简写形式

---

语法可以使用下面的形式简单表示 , 没有必要使用繁琐的形式 , 可以使用约定的简写形式 ;

约定写法 :

• $A \to 0A1$A→0A1
• $A \to B$A→B
• $B \to l$B→l

开始状态约定 : 左上方的变元 $A$A 约定是 开始变元 ;

变元约定 : 大写字母 $A,B$A,B 约定为 变元 ;

终端字符约定 : 小写字母 约定为 终端字符 ;

VI . 语法分析树

---

语法分析树 : 字符串生成的过程 , 可以写成语法分析树 ;

将上述 简写的 约定语法描述 , 生成 终端字符构成的字符串 ;

1 . 开始状态 : $A$A , 使用 $0A1$0A1 替换 $A$A ;

$A \Rightarrow 0A1$A⇒0A1

当前语法分析树 :

2 . 使用 $0A1$0A1 替换 $A$A ;

$A \Rightarrow 0A1 \Rightarrow 00A11$A⇒0A1⇒00A11

当前语法分析树 :

3 . 使用 $0A1$0A1 替换 $A$A ;

$A \Rightarrow 0A1 \Rightarrow 00A11 \Rightarrow 000A111$A⇒0A1⇒00A11⇒000A111

当前语法分析树 :

4 . 使用 $B$B 替换 $A$A ;

$A \Rightarrow 0A1 \Rightarrow 00A11 \Rightarrow 000A111 \Rightarrow 000B111$A⇒0A1⇒00A11⇒000A111⇒000B111

当前语法分析树 :

5 . 使用 $l$l 替换 $B$B ;

$A \Rightarrow 0A1 \Rightarrow 00A11 \Rightarrow 000A111 \Rightarrow 000B111 \Rightarrow 000l111$A⇒0A1⇒00A11⇒000A111⇒000B111⇒000l111

当前语法分析树 :

6 . 最终得到的字符串为 $000l111$000l111 ;

VII . 代数表达式 语法

---

1 . 代数表达式 语法 : $G4 = ( V , A , R , Expression )$G4=(V,A,R,Expression) 是代数表达式语法 ;

① 终端字符集 : $A = \{ a , + , \times , () \}$A={a,+,×,()} ;

② 变量集 : $V = \{ Expression , Term , Factor \}$V={Expression,Term,Factor} ;

• $Expression$Expression 是表达式 ;
• $Term$Term 是项 ;
• $Factor$Factor 是因子 ;

2 . $Expression$Expression 表达式 规则 :

$Expression \to Expression + Term | Term$Expression→Expression+Term∣Term

$Expression$Expression ( 表达式 ) 可以通过 $Expression + Term | Term$Expression+Term∣Term 代替 ;

3 . $Term$Term 项 规则 :

$Term \to Term \times Factor | Factor$Term→Term×Factor∣Factor

$Term$Term 项 可以通过 $Term \times Factor | Factor$Term×Factor∣Factor 代替 ;

4 . $Factor$Factor 因子 规则 :

$Factor \to Expression | a$Factor→Expression∣a

$Factor$Factor 因子 可以通过 $Expression | a$Expression∣a 代替 ;