本节前言：

编译器要对高级程序设计语言进行词法、句法等分析；
要想让计算机自动地分析语言，就要把相关的语言学知识，也就是文法提供给计算机

字母表(Alphabet)和串(String)

字母表

基本概念：设字母表ΣΣ是一个有穷符号集合

  • 符号：字母、数字、标点符号、…
  • 比如：
    • 二进制字母表：{0,1}
    • ASCII字符集
    • Unicode字符集

字母表上的运算

  • 字母表Σ1Σ_1和Σ2Σ_2的乘积(product)
    • 类似于将符号的拼接看作乘积操作
    • Σ1Σ2={ab∣a∈Σ1,b∈Σ2}Σ_1Σ_2 = \{ab|a∈Σ_1,b∈Σ_2\}
    • 例：{0,1}{a,b}={0a,0b,1a,1b}\{0,1\}\{a,b\}=\{0a,0b,1a,1b\}
  • 字母表ΣΣ的n次幂(power)
    • n次幂：长度为n的符号串构成的集合
      • Σ0={ε},Σn=Σ×Σn−1,n≥1Σ^0 = \{ε\}, Σ^n = Σ\timesΣ^{n-1},n\geq 1
    • 例：{0,1}3={0,1}2{0,1}={00,01,10,11}{0,1}={000,001,010,011,100,101,110,111}\{0,1\}^3=\{0,1\}^2\{0,1\}=\{00,01,10,11\}\{0,1\}=\{000,001,010,011,100,101,110,111\}
  • 字母表Σ的正闭包(positive closure)
    • 正闭包：长度为正数的符号串构成的集合
      • Σ+=Σ∪Σ2∪Σ3∪...Σ^+ = Σ ∪ Σ^2 ∪ Σ^3 ∪ ...
    • 例：{a,b,c,d}+={a,b,c,d,aa,ab,ac,ad,ba,bb,bc,bd,...aaa,aab,aac,aad,aba,abb,abc,......}\{a,b,c,d\}^+ = \{a,b,c,d,aa,ab,ac,ad,ba,bb,bc,bd,...aaa,aab,aac,aad,aba,abb,abc,......\}
  • 字母表Σ的克林闭包(Kleene closure)
    • 克林闭包：任意符号串(长度可以为零)构成的集合，即在正闭包的基础上加入空串的组合
      • Σ∗=Σ0∪Σ+=ε∪Σ∪Σ2∪Σ3∪...Σ^* = Σ^0 ∪ Σ^{+} = ε ∪ Σ ∪ Σ^2 ∪ Σ^3 ∪ ...
    • 例：{a,b,c,d}∗={ε,a,b,c,d,aa,ab,,ac,ad,ba,bb,bc,bd,...,aaa,aab,aac,aad,aba,abb,abc,......}\{a,b,c,d\}^* = \{ε,a,b,c,d,aa,ab,,ac,ad,ba,bb,bc,bd,...,aaa,aab,aac,aad,aba,abb,abc,......\}

串

设ΣΣ是一个字母表，∀x∈Σ∗∀x∈Σ^*，x称为是ΣΣ上的一个串

  • 串是字母表中符号的一个有穷序列
  • 串s的长度，通常记为∣s∣|s|，是指s中符号的个数
    • 例：∣aab∣=3|aab|=3
  • 空串是长度为0的串，用εε(epsilon)表示，∣ε∣=0|ε|=0

串上的运算

  • 连接运算
    • 如果x和y是串，那么x和y的连接(concatenation)是将y附加到x后面而形成的串，记作xy
    • 设x,y,z是三个字符串，若x=yz，则称y是x的前缀，z是x的后缀
      • 例2.6：若x=dog，y=house，那么xy=doghouse
    • 空串啊是连接运算的单位元(identity)，即对于任何串s都有，εs=sε=sε
  • 幂运算
    • 串s的n次幂：将n个s连接起来
    • s0=ε,sn=ssn−1,n≥1s^0 = ε,s^n = ss^{n-1},n\geq1
    • s1=s,s2=ss,s3=sss,...s^1 = s, s^2 = ss, s^3=sss,...
    • 例：若s=bas=ba,那么s2=baba,s3=bababa,...s^2=baba,s^3=bababa,...

