编译原理内容.

1、安 徽 大 学 实 验 课 程 教 案课 程 名 称编译原理课 程 属 性专业基础开 课 学 年开 课 学 期 年 级 专 业 主 讲 教 师课程所属院系部课程所属系(教研室)实验一名称Chomsky文法类型判断（Recognizing the type of the Chomsky grammar）一、背景资料1956年，N.Chomsky首先对形式语言进行了描述。N.Chomsky在对某些自然语言进行研究的基础上，提出了一种用于描述语言和文法的数学系统，按照对文法规则的不同定义形式，对语言和文法分成了4类，对每一类语言，让它与一种特定种类的自动机那样的识别器联系起来。形式语言理论的形成与发

2、展，对计算机科学的发展是一个推动，在程序设计语言的设计与编译实现以及计算复杂性等方面都有着重大影响。二、实验目的要求输入：一组任意的规则。输出：相应的Chomsky 文法的类型。三、实验原理10型文法（短语文法）如果对于某文法G，P中的每个规则具有下列形式：u: = v其中uV，vV*，则称该文法G为0型文法或短语文法，简写为PSG。0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。这种文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集。这种语言可由图灵机（Turning）来识别。21型文

3、法（上下文有关文法）如果对于某文法G，P中的每个规则具有下列形式：xUy: = xuy其中UVN；uV；x，yV*，则称该文法G为1型文法或上下文有关文法，也称上下文敏感文法，简写为CSG。1型文法的规则左部的U和右部的u具有相同的上文x和下文y，利用该规则进行推导时，要用u替换U，必须在前面有x和后面有y的情况下才能进行，显示了上下文有关的特性。1型文法所确定的语言为1型语言L1，1型语言可由线性有界自动机来识别。32型文法（上下文无关文法）如果对于某文法G，P中的每个规则具有下列形式：U : = u其中UVN；uV，则称该文法G为2型文法或上下文无关文法，简写为CFG。按照这条规则，对于上

4、下文无关文法，利用该规则进行推导时，无需考虑非终结符U所在的上下文，总能用u替换U，或者将u归约为U，显示了上下文无关的特点。2型文法所确定的语言为2型语言L2，2型语言可由非确定的下推自动机来识别。一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此，上下文无关文法及相应语言引起了人们较大的兴趣与重视。43型文法（正则文法，线性文法）如果对于某文法G，P中的每个规则具有下列形式：U : = T 或 U : = WT其中TVT；U,WVN，则称该文法G为左线性文法。如果对于某文法G，P中的每个规则具有下列形式：U : = T 或 U : = TW其中TVT；U, WVN，则称该文法

5、G为右线性文法。左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG。按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3，3型语言可由确定的有限状态自动机来识别。在常见的程序设计语言中，多数与词法有关的文法属于3型文法。可以看出，上述4类文法，从0型到3型，产生式限制越来越强，其后一类都是前一类的子集，而描述语言的功能越来越弱，四类文法及其表示的语言之间的关系可表示为：0型1型2型3型；即L0 L1 L2 L3四、仪器微机

6、五、实验步骤（包括操作方法、数据处理）六、注意事项 文法的输入应简便。 指明是哪一类Chomsky 文法，并给出相应的四元组形式：G=（VN，VT，P，S）。说明：简单起见， 可以不考虑0型文法类。七、思考题3型文法和DFA、NFA、正规式的关系如何？实验 二名称消除文法的左递归（Removing the left recursion of the grammar）一、背景资料一个文法是含有左递归的，如果存在非终结符PPP含有左递归的文法将使上述的自上而下的分析过程陷入无限循环，即当试图用P去匹配输入串时，就会出现在没有吃进任何输入符号的情况下，又得重新要求P去进行新的匹配。因此，使用自上而下

7、分析法必须消除文法的左递归性。二、实验目的要求输入：任意的上下文无关文法。输出：消除了左递归的等价文法。三、实验原理1直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为PP / 其中，是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式： PP PP / 这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。 设有简单表达式文法GE： EE+T/ T TT*F/ F F（E）/ I经消除直接左递归后得到如下文法： ETE E +TE/ TFTT *FT/ F（E）/ I考虑更一般的情况，假定关于非终结符P的规则为PP1 / P2

