首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >【计算理论】上下文无关语法 ( 代数表达式 | 代数表达式示例 | 确定性有限自动机 DFA 转为 上下文无关语法 )

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

作者头像
韩曙亮
发布于 2023-03-27 20:15:47
发布于 2023-03-27 20:15:47
9190
举报

文章目录

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 Term
Expression

( 表达式 ) 可以通过

Expression + Term \quad | \quad Term

代替 ;

3 .

Term

项 规则 :

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

项 可以通过

Term \times Factor \quad | \quad Factor

代替 ;

4 .

Factor

因子 规则 :

Factor \to Expression \quad | \quad a
Factor

因子 可以通过

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_B

3 . 自动机的状态

A

读取 字符

a

转换成另一个状态

B

, 都可以转换成对应的规则

R_A \to aR_B

;

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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-05-18,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 文章目录
    • I . 代数表达式 语法
    • II . 代数表达式 语法 示例
    • III . 设计 上下文无关语法
    • IV . 确定性有限自动机 DFA 转为 上下文无关语法
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档