文章目录
I . 代数表达式 语法
1 . 代数表达式 语法 :
G4 = ( V , A , R , Expression ) 是代数表达式语法 ;
① 终端字符集 :
A = \{ a , + , \times , () \} ;
② 变量集 :
V = \{ Expression , Term , Factor \} ;
Expression 是表达式 ;
Term 是项 ;
Factor 是因子 ;
2 .
Expression 表达式 规则 :
Expression \to Expression + Term \quad | \quad TermExpression ( 表达式 ) 可以通过
Expression + Term \quad | \quad Term 代替 ;
3 .
Term 项 规则 :
Term \to Term \times Factor \quad | \quad FactorTerm 项 可以通过
Term \times Factor \quad | \quad Factor 代替 ;
4 .
Factor 因子 规则 :
Factor \to Expression \quad | \quad aFactor 因子 可以通过
Expression \quad | \quad a 代替 ;
II . 代数表达式 语法 示例
为字符串
(a + a) \times a 构建 语法分析树 ;
1 . 起始状态 : 语法的起始状态是
Expression , 根据
Expression \to Expression + Term \quad | \quad Term 规则 ,
Expression 可以使用
Term 替换 , 直接从起始状态 , 使用
Term 替换
Expression ;
2 .
(a + a) \times a 字符串的语法分析树 :
符号 : 其中有
\times 乘号 ;
语法分析树 :
(a + a) \times a 中间有
\times , 带有
\times 乘号的替换规则为
Term \to Term \times Factor | Factor , 显然该项很显然是一个
Term 项 ;
3 . 根据上述
Term \to Term \times Factor 可知 ,
Term 是由
Term \times Factor 进行替换的 , 左侧的
(a + a) 是一个
Term , 右侧的
a 是一个
Factor ;
4 . 根据
Factor \to Expression | a 规则 , 右侧的
Factor 直接使用
a 进行替代 , 可得如下语法分析树 :
5 . 想办法将左侧的
Term 替换成
(a + a) :
加法只能是
Expression , 先替换成
Expression ;
6 . 这里先使用
Factor 替换
Term : 使用规则
Term \to Term \times Factor | Factor ;
7 . 在使用
Expression 替换
Factor : 使用规则
Factor \to Expression | a ;
8 . 使用
Expression + Term 替换
Expression : 使用规则
Expression \to Expression + Term | Term ;
9 . 使用
Term 替换 左侧的
Expression : 使用规则
Expression \to Expression + Term | Term ;
10 . 使用
Factor 替换左侧的
Term : 使用规则
Term \to Term \times Factor | Factor ;
11 . 使用
a 替换左侧的
Factor : 使用规则
Factor \to Expression | a ;
12 . 使用
Factor 替换右侧的
Term : 使用规则
Term \to Term \times Factor | Factor ;
13 . 使用
a 替换右侧的
Factor : 使用规则
Factor \to Expression | a ;
最终的 语法分析树为 :
此时可以得到语法分析树 ; 该语法分析树是一个代数表达式 ; 将该语法分析树写出 , 即可理解 上下文无关 语法 ;
代数表达式就是上下文无关的语法 ;
III . 设计 上下文无关语法
给定语言 , 设计上下文无关语法 , 使用该语法可以生成该语言 ;
上下文无关语法 设计技巧 : 将复杂的语言分解 , 化整为零 , 针对每个部分设计上下文无关的语法 , 最终将这些语法合并在一起 ;
上下文无关语法 与 自动机 : 如果给定的语言是正则语言 , 是由正则表达式表达的 , 能够找到一个自动机可以识别该语言 , 首先将语言转换成自动机 , 将自动机转化为上下文无关的语法 ;
IV . 确定性有限自动机 DFA 转为 上下文无关语法
1 . 确定性有限自动机 ( DFA ) 转为 上下文无关语法 ( CFG ) : 将 确定性有限自动机 ( DFA ) 的指令 , 转为 对应的 上下文无关语法 ( CFG ) 规则 :
\delta ( q_i, a ) = q_j \Rightarrow R_i \to aR_j\delta ( q_i, a ) = q_j 表示
q_i 状态下 , 读取字符
a , 跳转到
q_j 状态 ;
2 . 自动机的 状态跳转 转换成 规则 示例 : 上图中的 确定性有限自动机 , 开始状态
A 读取
1 字符 转化成
B 状态 , 表示成规则就是
R_A \to 1R_B3 . 自动机的状态
A 读取 字符
a 转换成另一个状态
B , 都可以转换成对应的规则
R_A \to aR_B ;
4 . 计算能力对比 : 上下文无关语法 的计算能力 要大于等于 自动机的计算能力 ;