|
知识路径: > 计算机系统基础知识 > 计算机软件基础知识 > 程序设计语言和语言处理程序知识 > 汇编、编译、解释系统的基本知识和基本工作原理 > 程序语言翻译基础 > 编译程序基本原理 >
|
相关知识点:24个
|
|
|
|
语言L是有限字母表Σ上有限长度字符串的集合,这个集合中的每个字符串都是按照一定的规则生成的。下面从产生语言的角度出发,给出文法和语言的形式定义。所谓产生语言,是指制定出有限个规则,借助它们就能产生此语言的全部句子。
|
|
|
|
.字母表Σ和字符:字母表是字符的非空有穷集合,字符是字母表Σ中的一个元素。例如Σ={a,b},a或b是字符。
|
|
|
.字符串:Σ中的字符组成的有穷序列。例如a,ab,aba,aaaa都是Σ的字符串。
|
|
|
.字符串的长度:指字符串中的字符个数。如|aba|=3。
|
|
|
|
.连接:字符串S和T的连接是指将串T接续在串S之后,表示为S·T,连接符号“·”可省略。显然,对于字母表Σ的任意字符串S,S·ε=ε·S=S。
|
|
|
.Σ*:是指包括空串ε在内的Σ上所有字符串的集合。例如,设Σ={a,b},Σ*={ε,a,b,aa,bb,ab,ba,aaa,…}。
|
|
|
.字符串的方幂:把字符串α自身连接n次得到的串,称为字符串α的n次方幂,记为αn。α0=ε,αn=ααn-1=αn-1α(n>0)。
|
|
|
.字符串集合的运算:设A,B代表字母表Σ上的两个字符串集合。
|
|
|
或(合并):A∪B={α|α∈A或α∈B}。
|
|
|
积(连接):AB={αβ|α∈A且β∈B}。
|
|
|
幂:An=A·An-1=An-1:A(n>0),并规A0={ε}。
|
|
|
正则闭包+:A+=A1∪A2∪A3∪…∪An∪…。
|
|
|
闭包*:A*+A0∪A+。显然,Σ*=Σ0∪Σ1∪Σ2∪…∪Σn∪…。
|
|
|
|
描述语言语法结构的形式规则称为文法。文法G是一个四元组,可表示为G=(VN,VT,P,S)。其中VT是一个非空有限集,其每个元素称为一个终结符;VN是一个非空有限集,其每个元素称为非终结符。VN∩VT=Φ,即VN和VT不含公共元素。令V=VN∪VT,称V为文法G的词汇表,V中的符号称为文法符号,包括终结符和非终结符。S∈VN,称为开始符号,它至少要在一条产生式中作为左部出现。P是产生式的有限集合,每个产生式形如“α→β”。其中,α称为产生式的左部,α∈V+且α中至少含有一个非终结符;β称为产生式的右部,且β∈V*。若干个产生式α→β1,α→β2,…,α→βn的左部相同时,可简写为α→β1|β2|…|βn,称βi(1≤i≤n)为α的一个候选式。
|
|
|
(1)文法的分类。乔姆斯基(Chomsky)把文法分成4种类型,即0型、1型、2型和3型。这4类文法之间的差别在于对产生式要施加不同的限制。若文法G=(VN,VT,P,S)的每个产生式α→β,均有α∈(VN∪VT)*,α至少含有一个非终结符,且β∈(VN∪VT)*,则称G为0型文法。对0型文法的每条产生式分别施加以下限制,则可得以下文法:
|
|
|
.1型文法:G的任何产生式α→β(S→ε除外)均满足|α|≤|β|(|x|表示x中文法符号的个数)。
|
|
|
.2型文法:G的任何产生式形如A→β,其中A∈VN,β∈(VN∪VT)*。
|
|
|
.3型文法:G的任何产生式形如A→a或A→aB(或者A→Ba),其中A,B∈VN,a∈VT。
|
|
|
0型文法也称为短语文法,其能力相当于图灵机,任何0型语言都是递归可枚举的;反之,递归可枚举集也必定是一个0型语言。1型文法也称为上下文有关文法,它意味着对非终结符的替换必须考虑上下文,并且一般不允许替换成ε串。例如,若αAβ→αγβ是1型文法的产生式,α和β不全为空,则非终结符A只有在左边是α,右边是β的上下文中才能替换成γ。2型文法就是上下文无关文法,其非终结符的替换无需考虑上下文。3型文法等价于正规式,因此也被称为正规文法或线性文法。
|
|
|
若文法G1与文法G2产生的语言相同,即L(G1)=L(G2),则称这两个文法是等价的。
|
|
|
(2)句子和语言。设有文法G=(VN,VT,P,S)。
|
|
|
.推导与直接推导:推导就是从文法的开始符号S出发,反复使用产生式,将产生式左部的非终结符替换为右部的文法符号序列(展开产生式用表示),直到产生一个终结符的序列时为止。若有产生式α→β∈P,且γ,δ∈V*,则称为文法G中的一个直接推导,并称γαδ可直接推导出γβδ。显然,对P中的每一个产生式α→β都有。若在文法中存在一个直接推导序列,即,则称α0可推导出αn,αn是α0的一个推导,并记为。用记号表示α0=αn或者。
|
|
|
.直接归约和归约:归约是推导的逆过程。若文法G中有一个直接推导,则称β可直接归约成α,或α是β的一个直接归约。若文法G中有一个推导,则称δ可归约成γ,或γ是δ的一个归约。
|
|
|
.句型和句子:若文法G的开始符号为S,那么,从开始符号S能推导出的符号串称为文法的一个句型,即α是文法G的一个句型,当且仅当有如下推导,α∈V*。若X是文法G的一个句型,且,则称X是文法G的一个句子,即仅含终结符的句型是一个句子。
|
|
|
.语言:从文法G的开始符号出发,能推导出的句子的全体称为文法G产生的语言,记为L(G)。
|
|
|