上下文无关文法
上下文无关文法是一种用于描述程序设计语言语法的表示方法, 或简称"文法”。文法一般被用于组织编译器前端。
CFG
是一个四元组:G =(N,T,P,S)
,被称作一个文法,其中
N
是非终结符(Nonterminals
)的有限集合;
T
是终结符(Terminals
)的有限集合,且N∩T=Φ;
P
是产生式(Productions
)的有限集合,形如:A→α
,其中A∈N
(左部),α∈(N∪T)*
(右部),若α=ε
,则称A→ε
为空产生式(也可以记为A →
);
S
是非终结符,称为文法的开始符号(Start symbol
)。
下面是一个例子
G=(N,T,P,S)
N = { S }, T ={ 0, 1 }
P={ S→0S1, S→01 }
S为开始符号
我们可以得到:S → 0S1 → 00S11 → 000S111 → 00001111
$S {=>}^* V$ 就是S
可以推出V
,而且S
可以等于V
$S {=>}^+ V$ 就是S
可以推出V
,但是S
不等于V
句子和句型
G
: S→0S1
, S→01
G
的句型S
,0S1
,00S11
,000S111
,00001111
G
的句子00001111
, 01
,句子一定是句型,反之不然(即句子中必须不能有S
,不可再往下推)
语言
由文法G
生成的语言记为L(G)
,它是文法G
的一切句子的集合(一切实例的集合):
例子:
推导过程如下
S →aSBE
→aaBEBE
→aaBBEE
→aabBEE
→aabbEE
→aabbet
→aabbee = a^2b^2c^2
四种文法
0型文法(对应图灵机)
- 如果它的每个产生式α→β是这样一种结构:α∈(VN∪VT)且至少含有一个非终结符,而β∈(VN∪VT),则G[S]是一个0型文法。
- 0型文法也称短语文法,记为PSG。
- 一个非常重要的理论结果是:0型文法的能力相当于图灵机。或者说,任何0型文语言都是递归可枚举的,反之,递归可枚举集必定是一个0型语言。
1型文法(对应线性界线自动机,自然语言)
- 它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。
- 注意:虽然要求|β|>=|α|,但有一特例:α→ε也满足1型文法。
- 1型文法也叫上下文有关文法,记为CSG。
- 此文法对应于线性有界自动机。
2型文法(对应下推自动机,程序设计语言)
- 2型文法是在1型文法的基础上,再满足:每一个α→β都有α是非终结符。
- 2型文法也叫上下文无关文法,记为CFG。
- 此文法对应于下推自动机。
3型文法(对应有限自动机)
- 它是在2型文法的基础上满足:A→α|αB(右线性)或A→α|Bα(左线性)。
- 3型文法也叫正规文法,记为RG。
- 此文法对应于有限状态自动机。
二义性
输入一个句子(字符串),如果能构造出多颗语法树,那么说文法具有二义性。
如下图,对于同一个句子 i*i+i
,同一个文法可以构造成下面两种语法树。
句型的分析
自上而下分析法
从文法的开始符号出发,反复使用文法的产生式,寻找与输入符号串匹配的推导,或者说,为输入串寻找一个最左推导。
自下而上分析法:
从输入符号串开始,逐步进行归约,直至归约到文法的开始符号。
短语和句柄
短语就是所有子树的叶子结点构成的
直接短语是只有父子关系的短语
句柄是最左的直接短语
简单可以这么理解:
- 每个句型都有一棵语法树;
- 每棵语法树的叶(从左到右)组成一句型;
- 每个子树的叶(从左到右)组成一短语;
- 每个简单子树的叶(从左到右)组成一简单短语;
简单子树就是只有父子关系的树(可以理解为只有两层),任何一个儿子都必须为叶子
- 最左简单子树的叶(从左到右)组成一句柄。
规范规约
一些性质
多余规则与有害规则
有害规则:形如U→U
的产生式。会引起文法的二义性
多余规则:指文法中任何句子的推导都不会用到的规则
消除左递归问题
对于自上而下分析要求文法不含左递归规则(引起无限循环),我们只能处理不含左递归和回溯的文法
直接左递归:有产生式P→Pa
间接左递归:文法中存在某个P
属于Vn
,有P→+Pa