【编译原理】上下文无关语法和语言

r囧r小猫 2023-09-24 17:48 102阅读 0赞

### 上下文无关语法和语言 ###

*  回顾乔姆斯基层次结构（Chomsky Hierarchy）
 *  上下文无关语言
 *  上下文无关语法
 *  使用示例比较两种语法的写法
 *  使用语法生成属于该语言的字符串
 *   *  方法一：用双箭头来表示推导过程
     *  方法二：用树来表示
 *  语法语言
 *  上下文无关语法（CFG）的定义
 *  派生（Derivations）
 *  从语法中消除歧义
 *  下拉自动机(PDA)的正式定义
 *  上下文无关语法和自动机（Automata）

# 回顾乔姆斯基层次结构（Chomsky Hierarchy） #

乔姆斯基将语法分为4个类，每个类对应一种语言：  
![在这里插入图片描述][61900fd33d5d4a868d40a66750a81d2f.png]

类型2（上下文无关语法）：G中的规则为A → β、 A∈Vn，β∈V+  
由类型2定义的语言：L2或**上下文无关语言**  
抽水原理（Pumping Lemma）：接受或承认这类语言

类型3（正则语法）:G中的规则为  
A → aB or A → a, A、B∈Vn , a∈Vt  
A → Ba or A → a, A、B∈Vn , a∈Vt  
由类型3定义的语言：L3或**正则语言**  
有限自动机（Finite Automata）：接受或识别这种类型的语言

L0⊃L1⊃L2⊃L3 (L3限制条件最多的, 四种语法包含关系)  
类型0语法：α中至少有一个非终结符  
类型1语法：|α|≤|β|  
类型2语法：α∈Vn  
类型3语法：A→wB或A→Bw

如果语法是正则的，那么它必须是上下文无关的

# 上下文无关语言 #

并非所有语言都是正则的

事实证明，有一类更大的语言结合了L语言，事实上所有的正则语言：

1.  上下文无关语言
2.  正则语言是上下文无关语言的严格子集

# 上下文无关语法 #

定义上下文无关语言：

1.  实际上很重要（首次研究人类语言的结构）

应用于编程语言的编译器：

1.  指定语言的语法
2.  解析器用于从输入中提取可用于进一步编译的结构（例如抽象语法树）

# 使用示例比较两种语法的写法 #

**上下文无关语法:**  
左边代表结构的名字  
![在这里插入图片描述][58737c092d26447f9f24ef124528a10e.png]  
**正则表达式:**  
![在这里插入图片描述][67b36346e4114c2999bf04cb5caff1ce.png]

# 使用语法生成属于该语言的字符串 #

应用替换规则，直到没有变量。

获得字符串的替换序列称为派生（derivation）。

每个替换由⇒

## 方法一：用双箭头来表示推导过程 ##

![在这里插入图片描述][6636f706a8e94907805aa36dbdcfc2a4.png]

## 方法二：用树来表示 ##

派生的替代表示（我们将在后面讨论）  
![在这里插入图片描述][27dce2bfb123466fb6bc68f96edcae8b.png]

# 语法语言 #

**派生生成的所有字符串**  
任何可以由上下文无关语法生成的语言都是上下文无关语言。

# 上下文无关语法（CFG）的定义 #

![在这里插入图片描述][9123eff6c4964b69b47dad3eb1d8ff90.png]

# 派生（Derivations） #

**派生（Derivation，长度为n时）**：假设u0，u1，…，un（n>0）是V\*中的所有字符串，并且  
![在这里插入图片描述][e9ca73bd895848fb9c3bb2f4ee49f90a.png]  
然后，上述序列称为“长度n的推导”，也称为r**推导**（produces/yields）w，反之亦然（w规约（reduces）r）

***推导和规约是两个相反的过程***

# 从语法中消除歧义 #

尽量避免左递归的形式，容易出现二歧义的问题

# 下拉自动机(PDA)的正式定义 #

![在这里插入图片描述][f3baf527ac464adb8c55d6f3ac651420.png]

# 上下文无关语法和自动机（Automata） #

对于每个上下文无关语法，都有一个PDA可以识别相同的语言，反之亦然。

每个有限自动机都是PDA的特殊情况，其中堆栈内容无关紧要。

***Thanks to Dr. John: Some contents are from their slides.***

[61900fd33d5d4a868d40a66750a81d2f.png]: https://img-blog.csdnimg.cn/61900fd33d5d4a868d40a66750a81d2f.png
[58737c092d26447f9f24ef124528a10e.png]: https://img-blog.csdnimg.cn/58737c092d26447f9f24ef124528a10e.png
[67b36346e4114c2999bf04cb5caff1ce.png]: https://img-blog.csdnimg.cn/67b36346e4114c2999bf04cb5caff1ce.png
[6636f706a8e94907805aa36dbdcfc2a4.png]: https://img-blog.csdnimg.cn/6636f706a8e94907805aa36dbdcfc2a4.png
[27dce2bfb123466fb6bc68f96edcae8b.png]: https://img-blog.csdnimg.cn/27dce2bfb123466fb6bc68f96edcae8b.png
[9123eff6c4964b69b47dad3eb1d8ff90.png]: https://img-blog.csdnimg.cn/9123eff6c4964b69b47dad3eb1d8ff90.png
[e9ca73bd895848fb9c3bb2f4ee49f90a.png]: https://img-blog.csdnimg.cn/e9ca73bd895848fb9c3bb2f4ee49f90a.png
[f3baf527ac464adb8c55d6f3ac651420.png]: https://img-blog.csdnimg.cn/f3baf527ac464adb8c55d6f3ac651420.png