8、 / Pn / 1 / 2 /m其中，i（I1，2，n）都不为，而每个j（j1，2，m）都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归：P1 P / 2 P /m PP 1P / 2 P / n P /2间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设有文法GS：SQc/ cQRb/ bRSa/ a虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有SQcRbcSabcQRbSabQcabRSaQc

9、aRbca就显现出其左递归性了，这就是间接左递归文法。消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。如果一个文法不含有回路，即形如PP的推导，也不含有以为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：（1） 把文法G的所有非终结符按任一顺序排列，例如，A1，A2，An。（2） for （i1；i<=n；i+）for （j1；j<=i1；j+）把形如AiAj的产生式改写成Ai1 /2 /k 其中Aj1 /2 /k是关于的Aj全部规则； 消除Ai规则中的直接左递归； （3） 化简由（2）所得到的文法，即去掉

10、多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。首先，令非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q中的相关规则中，则Q的规则变为QSab/ ab/ b。代换后的Q不含有直接左递归，将其代入S，S的规则变为SSabc/ abc/ bc/ c。此时，S存在直接左递归。在消除了S的直接左递归后，得到整个文法为：SabcS/ bcS'/ cS'S abcS'/ QSab/ ab/ bRSa/ a可以看到从文法开始符号S出发，永远无法达到Q和R，所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法GS为：SabcS'/ bcS/

11、cS'S' abcS'/ 当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q、R，那么最后得到的文法GR为： RbcaR'/ caR'/ aRR' bcaR'/ 容易证明上述两个文法是等价的。四、材料、试剂及仪器微机五、实验步骤（包括操作方法、数据处理）消除左递归算法：（4） 把文法G的所有非终结符按任一顺序排列，例如，A1，A2，An。（5） for （i1；i<=n；i+）for （j1；j<=i1；j+）把形如AiAj的产生式改写成Ai1 /2 /

12、k 其中Aj1 /2 /k是关于的Aj全部规则； 消除Ai规则中的直接左递归； （6） 化简由（2）所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。六、注意事项指明是否存在左递归，以及左递归的类型。对于直接左递归，可将其改为直接右递归；对于间接左递归（也称文法左递归），则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。（应该有n！种）七、思考题实验 三名称由正规（则）文法构造正规（则）式（Generating regular expression based on the given canonical grammar）一、背景资料一个文法可以定义某种

13、语言，而一个特定的语言也可以由文法来描述。但文法与语言之间并不存在一一对应的关系。形式语言理论已经证明：（1） 给定一个文法，就能从结构上惟一地确定其语言，即GL（G）（2）给出文法后，语言也就相应地确定了，其语言可以是有限的，也可以是无限的。二、实验目的要求输入：任意的正规文法。输出：相应的正规式。三、实验原理3型文法（正则文法，线性文法） 如果对于某文法G，P中的每个规则具有下列形式：U : = T 或 U : = WT其中TVT；U,WVN，则称该文法G为左线性文法。如果对于某文法G，P中的每个规则具有下列形式：U : = T 或 U : = TW其中TVT；U, WVN，则称该文法G为

14、右线性文法。左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG。按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3，3型语言可由确定的有限状态自动机来识别。程序设计语言的单词可由正则文法产生，例如，标识符的定义可由正则文法描述如下：<标识符>:=<字母>/<标识符><字母>/<标识符><数字>显然，该文法描述了以字母开头的字母数字串的集合。现在要引入

15、另一种适合于描述单词的表示法正则表达式。正则表达式又称为正则式，每个正则表达式描述的集合称为正则集。之所以采用正则表达式来描述，主要基于以下几点原因：（1） 词法规则简单，无需上下文无关文法那样严格的表示法，用正则式表示法来理解被定义的符号集合比理解由重写规则集合定义的语言更为容易；（2） 从正则式构造高效识别程序比上下文无关文法更容易；（3） 可以从某个正则式自动地构造识别程序，它可以识别用该正则式表示的字符串集合中的字符串，从而减轻后面要介绍的词法分析时的工作量。（4） 可用于其他各种信息流的处理，例如，已经应用于某些模式识别问题、文献目录检索系统以及正文编辑程序等。正则表达式和正则集设有