文法的定义

文法：语言规则
文法的形式化定义：G=(V(T),V(N),S,P)G=(V(T),V(N),S,P)

  • V(T)V(T)：终结符集合
    • 终结符(terminal symbol)是文法所定义的语言的基本符号，有时也称为token(词法单元)
    • 例：V(T)={apple,boy,eat,little}V(T)=\{apple,boy,eat,little\}
  • V(N)V(N)：非终结符集合
    • 非终结符(nonterminal)是用来表示语法成分的符号，有时也称为“语法变量”
    • 例：V(N)={V(N)=\{<句子>,<名词短语>,<动词短语>,<名词>,...}...\}
    • V(T)∩V(N)=∅,V(T)∪V(N)=V(T) ∩ V(N) = ∅, V(T) ∪ V(N) =文法符号集
  • P：产生式集合
    • 产生式(production)描述了将终结符和非终结符组合成串的方法
    • 产生式的一般形式：α→βα\rightarrowβ 读作：αα定义为ββ (或αα可以具有ββ的形式)
      • α∈(V(T)∪V(n))+α∈(V(T) ∪ V(n))^+，(αα属于文法符号集的正闭包)
        • αα中至少包含V(N)V(N)中的一个元素
          • 称为产生式的头(head)或左部(left side)
      • β∈(V(T)∪V(n))∗β∈(V(T) ∪ V(n))^*，(ββ属于文法符号集的克林闭包)
        • 称为产生式的体(body)或右部(right side)
    • 例：以一个自然语言句子的构成规则为例
      • 其中用尖括号括起来的部分称为语法成分(非终结符)，语法成分由语言的基本符号(终结符)定义

P=<句子> -> <名词短语> <动词短语>
<名词短语> -> <形容词> <名词短语>
<名词短语> -> <名词>
<动词短语> -> <动词> <名词短语>
…

  • S：开始符号
    • 开始符号(start symbol)表示的是该文法中最大的语法成分
    • S∈V(N)S∈V(N)
    • 例：S=S=<句子>
  • 约定：在不引起歧义的前提下，描述表达文法时只写产生式即可
    • 产生式的简写
      • 对一组具有相同头部的αα产生式：α→β1,α→β2,...,α→βnα\rightarrowβ_1,α\rightarrowβ_2,...,α\rightarrowβ_n
      • 可简记为：α→β1∣β2∣...∣βnα\rightarrow β_1|β_2|...|β_n
      • 读作αα定义为β1β_1，或者β2β_2，…，或者βnβ_n
      • β1,β2,...,βnβ_1,β_2,...,β_n称为αα的候选式(Candidate)

本系列文章中讨论文法时的符号约定：

  • 字母表中排在前面的小写字母，如a、b、c等表示终结符
  • 字母表中排在前面的大写字母，如A、B、C等表示非终结符
  • 字母表中排在后面的大写字母，如X、Y、Z等，表示文法符号(既可以是终结符也可以是非终结符)
  • 字母表中排在后面的小写字母，主要是u、v、…、z等表示终结符号串(包括空串)
  • 小写希腊字母，如αα、ββ、γγ等，表示文法符号串(包括空串)
  • 运算符，如+、*等；标点符号，如括号，逗号等；数字0、1、…、9，都表示终结符
  • 用粗体表示的名字一般表示终结符，用小写、斜体表示的名字一般表示非终结符
  • 字母S，通常表示开始符号，以及一些代表程序构造的大写字母，如E(表达式)、T(项)、F(因子)等为非终结符
  • 除非特殊说明，第一个产生式的左部就是开始符号

例：对一个文法形式定义G=({id,+,∗,(,)},{E},P,E)G=(\{id,+,*,(,)\},\{E\},P,E)

P={E→E+E,E→E∗E,E→(E),E→id}P=\{E\rightarrow E+E,E\rightarrow E*E,E\rightarrow(E),E\rightarrow id\}
等价于
P={E→E+E∣(E)∣id∣E∗E}P=\{E\rightarrow E+E|(E)|id|E*E\}

文法的一些术语

