编译原理：文法和语言type
status
date
slug
summary
tags
category
icon
password
文法和语言的基础知识
1 基本概念
1.1 字母表
字母表是元素的有穷非空集合。
- 汉语字母表：汉字、数字和标点符号的集合。
- 英语字母表：字母、数字、标点符号的集合。
- C语言字母表：字母、数字和若干专用符号的集合
1.2 符号和符号串
字母表中的元素称为符号，或称为字符。
符号的有穷序列称为符号串。
- 由有穷多个符号组成。
- 不同顺序的符号排列看做不同的符号串。
- 符号串的长度指的是符号串符号的个数。
- 不包含任何符号的符号串，称为空符号串，用
ε表示，其长度|ε|=0。
1.3 符号串的运算法则
- 符号串的连接：两个字符串的顺序拼接。
- x=abc,y=10a ==> xy=abc10a
- εx=xε=x
- 集合的乘积：其实就是笛卡尔积的运算
- A={a，b}，B={c，d},则AB={ac,ad,bc,bd}
- {ε}A = A{ε} = A
- 符号串的幂运算：字符串的n次连接
- x^0=ε
- x^1=x
- x^2=xx
- 集合的幂运算
- A^0={ε}
- A^1=A
- A^2=AA
- A^n=A[A^(n-1)]
- 集合的正闭包与闭包(*是全选的意思)
- A* = A^0 ∪ A^1 ∪ A^2 ∪......∪ A^n
- A+ = A^1 ∪ A^2 ∪......∪ A^n
- 集合上的正闭包表示A上元素a,b构成的所有符号串的集合，集合A的闭包比集合A的正闭包多含一个空符号串ε
1.4 符号表示
（1）符号”::=”表示“···是由···组成的”
（2)符号”|”表示“或者”的意义
（3)符号”=>”表示“推导”
S +⇒ 011，表示经过 1 步或者多步推导
S *⇒ 011，表示经过 0 步或者多步推导。
- 符号串长度：符号串α的长度是指符号串α中含有符号的个数，记为︱α︱。特别约定，空串ε为零，即︱α︱＝0。
- 符号串集合：如果集合A的元素都是字母表∑上的符号串，则称集合A为∑上的符号串集合，简称串集。
2 文法
2.1 形式语言
序列的集合称为形式语言，每个形式语言都是某个字母表上按某种规则构成的所有符号的集合。
语言包括语法和语义两个方面,形式语言是指不考虑语言的具体意义，即不考虑语义。
形式语言的两种描述方法：
- 有穷集合的语言：枚举法
- 无穷集合的语言：文法
2.2 文法
文法是描述语言语法结构的形式规则。它的形式化定义是一个四元组，即 G = { VN , VT , P , S }。文法借鉴了递归函数、数学归约的类似思想。
文法G定义为一个四元组（VN，VT，P，S），记为G＝（VN，VT，P，S）。其中，① VN是非空有穷集合，称为非终结符集，其元素称为非终结符；② VT是有穷集合，称为终结符集，其元素称为终结符；③ P是非空有穷集合，称为规则集，其元素是字母表VN∪VT上的规则，VN∪VT称为文法的字母表V，且VN∩VT＝空集；④ S∈VN，称为开始符。
- VN 指的是非终结符集合。非终结符即
nonterminal symbol，它是用来表示语法成分的符号，有时候也称为“语法变量”。其中非终结意为“还没有到尽头，还可以继续拆分，一般用大写字母表示。
- VT 指的是终结符集合。终结符即
terminal symbol，它是文法所定义的语言的最基本符号，这意味着一个终结符不可再细分（注意“终结”这个词）。在编程语言中，终结符其实就是之前提到的 token，比如保留字、运算符、界符等这些最最基本的符号。终结符一般用小写字母表示。
- P 即
production，指的是产生式集合。终结符和非终结符的转换依靠的就是产生式（或者说生成式，推导规则）。 - 产生式形如 a → β （或者 a : : = β ，这种表示方法即巴科斯范式 ），意思是将 a 定义为 β。
- a 称为产生式左部，它是终结符集合的一个元素；而 β 称为产生式右部，它是终结符和非终结符并集的一个元素。
- 产生式的左部不能是终结符，因为左部都是可以继续细分的，但是终结符不能再细分了，而右部在一开始可能是非终结符（还没拆完），但在最后一定会变成终结符（拆完了，不能再拆了）。
- S 即
start symbol，指的是开始符号（识别符号）。它是最开始的那条产生式的左部，一切的推导都是从它这里开始进行的，可以认为它就是最大的那个成分。所以也注定了 S 必须在 P 中至少作为某一条产生式的左部（不然无从推导）。
3 语言的形式定义
3.1 直接推导
假如文法 G = { VN , VT , P , S } 有一条产生式为 a → β ，γ 和 δ 是 V*= VN ∪ VT 中的任意符号（即是文法中的任意终结符或者非终结符），若有符号串满足：
V = γ a δ ，W = γ β δ那么就说 V 可以直接推导得到 W，或者说 W 是 V 的直接推导，W 直接规约到 V —— 记作 V ⇒ W。
假如现在有文法 G =（{S，A，B}，{0，1}，P，S），其中，P = { S → 0A，S → 1B，A → 1B，B → 1 }。
那么以产生式 S → 0A 为例，我们是可以说 S ⇒ 0A 的，因为 S = εSε，0A = ε0Aε（别忘了，空符号串也是属于 V* 的），以此类推，所有的产生式实际上都是一个直接推导。
3.2 推导
推导指的是从文法的开始符号出发，反复连续地使用产生式，对非终结符施行替换和展开，最终得到一个仅由终结符构成的符号串，推导过程的每一步都是一个直接推导。
还是以上面的文法为例，那么就有 S ⇒ 0A ⇒ 01B ⇒ 011，这个序列就是从 S 到 011 的一个推导，或者说 S 可以推导出 011。
3.3 广义推导
序列可以简写为 S +⇒ 011，表示经过一步或者多步推导，而 S *⇒ 011 表示经过 0 步或者多步推导。
所以，S *⇒ 011 要么是 S = 011，要么是 S +⇒ 011。
3.4 最左/最右推导与归约
推导的过程并不是唯一的。对于任何一步 α ⇒ β，如果都是对 α 中的最左非终结符进行替换，那么就说最左推导，反之就是最右推导。
假如给定文法G：
E → E + E | E * E | (E) | i，由该文法最终可以推导得到句子 (i * i + i)。如果采用最右推导，那么过程就是：E ⇒ (E) ⇒ (E + E) ⇒ (E + i) ⇒ (E * E + i) ⇒ (E * i + i) ⇒ (i * i + i)。
在每一步中，我们都尽可能地替换 α 中的最右非终结符。
- 最右推导也成为规范推导，用规范推导推导出的句型称为规范句型。
- 归约是与推导相对的概念，是把句型中的某个子串用一个非终结符来替换的过程。用’·’+’⇒’表示归约。
- 规范推导的逆过程，称为最左归约，也称为规范归约。
4 句型、句子、语言
设文法G＝（VN，VT，P，S），如果有S=>* β，则称β是文法G的句型。如果有S=>* β，且β∈VT*，则称β是文法G的句子。
- 句型：如果 S *⇒ a，开始符号 S 可以推导得到某个符号串，那么这个符号串 a 就称为句型。以上面文法为例，0A ，01B，011 … 都是句型。
- 句子：在推导之初，句型可能既包含终结符也包含非终结符，但最终肯定只剩下终结符构成的符号串，此时这个符号串就称为句子。以上面文法为例，011 就是句子。
文法G＝（VN，VT，P，S）的产生语言定义为文法G的句子集合，记为L(G)。即：L(G)＝｛β︱S=>^^β，β∈VT^^｝。
- 语言：文法产生的句子的全体就构成了语言，记作 L(G)。以上面文法为例，L(G) = { 011，11 }。
5 递归
- 规则具有递归性：规则的左部和右部具有相同的非终结符的规则。使我们能用有限的规则定义无穷集合的语言。
- 规则左递归：A→A…
- 规则右递归：A→…A
- 规则递归：A→…A…
- 文法具有递归性：存在 非终结符 +⇒ 含非终结符的符号串 的文法。
- 文法左递归：A +⇒ A…
- 文法右递归：A +⇒…A
- 文法递归：A +⇒…A…
- 当一个语言是无穷集合时，定义该语言的文法一定是递归的。
6 短语、直接短语和句柄
6.1 概念
- 短语：子树的末端结点形成的符号串。
- 简单子树：只有一层分支的子树。
- 直接短语（简单短语）：简单子树的末端结点形成的符号串。
- 句柄：子树中最左边的那棵只有父子两代的子树的所有叶结点自左至右排列起来，就是该句型的句柄。
6.2 三者间的关系
6.3 例题
由此可得S=(Sd(T)db)为此文法的一个句型：
- 短语:S，(T)，b，Sd(T)，Sd(T)db，（Sd(T)db)
- 直接短语:S，(T)，b
- 句柄:S
- 此时的最左直接短语是S所有句柄为S
6.4 语法树与文法的二义性
- 概念：存在某个句子对应两棵不同的语法树(或不同的最左(最右)推导)。
- 消除：利用文法的等价性，把排除二义性的规则合并到原有文法中，改写原有的文法。或添加语法的非形式规定，如运算符的优先顺序和结合顺序。
- 核心：把优先级和结合性说清楚。
- 不改变原有的语法规则，仅加进一些非形式的语法规定
- 构造一个构造一个等价的无二义性文法
- 语言的二义性(先天二义性语言)：不存在无二义性的文法的语言。
【例】： 设文法 G： E → E+E | E*E | (E) | -E | id
则，句子 id+id*id、id+id+id 可能的分析树有：
在该例中，虽然 id+id+id 的 “+” 的结合性无论左右都不会影响结果。但万一，万一“+”的含义变成了“减法”，那么左结合和右结合就会引起很大的问题了。
- 优先级越低越靠近根节，优先级越高越靠近叶子结点。
7 文法和语言的分类
7.1 0型文法-短语结构文法
G=( V,T,P,S )
若P中任一产生式都有一般形式如下，且对不加任何限制，则称G为0型文法，也叫短语结构文法，记为PSG(Phrase Structure Grammar）。
由0型文法生成的语言L(G)称为0型语言，也叫短语结构语言(PSL Phrase Structure Language)或递归可枚举集(recursively enumerable
set)。它可由图灵机识别。
7.2 1型文法-上下文有关文法
产生式：右部长度≥左部长度
对于文法G，如果从它的产生式集合随便抽出一个产生式α→β，| β | ≥ | α |恒成立，即右部表达式的长度永远大于等于左部表达式的长度，那么该文法G就被称为1型文法，也被称为上下文有关文法(CSG:context sensitive grammar)。
文法G产生的语言L(G)就被称为1型语言或上下文有关语言(CSL)。
这里需要注意的就是 ，在这里 | α | 表示的是字符串α的长度，而不是求它的绝对值。
下列文法是CSG：
- S → A=B （左部长度为1，右部长度为3）
- A → a | b | c (左部长度为1，右部长度为1-1-1）
- A → = (左部长度为1，右部长度为1）
下列文法不是CSG：
- S → ε（左部长度为1，右部长度为0）
- AB → a | ε (左部长度为2，右部长度为1-0）
7.3 2型文法-上下文无关文法
产生式：右部长度≥左部长度 ，且左部量为语法范畴（VN）
对于文法G，如果在上下文有关文法的基础上（右部长度≥左部长度），左部还是语法变量，那么文法G就被称为2型文法，或上下文无关文法(CFG:context-free grammar)。
文法G产生的语言L(G)被称为2型语言，或上下文无关语言(CFL)。
直接来例子，我们把CSG和CFG结合在一起看：
下列文法即是CFG，也为CSG：
- A → a | b | c
- AB → a= | b= |c=
- S → A=B
下列文法不是CFG，但为CSG：
- aS → Sa (左部不为语法变量）
- a+b → b+a （左部不为语法变量）
7.4 3型文法-正则文法
产生式：左为语法变量，右为字符串*（语法变量）
左线性文法与右线性文法
对于文法G，如果从它的产生式集合随便抽出一个产生式 α→β。如果产生式左部都为语法变量，而右部为”字符串“或“字符串*语法变量”，那么该文法就被称为3型文法，也被称为正则文法(RG:regular grammar)。
对于的语言L(G)就被叫做3型语言，也被称为正则语言或正规语言(RL)。
同时根据“字符串*语法变量”或“语法变量*字符串”，即字符串和语法变量的先后顺序，RG又可被分为左线性文法和右线性文法。如果语法变量在字符串前，就被称为左线性文法；如果语法变量在字符串后，则被称为右线性文法。
由于两者等价，所以统称为正则文法。
我们可以发现，正则文法RG和上下文无关文法CFG，上下文有关文法CSG的区别在于：
- RG没有右部长度大于左部长度的要求，但CFG和CSG都有。
- 对于产生式α → β，RG和CFG的左部量α都要求是语法变量，而CSG的左右部没有限制。
直接来看例子，我们把RG，CFG，CSG综合来看。
以下文法是RG，也是CFG，也是CSG：
- A → a | b | c
- A → a | B
以下文法不是RG，但为CFG，也为CSG：
- B → E
- S → A | B | a | b | c
以下文法不是RG，不是CFG，但为CSG：
- aS → Sa
- ab → ba
7.5 判断文法的类型
长度，语法变量
综上我们已经对四类文法有了大致的了解，接下来就是总结了。
- 文法RG：左部为语法变量，右部为“字符串”或“字符串*语法变量”。
- 文法CFG：左部为语法变量，右部长度大于等于左部。
- 文法CSG：右部长度大于等于左部。
可以看到，如果一个文法是RG，那么它右部一定大于或等于左部。所以一个文法如果是RG，那么它一定是CFG，也一定是CSG，反之则不然。
8 概念合集
- 字母表是元素的有穷非空集合。
- 字母表中的元素称为符号，或称为字符。
- 符号的有穷序列称为符号串。
- 文法是描述语言语法结构的形式规则。它的形式化定义是一个四元组，即 G = { VN , VT , P , S }。
- 推导指的是从文法的开始符号出发，反复连续地使用产生式，对非终结符施行替换和展开，最终得到一个仅由终结符构成的符号串，推导过程的每一步都是一个直接推导。
- 广义推导：序列可以简写为 S +⇒ 011，表示经过一步或者多步推导，而 S *⇒ 011 表示经过 0 步或者多步推导。所以，S *⇒ 011 要么是 S = 011，要么是 S +⇒ 011。
- 规范推导：最右推导。
- 规范规约：最左归约。
- 规则具有递归性：规则的左部和右部具有相同的非终结符的规则。
- 递归文法：当一个语言是无穷集合时，定义该语言的文法一定是递归的。
- 文法二义性：存在某个句子对应两棵不同的语法树(或不同的最左(最右)推导)。
📎 参考文章
有关问题，欢迎您在底部评论区留言，一起交流~
- Author:Koreyoshi
- URL:https://Koreyoshi1216.com/article/1a4c7b13-c6a7-80c3-b87d-c8d5749e6cd0
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
