编译原理

编译原理

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

词法规则是指单词符号的形成规则。

语法规则是语法单位的形成规则，规定了如何从单词符号形成更大的结构（即语法单位或语法范畴）。

一般程序语言的语法单位有：表达式、语句、分程序、函数、过程和程序等。

程序语言的基本功能是描述数据和对数据的运算。所谓程序，从本质上来说是描述一定数据的处理过程。

强制式语言也称过程式语言。其特点是命令驱动，面向语句。一个强制式语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变。

应用式语言更注重程序所表示的功能，而不是一个语句接一个语句地执行。

文法是描述语言的语法结构的形式规则（即语法规则）。

所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位)是完全独立于这种范畴可能出现的环境的。

一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符，一个开始符号，以及一组产生式。形式上定义一个上下文无关文法Ｇ是一个四元式（Ｖ_Ｔ，Ｖ_Ｎ，Ｓ，P）

其中

Ｖ_Ｔ是一个非空有限集，它的每一个元素称为终结符号；

Ｖ_Ｎ是一个非空有限集，它的每一个元素称为非终结符号，Ｖ_Ｔ∩Ｖ_Ｎ＝f；

Ｓ是一个非终结符号，称为开始符号；

P是一个产生式（有限）集合，每个产生式形式是A→a　，其中，A∈Ｖ_Ｎ，a∈（　Ｖ_Ｔ∪Ｖ_Ｎ）^＊开始符号S至少必须在某一产生式的左部出现一次。

假定G是一个文法，S是它的开始符号。如果SÞa(表示从S出发，经0步或若干步可推出a），则称a是一个句型。仅含终结符号的句型是一个句子。

最左推导：任何一步aÞb都是对a中的最左非终结符进行替换的。同样，可定义最右推导。

字母表：由若干元素组成的有限非空集合，用S表示，它的每个元素称为一个符号。

符号串： 由S中的符号所构成的有穷序列。

符号串的前缀和后缀及子串：设x是一个符号串，将x的尾（前）部删掉几个字符后形成的符号串，称为x的前（后）缀；从一个符号串中删去他的一个前缀和后缀后所剩下部分称为x的子串。

空串（字）：不包含符号的序列称为空串（字） ，记为e。

用S^*表示S上的所有符号串的全体，空字也包括在其中。如：若S={a,b}则S^*={ e,a,b,aa,ab,bb,aaa,…}。f表示不含人何元素的空集{}。这里要注意e、{}和{e}的区别。

符号串的连接运算：设x和y是两个符号串，如果将y直接拼接在x之后，称这种操作为符号串的连接,记作： x.y

符号串的方幂：一个符号串与其自身的n-1的任意连接称为符号串的n次幂，记作：xⁿ

   xⁿ = x^n-1.x=x.x^n-1

特别地:x⁰= e

字符串集合的和(等价于集合的并运算)：设A、B是两个符号串的集合，则将集合A、B的和记为A+B或A∪B,定义为：A∪B={w|wÎA或wÎB}

符号串集合的连接：S^*的子集U和V中的（连接）积定义为:

         UV={ab∣aÎU & bÎV }

即集合UV中的符号串是由U和V的符号串连接而成的。注意，一般UV¹VU，但（UV)W=U(VW).

符号串集合V自身的n次（连接）积记为：

  Vⁿ = V V…V =V^n-1V=VV^n-1 (n个V)

规定 V⁰ = {e}.

V的闭包：令： V^*  = V⁰ ∪ V¹ ∪ V² ∪ …  称 V^*是V的闭包。

V的正则包（正闭包，正则闭包）：记V⁺ = VV^*, 称 V⁺是V的正则包，即V⁺ =V¹ ∪ V² ∪ V³ ∪ …。

产生式（也称为产生规则或简称规则）是定义语法范畴的一种书写规则。

 一个产生式的形式是  A→ α.

0型文法:设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*，则G是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是：0型文法的能力相当于图灵机(Turing)。或者说，任何0型文语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。0型文法是这几类文法中，限制最少的一个，所以我们在试题中见到的,至少是0型文法。

1型文法:也叫上下文有关文法，此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。

注意：虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法。

如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a，则不符合1型文法。

2型文法:也叫上下文无关文法，它对应于下推自动机。2型文法是在1型文法的基础上,再满足：每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。

如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求，因为其α=Ab，而Ab不是一个非终结符。

3型文法:也叫正规文法，它对应于有限状态自动机。它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）。

如有：A->a,A->aB,B->a,B->cB，则符合3型文法的要求。但如果推导为:A->ab,A->aB,B->a,B->cB或推导为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。具体的说，例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定义,如果把后面的ab,改成“一个非终结符＋一个终结符”的形式（即为aB）就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为B->Bc的形式就对了,因为A→α|αB（右线性）和A→α|Bα（左线性）两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法。

注意：上面例子中的大写字母表示的是非终结符,而小写字母表示的是终结符。

状态转换图 :由有限个结点所组成的有向图。

每个结点代表在识别分析过程中扫描器所处的状态，其中 含有一个初始状态和若干个终态。在图中，状态用圆圈表示，终态用双层圆圈表示。

