编译原理系列之二 文法和语言 | 您所在的位置:网站首页 › 0和空集是一个概念吗 › 编译原理系列之二 文法和语言 |
ε,{ε},Ø三者之间的区别 : ε是一个终结符推导出的结果,表示一个不包含任何字符的序列。 Ø是不包含任何元素的空集{},表示不存在匹配文法的句子。 {ε}是任意一个符号串集合的0次幂,表示一个由空字组成的集合。 句子与句型: 如果符号串x是由起始符号推导出的,则称x是文法G[S]的句型。 如果x中只包含终结符,则称x是文法G[S]的句子。 文法描述的语言是该文法一切句子的集合。 四种文法: 0型文法:α→β,其中α至少包含一个非终结符。 1型文法(上下文有关文法):α→β,其中|β|≥|α|,S→ε除外。 2型文法(上下文无关文法):a→β,其中a是一个非终结符。 3型文法(规范文法):A→a或A→aB. 4种文法是逐渐增加限制的,所以规范文法一定是0型文法、1型文法、2型文法,上下文无关文法也一定是0型文法、1型文法... 规范推导: 最右推导为规范推导,由规范推导推出的句型称为右句型或规范句型。 文法的二义性: 一个句型可能对应多个语法树,一个句型可能对应多个最左/最右推导。 如果一个文法中的某个句子可以对应两个不同的语法树,则称这个文法是二义的。 两个不同的文法可能是一样的语言。 如果一种语言的所有文法都是二义的,则称此语言先天二义。 判定一个文法是否是二义的是递归不可解的。 |
CopyRight 2018-2019 实验室设备网 版权所有 |