编译原理笔记2-文法和语言

语言的语法是指一组规则，用它可以形成和产生一个合适的程序

语法只定义什么样的符号序列是合法的

阐明语法的工具是文法

基本概念

字母表

  • 元素的非空有限集，记为 Σ
  • 字母表中的元素称为符号，字母表包含了语言中所有允许出现的所有符号

符号串

​ 符号的有穷序列，无任何符号的符号串记为空符号串，ε

  • 符号串长度：|X|，等于组成该符号串的符号个数
  • 符号串连接：x，y是定义在同一个字母表的符号串，则xy为x和y的连接
  • 符号串集合的乘积：类似笛卡尔积
  • 符号串集合的方幂：
  • 符号串集合的正闭包（传递闭包）
  • 符号串集合的自反闭包（自反传递闭包，方幂的无穷并）

文法

一个上下文无关文法G包括四个部分组成：

  • 一组终结符号
  • 一组非终结符号
  • 一个开始符号
  • 一组产生式

文法的形式化定义

文法定义成一个四元组 G=(Vn,Vt,S,P)

  • Vn：非空有限的非终结符集
  • Vt：非空有限的终结符集
  • S：开始符号
  • P：产生式集合

其中，Vn ∩ Vt = 空集；S∈Vn

P中产生式一般形式为：A -> a|b；其中A∈Vn；a、b∈(Vn∪Vt)的自反闭包

文法的分类

  • 3型文法一定是2型，2型文法一定是1型…以此类推
  • 2型文法扩充：允许有空产生式：A —> ε
  • 如今大多数高级程序设计语言采用上下文无关文法就够了

推导与归约

推导

  • 直接推导
  • 一步或多步推导，0步或多步推导
  • 最左推导和最右推导
  • 最右直接推导又称规范直接推导；最右推导又称规范推导

归约

最左推导的逆过程是最右归约，最右推导的逆过程是最左归约

假定X1，X2，…Xn是一个最左推导，则称序列Xn，Xn-1，…X1是一个最右归约

句型、句子、语言的定义

  • 设S是文法G的识别符号，如果S经过0步或任意多步推导出u，则U为文法G的句型。0步或任意多步，即S本身是一个句型
  • 设S是文法G的识别符号，如果S经一步或任意多步推导出u，且u∈终结符集，则称u为文法G的句子（句子也是句型）
  • 文法的语言是文法所有句子的集合

文法等价

如果两个文法定义的语言一样，则称这两个文法是等价的