编译原理-文法和语言的知识讲解

文法和语言的形式定义

如何来描述一种语言？

  • 如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示
    • 如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：
      • 生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。
      • 识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。
      • 文法即是以有穷的集合刻画无穷的集合的一个工具。
      • 生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造

几个概念

  • 考虑一个有穷 字母表∑ 字符集
  • 其中每一个元素称为一个字符
  • ∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列
  • 不包含任何字符的序列称为空字，记为ε
  • 用∑*表示∑上的所有字的全体,包含空字ε
  • 例如: 设 ∑={a， b}，则 ∑*={ε,a,b,aa,ab,ba,bb,aaa,...}
  • ∑*的子集U和V的连接（积）定义为 UV＝{ αβ | α∈U & β∈V }
  • 设：U＝{ a, aa }，V＝ { b, bb } 那么：UV= { ab, abb, aab, aabb}
  • ∑*的子集U和V的连接（积）定义为UV＝{ αβ | α∈U & β∈V }
  • V自身的 n次积记为Vn=VV…V
  • 规定V0={ε}，令V*=V0∪V1∪V2∪V3∪…

称V*是V的闭包;

  • 记 V＋＝VV* ，称V+是V的正规闭包。
  • 设：U＝{ a, aa }
  • 那么：U* = { ε , a, aa, aaa, aaaa, …}，U＋ = { a, aa, aaa, aaaa, …}

文法的定义

文法的写法

推导的定义

文法生成语言的定义

文法的等价

文法的类型

四种类型描述能力的比较

文法的语言

赞 (0)

相关推荐