编译原理-文法复习

亦凉 2022-06-01 11:42 237阅读 0赞

# 文法的相关概念 #

> 文法是以有穷的集合刻画无穷的集合的一个工具。  
> 语言：是句子组成的集合，是由一组符号所构成的集合  
> 语法：是每个句子构成的规则  
> 语义：是每个句子的含义

闭包的概念：

> \*代表任意次推导，也叫克林闭包  
> \+代表至少一次推导，成为正闭包。

文法定义为四元组（Vn，Vt，P，S）

> Vn：非终结符的集合（一般用大写字母表示）  
> Vt：终结符的集合（一般用小写字母表示）  
> P：产生式的集合  
> S：为开始符号

推导：用产生式的右侧来替换产生式的左侧。  
规约：用产生式的左侧来替换产生式的右侧。

句型：从文法的开始符号经过任意次推导可以得到的符号串，称为一个句型，一个文法可以有很多个句型。

文法是用来描述语言的，这个语言是该文法一切句子的集合。

# 文法的类型 #

乔姆斯基把文法分成4中类型，0型、1型、2型、3型，他们的差别在于对产生式施加不同的限制。

0型文法(PSG)： α∈(VN∪VT)\* ，且至少含一个VN  
β∈(VN∪VT)\*  
对产生式没有任何限制

例如：A0→A0 , A1→B  
0型文法说明：  
0型文法也称为短语文法。  
  一个非常重要的理论结果是，0型文法的能力相当于图灵机（Turing）。或者说，任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。  
  对0型文法产生式的形式作某些限制，以给出1，2和3型文法的定义。  
（注意）  
文法G 定义为四元组（VN ,VT ,P,S）  
¨VN ：非终结符集  
¨VT ：终结符集  
¨P ：产生式集合（规则集合）  
¨S ：开始符号（识别符号）

1型文法（上下文有关文法context-sensitive）：  
　　对任一产生式α→β，都有|β|>=|α|， 仅仅 S→ε除外  
　　产生式的形式描述：α1Aα2→α1βα2  
　　(其中，α1、α2、β∈（VN∪VT）\*，β≠ε，A∈VN)  
　　即：A只有出现在α1α2的上下文中，才允许用β替换。  
　　产生的语言称“上下文有关语言”但S不能出现在产生式的右部。

例如：0A0→011000 1A1→101011

2型文法(CFG)：对任一产生式α→β，都有α∈VN，β∈（VN∪VT）\*  
　　产生式的形式描述：A→β(A∈VN)  
　　即β取代A时，与A所处的上下文无关。  
　　产生的语言称“上下文无关语言”  
　　例如：G\[S\]：S→01 S→0S1

3型文法(RG)：也称正规文法  
　　每个产生式均为 “A→aB”或“A→a” —— 右线性  
　　 “A→Ba”或“A→a” —— 左线性  
　　其中，A、B∈VN，a∈VT\*  
　　产生的语言称“正规语言”  
　　例如：G\[S\]： S→0A | 0  
　　A→1B | B  
　　B→1 | 0

> 4个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。

# 语法树 #

> 子树：由任意节点和它的分支所构成的部分树。  
> 简单子树：只有父子两代的子树。  
> 句型：每棵子树的叶子组成一个句型  
> 短语：每棵子树的叶子组成一短语  
> 简单短语：每棵简单子树的叶子组成一个简单短语  
> 句柄：最左边简单子树的叶子构成一个句柄。  
> 素短语：不含其它短语的短语  
> 最左素短语：最左边的素短语

规范：

> 如果每次推导都是对最左（最右）边的非终结符进行替换，则成这种推导为最左（最右）推导。最右推导称为规范推导，由规范推导所得的句型称为右句型或规范句型。
> 
> 最左规约为规范规约。

## 句型的分析 ##

就是识别一个符号串是否为某文法的句型。分为：自顶向下和自底向上。

> **自顶向下**是从文法的开始符号触发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。  
> 问题：如何选择那一个推导式来进行推导
> 
> **自底向上**则是从输入符号开始，逐步进行“规约”，直至规约到文法的开始符号。  
> 问题：如何识别可规约的串