上下文无关文法
上下文无关文法是一种用于描述程序设计语言语法的表示方法, 或简称"文法”。文法一般被用于组织编译器前端。
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
