2023-03-28 20:19:14
浏览数 (1)
文章目录
- 一、乔姆斯基范式
- 二、上下文无关语法转为乔姆斯基范式步骤
- 三、上下文无关语法转为乔姆斯基范式示例1
- 四、上下文无关语法转为乔姆斯基范式示例 2
参考博客 :
- 【计算理论】上下文无关语法 ( 语法组成 | 规则 | 语法 | 语法示例 | 约定的简写形式 | 语法分析树 )
- 【计算理论】上下文无关语法 ( 代数表达式 | 代数表达式示例 | 确定性有限自动机 DFA 转为 上下文无关语法 )
- 【计算理论】上下文无关语法 CFG ( CFG 设计示例 | CFG 歧义性 | Chomsky 范式 | 上下文无关语法 转为 Chomsky 范式 )
一、乔姆斯基范式
1 . Chomsky 范式 : 上下文无关语法中的任何规则都是如下 格式 ;
① 单个变元到
2 个变元
rm A to BC :
A 是 变元 ,
rm B,C 也是变元 ;
② 单个变元到常元
rm A to a :
rm A 是 变元 ,
rm a 是常元 ,
rm A 可以被终端字符替换 ;
③
rm B ,C 变元要求 :
rm B, C 变元一定不能是开始变元 ;
④
rm S to varepsilon :
rm S 开始变元可以为空 ;
⑤ 不能出现
rm 变元 to 变元 单个变元 到 单个变元不允许出现 ;
2 .
rm S to varepsilon 规则 说明 :
① 语言包含空字符串 : 如果上下文无关语法包含空字符串时 , 一定 需要
rm S to varepsilon 规则 ;
② 语言不包含空字符串 : 如果上下文无关语法不包含空字符串时 , 一定 不需要
rm S to varepsilon 规则 ;
③ 规则总结 : 该规则决定 上下文无关语法 所生成的语言 是否包含 空字符串 ; 如果包含 , 必须要这个规则 ; 如果不包含 , 空字符串一定不要这个规则 ;
二、上下文无关语法转为乔姆斯基范式步骤
上下文无关语法转为乔姆斯基范式步骤 :
1 . 添加开始变元及规则 : 添加一个新的 开始变元
rm S_0 , 以及配套的规则
rm S_0 to S ,
rm S 是旧的开始变元 ;
① 目的 : 添加开始变元的目的是 开始变元 永远出现在左边 ;
② Chomsky 范式 中 , 开始变元始终在规则的左边 , 不允许开始变元在规则的右侧 ;
③ 对应 Chomsky 范式 规则 :
rm A to BC 规则 ,
rm A 是 变元 ,
rm B,C 也是变元 , 并且
rm B,C 不允许是开始变元 ;
2 . 消除所有的
varepsilon 规则 : 消除所有 从 变元 到 空字符 的规则 ;
3 . 消除所有的
rm A to B 规则 : 消除所有 从 单个变元 到 单个变元的 单条规则 , 允许从 单个变元 到 多个变元或常元 ; 如 :
rm A to B 是需要删除的 ,
rm A to BS 可以保留 ;
4 . 添加变元 : 将
rm A to BCD 规则 , 转为
rm A to ED 规则 , 添加变元
rm E to BC ;
三、上下文无关语法转为乔姆斯基范式示例1
将 上下文无关语法 转为 Chomsky 范式 :
rm S to ASA | aBrm A to B|Srm B to b|varepsilon1 . 添加新的开始变元 :
rm S_0 ;
rm S_0 to Srm S to ASA | aBrm A to B|Srm B to b|varepsilon2 . 消除
rm B to varepsilon 规则 : 根据消除前后等价原则 , 重新构造含有
rm B 的规则 ; 消除
rm B to varepsilon , 即在对应的含有
rm B 的规则中添加
rm B 为空的情况 ,
rm aB 如果
rm B 为空就是
rm a ,
rm B 如果
rm B 为空就是
rm varepsilon ;
rm S_0 to Srm S to ASA | aB | arm A to B| varepsilon |Srm B to b3 . 消除
rm A to varepsilon 规则 : 根据消除前后等价原则 , 重新构造含有
rm A 的规则 ; 消除
rm A to varepsilon , 即在对应的含有
rm A 的规则中添加
rm A 为空的情况 ,
rm ASA 如果
rm A 为空就产生
rm S , AS, SA 三种 ( 考虑不同
rm A 为空的情况 ) ;
rm S_0 to Srm S to ASA | AS | SA | aB | arm A to B| Srm B to b4 . 消除
rm A to B 规则 : 找
rm B 出现在左边的情况 , 发现有
rm B to b 规则 , 直接使用
rm A to b 替换
rm A to B 规则 ; ( 注意 :
rm B to b 规则 不变 )
rm S_0 to Srm S to ASA | AS | SA | S | aB | arm A to b | Srm B to b5 . 消除
rm S_0 to S 规则 : 找
rm S 出现在左边的情况 , 发现有
rm S to ASA | AS | SA | S | aB | a , 使用
rm S_0 to ASA | AS | SA | S | aB | a , 替换
rm S_0 to S ; ( 注意 :
rm S to ASA | AS | SA | S | aB | a 规则不变 )
rm S_0 to ASA | AS | SA | S | aB | arm S to ASA | AS | SA | aB | arm A to b | ASA | AS | SA | aB | arm B to b6 . 添加变元 : 添加新规则
rm R to SA ;
rm S_0 to AR | AS | SA | S | aB | arm S to AR | AS | SA | aB | arm A to b | AR | AS | SA | aB | arm R to SArm B to b四、上下文无关语法转为乔姆斯基范式示例 2
将 上下文无关语法转为 Chomsky 范式 :
rm A to BAB | B | varepsilonrm B to 00 | varepsilon1 . 添加新的开始变元 :
rm S_0 ;
rm S_0 to Arm A to BAB | B | varepsilonrm B to 00 | varepsilon2 . 消除
rm B to varepsilon 规则 : 根据消除前后等价原则 , 重新构造含有
rm B 的规则 , 即添加使用
varepsilon 替换
rm B 的各种情况 , 如 :
rm BAB , 替换
1 个
rm B 两种情况 , 替换
2 个
rm B 一种情况 ;
rm S_0 to Arm A to BAB | BA | AB | A | B | varepsilonrm B to 003 . 消除
rm A to varepsilon 规则 : 根据消除前后等价原则 , 重新构造含有
rm A 的规则 , 如 :
rm BAB 如果
rm A 为空 就是
rm BB ,
rm AB 如果
rm A 为空 , 多出一个
rm B ;
rm S_0 to Arm A to BAB | BA | AB | A | B | BBrm B to 004 . 消除
rm A to B 规则 : 找
rm B 出现在左边的情况 , 发现有
rm B to 00 规则 , 直接使用
rm A to 00 规则 替换
rm A to B 规则 ; ( 注意 :
rm B to 00 规则 不变 )
rm S_0 to Arm A to BAB | BA | AB | A | 00 | BBrm B to 005 . 消除
rm S_0 to A 规则 : 找
rm A 出现在左边的情况 , 发现有
rm A to BAB | BA | AB | A | 00 | BB 规则 , 直接使用
rm S_0 to BAB | BA | AB | A | 00 | BB 规则 替换
rm S_0 to A 规则 ; ( 注意
rm A to BAB | BA | AB | A | 00 | BB 规则 规则不变 )
rm S_0 to BAB | BA | AB | A | 00 | BBrm A to BAB | BA | AB | A | 00 | BBrm B to 006 . 添加变元 : 添加新规则
rm R to BA ; 目的是使用
2 个变元的规则替换
3 个变元的规则 ;
rm S_0 to RB | BA | AB | A | 00 | BBrm A to RB | BA | AB | A | 00 | BBrm B to 00rm R to BA7 . 添加变元 : 添加新规则
rm C to 0 ; 目的是将
rm B to 00 中的
2 个终端字符转为两个变元 ;
rm S_0 to RB | BA | AB | A | CC | BBrm A to RB | BA | AB | A | CC | BBrm B to CCrm R to BArm C to 0