16、字母表。上的正则表达式和它所表示的正则集递归地定义如下：（1） 和都是上的正则表达式，它们所表示的正则集分别为和，其中是空串，是空集；（2） 任意的a是正则表达式，它所表示的正则集是a；（3） 如果e1和e2是上的任意的正则表达式，且分别表示的正则集为L（e1）和L（e2），则：· e1/e2也是正则表达式，表示的正则集为L（e1 / e2）L（e1）L（e2）。· e1 e2也是正则表达式，表示的正则集为L（e1 e2）L（e1）L（e2）。· （e1）*也是正则表达式，表示的正则集为L（e1）*）L（e1）*。定义中（1）和（2）定义了原子正则表达式，而（3）

17、则表明字母表上的正则表达式可由原子正则表达式或较简单的正则表达式通过联合、连接与闭包运算构成一般的正则表达式。正则表达式的性质如果两个正则表达式e1和e2表示的正则集相同，即值相等，则称它们是等价的。记为e1e2。正则表达式与正则文法的关系一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出，除了符号外，一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如，对于<数字> := 0/1/2/9，由非终结符数字所产生的字符串集合与正则表达式0/1/2/9所定义的字符串集合是相同的。正则集，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。

18、四、材料、试剂及仪器微机五、实验步骤（包括操作方法、数据处理）六、注意事项要求：输出界面为：正规文法正规式七、思考题实验 四名称不确定有限状态自动机的确定化（Affirmation of the indefinitely finite automata）一、背景资料有限自动机（FA）可以看作是由一个带有读头的有限控制器和一条字符输入带组成，如图所示。a a a b b b c c 输入带控制器FA的示意图控制器的读头从左至右顺次扫描输入带，每当从输入带上读到一个符号时，便引起控制器状态的改变，同时读头右移一个符号位。控制器包括有限个状态，状态和状态之间存在转换关系。当处于某个状态，读入一个字符

19、时，则使状态改变为另一个状态，从而形成状态转换，改变后的状态称为后继状态。状态转换后的后继状态有三种可能情况：（1）后继状态为自身；（2）后继状态为一个；（3）后继状态为若干个。某个有限自动机，如果每次状态转换的后继状态都是惟一的，则称它是确定有限自动机（DFA）；如果转换后的后继状态并不都是惟一的，则称它是不确定有限自动机（NFA）。有限自动机的开始工作状态称为初始状态，结束工作的状态称为终止工作状态或接收状态。如果把上一小节中的状态转换图的各个结点看成是某一个状态，初始结点为初始状态，终止结点为终止状态，并且每一条边表示一个转换关系，这样一个有限自动机的工作状态就可以采用状态转换图来描述了

20、，从而可以把前面的图看成是一个有限自动机。对于上图，有限自动机处在初始状态0，当读入符号a后，自动机便从状态0转换到后继状态1中，再读入一个符号b后，自动机便从状态1转换到后继状态2。当自动机读入一个符号串，自动机则从初始状态开始，经过一系列状态转换，最终若能够到达终止状态，则称这一符号串被该自动机所接收或识别，否则不能被该自动机所接收。二、实验目的要求输入： 非确定有限（穷）状态自动机。输出： 确定化的有限（穷）状态自动机三、实验原理一个确定的有限自动机（DFA）M可以定义为一个五元组，M（K，F，S，Z），其中：（1） K是一个有穷非空集，集合中的每个元素称为一个状态；（2） 是一个有穷字

21、母表，中的每个元素称为一个输入符号；（3） F是一个从K×K的单值转换函数，即F（R，a）Q，（R，QK）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q称为状态R的后继状态；（4） SK，是惟一的初态；（5） ZK，是一个终态集。由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。 对于DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M所接受。若M的初态结点同时又是终态结点，则称可为M所接受（或识别），DFA M所能接受的全部字符串（字）组

22、成的集合记作L（M）。 一个不确定有限自动机（NFA）M可以定义为一个五元组，M（K，F，S，Z），其中：（1） k是一个有穷非空集，集合中的每个元素称为一个状态；（2） 是一个有穷字母表，中的每个元素称为一个输入符号；（3） F是一个从K×K的子集的转换函数；（4） SK，是一个非空的初态集；（5） ZK，是一个终态集。由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是：（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；（2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数

23、。因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。和DFA一样，NFA也可以用矩阵和状态转换图来表示。对于NFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记（除外）连接形成的字符串可为M所接受。NFA M所能接受的全部字符串（字）组成的集合记作L（M）。由于DFA是NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。设M1和M2是同一个字母集上的有限自动机，若L（M1）L（M2），则称有限自动机M1和M2等价。由以上定义可知，若两个自动机能够接受相同的语言，则称这两个自动机等价。DFA是NFA的特例，因此对于每一个NFA M1

