编译原理(清华大学出版社)-- 文法和语言

  • 对Pascal程序来说,一个上下文无关文法,可以定义为符号串 A := BC
  • 程序设计语义分为两类:静态语义和动态语义

文法的直观概念

推导或产生句子

例如,我是大学生

<句子> => <主语><谓语>

            => <代词><谓语>

            =>  我<谓语>

            =>  我<动词><直接宾语>

            =>  我是<直接宾语>

            =>  我是<名词>

            =>  我是大学生

  • 符号 => 的含义是,使用一条规则,代替其左端的某个符号,产生其右端的符号串

符号和符号串

字母表

  • 字母表的元素的非空有穷集合,字母表中的元素称为符号
  • 因此字母表也称为符号集
  • 不同语言可以有不同的字母表

符号串

  • 由字母表中的符号组成的任何有穷序列称为符号串
  • 例如,001110 是字母表{0, 1}的符号串;a,b,c,aaca是A={a,b,c}上的符号串
  • 允许空符号串,不包含任何符号的符号串,用ε表示,其长度为0,即|ε|=0

符号串的运算

  • 符号串的头尾,固有头和固有尾
  • 如果 z=xy 是一符号串,那么 x 是z的头,y是z的尾,如果x是非空的,那么y是固有尾;如果y是非空的,那么x是固有头
  • 设z=abc,那么z的头是ε,a,ab和abc;除abc外,其他都是固有头;z的尾是ε,c,bc和abc;z的固有尾是ε,c和bc
  • 省略写法:z=x...,z=...x...

符号串的连接

  • 设x和y是符号串,它们的连接xy是把y的符号写在x的符号之后得到的符号串
  • 例如,设x=ST,y=abu,则它们的连接xy=STabu,看出|x|=2,|y|=3,|xy|=5,由于ε的含义,显然由 εx=xε=x

符号串的方幂

  • 设x是符号串,把x自身连接n次得到符号串z,即z=xx...xx,称为符号串x的方幂,写作z=xn,即把符号串x相继地重复写n次
  • x0=ε,x1=ε,x2=xx,x3=xxx分别对应于n=0,1,2,3
  • 对于n>0,有xn=xxn-1=xn-1x

符号串集合

  • 若集合A中的一切元素都是某字母表上的符号串,则称A为该字母表上的符号串集合
  • 两个符号串集合A和B的乘积定义如下:AB={xy|x∈A且y∈B},即AB是满足x属于A,y属于B的所有符号串xy所组成的集合
  • 例如,若A={a,b},B={c,d},则集合AB={ac, ad, bc, bd},对任意符号串x有εx=xε=x,所以有{ε}A=A{ε}=A
  • 指定字母表∑之后,可以用∑*表示∑上所有有穷长的串的集合,例如∑={0,1},则∑*={ε,0,1,00,01,10,11,000,001,010,...},也可表示为字母表的方幂形式,∑*称为集合∑的闭包
  • 而∑+=∑1∪∑2...∑n称为∑的正闭包,显然有 ∑*=∑0∪∑+,∑+=∑∑*=∑*
  • *具有可数的无穷数量的元素,若x是∑*中的元素,则表示为x∈∑*,否则x不属于∑*,对于所有的∑,有ε∈∑*

文法和语言的形式定义

相关推荐