学习一门语言最基础的就是语言基础，编译程序要正确准确的翻译程序设计语言，我们从程序设计语言的语法、语义、语用三个因素来考虑。
语法：对语言结构的定义
语义：描述语言的含义
语用：非形式化的描述
非形式化的描述不够准确，为了精确定义程序设计语言采用形式化的方法（形式化的方法是著名语言学家Noam Chomsky用一整套带有严格规定的符号体系来描述问题滴方法）让我们一起来看看编译原理的形式语言理论吧！
§字母表和符号串
（1） 定义：
字母表：元素的非空有穷集合 任何语言的字母表指出了该语言允许出现的一切符号
符号（字符）：字母表中的元素
符号串（字）：符号的有穷序列 符号串是字母表里面的符号的有穷多个组合，符号串的符号的顺序很重要
（2）符号串的运算.
(a) 符号串的连接：xy是把y的符号写在x的符号之后得到的符号串
空串 ε: 不包含任何符号的符号串 ，是符号串不是集合 （注：空串也有连接运算εx = xε =x ）
ε和 Ø 不同，Ø ={}
例：x=abc,y=10a,则xy=abc10a,yx=10aabc
(b) 符号串的幂运算：把x自身连接n次得到的符号串
=ε，
=x,
=xx...
对于n>0, 有 = x·
例：x=abc则，=ε；
=abc;
=abcabc
符号串的集合 : 由字母表上的符号串组成的集合 ，现在假设U和 V是符号串集合
(a) U和V的乘积(连接)：满足α∈U且β∈V的所有符号串αβ所构成的集合
UV= {αβ|α∈U且β∈V}
例：A={a,b}，B={c,d}，则AB={ac,ad,bc,bd}
(b)集合的幂运算：
V自身的n次乘积 =VV…V=V`
={ε}
例：设A={a,b}，={ε}，
={a,b},
=AA{aa,ab,ba,bb},
=
`A={aaa,aab,aba,abb,baa,bab,bba,bbb}
集合的正闭包和闭包：（集合A的闭包比正闭包多包含一个空符号串ε）
∑* = ∑0∪∑1∪∑2 … ∪ ∑n ∪ … ={ε}∪ ∑＋
∑＋ = ∑1 ∪∑2 … ∑n…
∑* = ∑0 ∪ ∑＋
∑＋ = ∑*- {ε}
∑＋ = ∑∑* = ∑*∑
对所有的∑, 有ε∪∑*
§文法和语言的形式定义
形式语言：序列的集合称为语言，每个形式语言都是字母表上按照某种规则构成的符号串集合
(1)文法的形式定义
（a)规则(产生式）
A(符号)->B（符号串) 符号生成符号串
符号分为终结符号(一般小写)和非终结符号(一般大写)
终结符号∩非终结符号=Ø，终结符号∪非终结符号=字汇表
(b)文法
文法是规则的有穷集合，通常表示为四元组A=（非终结符号集合，终结符号集合，文法规则集合，文法的开始符号非终结符号至少在一条规则作为左边出现）
例1：设字母表∑={a,b},L={,
|n>=1},则语言L是偶数个a偶数个b符号串组成的集合定义L语言的文法为：
G（,
,P,S）
其中，={A,B,D},
={a,b}，
P={A->aa|aaB|bb|bbD
B->aa|aaB
D->bb|bbD}
S=A
例2：设计一个表示所有标识符的文法
G（,
,P,S）
其中，={I,L,D},
={a,b,c,...,x,y,z,0,1,2,3,...,9}，
P={I->L|IL|ID
L->a|b|c|...|x|y|
D->0|1|2|3|...|9}
S=I
例3：字母表∑={a,b},设计文法描述语言L={aa|n>=0}
第一步：找语言符号串的规律当n=0时L={aa}，n=1,L={aba}...得出L={aa,aba,abba,..}
第二步，定义语言的文法为：G=（{A,B}，{a,b}，{A->aBa,B->Bb|ε},A）
(2)语言的形式定义
如何给出已知文法所定义的语言呢？
首先知道以下一点
•直接推导（推导长度=1）
G是一个文法，A->a是G的一个规则，x,y（
∪
）*,xAy=>xay只使用一次规则推出,则为直接推导。（注：推导是=>而不是规则->）
•推导（推导长度>=1）
(a)最左直接推导()
每次换最左边该还的符号，然后换第二次最左边该换的符号，一直换到最后
(b)最右直接推导
每次换最右边该还的符号，然后换第二次最右边该换的符号，一直换到最后
•广义推导（推导长度>=0）
不一定是从开始符合开始推导
•句型和句子
句型：x(
∪
)*
句子:x*
•语言
所有句子的集合称为语言
例：设有文法G[S]:=S->01|0S1求该文法所定义的语言
S=>0S1=>00S11=>000S111...=>0(n-1)S1(n-1)=>0n1n
L（G[S]）={0n1n|n>=1}
规范推导也就是最右推导，=>
规范归约也是就是最左归约，是规范推导逆过程推，注意=>•在箭头上有个点
网友评论