【计算理论】上下文无关语法 CFG ( CFG 设计示例 | CFG 歧义性 | Chomsky 范式 | 上下文无关语法转为 Chomsky 范式 )

韩曙亮

发布于 2023-03-27 20:16:17

1.8K0

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、上下文无关语法设计示例

1 . 上下文无关语法设计要求 : 设计一个语法 , 使用该语法生成语言

, 该

语言的字符串的开始和结尾的字符是相同的 ;

2 . 设计方法 : 非确定性优先自动机 ( NFA ) 识别某语言 , 将 NFA 转为确定性优先自动机 ( DFA ) , 然后将 DFA 转为上下文无关语法 ;

3 . 语法设计要求分析 :

开始字符要么是

, 要么就是

;

如果开始字符是

, 对应的结尾字符也是

;

如果开始字符是

, 对应的结尾字符也是

;

4 . 初始状态

规则 : 上述语法描述转为规则如下 , 其中

为初始状态 ;

S \to 0S'0 | 1S'1

5 .

规则 :

表示中间的字符串 , 这个

字符串可以是任意字符串 , 根据下面的规则可以生成任意的

0,1

组成的字符串 ;

S' \to 0S' | 1S' | \varepsilon

二、上下文无关语法的歧义性

给出如下上下文无关语法 ( CFG ) :

Expression \to Expression + Expression | Expression \times Expression | Expression | a

语法的含义是 :

Expression

可以被

Expression + Expression

替换 ;

Expression

可以被

Expression \times Expression

替换 ;

Expression

可以被

Expression

替换 ;

Expression

可以被

替换 ;

1 . 语法的有歧义性 : 同样的一个字符串 , 可以有不同的语法分析树 ;

① 语法分析树 1 :

2 . 在上述的语法分析树中 , 加法优先级高于乘法 , 这是错误的分析 ;

② 语法分析树 2 :

在上述的语法分析树中 , 乘法优先级高于加法 , 这是正确的分析 ;

3 . 语法歧义性分析 : 上述语法中是无法区分加法和乘法的优先级的 , 因此这里得到两个完全不一致得我语法分析树 , 那么该语法是有歧义的 ;

4 . 与代数表达式语法对比 : 之前讲的代数表达式是好的语法 , 乘法和加法的优先级也体现出来 , 乘法优先级高于加法 , 括号的优先级高于乘法 ;

① 代数表达式语法 :

Expression \to Expression + Term \quad | \quad Term

Term \to Term \times Factor \quad | \quad Factor

Factor \to Expression \quad | \quad a

② 代数表达式语法分析树 : 这个语法分析树是唯一的 , 没有其它的形式 , 该语法是没有歧义的 ;

③ 有歧义的语法 : 在本节的语法中 , 无法区分加法和乘法的优先级 , 该语法是有歧义的 ;

5 . 总结 : 如果语法有歧义 , 那么中间的字符串有歧义 ; 没有算法可以判定上下文无关语法是否有歧义 ; 有些语法天生就是有歧义的 , 但可以通过某种方法去掉语法中的歧义性 ;

三、Chomsky 范式

1 . Chomsky 范式 : 上下文无关语法中的任何规则都是如下格式 ;

①

A \to BC

是变元 ,

B,C

也是变元 ;

②

A \to a

是变元 ,

是常元 ,

可以被终端字符替换 ;

③

B ,C

变元要求 :

B, C

变元一定不能是开始变元 ;

④

S \to \varepsilon

开始变元可以为空 ;

⑤ 不能出现

变元 \to 变元

单个变元到单个变元不允许出现 ;

2 .

S \to \varepsilon

规则说明 :

① 语言包含空字符串 : 如果上下文无关语法包含空字符串时 , 一定需要

S \to \varepsilon

规则 ;

② 语言不包含空字符串 : 如果上下文无关语法不包含空字符串时 , 一定不需要

S \to \varepsilon

规则 ;

③ 规则总结 : 该规则决定上下文无关语法所生成的语言是否包含空字符串 , 如果包含必须要这个规则 , 如果不包含空字符串一定不要这个规则 ;