对一个给定文法G=(V(T),V(N),P,S)G=(V(T),V(N),P,S)

  • 推导(Derivations)：若α→β∈Pα\rightarrow β∈P，那么可以将符号串γαδγαδ重写(rewrite)为γβδγβδ，记作γαδ⇒γβδγαδ \Rightarrow γβδ
    • 此时称文法中的符号串γαδγαδ直接推导(directly derive)出γβδγβδ，简而言之，用产生式右部替换产生式左部
    • 若α0⇒α1,α1⇒α2,α2⇒α3,...,αn−1⇒αnα_0 \Rightarrow α_1,α_1 \Rightarrow α_2,α_2\Rightarrow α_3,...,α_{n-1} \Rightarrow α_n，
      • 可以记作α0⇒α1⇒α2⇒α3⇒...⇒αn−1⇒αnα_0 \Rightarrow α_1 \Rightarrow α_2 \Rightarrow α_3 \Rightarrow ... \Rightarrow α_{n-1} \Rightarrow α_n
      • 此时称符号串α0α_0经过n步推导出αnα_n，可简记为α0⇒nαnα_0 \stackrel{n}{\Rightarrow}α_n
        • α⇒0αα\stackrel{0}{\Rightarrow}α；
        • ⇒+\stackrel{+}{\Rightarrow}表示“经过正数步推导”(直接推导的正闭包)；
        • ⇒∗\stackrel{*}{\Rightarrow}表示经过若干(可以是0)步推导(直接推导的克林闭包)
  • 规约(Reductions)：推导的逆过程，即通过文法规则将产生式的左部替换右部的过程
  • 句型(sentenial form)：如果S⇒∗a，a∈(V(T)∪V(n))∗S\stackrel{* }{\Rightarrow}a，a∈(V(T) ∪ V(n))^*，则称aa是GG的一个句型
    • 一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串
  • 句子(sentence)：如果S⇒∗w,w∈V(T)∗S\stackrel{* }{\Rightarrow}w, w∈V(T)^*，则称ww是GG的一个句子
    • 句子是不包含非终结符的句型
  • 短语(phrase)：给定一个句型，其分析树中每一棵子树的边缘称为该句型的一个短语(phrase)
    • 如果子树只有父子两代结点，那么这棵子树的边缘称为该句型的一个直接短语(immediate phrase)
    • 直接短语一定是某产生式的右部，但产生式的右部不一定是给定句型的直接短语
  • 根据文法，如何判定某一词串是否是该语言的句子
    • 从生成语言的角度
      • 句子的推导(派生)->自顶向下
    • 从识别语言的角度
      • 句子的规约->自底向上
    • 编译过程中，语法分析的主要任务就是从给定输入，找出从文法开始符号推导出输入串或者从输入串规约出文法开始符号的方法
      • 如果无法从文法开始符号推导得出该终结符号串，则报告该终结符号串中包含的语法错误

例：一个自然语言文法的例子 (属于上下文无关文法)

<句子> -> <名词短语> <动词短语>
<名词短语> -> <形容词> <名词短语>
<名词短语> -> <名词>
<动词短语> -> <动词> <名词短语>
<形容词> -> little
<名词> -> boy
<名词> -> apple
<动词> -> eat

该文法的推导(自顶向下)过程

<句子> => <名词短语> <动词短语>
=> <形容词> <名词短语> <动词短语>
=> little <名词短语> <动词短语>
=> little boy <动词短语>
=> little boy <动词短语> <名词短语>
=> little boy eats <名词短语>
=> little boy eats <名词>
=> little boy eats apple

(上面的串均为句型，最后一个是句子)

