二、高级语言设计基础

引入形式语言的概念，介绍高级语言的语法结构及其定义方法。

符号和符号串

符号串

• 定义：指由该字母表中的符号构成的有穷序列，又称为字。
• 空字：不包含任何符号的序列，记作ε。

符号串集合

• 定义：若集合U中的所有元素都是字母表∑上的符号串，则称U为∑上的符号串集合。
• 设U、V、W是字母表∑上的符号串集合：
  1. 符号串s的长度：指出现在s中符号的个数，往往记作|s|。例如，00110长度为5，
     • 空字长度为0
  2. 两符号串的连接：如果α和β都是符号串，那么α和β的连接，是把β加到α后面形成的符号串，写成αβ。如α=01，β=110，则αβ=01110，βα=11001。一般而言，αβ≠βα。
     • 空字是连接运算的恒等元素，即sε=εs=s
  3. 集合U与V的乘积：表示为UV,即UV={αβ|α∈U & β∈V}。即集合UV是由U中的任一符号串与V中任一符号串连接构成的符号串集合。
     • 一般而言，UV≠VU，但(UV)W=U(VW)
  4. 集合V的n次幂：是指V自身的n次乘积，记为Vⁿ。
     • 规定V⁰={ε}
  5. ∑的闭包和正闭包：
     • 闭包：根据方幂的定义，设∑的闭包表示为∑^*，有
       • ∑^*=∑⁰ ∪ ∑¹ ∪ ∑² ∪ ∑³ ∪ …
       • ∑^*表示∑上所有符号串的全体，空字也包含在其中。
     • 正闭包：设∑的正闭包表示为∑⁺，且有
       • ∑⁺=∑∑^*
     • ∑^*中任意一个按一定规则构成的子集称为∑上的一个（形式）语言，属于该语言的符号串称为该语言的句子

文法与语言

文法定义

• 文法
  • 程序设计语言的语法结构的形式化描述称为文法，主要用于语言的设计和编译。
  • 文法是描述语言的语法结构的形式规则（即语法规则），这些规则必须准确而且可理解。
• 文法定义的四部分：
  • 非终结符号：各自代表一个语法成分，表示一类具有某种性质的语法范畴。在程序设计语言中的非终结符有“算术表达式”、“赋值语句”等，用V_N表示非终结符的集合
  • 终结符号：出现在句子中的符号称为终结符，它是一个语言不可再分的基本单位。在程序设计语言中终结符就是指单词符号，如关键字、标识符和界符等，用V_T表示终结符的集合。
    • 其中，V=V_N∪V_T，构成文法G的字母表，V_N∩V_T=∅
  • 产生式：按一定格式书写的、用于定义语法范畴的规则，又称为规则生成式或生成式，说明了终结符和非终结符组合成符号串的方式，形如α→β或α::=β，称α为左部，α∈V⁺，α至少包含一个非终结符，β为右部，β∈V^*。用P表示产生式的集合
  • 开始符号：开始符号是一个特殊的非终结符，至少在一个产生时的左部出现一次。用S表示，代表该文法定义的语言最终要得到的语法范畴。在程序设计语言中，开始符号就是“程序”，文法定义的其他语法范畴都为此服务
• 由此，文法G是一个四元组，G=(V_N, V_T, P, S)

文法产生的语言

• 推导（从左到右）
  • 从文法的开始符号出发，反复连续使用所有可能的产生式，将一个符号串中的非终结符用某个产生式右部进行替换和展开，直到全部为终结符为止。这个过程就是推导。
  • 如果A→γ是产生式，α和β是文法的任意符号串，αAβ⇒αγβ称为直接推导，也称一步推导，用“⇒”表示“一步推导”。
• 归约（从右到左）
  • 推倒的逆过程称为归约。
  • 如果α₁推导出α_n，则称α_n归约为α₁。