24、总存在一个DFA M2，使得L（M1）L（M2）。即一个不确定有限自动机能接受的语言总可以找到一个等价的确定有限自动机来接受该语言。NFA确定化为DFA同一个字符串可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。下面介绍一种NFA的确定化算法，这种算法称为子集法：（1） 若NFA的全部初态为S1，S2，Sn，则令DFA的初态为：SS1，S2，Sn，其中方括号用来表示若干个状态构成的某一状态。（2） 设DFA的状态集K中有一状态为Si

25、，Si+1，Sj，若对某符号a，在NFA中有F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 则令F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 为DFA的一个转换函数。若 Si，Si+1，Sk 不在K中，则将其作为新的状态加入到K中。（3） 重复第2步，直到K中不再有新的状态加入为止。（4） 上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表。（5） DFA中凡是含有NFA终态的状态都是DFA的终态。对于上述NFA确定化算法子集法，还可以采用另一种操作性更强的描述方式，下面我们给出其详细描述。首先给出两个相关定义。 假设I

26、是NFA M状态集K的一个子集（即IK），则定义-closure（I）为：（1） 若QI，则Q-closure（I）；（2） 若QI，则从Q出发经过任意条弧而能到达的任何状态Q，则Q-closure（I）。状态集-closure（I）称为状态I的闭包。假设NFA M（K，F，S，Z），若IK，a，则定义Ia-closure（J），其中J是所有从-closure（I）出发，经过一条a弧而到达的状态集。NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化