文法的分类：Chomsky文法分类体系

  • 0型文法(Type-0 Grammar)
    • 无限制文法(Unrestricted Grammar)/短语结构文法(Phrase Structure Grammar,PSG)
    • ∀α→β∈P∀α\rightarrow β∈P，αα至少包含一个非终结符
      • 要求满足左部的基本定义即可
    • 由0型文法G生成的语言L(G)为0型语言
  • 1型文法(Type-1 Grammar)
    • 上下文有关文法(Context-Sensitive Grammar,CSG)
    • ∀α→β∈P∀α\rightarrow β∈P，∣α∣≤∣β∣|α|\leq|β|
    • CSG中无法产生空串，即ε_ε\_产生式
    • 产生式的一般形式为：α1Aα2→α1βα2,β!=εα_1Aα_2 \rightarrow α_1βα_2,β!=ε
      • 只有当上下文为α1,α2α_1,α_2时才能将AA替换为ββ
    • 由上下文有关文法G生成的语言L(G)为上下文有关语言(1型语言)
  • 2型文法(Type-2 Grammar)
    • 上下文无关文法(Context-Free Grammar,CFG)
    • ∀α→β∈P∀α\rightarrow β∈P，α∈V(N)α∈V(N)
    • 产生式的一般形式为A→βA\rightarrow β
      • 要求左部是一个非终结符
    • 由上下文无关文法G生成的语言L(G)为上下文无关语言(2型语言)
    • 例：一个上下文无关文法

S→L∣LTS\rightarrow L|LT
T→L∣D∣TL∣TDT\rightarrow L|D|TL|TD
L→a∣b∣c∣dL\rightarrow a|b|c|d
D→0∣1∣2∣3∣4∣5D\rightarrow 0|1|2|3|4|5

  • 3型文法(Type-3 Grammar)
    • 正则文法(Regular Grammar,RG)
      • 右线性(Right Linear)文法：A→wB∣wA\rightarrow wB|w
      • 左线性(Left Linear)文法：A→Bw∣wA\rightarrow Bw|w
      • 左线性文法和右线性文法均称作正则文法
    • 正则文法可描述程序设计语言的多数单词
    • 例：生成标识符的右线性文法和左线性文法

S→a∣b∣c∣dS\rightarrow a|b|c|d
S→aT∣bT∣cT∣dTS\rightarrow aT|bT|cT|dT
T→a∣b∣c∣d∣0∣1∣2∣3∣4∣5T\rightarrow a|b|c|d|0|1|2|3|4|5
T→aT∣bT∣cT∣dT∣0T∣1T∣2T∣3T∣4T∣5TT\rightarrow aT|bT|cT|dT|0T|1T|2T|3T|4T|5T

S→a∣b∣c∣dS\rightarrow a|b|c|d
S→Sa∣Sb∣Sc∣Sd∣S0∣S1∣S2∣S3∣S4∣S5∣S\rightarrow Sa|Sb|Sc|Sd|S0|S1|S2|S3|S4|S5|

  • 四种文法间从低到高为包含的关系，即0型文法集合⊇1型文法集合⊇2型文法集合⊇3型文法集合，并且从低到高限制性越来越强

增广文法(Augmented Grammar)

  • 如果G是一个以S为开始符号的文法，则G的增广文法G’就是在G中加上新开始符号S’和产生式S’->S而得到的文法
  • 引入这个新的开始产生式的原因：
    • 使文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接收状态
  • 例：文法G的产生式为： E→E+T∣T,T→T∗F∣F,F→(E)∣idE\rightarrow E+T|T,T\rightarrow T*F|F,F\rightarrow (E)|id
    • 改为增广文法G’：E′→E,E→E+T∣T,T→T∗F∣F,F→(E)∣idE'\rightarrow E,E\rightarrow E+T|T,T\rightarrow T*F|F,F\rightarrow (E)|id

语言的形式化定义

由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言，记为L(G)
即 L(G)={w∣S⇒∗w,w∈V(T)∗}L(G)=\{w|S\stackrel{*}{\Rightarrow}w,w∈V(T)^*\}

  • 若一个文法是递归的，则它所产生的语言是无限集

例：文法G的产生式如下

S→L∣LTS\rightarrow L|LT
T→L∣D∣TL∣TDT\rightarrow L|D|TL|TD
L→a∣b∣c∣...∣zL\rightarrow a|b|c|...|z
D→0∣1∣2∣3∣...∣9D\rightarrow 0|1|2|3|...|9

该文法生成的语言为：标识符(字母数字串)
同理也可以写出无符号整数和浮点数的文法：

S→T∣TLTS\rightarrow T|TLT
T→D∣DTT\rightarrow D|DT
D→0∣1∣2∣3∣...∣9D\rightarrow 0|1|2|3|...|9
L→.L\rightarrow .