抽象地看,状态转换图由五个部分组成:

(1) 有限个状态之集,记作K;

(2) 有限个输入符号组成的字母表,记作S;

(3) 从K´S到K的转换函数 f: K´SK. f(p,a)=q表示若当前状态为p,且输入符号为a,则进入下一个状态为q;

(4) S0ÎK,初始(开始)状态;

(5) 若干个终态之集: Z( ÍK )

        由上述五个要素组成的五元式  M=(K, S, f,S0,Z )称为一个确定的有限自动机(DFA: Deterministic Finite Automata).由此可见,一DFA实际上是状态转换图的形式描述(数学定义),状态转换图是DFA的几何(图形)表示.

有穷自动机，或有穷状态的机器，是描述（或“机器”）特定类型算法的数学方法。特别地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。当然有穷自动机与正则表达式之间有着很密切的关系，在下一节中大家将会看到如何从正则表达式中构造有穷自动机。但在学习有穷自动机之前，先看一个说明的示例。

通过下面的正则表达式可在程序设计语言中给出标识符模式的一般定义（假设已定义了letter 和digit）：

identifier = letter ( letter | digit ) *

它代表以一个字母开头且其后为任意字母和/ 或数字序列的串。

有穷自动机

　　通过标明数字1 和2 的圆圈表示的是状态（state），它们表示其中记录已被发现的模式的数量在识别过程中的位置。带有箭头的线代表由记录一个状态向另一个状态的转换（transition），该转换依赖于所标字符的匹配。

有穷自动机又分为确定型的有穷自动机（DFA）与非确定型的有穷自动机（NFA）两种。由于NFA与DFA是等价的,今后统称FA.

正规表达式就是用特定的运算符及运算对象按某种规则构造的表达式，用于描述给定3型语言的所有句子。

确定有穷自动机的化简方法有很多，我们介绍一个方法，叫做"分割法"：把一个DFA(不含多余状态)的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。

首先将M的状态分成两个子集：一个由终态(可接受态)组成，一个由非终态组成，

初始划分P₀为：P₀=({1，2，3，4},{5，6，7}) 。
　　第一个子集{1，2，3，4}，在读入输入符号a后，状态3和4分别转换为第一个子集中所含的状态1和4，而1 和2分别转换为第二个子集中所含的状态6和7，这就意味着{1，2}中的状态和{3，4}中的任何状态在读入a后到达了不等价的状态，因此{1，2}中的任何状态与{3，4}中的任何状态都是可区别的，因此得到了新的划分P1如下：

       P₁=({1，2} {3，4} {5，6，7})
　　P₁中的子集{3，4}对应输入符号a将再分割，而得到划分P₂=({1，2}，{3}，{4}，{5，6，7})。
P₂中的{5，6，7}可由输入符号a或b而分割，得到划分P₃=({1，2}，{3}，{4}，{5}，{6，7})。令1代表{1，2}消去2，令6代表{6,7}，消去7，我们便得到了化简了的DFA M′。

定义 设S是一字母表,则S上的正规表达式(正则表达式,正规式)及其表示的正规集可递归定义如下:

(1) f是一正规式,  相应的正规集为f;

(2) e是一正规式,  相应的正规集为{e};

(3) "aÎS,a 是一正规式,  相应的正规集为{a};

(4) 设r,s是正规式, 且它们所表示的正规集为Lr,Ls,则

1. (r) •(s)是正规式, 相应的正规集为Lr•Ls;

2. (r)|(s)是正规式, 相应的正规集为LrÈ Ls;

3. (r)*是正规式, 相应的正规集为Lr*

有限地使用上面的规则(4),所得的表达式均是正规式.

正规式的基本等价关系(“公理”)

A1.  r|s=s|r             A2. r|r=r        

A3.  r|f=r                A4. (r|s)|t=r|(s|t)

A5. (rs)t=r(st)       A6. r(s|t)=rs|rt

A7. (s|t)r=sr|st        A8. rf=fr=f

A9. re=er=r                A10. r*=(e|r)*=e|rr*

对于给定的三型文法G,如何构造正规式r,使Lr=L(G)

方法: 将G视为定义所含非终结符为变量的联立方程组,通过解方程组求得相应的正规式.

例  SaS | bA | b  AaS  设S,A所产生的正规集为L_S, L_A 则有

            L_S={a} L_S È{b} L_A È{b}          L_A ={a} L_S

         由定义可知,L(G)= L_S,视S, A为L_S, L_A 的正规式,相应的关系为

             S=aS | bA |b   A=aS  记 ‘|’ 为’+’, 有

               S=aS + bA + b     (1)  

              A=aS                     (2)

将(2)代入(1),得  S=aS + baS + b = (a+ba) S +b   (3)

得到形如         X= aX + b 的方程.关于这类方程有如下论断:

论断3.1 方程X=aX+b 有解 X=a*b    (不唯一)

证: 将x= a*b 代入右边: 右= aa*b+ b=(aa*+e) b= a*b=左

由论断3.1可知,S=(a+ba)*b=(a|ba)*b .

