编译原理笔记——文法和语言的基本知识
学习一门语言最基础的就是语言基础,编译程序要正确准确的翻译程序设计语言,我们从程序设计语言的语法、语义、语用三个因素来考虑。
语法:对语言结构的定义
语义:描述语言的含义
语用:非形式化的描述
非形式化的描述不够准确,为了精确定义程序设计语言采用形式化的方法(形式化的方法是著名语言学家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}
规范推导也就是最右推导,=>
规范归约也是就是最左归约,是规范推导逆过程推,注意=>•在箭头上有个点