• 为了理解某些分析器的工作过程，需要考虑每一步推导中非终结符的替换顺序。
  • 最左推导：在整个推导中，每一步都是替换句型中最左边的非终结符。
  • 最右推导：在推导的每一步都替换最右边的非终结符。最右推导又称为规范推导。
    • 最左推导的逆过程为最右归约，最右推导的逆过程为最左归约（规范归约）。
• 句型
  • 若S是文法G的开始符号，从开始符号S出发推导出的符号串称为文法G的一个句型。
  • 即α是文法G的一个句型，当且仅当存在如下推导：S⇒^*α,α∈V^*
• 句子
  • 若X是文法G的一个句型，且X∈V_T^*，则称X是文法G的一个句子。
  • 即仅含终结符的句型是一个句子。
• 语言
  • 把文法G产生的所有句子的集合称为G产生的语言，记为L(G)，表示为
    • L(G) = { X | S⇒^*X, X∈V_T^* }
  • 如果文法G₁与文法G₂产生的语言是相同的，即L(G₁)=L(G₂)，则称这两个文法是等价的。

文法的二义性

• 语法树
  • 用一棵树来表示句型的推导称为语法树，也可称为分析树。语法树用来表示句子的层次关系。
    • 语法树通常为一棵倒立的树，其根在上，枝叶在下，根节点由开始符号标记。
    • 随着推导展开，当某个非终结符被它的候选式所替换时，这个非终结符就产生出下一代新结点。
    • 候选式中自左至右的每个符号对应一个新结点，每个新结点和其父结点之间有一条连线。
    • 语法树的叶结点由非终结符或终结符标记。
  • 在语法树生长的任意时刻，所有那些没有后代的末端结点从左到右排列起来构成一个句型。
  • 如果自左至右末端结点排列起来都是非终结符，那么这棵语法树表示了一个句子的推导过程。
• 二义文法
  • 如果存在某个句型对应两棵或两棵以上的语法树，则称这个文法为二义文法。
  • 二义文法是存在某个句型有不止一个最左（最右）推导的文法。
  • 文法的二义性并不代表语言一定是二义的。只有当产生一个语言的所有文法都是二义的，这个语言才是二义的。

文法的分类

• 乔姆斯基（Chomsky）把文法分成4种类型，即0型、1型、2型、3型。4类文法的差别在于对产生式施加不同的限制。
• 设G=(V_N, V_T, P, S)，其中α,β∈(V_N∪V_T)^*。这四类文法的定义为：
  • 0型文法：对产生式α→β只要求α中至少含有一个非终结符。
    • 0型文法又称为短语文法。
    • 0型文法描述的语言称为0型语言。0型语言是递归可枚举的；反之，递归可枚举集必定是0型语言。
  • 1型文法：限定P的产生式形如α→β，均满足|β|≥|α|，仅S→ε除外，但S不能出现在任何产生式的右部。
    • 1型文法又称为上下文有关文法。可以描述为α₁Aα₂→α₁βα₂
    • 1型文法描述的语言称为1型语言或上下文有关语言。1型语言可由线性界限自动机识别。
  • 2型文法：限定P的产生式形如A→α，，其中A∈V_N。
    • 2型文法又称为上下文无关文法。2型文法主要用来描述高级程序设计语言的语法结构。
    • 2型文法所描述的语言称为2型语言或上下文无关语言。2型语言可由下推自动机识别。
  • 3型文法：限定P的产生式形如A→αB或A→α，其中A,B∈V_N,α∈V_T^*。
    • 3型文法又称为正规文法或右线性文法。3型文法主要用来描述单词的构成。
    • 3型文法还有一种形式：限定P的产生式形如A→Bα或A→α，称为左线型文法。
    • 3型文法描述的语言称为3型语言或正规语言（正规集）。3型语言可由有穷自动机识别。
• 4类文法的定义是对产生式逐渐增加限制的，对应语言的描述能力越来越弱。

高级语言的设计

• 语言设计的步骤
  1. 设计该语言的字符集
  2. 设计单词集
  3. 设计数据类型
  4. 设计表达式
  5. 设计语句
  6. 程序的设计