另外,对(3)连续使用两次论断3.1,有S=a*(baS+b)=a*baS+a*b=(a*ba)*a*b 我们可得一副产品: (a|ba)*b = (a*ba)*a*b

例  SaA         AbA | aB | b       BaA

相应的方程组为

           S=aA                  (1)

           A=bA+aB+b             (2)

           B=aA                  (3)

           (3) 代入(2):   A=(b+aa)A+b 得         A=(b+aa)*b

         代入(1):   S=a(b+aa)*b=a(b|aa)*b

Thmopson 法

(1) r= r1|r2 ,引入新开始状态S0,终态Sf,将M1,M2并联:

(2) r=r1·r2 , 将M1,M2串联

(3) r=r*,引入新开始状态S0,终态Sf,令原M1构成循环

在实际的构造中，我们可以省略一些e矢线。

第四章 语法分析和语法分析程序

自顶向下：对已给的输入串w，试图自上而下地建立一棵语法树；或者说,从S出发，为w构造一个最左推导。若成功,则wÎL(G)，否则拒绝。

    一般说来，在为w寻求最左推导的每一步，都涉及使用何产生式进行替换的问题。最简单的方法是，逐一试探。但是，逐一试探也不能完全解决问题。

消除文法的左递归：设文法是已简化的。若文法含直接左递归式:

      AAa | b (aÎV⁺) ,      则类似正规式求解方法，我们有

           A b {a}  (b a*).

    引入新的非终结符A’，令其产生a*，则有:   A bA’        A’ aA’|e      

例:  ET                可改写为：

     E EAT                  ETE’

     TF                    E’ATE’|e

     T TMF                 TFT’

     F(E)                   T’MFT’|e 

     F i                    F(E) | i 

     A+|-                  A+|-

     M* | /                M *|/

例： SaA | b      AcAS | e 

     FIRST(cAS)={c}

     FOLLOW(A) =FIRST(S)È{#}={a,b,#} 两个集合不相交, 故可进行无回溯的自顶向下分析。

设输入串w=aca#，其推导过程如下:

S#ÞaA#  当前输入符a属于FIRST(aA),用SaA推导

ÞacAS#  当前输入符c属于FIRST(cAS),用AcAS推导

ÞacS#  当前输入符a属于FOLLOW(A),用Ae推导.

ÞacaA# 当前输入符a属于FIRST(aA),用SaA推导

Þaca#            当前输入符#属于FOLLOW(A),用Ae推导,成功。

提取左因子  当文法中含有形如  Aab1|ab2|…|abm  的产生式时,可将其改写为:    AaA’      A’b1|b2|…|bm   

例如, EE+T | T     T(E) | a(E) | a        经改造后可得文法                   ETE’      E’+TE’| e      TaT’ | (E)      T’ (E) | e        这是一个LL(1)文法.

并非所有的文法都能改造为LL(1)文法.

能由LL(1)文法产生的语言称为LL(1)语言.它们已被证明具有许多重要特性, 主要有:

(1) 任何LL(1)文法都是无二义性的;

(2) 左递归文法是非LL(1)的;

(3) 存在一种算法,它能判定任意文法是否为LL(1)的;

(4) 存在一种算法,它能判定任意两个LL(1)文法是否等价;

(5) CFL是否是LL(1)语言是不可判定的;

(6) 非LL(1)语言是存在的.

若在分析过程中,每步向前扫描k个符号来确定选用的产生式,此分析方法称为是LL(k)分析.

例：表达式文法为：
E→E+T|T
T→T*F|F
F→i|(E)

(1)     判断文法是否为LL(1)文法

　　消除左递归，使文法变为：
E→TE′
E′→+TE′|ε
T→FT′
T′→*FT′|ε
F→i|(E)

(2) 构造预测分析表
对每个终结符或"#"号用a表示。
若a∈SELECT(A→α)，则把A→α放入M[A,a]中。
把所有无定义的M[A,a]标上出错标记。
为了使表简化，其产生式的左部可以不写入表中，表中空白处为出错。

定义：设G=（V_T，V_N，S，P）是上下文无关文法。

   FIRST（α）=｛a|α   aβ，a∈V_T，α，β∈V*｝,若α   ε，则规定ε∈FIRST（α）

预测分析法实例

ETE’ 

E’ATE’|e    

TFT’ 

T’MFT’|e 

F(E) | i 

A+|-

M *|/

对i+i*i进行预测分析的过程

LL(1)算法流程图

简单优先关系的定义:设G是已化简的文法,s,tÎV,若G中存在规范句型 a=…st…, 则s,t与a的句柄之间的关系必有下述情况之一:

对于上述情况,我们规定,       情况1: s>t; 情况2: s=t;         情况3: s<t

另外,还有一种情况,就是s和t均不在句柄中,那么一定存在某句型使得它们进入上述三种情况之一.

若s和t在任何句型中都不可能相邻出现,则我们规定二者无关系.

注意,这种优先关系是不对称的!

定义:若一文法G的任何两个符号之间至多存在一种优先关系,且任意两个不同的产生式无相同的右部,则称G为简单优先文法 .