语言上的运算

运算 定义和表示
L和M的并 L∪M={s∥s∈L∨s∈M}L ∪ M = \{s\|s∈L∨s∈M\}
L和M的连接 LM={st∥s∈L∧t∈M}LM = \{st\|s∈L∧t∈M\}
L的幂 L0=ε,Ln=LLn−1,n>=1L^0={ε}, L^n=LL^{n-1},n>=1
L的克林闭包 L∗=⋃i=1∞LiL^*=\bigcup_{i=1}^{∞}L^i
L的正闭包 L+=⋃i=1∞LiL^+=\bigcup_{i=1}^{∞}L^i

例：令L=A,B,...,Z,a,b,...,z,D=0,1,...,9L={A,B,...,Z,a,b,...,z},D={0,1,...,9}，则L(L∪D)∗L(L ∪ D)^*表示的语言是标识符

CFG的分析树

  • 根结点的标号为文法开始符号
  • 内部结点表示对一个产生式A→βA\rightarrow β的应用
    • 内部结点本身是该产生式的左部AA
    • 叶结点的标号既可以是非终结符，也可以是终结符
    • 该结点的子结点的标号从左到右构成产生式的右部ββ
      • 从左到右排列叶结点得到的符号串称为是这棵树的产出(yield)或边缘(frontier)
      • 从文法开始符号推导出的串是文法的一个句型，对应于一棵分析树中从根结点向下展开的所有子树
      • 分析树中所有子树的边缘<->文法的一个短语，当子树高度<2时，边缘为直接短语
      • 每棵高度为2的子树对应于一个产生式，因此直接短语一定是一个产生式的右部
      • 对于一个句子中只能有终结符号，因此一定从开始符号推导到最后的结果，也就是对应于整棵分析树的边缘
      • 一个句子可以包含多次产生式的推导，但不一定用到文法的所有产生式，因此并不是所有的产生式右部都是一个给定句子中的短语
  • 给定一个推导S⇒α1⇒α2⇒...⇒αnS\Rightarrow α_1\Rightarrow α_2\Rightarrow ...\Rightarrow α_n
    • 对于推导过程中得到的每一个句型αiα_i，都可以构造出一个边缘为αiα_i的分析树
    • 分析树是推导过程的图形化表示
    • 根据文法描述单词，根据分析树描述一整个推导过程(分析树是一个推导相关的概念)

例：一个文法产生式为P={E→E+E∣(E)∣−E}P=\{E\rightarrow E+E|(E)|-E\}，推导过程：E⇒−E⇒−(E)⇒−(E+E)E \Rightarrow -E \Rightarrow -(E) \Rightarrow -(E+E)
构建分析树：

该分析树中短语为：-(E+E),(E+E),E+E，其中E+E是直接短语

例：一个自然语言的文法

<句子> -> <动词短语>
<动词短语> -> <动词> <名词短语>
<名词短语> -> <名词> <名词短语>|<名词>
<动词> -> 提高
<名词> -> 高人|人民|民生|生活|活水|水平

输入字符序列：提 高 人 民 生 活 水 平
构建分析树：

此例中高人、民生、活水虽然是产生式右部，但并不是句子的直接短语

二义性文法

如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性(Ambiguous)的

  • 对于任意一个上下文无关文法，不存在一个算法，判定其是无二义性的
    • 但是可以给出一组充分条件，满足这组充分条件的文法是无二义性的
      • 满足条件，肯定无二义性；不满足，可能是有二义性的(未必一定是)
      • 比如文法满足确定性则文法一定是无二义性的
  • 应尽量避免为编译应用设计出具有二义性的文法，或者在使用二义性文法时使用附加规则消除二义性

例：一个文法的产生式为 S→if E then S∣if E then S else S∣otherS \rightarrow if\space E\space then\space S|if\space E\space then\space S\space else\space S|other
该文法生成条件语句或其他语句
对一个给定的句型：if E1 then if E2 then S1 else S2if\space E1\space then\space if\space E2\space then\space S1\space else\space S2
构造对应的分析树：

此时存在可用的消歧规则：令每个else和最近的尚未匹配的if匹配(选择分析树1)