【计算理论】上下文无关语法 ( 代数表达式 | 代数表达式示例 | 确定性有限自动机 DFA 转为 上下文无关语法 )

I . 代数表达式 语法

---

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 \quad | \quad Term$Expression→Expression+Term∣Term

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

3 . $Term$Term 项 规则 :

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

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

4 . $Factor$Factor 因子 规则 :

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

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

II . 代数表达式 语法 示例

---

为字符串 $(a + a) \times a$(a+a)×a 构建 语法分析树 ;

1 . 起始状态 : 语法的起始状态是 $Expression$Expression , 根据 $Expression \to Expression + Term \quad | \quad Term$Expression→Expression+Term∣Term 规则 , $Expression$Expression 可以使用 $Term$Term 替换 , 直接从起始状态 , 使用 $Term$Term 替换 $Expression$Expression ;

2 . $(a + a) \times a$(a+a)×a 字符串的语法分析树 :

符号 : 其中有 $\times$× 乘号 ;

语法分析树 : $(a + a) \times a$(a+a)×a 中间有 $\times$× , 带有 $\times$× 乘号的替换规则为 $Term \to Term \times Factor | Factor$Term→Term×Factor∣Factor , 显然该项很显然是一个 $Term$Term 项 ;

3 . 根据上述 $Term \to Term \times Factor$Term→Term×Factor 可知 , $Term$Term 是由 $Term \times Factor$Term×Factor 进行替换的 , 左侧的 $(a + a)$(a+a) 是一个 $Term$Term , 右侧的 $a$a 是一个 $Factor$Factor ;

4 . 根据 $Factor \to Expression | a$Factor→Expression∣a 规则 , 右侧的 $Factor$Factor 直接使用 $a$a 进行替代 , 可得如下语法分析树 :

5 . 想办法将左侧的 $Term$Term 替换成 $(a + a)$(a+a) :

加法只能是 $Expression$Expression , 先替换成 $Expression$Expression ;

6 . 这里先使用 $Factor$Factor 替换 $Term$Term : 使用规则 $Term \to Term \times Factor | Factor$Term→Term×Factor∣Factor ;

7 . 在使用 $Expression$Expression 替换 $Factor$Factor : 使用规则 $Factor \to Expression | a$Factor→Expression∣a ;

8 . 使用 $Expression + Term$Expression+Term 替换 $Expression$Expression : 使用规则 $Expression \to Expression + Term | Term$Expression→Expression+Term∣Term ;

9 . 使用 $Term$Term 替换 左侧的 $Expression$Expression : 使用规则 $Expression \to Expression + Term | Term$Expression→Expression+Term∣Term ;

10 . 使用 $Factor$Factor 替换左侧的 $Term$Term : 使用规则 $Term \to Term \times Factor | Factor$Term→Term×Factor∣Factor ;

11 . 使用 $a$a 替换左侧的 $Factor$Factor : 使用规则 $Factor \to Expression | a$Factor→Expression∣a ;

12 . 使用 $Factor$Factor 替换右侧的 $Term$Term : 使用规则 $Term \to Term \times Factor | Factor$Term→Term×Factor∣Factor ;

13 . 使用 $a$a 替换右侧的 $Factor$Factor : 使用规则 $Factor \to Expression | a$Factor→Expression∣a ;

最终的 语法分析树为 :

此时可以得到语法分析树 ; 该语法分析树是一个代数表达式 ; 将该语法分析树写出 , 即可理解 上下文无关 语法 ;

代数表达式就是上下文无关的语法 ;

III . 设计 上下文无关语法

---

给定语言 , 设计上下文无关语法 , 使用该语法可以生成该语言 ;

上下文无关语法 设计技巧 : 将复杂的语言分解 , 化整为零 , 针对每个部分设计上下文无关的语法 , 最终将这些语法合并在一起 ;

上下文无关语法 与 自动机 : 如果给定的语言是正则语言 , 是由正则表达式表达的 , 能够找到一个自动机可以识别该语言 , 首先将语言转换成自动机 , 将自动机转化为上下文无关的语法 ;

IV . 确定性有限自动机 DFA 转为 上下文无关语法

---

1 . 确定性有限自动机 ( DFA ) 转为 上下文无关语法 ( CFG ) : 将 确定性有限自动机 ( DFA ) 的指令 , 转为 对应的 上下文无关语法 ( CFG ) 规则 :

$\delta ( q_i, a ) = q_j \Rightarrow R_i \to aR_j$δ(qi​,a)=qj​⇒Ri​→aRj​

$\delta ( q_i, a ) = q_j$δ(qi​,a)=qj​ 表示 $q_i$qi​ 状态下 , 读取字符 $a$a , 跳转到 $q_j$qj​ 状态 ;

2 . 自动机的 状态跳转 转换成 规则 示例 : 上图中的 确定性有限自动机 , 开始状态 $A$A 读取 $1$1 字符 转化成 $B$B 状态 , 表示成规则就是

$R_A \to 1R_B$RA​→1RB​

3 . 自动机的状态 $A$A 读取 字符 $a$a 转换成另一个状态 $B$B , 都可以转换成对应的规则 $R_A \to aR_B$RA​→aRB​ ;

4 . 计算能力对比 : 上下文无关语法 的计算能力 要大于等于 自动机的计算能力 ;