27、。四、材料、试剂及仪器微机五、实验步骤（包括操作方法、数据处理）六、注意事项 实现计算闭包closure（I）的算法； 实现转换函数move（q，a）的算法； 输出界面如下：NFA的 图形形式DFA的图形形式七、思考题实验 五名称DFA的最小化(Minimizing definitely finite automata ）一、背景资料NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。二、实验目的要求输入： DFA。输出： 最小化的DFA。 三、实

28、验原理所谓自动机的化简问题即是对任何一个确定有限自动机DFA M，构造另一个确定有限自动机DFA M，有L（M）L（M），并且M的状态个数不多于M的状态个数，而且可以肯定地说，能够找到一个状态个数为最小的M。下面首先来介绍一些相关的基本概念。 设Si是自动机M的一个状态，从Si出发能导出的所有符号串集合记为L（Si）。 设有两个状态Si和Sj，若有L（Si）L（Sj），则称Si和Sj是等价状态。 下图所示的自动机中L（B）L（C）1，所有状态B和状态C是等价状态。1ABCD011又例如终态导出的符号串集合中必然包含空串，而非终止状态导出的符号串集合中不可能包含空串，所以终态和非终止状态是不等价

29、的。对于等价的概念，我们还可以从另一个角度来给出定义。给定一个DFA M，如果从某个状态P开始，以字符串w作为输入，DFA M将结束于终态，而从另一状态Q开始，以字符串w作为输入，DFA M将结束于非终止状态，则称字符串w把状态P和状态Q区分开来。把不可区分开来的两个状态称为等价状态。设Si是自动机M的一个状态，如果从开始状态不可能达到该状态Si，则称Si为无用状态。设Si是自动机M的一个状态，如果对任何输入符号a都转到其本身，而不可能达到终止状态，则称Si为死状态。化简DFA关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不相交的子集间的状态都是可区分的，而同一个子集中的任何两个

30、状态都是等价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删去，也就获得了状态数最小的DFA。下面具体介绍DFA的化简算法：（1） 首先将DFA M的状态划分出终止状态集K1和非终止状态集K2。KK1K2 由上述定义知，K1和K2是不等价的。（2） 对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。设第i次划分已将状态集划分为k组，即：KK1(i)K2(i)Kk(i)对于状态集Kj(i)（j=1,2,k）中的各个状态逐个检查，设有两个状态Kj、 KjKj(i)，且对于输入符号a，有：F（Kj'，a）KmF（Kj''，a）Kn如果Km和Kn属

31、于同一个状态集合，则将Kj和Kj放到同一集合中，否则将Kj和Kj分为两个集合。（3） 重复第（2）步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。（4） 合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。（5） 若有无关状态，则将其删去。根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的自动机。四、材料、试剂及仪器微机五、实验步骤（包括操作方法、数据处理）六、注意事项要求： 实现子集划分算法； 输出界面如下：DFA的图形形式最小DFA的图形形式七、思考题实验 六名称计算first集合和follow集合（Comput

32、ing the first set and follow set）一、背景资料如果一个文法具有以下两个特点：（1） 每个产生式的右部都由终结符开始；（2） 如果两个产生式有相同的左部，那么他们的右部则由不同的终结符开始。显然对于这样的文法，其推导过程完全可以根据当前的输入符号，决定选哪个产生式往下推导，分析过程是惟一确定的，可以采用不带回溯的自上而下的预测分析方法。如果两个产生式的左部相同，而右部都由非终结符开始，例如，存在A / , 和均以非终结符开始，那么就很难决定何时使用A 选项，何时使用A选项。二、实验目的要求输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的fir

33、st集合和follow集合。三、实验原理设文法GS（VN，VT，P，S），则首字符集为： FIRST（）a | a，aVT，,V *。若，FIRST（）。由定义可以看出，FIRST（）是指符号串能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设x1x2xn，FIRST（）可按下列方法求得：令FIRST（），i1；（1） 若xiVT，则xiFIRST（）；（2） 若xiVN； 若FIRST（xi），则FIRST（xi）FIRST（）； 若FIRST（xi），则FIRST（xi）FIRST（）；（3） ii+1，重复（1）、（2），直到xiVT，（i2，3，n

34、）或xiVN且若FIRST（xi）或i>n为止。当一个文法中存在产生式时，例如，存在A，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法GS（VN，VT，P，S），则 FOLLOW（A）a | S Aa ，aVT。若SA，#FOLLOW（A）。由定义可以看出，FOLLOW（A）是指在文法GS的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：（1） 对于文法GS的开始符号S，有#FOLLOW（S）；（2） 若文法GS中

35、有形如BxAy的规则，其中x，yV *，则FIRST（y）FOLLOW（A）；（3） 若文法GS中有形如BxA的规则，或形如BxAy的规则且FIRST（y），其中x，yV *，则FOLLOW（B）FOLLOW（A）；四、材料、试剂及仪器微机五、实验步骤（包括操作方法、数据处理）六、注意事项 能处理含产生式的上下文无关文法； 程序的输出应包括first集合、follow集合以及所给定的文法是否为LL（1）文法的信息，输出界面如下：非终结符firstfollow判定结论七、思考题实验 七名称自动生成LR（0）分析表（Generating LR(0) analyzing table）一、背景资料LR

36、（K）分析方法是1965年Knuth首先提出的，这里的L是指从左至右扫描输入符号串，R是指构造一个最右推导的逆过程，K是指为了做出分析决定而向前看的输入符号的个数。LR（K）分析方法是当前最广义的无回溯的“移进- 归约”方法。根据栈中的符号串和向右顺序查看输入串的K(K³0)个符号，就能惟一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。自下而上分析方法是一种移进-归约过程，当分析栈的栈顶符号串形成句柄时就采取归约动作，因而自下而上分析法的关键问题是在分析过程中如何确定句柄。LR分析法根据分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K0）符号就可惟一地确定

37、分析器的动作是移进还是归约以及用哪个产生式归约，因而也就能惟一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR的分析过程是一种规范归约过程。LR分析方法的基本思想是，在规范归约过程中，一方面记住已移进和归约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号这3方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。LR分析法的基本思想是符合哲理的。所以，这种分析法也是非常一般的。因此，实现起来也就非常困难。作为归约过

38、程的“历史”材料的积累虽不困难（实际上，这些材料都保存在分析栈中），但是，“展望”材料的汇集却是一件很不容易的事情。这种困难不是理论上的，而是实际实现上的。因为，根据历史推测未来，即使是推测未来的一个符号，也常常存在着很多可能性 。所以，当把“历史”和“展望”材料综合在一起时，复杂性就大大增加。如果简化对“展望”材料的要求，我们就可能获得实际可行的分析算法。LR分析法比起自上向下的LL分析法和自下向上的优先分析方法对文法的限制要少得多，也就是说，对于大多数用无二义性上下文无关文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快、准确、及时地指出出错位置的优点。LR分析法

39、的一个主要缺点是，若用手工构造分析程序，则工作量相当大，因此，必须求助于自动产生这种分析程序的产生器。这种产生器称为LR分析程序自动产生器。本章我们将讨论这样一类产生器，利用这种产生器，我们不仅能自动产生一大类上下文无关文法的LR分析程序，还能指出文法含二义的情形或难于分析的特殊结构。二、实验目的要求输入：任意的压缩了的上下文无关文法。输出：相应的LR（0）分析表。三、实验原理对于LR文法，我们可以自动构造相应的LR分析表。为了构造LR分析表，我们需要定义一个重要概念文法的规范句型“活前缀”。这种句柄之后不含任何符号的前缀称为活前缀。在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）

40、X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证在分析的过程中，如果分析的句子是正确的，栈里的文法符号（自栈底而上）始终构成活前缀。假若一个文法G的拓广文法的活前缀识别自动机中的每个状态（项目集）不存在下述情况：（1）既含移进项目又含归约项目；（2）含有多个归约项目，则称G是一个LR（0）文法。该自动机的状态集合即

41、为该文法的LR（0）项目集规范族。构造识别文法活前缀DFA有3种方法：（1）根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA再确定为DFA；（2）求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA；（3）使用闭包函数（CLOSURE）和转向函数(GO(I,X)构造文法G的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。符号串的前缀是指该符号串的任意首部，包括空串。例如，对于符号串abc，其前缀有，a，ab，abc。如果输入串没有错误的话，一个规范句型的活前缀是该句型的一个前缀，但它不含句柄之后的任何符号。之所以称为活前缀，

42、是因为在该前缀后联接尚未输入的符号串可以构成一个规范句型。活前缀与句柄的关系如下：（1）活前缀已含有句柄的全部符号，表明产生式A的右部已出现在栈顶。（2）活前缀只含句柄的一部分符号，表明A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号。（3）活前缀不含有句柄的任何符号，此时期望A的右部所推出的符号串。在文法G的每个产生式的右部（候选式）的任何位置上添加一个圆点，所构成的每个产生式称为LR（0）项目。如产生式A® xyz有如下项目：A®.xyz，A®x.yz，A®xy.z，A®xyz.。为刻划分析过程中的文法的每一个产生式的右部符号

43、已有多大一部分被识别（出现在栈顶），可以用这种标有圆点的产生式来确定。（1）A.刻划产生式A的右部已出现在栈顶。 （2）A1.2 刻划A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号。 （3）A. 刻划没有句柄的任何符号在栈顶，此时期望A的右部所推出的符号串。（4）对于A的LR(0)项目只有A。设文法G=（VT，VN，S，P）是一个上下文无关文法，若存在一个规范推导SAw12w（其中A12P），则称项目A12对活前缀=1是有效的，即LR(0) 有效项目。从直观意义上讲，一个LR(0)项目指明了在分析过程中的某一步我们看到产生式的多大部分被识别，LR(0)项目中的圆点可看成是分析栈

44、栈顶与输入串的分界线，圆点左边为已进入分析栈的部分，右边是当前输入或继续扫描的符号串。不同的LR(0)项目，反映了分析栈顶的不同情况。我们根据LR(0)项目的作用不同，将其分为四类：（1）归约项目：表现形式：Aa.这类LR(0)项目表示句柄a恰好包含在栈中，即当前栈顶的部分内容构成了所期望的句柄，应按Aa进行归约。（2）接受项目：表现形式：a.其中是文法惟一的开始符号。这类LR(0)项目实际是特殊的归约项目，表示分析栈中内容恰好为a，用a进行归约，则整个分析成功。（3）移进项目：表现形式：Aa.（bVT）这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b移

45、进分析栈。（4）待约项目：表现形式：A.B （BVN）这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。在给出LR(0)项目的定义和分类之后，我们从这些LR(0)项目出发，来构造能识别文法所有前缀的有限自动机。其步骤是：首先构造能识别文法所有活前缀的非确定的有限自动机，再将其确定化和最小化，最终得到所需的确定的有限自动机。由文法G的LR(0)项目构造识别文法G的所有活前缀的非确定有限自动机的方法：（1）规定含有文法开始符号的产生式（设A）的第一个LR(0)项目（即.A）为NFA的惟一初态。（2）令所有LR(0)项目分别对

46、应NFA的一个状态且LR(0)项目为归约项目的对应状态为终态。（3）若状态i和状态j出自同一文法G的产生式且两个状态LR(0)项目的圆点只相差一个位置，即：若i为XX1X2·Xi-1·XiXn， j为 XX1X2Xi·Xi+1Xn，则从状态i引一条标记为Xi的弧到状态j。（4）若状态i为待约项目（设X·A），则从状态i引弧到所有A·r的状态。为了使“接受”状态易于识别，我们通常将文法G进行拓广。假定文法G是一个以S为开始符号的文法，我们构造一个，它包含了整个G，但它引进了一个不出现在G中的非终结符，并加进一个新产生式S，以S为开始符号。那么，我

47、们称是G的拓广文法。这样，便会有一个仅含项目S的状态，这就是惟一的“接受”态。如果I是文法G的一个项目集，定义和构造I的闭包CLOSURE(I)如下：（1） I的项目都在CLOSURE(I)中。（2） 若Aa.Bb属于CLOSURE(I)，则每一形如B.g的项目也属于CLOSURE(I)。（3） 重复（2）直到CLOSURE(I)不再扩大。定义转换函数如下：GO（I，X）= CLOSURE（J）其中：I为包含某一项目集的状态，X为一文法符号，J= AaX .b | Aa.X bI。圆点不在产生式右部最左边的项目称为核，惟一的例外是S.S，因此用GOTO（I，X）状态转换函数得到的J为转向后状态

48、闭包项目集的核。使用闭包函数（CLOSURE）和转换函数(GO(I,X)构造文法G的LR(0)的项目集规范族，步骤如下：（1） 置项目S.S为初态集的核，然后对核求闭包CLOSURE（S.S）得到初态的闭包项目集。（2） 对初态集或其他所构造的项目集应用转换函数GO(I，X)= CLOSURE(J)求出新状态J的闭包项目集。（3） 重复（2）直到不出现新的项目集为止。计算LR（0）项目集规范族C=I0，I1 , . In 的算法伪代码如下： Procedure itemsets(G); Begin C := CLOSURE (S®.S) Repeat For C 中每一项目集I和每一

49、文法符号X Do if GO(I,X) 非空且不属于C Then 把 GO(I,X) 放入C中 Until C 不再增大End;一个项目集可能包含多种项目，若移进和归约项目同时存在，则称移进-归约冲突，若归约和归约项目同时存在，则称归约-归约冲突。下面看一个具体的例子：我们希望能根据识别文法的活前缀的DFA建立LR分析器，因此，需要研究这个DFA的每个项目集（状态）中的项目的不同作用。我们说项目A1.2对活前缀1是有效的，其条件是存在规范推导。一般而言，同一项目可能对几个活前缀都是有效的（当一个项目出现在几个不同的集合中时便是这种情形）。若归约项目A1.对活前缀是有效的，则它告诉我们应把符号串

50、归约为A，即把活前缀变成A。若移进项目A1.2对活前缀是有效的，则它告诉我们，句柄尚未形成，因此，下一步动作应是移进。但是，可能存在这样的情形，对同一活前缀，存在若干项目对它都是有效的。而且它们告诉我们应做的事情各不相同，互相冲突。这种冲突通过向前多看几个输入符号，或许能够获得解决。对于每个活前缀，我们可以构造它的有效项目集。实际上，一个活前缀的有效项目集正是从上述的DFA的初态出发，经读出后而到达的那个项目集（状态）。换言之，在任何时候，分析栈中的活前缀X1X2Xm的有效项目集正是栈顶状态Sm所代表的那个集合。这是LR分析理论的一条基本定理。实际上，栈顶的项目集（状态）体现了栈里的一切有用信

51、息历史。 前面我们已经对LR（0）文法进行了定义,下面我们来看一下LR（0）分析表是如何构造的。对于LR（0）文法，我们可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数GO构造出LR分析表。下面是构造LR（0）分析表的算法。假定C=I0, I1,，In，令每个项目集Ik的下标k为分析器的一个状态，因此，G'的LR(0)分析表含有状态0，1，n。令那个含有项目S'S的Ik的下标k为初态。ACTION子表和GOTO子表可按如下方法构造：（1）若项目A.a属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTIONk, a为“把状态j和符号a移进栈”，简记为“sj”；（2）若项目A属于Ik，那么，对任何终结符a，置ACTIONk，a为“用产生式A进行规约”，简记为“rj”；其中，假定A为文法G'的第j个产生式；（3）若项目S'S属于Ik, 则置ACTIONk, #为“接受”，简记为“acc”；（4）若GO (Ik, A)