文法：以有穷的集合描述无穷的计划的工具。
字母表：元素的非空有穷集合，其中的元素称为符号，因此也叫符号集。
符号串：由字母表中的元素组成的任何有穷序列，串中的元素个数叫做符号串的长度，空符号串ε，长度为0。
符号串的运算：
连接-符号串x = ab,y=cd, xy = abcd
方幂-z=xn，当n = 0, z = ε，当 n = 2, z = xx
集合的闭包-∑* = ∑0 ∪∑1 ∪∑2 ∪…∪∑n
∑+ 为正闭包 = ∑1 ∪∑2 ∪…∪∑n
规则|产生式|生成式，是形如α->β的有序对，读作α定义为β，相同左部的产生式可缩写A->a|b|c|d。
文法定义的形式-四元组（Vn,Vt,P,S）: Vn为非终结符集，Vt 为终结符集，P为规则集，S为识别符|开始符，至少要在一个规则中作为左部出现，Vn ∩ Vt = ∅。
直接推导=>， 长度为n(n>=1)的推导+=>，长度为n(n>=0)的推导=>【+在=上面】，v=0S1,w=0011,直接推导：0S1 =>0011，使用规则：S->01，γ=0，δ=1;可以说w是v的直接推导，或者w直接归约于v，由识别符号S推导出来的符号串称为文法的句型，如果该符号串仅由终结符号组成，称为句子。
G[S]称为文法，L[G]为文法的集合表示形式
若L[G1] = L[G2]，则称文法G1和G2是等价的。
G[S]：S->0S1，S->01
G[A]：A->0R，A->01，R->A1
L[S]=L[A]={0n1n|n>=1}
根据对文法施加不同的限制，分成4种类型。
0型或短语文法：文法的每个产生式α->β都是α、β属于字符集的闭包区间内且α至少包含有一个非终结符；左边有非终结符，右边有终结符；0型文法的能力相当于图灵机（Turing）。或者说，任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。
1型或上下文有关：α->β均满足|α|<=|β|, 除了S->ε外；小的推出大的或者相等的；
2型或上下文无关：α属于非终结符集Vn；左边必须是非终结符，然而一个终结符一个非终结符的组合不是一个非终结符，两个非终结符的组合就是一个非终结符；
3型或正规文法：一个非终结符推出一个终结符，要么一个非终结符推出一个终结符并且带一个非终结符; 这右线性与左线性是相互独立的，不能一会写一下右线性一会写一下左线性，这样拼凑在一起就构成不了3型文法了。要写就只写右线性，或者只写左线性，不能一块来，分开来就对了; 左边必须只有一个字符，且必须是非终结符；其右边最多只能有两个字符，且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时，此字符必须为终结符。
描述一种上下文无关的推导工具：句型的推导和语法树（推导树）
给定文法G（VN,VT,P ,S）,对于G的任何句型都能构造与之关联的语法树。这棵树满足下面四个条件：
① 每个结点都有一个标记，此标记是V的 一个符号。（说的是节点一定是终结符或非终结符）
② 根的标记是S。（说的是树根的标记是开始符号S）
③ 若一结点标记A,至少有一个从它出发的分枝，则A肯定在Vn中（说的是如果一个节点有分支的话，这个节点一定是非终结符）
④ 如果标记为A，有n个从它出发的分枝，并且这些分枝的结点的标记（从左到右）为B1, B2，…，Bn，那么A→B1B2，…，Bn一定是P中的一个产生式。（说的是从A出发的叶子节点从左到右排列，一定是P中规则的一个产生式） 
推导的每一步都是对最左非终结符进行替换，称为最左推导；最右推导也称规范推导
句型的分析：自上而下的分析和自下而上的分析。
一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语；相对于非终结符的短语
如果子树中不再包含其他的子树，即A只能推导出b，而b不能再推出其他的式子，则b为此句型的直接短语；相对于规则的直接短语；
直接短语中的最左直接短语为该句型的句柄[最右推导，右句型]；某句型的句柄；
案例：
S -> a|b|(T)
T -> TdS|S
证明(Sd(T)db)是S的一个句型，并求出短语，直接短语，句柄
此文法的抽象语法树为: 
由此可得S=(Sd(T)db)为此文法的一个句型：
• 短语:S，(T)，b，Sd(T)，Sd(T)db，（Sd(T)db)
• 直接短语:S，(T)，b
• 句柄:S
文法的实用限制：
有害规则：形如U->U的规则，没用，容易引起二义性；
多余规则：非终结符不在任意规则的右部出现，不可到达；非终结符不能推导出终结符，不可终止；