四、上下文无关语法转为 Chomsky 范式

Chomsky 范式规则的上下文无关语法生成的语言的语法分析树除叶子节点之外都是二叉树 , 叶子节点与上一层都是一对一的节点 ;

任何上下文无关语法 , 都可以找到一个 Chomsky 范式与其等价 ;

任何上下文无关语法的语法分析树都可以进行修剪 , 修剪后的树都是二叉树 ;

上下文无关语法转为 Chomsky 范式步骤 :

1 . 添加开始变元及规则 : 添加一个新的开始变元

S_0

, 以及配套的规则

S_0 \to S

是旧的开始变元 ;

① 目的 : 添加开始变元的目的是开始变元永远出现在左边 ;

② Chomsky 范式中 , 开始变元始终在规则的左边 , 不允许开始变元在规则的右侧 ;

③ 对应 Chomsky 范式规则 :

A \to BC

规则 ,

是变元 ,

B,C

也是变元 , 并且

B,C

不允许是开始变元 ;

2 . 消除所有的

\varepsilon

规则 : 消除所有从变元到空字符的规则 ;

3 . 消除所有的

A \to B

规则 : 消除所有从单个变元到单个变元的单条规则 , 允许从单个变元到多个变元或常元 ;

如

A \to B

是需要删除的 ,

A \to BS

可以保留 ;

五、上下文无关语法转为 Chomsky 范式示例

将上下文无关语法

转为 Chomsky 范式 :

S \to ASA | aB

A \to B|S

B \to b|\varepsilon

转换过程如下 :

1 . 添加新的开始变元 :

S_0

, 旧的开始变元

就不是开始变元了 ;

当前的语法格式如下 :

S_0 \to S

S \to ASA | aB

A \to B|S

B \to b|\varepsilon

2 . 消除

\varepsilon

规则 :

消除

\varepsilon

规则原则 : 假设有规则

C \to \varepsilon

D \to uCv

, 如果要删除

\varepsilon

规则 , 需要实现消除前后具有相同的替换效果 , 将规则改为

D \to uv

即可删除

\varepsilon

相关规则 ; ( 消除前后 , 替换效果必须一致 )

3 . 消除

B \to b|\varepsilon

中的

\varepsilon

: 会影响

S \to ASA | aB

和

A \to B|S

两条规则中涉及到了

变元 , 消除的原则是 " 消除前后 , 替换效果必须一致 " ;

3.1 .

S \to ASA | aB

规则消除

\varepsilon

分析 : 这里讨论消除

B \to b|\varepsilon

规则中的

B \to \varepsilon

规则对

的影响 ;

① 消除

B \to \varepsilon

规则前分析 : 使用

B \to b|\varepsilon

规则对

进行替换有两种情况 , 分别是

, 两种情况 ;

② 消除

B \to \varepsilon

规则后分析 : 如果要消除

B \to \varepsilon

规则 , 那么消除后的规则是

B \to b

, 使用

B \to b

规则对

进行替换 , 其替换结果必须是

, 两种情况 ;

分析

两种结果 :

使用

B \to b

规则替换 , 可以得到

;

替换结果无法获取 , 此时需要在

的平级 , 再次添加

即可达到上述效果 ;

最终修改方案 : 将

改为

aB|a

, 使用

B \to b

规则替换

aB|a

的结果是

, 与上述消除

B \to \varepsilon

规则前的结果一致 ;

③

S \to ASA | aB

规则对应的消除

B \to \varepsilon

规则后的结果为

S \to ASA | aB | a

④ 当前的语法格式如下 : 注意还没有讨论

A \to B|S

规则中的

B \to b|\varepsilon

规则中的

\varepsilon

还不能删除 ;

S_0 \to S

S \to ASA | aB | a

A \to B|S

: 注意此时该规则不完善 , 还没有删除

\varepsilon

;

B \to b

3.2 .

A \to B|S

规则消除

\varepsilon

分析 : 这里讨论消除

B \to b|\varepsilon

规则中的

B \to \varepsilon

规则对

的影响 ;

① 消除

B \to \varepsilon

规则前分析 : 使用

B \to b|\varepsilon

规则对

进行替换有两种情况 , 分别是

\varepsilon

, 两种情况 ;

② 消除

B \to \varepsilon

规则后分析 : 如果要消除

B \to \varepsilon

规则 , 那么消除后的规则是

B \to b

, 使用

B \to b

规则对

进行替换 , 其替换结果必须是

\varepsilon

, 两种情况 ;

分析

\varepsilon

两种结果 :

使用

B \to b

规则替换 , 可以得到

;

\varepsilon

替换结果无法获取 , 此时需要在

的平级 , 再次添加

\varepsilon

即可达到上述效果 ;

最终修改方案 : 将

改为

B|\varepsilon

, 使用

B \to b

规则替换

B|\varepsilon

的结果是

\varepsilon

, 与上述消除

B \to \varepsilon

规则前的结果一致 ;

③

A \to B|S

规则对应的消除

B \to \varepsilon

规则后的结果为

A \to B| \varepsilon|S

④ 当前的语法格式如下 : 注意还没有讨论

A \to B|S

规则中的

B \to b|\varepsilon

规则中的

\varepsilon

还不能删除 ;

S_0 \to S

S \to ASA | aB | a

A \to B| \varepsilon |S

B \to b

4 . 消除

A \to B| \varepsilon |S

中的

\varepsilon

: 会影响

S \to ASA | aB | a

规则中涉及到了

变元 , 消除的原则是 " 消除前后 , 替换效果必须一致 " ;

① 消除

ASA

中的

\varepsilon

, 添加以下项即可 :

第一个

通过

\varepsilon

代替 : 添加

项 ;

第二个

通过

\varepsilon

代替 : 添加

项 ;

两个

都通过

\varepsilon

代替 : 是

, 可以不同写 ,

S \to S

没啥意义 ;

②

S \to ASA | aB | a

规则对应的消除

A \to \varepsilon

规则后的结果为 :

S \to ASA | AS | SA | aB | a

③ 当前的语法格式如下 :

S_0 \to S

S \to ASA | AS | SA | aB | a

A \to B| S

B \to b

5 . 消除

A \to B

规则 :

假设要消除

C \to D

规则 : 如果语法中有

D \to W

规则 , 那么如果消除

C \to D

, 需要将

C \to W

体现出来 ;

消除

A \to B

规则 , 检查

出现在规则左边的情况 , 这里有

B \to b

规则 , 需要添加

A\to b

规则后 , 即可删除

A \to B

规则 ;

删除前规则 :

S_0 \to S

S \to ASA | AS | SA | aB | a

A \to B| S

B \to b

删除后规则如下 :

S_0 \to S

S \to ASA | AS | SA | aB | a

A \to b| S

6 . 消除

A \to S

规则 :

① 消除

A \to S

规则 , 检查

出现在规则左边的情况 , 这里有

S \to ASA | AS | SA | aB | a

规则 , 需要添加

A\to ASA | AS | SA | aB | a

规则后 , 即可删除

A \to S

规则 ;

② 删除前规则 :

S_0 \to S

S \to ASA | AS | SA | aB | a

A \to b | S

③ 删除后规则如下 :

S_0 \to S

S \to ASA | AS | SA | aB | a

A \to b| ASA | AS | SA | aB | a

7 . 分解规则 :

① 分解示例 :

S \to ASA

可以分解为

S \to R

R \to SA

② 分解前的规则 :

S_0 \to S

S \to ASA | AS | SA | aB | a

A \to b| ASA | AS | SA | aB | a

③ 分解后的规则 :

S_0 \to S

下面的规则是

S \to ASA | AS | SA | aB | a

分解后的规则 :

S \to R

R \to SA

S \to AS

S \to SA

S \to aB

S \to a

下面的规则是

A \to b| ASA | AS | SA | aB | a

分解后的规则 :

A \to b

A \to R

A \to SA

A \to AS

A \to SA

A \to aB

A \to a

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-05-19，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树