[工学]语法分析

[工学]语法分析

7/22/20211《编译原理》冶金工业出版社编译原理——第四章第4章语法分析语法分析是编译过程的核心部分，同词法分析一样，是编译系统逻辑组成的经典划分中必不可少的部分。语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成分，同时进行语法捡查，为语义分析和代码生成做准备。\n7/22/20212《编译原理》冶金工业出版社编译原理——第四章目前语法分析常用的方法有自顶向下分析和自底向上分析两大类。而自底向上分析又可分为算符优先分析和LR分析,各分析方法各有优缺点，但都是当今编译程序构造的实用方法。执行语法分析任务的程序称为语法分析程序，也称为语法分析器，它是编译程序的主要部分之一。\n7/22/20213《编译原理》冶金工业出版社编译原理——第四章4.1语法分析器的作用语法分析器读取词法分析器提供的符号串，检查它是否能由源语言的文法产生。希望该分析器能以易理解的形式报告任何语法错误，并从错误中恢复过来，使后面的分析能继续进行下去。\n7/22/20214《编译原理》冶金工业出版社编译原理——第四章语法分析器在编译器中的位置\n7/22/20215《编译原理》冶金工业出版社编译原理——第四章语法分析器主要作用有两点：（1）根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树）。（2）检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理。\n7/22/20216《编译原理》冶金工业出版社编译原理——第四章4.1.1语法错误的处理程序错误大致包含如下四种，它们分别是：（1）词法错误，如标识符、关键字或算符的拼写错。（2）语法错误，如算术表达式的括号不配对。（3）语义错误，如算符作用于不相容的运算对象。（4）逻辑错误，如无穷的递归调用。\n7/22/20217《编译原理》冶金工业出版社编译原理——第四章对语法错误的处理，一般希望达到以下基本目标：（1）清楚而准确地报告发现的错误，地点正确、不漏报、不错报也不多报（2）迅速地从每个错误中恢复过来，以便分析继续进行。（3）对语法正确的源程序的分析速度不应降低太多。\n7/22/20218《编译原理》冶金工业出版社编译原理——第四章4.1.2错误恢复策略以下是一些可能的恢复策略：1.紧急方式恢复（Panic-moderecovery）2.短语级恢复（Phrase-levelrecovery）3.出错产生式（Error-productions）4.全局纠正（Globalcorrection）\n7/22/20219《编译原理》冶金工业出版社编译原理——第四章4.2上下文无关文法上下文无关文法（ContextFreeGrammar,CFG）是一个四元组G=(N，T，P，S)，其中：（1）N是非终结符的有限集合（Nonterminals），非终结符是表示字符串集合的语法变量。（2）T是终结符的有限集合（Terminals），且N∩T=Φ。终结符是组成字符串的基本符号。\n7/22/202110《编译原理》冶金工业出版社编译原理——第四章（3）P是产生式的有限集合（Productions），每个产生式形如：A→α（有时用：：=代替箭头→），其中A∈N，被称为产生式的左部，α∈(N∪T)*，被称为产生式的右部，若α=ε，则称A→ε为空产生式（也可以记为A→）。（4）S是非终结符，被称为文法的开始符号（Startsymbol）。\n7/22/202111《编译原理》冶金工业出版社编译原理——第四章4.2.1符号的使用约定（1）下列符号是终结符：①字母表前面的小写字母，如a、b、c等。②运算符号，如+、-等。③标点符号，如括号、逗号等。④数字，如0、1、…、9。⑤保留字，如id、if等\n7/22/202112《编译原理》冶金工业出版社编译原理——第四章4.2.1符号的使用约定（2）下列符号是非终结符：①字母表前面的大写字母，如A、B、C等。②字母S，常代表开始符号。③小写字母的名字，如expr、stmt等。（3）字母表后面的大写字母（如X,Y,Z）代表文法符号，也就是非终结符或终结符。（4）字母表后面的小写字母（主要是u,v,…,z)代表终结符号串。\n7/22/202113《编译原理》冶金工业出版社编译原理——第四章（5）小写希腊字母（例如、、）代表文法的符号串。（6）如果A->1、A->2、…、A->k是所有以A为左部的产生式（称它们为A产生式）。可以把它们写成A->1|2|…|k，称1、2、…、k是A的候选式。（7）直接用产生式集合代替四元组来描述文法。除非另有说明，否则第一个产生式左部的符号是开始符号。\n7/22/202114《编译原理》冶金工业出版社编译原理——第四章4.2.2推导推导就是从文法的开始符号S开始，反复使用产生式，将产生式左部的非终结符替换为右部的文法符号序列（展开产生式，用标记=>表示），直到得到一个终结符序列。\n7/22/202115《编译原理》冶金工业出版社编译原理——第四章如果A->是产生式，和是文法的任意符号串，说由A=>。如果1=>2=>…=>n，称1推导出n。符号“=>”表示“一步推导”。通常用符号“=>*”表示“零步或多步推导”。于是：（1）对任何串，有=>*。（2）如果=>*，而且=>，那么=>*。类似地，用“=>+”表示“一步或多步推导”。\n7/22/202116《编译原理》冶金工业出版社编译原理——第四章给定开始符号为S的文法G，可以用“=>+”关系来定义G产生的语言L(G)。L(G)的串仅包含G的终结符。称终结符号串在L(G)中，当且仅当S=>+。终结符串叫做G的句子。由上下文无关文法产生的语言叫做上下文无关语言。如果两个文法产生同样的语言，则这两个文法叫做等价的。对于开始符号为S的文法G，如果S=>*，称为G的句型，其中可能含有非终结符。句子是不含非终结符的句型。\n7/22/202117《编译原理》冶金工业出版社编译原理——第四章在推导过程中,若每次直接推导均替换句型中最左边的非终结符,则称为最左推导,由最左推导产生的句型被称为左句型.如果=>是最左推导,可以写成=>lm。类似地，可以定义最右推导与右句型，最右推导也被称为规范推导。\n7/22/202118《编译原理》冶金工业出版社编译原理——第四章4.2.3分析树和推导推导的过程可以用一棵树来表示，称为分析树。因此，从某种意义上讲，分析树可以看作是推导的图形表示，它既反映语言结构的实质，也反映推导过程，但它不能显示出替代顺序的选择。\n7/22/202119《编译原理》冶金工业出版社编译原理——第四章对文法G的句型，分析树被定义为具有下述性质的一棵树：（1）根由开始符号所标记。（2）每个叶子由一个终结符、非终结符或ε标记，它们从左到右一个句型，称为树的边界或果实。（3）每个内部结点由一个非终结符标记。（4）若A→X1X2...Xn是一个产生式，则X1、X2、...、Xn是标记为A的内部结点从左到右所有孩子的标记。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子。\n7/22/202120《编译原理》冶金工业出版社编译原理——第四章分析树与文法和语言存在下述关系：（1）每一直接推导（或者每个产生式），对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子。（2）分析树的叶子从左到右，构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。\n7/22/202121《编译原理》冶金工业出版社编译原理——第四章如前所述，分析树忽略了句型中符号被替代的顺序。如果只考虑最左推导（或最右推导），则可以消除推导过程中产生式应用顺序的不一致。不难看出，每棵分析树都有一个与之对应的唯一的最左推导和唯一的最右推导。然而，每一个句子不一定只有一个分析树，或者说不一定有一个最左推导或最右推导。\n7/22/202122《编译原理》冶金工业出版社编译原理——第四章4.2.4二义性若文法G对同一个句子产生不止一棵分析树，则称G是二义的。结论：（1）一个句型有多于一棵分析树，仅与文法和句型有关，与采用的推导方法无关。（2）造成二义性的原因，是文法中缺少对文法符号优先级和结合性的规定。\n7/22/202123《编译原理》冶金工业出版社编译原理——第四章4.3文法的编写文法无论对程序设计语言的设计还是对编译器的编写，至少在以下三个方面起着重要作用：（1）文法给出了精确的、易于理解的语言结构的说明。（2）以文法为基础的语言，便于加入新的或修改、删除旧的语言结构。（3）有些类别的文法，可以自动生成高效的分析器。\n7/22/202124《编译原理》冶金工业出版社编译原理——第四章4.3.1正规表达式和上下文无关文法的比较正规式可以描述的每种结构都可以用上下文无关文法来描述。可以机械地把一个非确定的有限自动机（NFA）变换成一个上下文无关文法。它产生的语言和这个NFA识别的语言相同。\n7/22/202125《编译原理》冶金工业出版社编译原理——第四章用下列规则构造：首先确定终结符号集合；再为NFA的每个状态i引入非终结符Ai，其中A0是开始符号，因为0是开始状态。如果状态i有一个转换到状态j，引入产生式Ai->Aj；如果是转换，则引入Ai->Aj；如果i是接受状态，则引入Ai->。\n7/22/202126《编译原理》冶金工业出版社编译原理——第四章用正规式定义语言的词法，其理由如下：（1）词法规则简单，用正规式描述已足够。（2）对于记号，正规式的表示比上下文无关文法更直观、简洁、易于理解。（3）从正规式可以自动地构造出有效的词法分析器，从任何文法都很难构造词法分析器。（4）区分词法和语法，为编译器前端的模块划分提供方便。\n7/22/202127《编译原理》冶金工业出版社编译原理——第四章一般情况下，正规式适合描述线性结构，如标识符、关键字、注释等，而上下文无关文法适合描述具有嵌套（层次）性质的非线性结构，如不同结构的句子if-then-else、begin-end等。\n7/22/202128《编译原理》冶金工业出版社编译原理——第四章4.3.2验证文法所产生的语言判断给定的产生式集合能产生什么样的语言是重要的，虽然编译器的设计者很少为完整的程序设计语言文法做这件事。\n7/22/202129《编译原理》冶金工业出版社编译原理——第四章4.3.3消除二义性可以由以下两种方法解决二义性问题：（1）改写二义文法为非二义文法。（2）对二义文法施加限制，具体就是为文法符号规定优先级和结合性，使得分析过程中仅能产生一棵分析树。\n7/22/202130《编译原理》冶金工业出版社编译原理——第四章1.改写二义文法为非二义文法：改写二义文法的基本思想是通过引入新的非终结符，使原来分辨不清的结构受到约束，从而使得对任何一个句子，仅能构造一棵分析树。结论：（1）由于新引入的非终结符限制每一步直接推导均有唯一选择，使得同一个句子仅有一棵分析树。（2）最终产生的分析树与推导方法无关，而仅与文法的描述有关。通俗地讲，推导仅改变分析树结点生孩子的先后，文法才决定生什么样的孩子。\n7/22/202131《编译原理》冶金工业出版社编译原理——第四章（3）引入新的非终结符，使得直接推导的步骤数增加，分析树的高度增高，从而分析效率降低。（4）越接近S的A与a，优先级越低。（5）对具有递归定义性质的A产生式A->A，若a（A在a的左边），则a具有左结合性质，若a（A在a的右边），则a具有右结合性质。\n7/22/202132《编译原理》冶金工业出版社编译原理——第四章将书写非二义文法的关键步骤归纳为下述两点：（1）引入一个新的非终结符，增加一个子结构并提高一级优先级。（2）递归非终结符在产生式中的位置，反映文法符号的结合性。\n7/22/202133《编译原理》冶金工业出版社编译原理——第四章2.为文法符号规定优先级和结合性改写文法可以解决二义性问题，但不是唯一的解决方法。比较二义文法和非二义文法，发现二义文法至少有两个优点：（1）比非二义文法容易理解。（2）分析效率高（分析树低，直接推导步骤少）。\n7/22/202134《编译原理》冶金工业出版社编译原理——第四章另一种解决方案是：保留原来的二义文法，而对文法中有二义的文法符号规定适当的优先级与结合性，使得在产生语言的过程中，限制不确定的选项到惟一选择。\n7/22/202135《编译原理》冶金工业出版社编译原理——第四章4.3.4消除左递归若文法G中的非终结符A，对某个文法符号序列α存在推导A=>+Aα，则称文法G是左递归的。若文法G中有形如A→Aα的产生式，则称该产生式对A直接左递归。\n7/22/202136《编译原理》冶金工业出版社编译原理——第四章【算法4-1】消除直接左递归。输入：文法G中所有的A产生式。输出：等价的不含直接左递归的文法G'。方法：首先,整理A产生式为如下形式:A->A1|A2|…|Am|1|2|…|n其中,I非空,j均不以A开始．然后用下述产生式代替A产生式：A->1A’|2A’|…|nA’A’->1A’|2A’|…|mA’|\n7/22/202137《编译原理》冶金工业出版社编译原理——第四章【算法4-2】消除左递归。输入：无回路文法G。输出：无左递归的等价文法G'。方法：将非终结符合理排序：A1，A2，...，An，然后运用下述过程：fori:=1tondobeginforj:=1toi–1dobegin用产生式Ai→δ1γ|δ2γ|…|δkγ代替每个形如Ai→Ajγ的产生式，其中，Aj→δ1|δ2|…|δk是所有的当前Aj产生式;end消除Ai产生式中的直接左递归end\n7/22/202138《编译原理》冶金工业出版社编译原理——第四章4.3.5提取左因子提取左因子是一种对产生适合预测分析的文法非常有用的文法变换。提取左因子的基本思想是：当不清楚应该用两个选择中的哪一个来替换非终结符A时，可改写A产生式来推迟这种决定，直到看见足够的输入能做出正确选择为止。\n7/22/202139《编译原理》冶金工业出版社编译原理——第四章【算法4-3】提取文法的左因子。输入：文法G。输出：等价的无左因子文法G'。方法：为每个产生式A，找出其候选项中最长公共前缀，重排A产生式如下，其中是不以为前缀的其他候选项。A->1A|2A|…|nA|并用下述产生式替代之。A->A’|A’->1|2|…|n重复此过程，直到所有A产生式的候选项中均不再有公共前缀。\n7/22/202140《编译原理》冶金工业出版社编译原理——第四章4.3.6非上下文无关语言的结构有些语言不能用任何上下文无关文法产生。\n7/22/202141《编译原理》冶金工业出版社编译原理——第四章4.4自顶向下语法分析本节介绍自顶向下语法分析的基本概念以及构造无回溯自顶向下语法分析器的方法。自顶而下分析的基本思想是：对于任何一个输入序列，从文法的开始符号开始，进行最左推导，直到得到一个合法句子或者发现一个非法结构。\n7/22/202142《编译原理》冶金工业出版社编译原理——第四章4.4.1递归下降语法分析法自顶而下分析的目的是为输入字符串寻找最左推导，或者说，从根结点（文法开始符号）开始，自上而下、从左到右地为输入字符串建立一棵分析树，并以预先确定的顺序创建分析树的结点。现在考虑自顶向下分析的一般形式，称为递归下降分析法。它可能需要回溯，即需要重复地扫描输入。\n7/22/202143《编译原理》冶金工业出版社编译原理——第四章4.4.2预测语法分析器为构造不带回溯的自顶而下分析算法，首先要消除文法的左递归，并找出克服回溯的充分必要条件。为了消除回溯，就必须保证：对文法的任何非终结符，当要去匹配输入串时，它能够根据所面临的输入符号准确地指派它的一个选择去执行任务，并且此选择的工作结果应是确信无疑的。\n7/22/202144《编译原理》冶金工业出版社编译原理——第四章令G是不含左递归的文法，对G的非终结符的候选α，定义它的首符集FIRST(α)为：FIRST(α)={a|α=>*a...，a∈T}，若α=>*ε，则ε∈FIRST(α)。如果非终结符A的所有选择的首符集两两不相交，即对于A的任何两个不同的选择αi和αj，有FIRST(αi)FIRST(αj)=，那么，当要求A匹配输入串时，A就能根据它所面临的第一个输入符号α，准确地指派某个选择去执行任务，这个选择就是那个终结首符含a的α。\n7/22/202145《编译原理》冶金工业出版社编译原理——第四章4.4.3预测语法分析器的状态转换图为了由文法构造预测语法分析器的状态转换图，首先需要消除文法中的左递归，然后提取左因子，并对每个非终结符A执行如下操作：（1）创建一个开始状态和一个终态（返回状态）。（2）对每个产生式A->X1X2…Xn，创建一条从开始状态到终止状态的路径，边上的标记分别为X1、X2、…、Xn。\n7/22/202146《编译原理》冶金工业出版社编译原理——第四章4.4.4非递归的预测分析图4-12非递归的预测语法分析器模型预测分析程序输出XYZ$分析表Ma+b$输入栈\n7/22/202147《编译原理》冶金工业出版社编译原理——第四章由程序控制的这个分析器的工作过程是：程序根据栈顶当前的符号X和输入符号a决定分析器的动作，它有4种可能：（1）如果X=a=$，分析器宣告分析完全成功而停机。（2）如果X=a$，分析器弹出栈顶符号X，推进输入指针，指向下一个符号。（3）如果X是终结符但不是a，则报告出错，调用错误恢复例程。（4）如果X是非终结符，程序访问分析表M，若M[X,a]是X产生式，例如，M[X,a]={X->UVW}，那么分析器用WVU代替栈顶的X，让U在栈顶。如果M[X,a]出错，分析器调用错误恢复例程。\n7/22/202148《编译原理》冶金工业出版社编译原理——第四章【算法4-4】非递归的预测分析。输入：串和文法G的分析表M。输出：如果属于L(G)，则输出的最左推导，否则报告错误。方法：开始时，语法分析器的格局是$S在栈里（其中S是G的开始符号且在栈顶），$在输入缓冲区。\n7/22/202149《编译原理》冶金工业出版社编译原理——第四章令ip指向$的第一个符号；Repeat令X是栈顶符号，a是ip指向的符号；ifX是终结符或者是$thenifX=athen从栈中弹出X，ip指向下一个符号elseerror()elseifM[X,a]=X->Y1Y2…Ykthenbegin从栈中弹出X；将Yk,Yk-1,…,Y1压入栈，Y1在栈顶；输出产生式X->Y1Y2…Ykendelseerror()UntilX=$\n7/22/202150《编译原理》冶金工业出版社编译原理——第四章表4-1文法（4-13）的分析表非终结符Id+*()$EE->TE’E->TE’E’E’->+TE’E’->E’->TT->FT’T->FT’T’T’->T’->*FT’T’->T’->FF->idF->(E)输入符号\n7/22/202151《编译原理》冶金工业出版社编译原理——第四章4.4.5FIRST集合和FOLLOW集合所谓构造预测分析器，实际上就简化成为构造给定文法的预测分析表。构造分析表的过程可以分为两步走：首先根据文法构造两个集合，FIRST集合和FOLLOW集合；然后根据两个集合构造预测分析表。文法符号序列α的FIRST集合定义如下：FIRST(α)={a|α=>*a...，a∈T}，若α=>*ε，则ε∈FIRST(α)。\n7/22/202152《编译原理》冶金工业出版社编译原理——第四章非终结符A的FOLLOW集合定义如下：FOLLOW(A)={a|S=>*...Aa...，a∈T}，若A是某句型的最右符号，则$∈FOLLOW(A)。非形式地讲，文法符号序列的FIRST集合，就是从开始可以推导出的所有以终结符开头的序列中的开头终结符。而一个非终结符A的FOLLOW集合，就是从文法开始符号可以推导出的所有含A序列中紧跟A之后的终结符。\n7/22/202153《编译原理》冶金工业出版社编译原理——第四章【算法4-5】计算X的FIRST集合。输入：文法符号X。输出：X的FIRST集合。方法：应用下述规则：（1）若X是终结符，则FIRST(X)={X}。（2）若X是非终结符且有X->，则加入到FIRST(X)。（3）若X是非终结符且有X->Y1Y2…Yk，并令Y0=，Yk+1=，则对所有j（0jk），若FIRST(Yj+1)且FIRST(Yj)，加入到FIRST(X)。对任意文法符号序列X1X2…Xn，FIRST(X1X2…Xn)的计算方法与【算法4-5】中规则（3）类似，即：FIRST(X1X2…Xn)是所有FIRST(Xi)(I=1,2,…,k)的并集。其中k为第一个具有性质不属于FIRST(Xk)或k>n的文法符号，若k>n，则FIRST(X1X2…Xn)。\n7/22/202154《编译原理》冶金工业出版社编译原理——第四章【算法4-6】计算所有非终结符的FOLLOW集合。输入：文法G。输出：G中所有非终结符的FOLLOW集合。方法：应用下述规则：（1）加入$到FOLLOW(S)，其中，S是开始符号，$是输入结束标记。（2）若有产生式A->B，则除外，FIRST()的全体加入到FOLLOW(B)。（3）若有产生式A->B或A->B，而FIRST()，则FOLLOW(A)的全体加入到FOLLOW(B)。\n7/22/202155《编译原理》冶金工业出版社编译原理——第四章4.4.6预测分析表的构造该算法的基本思想是：如果A→α是产生式且a在FIRST(α)中，那么当前输入符号为a时，语法分析器将用α展开A。惟一复杂的情况发生在α＝ε或α=>*ε时。在这种情况下，如果当前输入符号属于FOLLOW(A)，或者如果输入已经到达$而$在FOLLOW(A)中，语法分析仍将用α展开A。\n7/22/202156《编译原理》冶金工业出版社编译原理——第四章【算法4-7】构造预测分析表。输入：文法G。输出：分析表M。方法：应用下述规则：（1）对文法的每个产生式A->，执行（2）和（3）。（2）对FIRST()的每个终结符a，将A->加入到M[A,a]中。（3）若在FIRST()中，则对FOLLOW(A)的每个终结符b，将A->加入到M[A,b]中；若在FIRST()中，且$在FOLLOW(A)中，则将A->加入到M[A,$]中。（4）将M中其他没有定义的条目均置为error。\n7/22/202157《编译原理》冶金工业出版社编译原理——第四章4.4.7LL(1)文法【算法4-7】可用于任何文法G产生分析表M。然而对某些文法，M可能含有一些多重定义的条目。一个文法G被称为是LL(1)文法，当且仅当为它构造的预测分析表中不含多重定义的条目。由此分析表所组成的分析器被称为LL(1)分析器，它所分析的语言被称为LL(1)语言。第一个L表示从左到右扫描输入序列，第二个L表示产生最左推导，1表示在确定分析器的每一步动作时向前看一个终结符。\n7/22/202158《编译原理》冶金工业出版社编译原理——第四章一个文法G是LL(1)的，当且仅当G的任何两个产生式A→α|β，满足下面条件：（1）对任何终结符a、α和β不能同时推导出以a开始的文法符号序列。（2）α和β最多有一个可以推导出ε。（3）若β=>*ε，则α不能推导出以在FOLLOW(A)中的终结符开始的任何文法符号序列。\n7/22/202159《编译原理》冶金工业出版社编译原理——第四章无论是递归下降子程序法还是非递归的预测分析法，它们都只能处理LL(1)文法。但LL(1)文法有着明显的弱点：（1）文法比较难写。（2）LL(1)文法适应范围有限，对于有些语言，往往写不出它的LL(1)文法。\n7/22/202160《编译原理》冶金工业出版社编译原理——第四章4.5自底向上语法分析自顶向下分析采用的方法是推导，从根到叶子构造分析树，或者说从文法的开始符号产生出句子。LR分析器的构造一般都借助于分析器生成工具，当前应用最广泛的工具之一是YACC系列。\n7/22/202161《编译原理》冶金工业出版社编译原理——第四章4.5.1句柄非形式地说，一个串的“句柄”是和一个产生式右部匹配的子串，并且把它归约成该产生式左部的非终结符代表了最右推导逆过程的一步。形式地说，右句型（最右推导可得到的句型）γ的句柄是一个产生式A→β以及γ中的一个位置，在这个位置可找到串β。\n7/22/202162《编译原理》冶金工业出版社编译原理——第四章4.5.2句柄裁剪在中，把β归约到A可想象成“剪除句柄”。通过“裁减句柄”可以得到最右推导的逆过程。从被分析的终结符串开始。如果是文法的一个句子，那么，=n，其中n是下面的未知最右推导的第n步右句型：S=0=>rm1=>rm2=>rm…=>rmn-1=>rmn=为构造这个推导的逆过程，需要在n中找到句柄βn，并用产生式An->βn的左部代替βn，得到第n-1步的右句型n-1。重复此过程，即在n-1中找到句柄βn-1，并对该句柄进行归约得到右句型n-2。如果继续此过程将得到只包含开始符号S的右句型，那么就宣告分析成功并停止。在归约过程中所用产生式序列的逆序就是输入串的最右推导。\n7/22/202163《编译原理》冶金工业出版社编译原理——第四章4.5.3用栈实现移动归约分析实现移动归约分析的一种方便的办法是用栈保存文法符号，用输入缓冲区保存要分析的串，用$标记栈底，也用它标记输入串的右端。起初，栈是空的，串在输入中，如下所示：栈输入$$分析器移动零个或多个输入符号入栈，直到句柄β在栈顶为止，再把β归约成某个恰当的产生式的左步。分析器重复这个过程，直到它发现错误，或者栈中只含开始符号并且输入串为空：栈输入$S$进入这个格局后，分析器停机并宣告分析成功完成。\n7/22/202164《编译原理》冶金工业出版社编译原理——第四章分析器的基本动作是移动和归约，实际可能的动作还有另外两种，即接受和报错。（1）移动动作：下一个输入符号移动到栈顶。（2）归约动作：分析知道句柄的右端已在栈顶，它必须在栈中确定句柄的左端，再决定用什么样的非终结符代表句柄。（3）接受动作：分析器宣告分析成功。（4）出错动作：分析器发现语法错误，调用错误恢复例程。\n7/22/202165《编译原理》冶金工业出版社编译原理——第四章4.5.4活前缀出现在移动归约语法分析器栈中的右句型的前缀集合称为活前缀。\n7/22/202166《编译原理》冶金工业出版社编译原理——第四章4.5.5移动归约分析过程中的冲突有些上下文无关的文法不能使用移动归约分析。这种文法的移动归约分析器会形成这样的格局：它根据栈中所有的内容和下一个输入符号不能决定是移动还是归约（移动-归约冲突），或不能决定按哪一个产生式进行归约（归约-归约冲突）。\n7/22/202167《编译原理》冶金工业出版社编译原理——第四章4.6算符优先分析法算符优先分析法只考虑算符（广义为终结符）之间的优先关系。算符优先分析法的关键是对一个给定文法G，人为地规定其算符的优先顺序，即给出优先级别和同一个级别中的结合性质，算符间的优先关系表示与简单优先关系的表示类似，其规定如下：\n7/22/202168《编译原理》冶金工业出版社编译原理——第四章a＜.b表示a的优先级低于b。a＝.b表示a的优先级等于b。a＞.b表示a的优先级高于b。但必须注意，这三个关系和数学中的＜、＝、＞是不同的，它们是有序的，也就是若有a∙＞b，不一定有b＜∙a。a＝∙b成立不一定有b＝∙a。\n7/22/202169《编译原理》冶金工业出版社编译原理——第四章下面给出一个表达式的文法为：E->E+E|E-E|E*E|E/E|EE|(E)|id可以对此表达式的文法按公认的计算顺序规定优先级和结合性如下：（1）优先级最高，遵循右结合。相当于＜.。（2）*和/优先级其次，服从左结合。相当于*.>*、*.>/、/.>*、/.>/。（3）+和-优先级最低，服从左结合。相当于+.>+、+.>-、-.>+、-.>-。（4）对‘(’和‘)’规定括号的优先性大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号。\n7/22/202170《编译原理》冶金工业出版社编译原理——第四章对于句子括号‘$’号规定与它相邻的任何运算符的优先性都比它大。此外，对运算对象的终结符Id其优先级最高。综上所述，可对表达式运算符的优先关系构造成如表4-8所示。\n7/22/202171《编译原理》冶金工业出版社编译原理——第四章表4-8算符优先关系表+-*/id()$+.>.><.<.<.<.<..>.>-.>.><.<.<.<.<..>.>*.>.>.>.><.<.<..>.>/.>.>.>.><.<.<..>.>.>.>.>.><.<.<..>.>id.>.>.>.>.><.<..>.>(<.<.<.<.<.<.<.=.).>.>.>.>.>.>.>$<.<.<.<.<.<.<.\n7/22/202172《编译原理》冶金工业出版社编译原理——第四章4.6.1算符优先文法的定义设有一文法G，如果G中没有形如A->…BC…的产生式，其中B和C为非终结符，则称G为算符文法，也称OG文法。算符文法有如下两个性质：（1）在算符文法中任何句型都不包含两个相邻的非终结符。（2）如果Ab或(bA)出现在算符文法的句型中，其中AN，bT，则中任何含b的短语必含有A。\n7/22/202173《编译原理》冶金工业出版社编译原理——第四章4.6.1算符优先文法的定义设G是一个算符文法，a和b是任意两个终结符，A、B、C是非终结符，算符优先关系=.、<.、.>定义如下：（1）a=.b当且仅当G中含有形如A->…ab…或A->…aBb…的产生式。（2）a<.b当且仅当G中含有形如A->…aB…的产生式，且B=>+b…或B=>+Cb…。（3）a.>b当且仅当G中含有形如A->…Bb…的产生式，且B=>+…a或B=>+…aC。\n7/22/202174《编译原理》冶金工业出版社编译原理——第四章设有一不含ε产生式的算符文法G，如果对任意两个终结符对a、b之间至多只有＜、＞和＝三种关系的一种成立，则称G是一个算符优先文法（OperatorPrecedenceGrammmar），即OPG文法。\n7/22/202175《编译原理》冶金工业出版社编译原理——第四章4.6.2算符优先关系表的构造FIRSTVT(P)={a|P=>+a…或P=>+Qa…，aVT而QVN}LASTVT(P)={a|P=>+…a或P=>+…aQ，aVT而QVN}按其定义，我们可用下面两条规则来构造集合FIRSTVT(P)：（1）若有产生式P->a…或P->Qa…，则aFIRSTVT(P);（2）若有aFIRSTVT(Q)，且有产生式P->Q…，则aFIRSTVT(P);按其定义，我们可用下面两条规则来构造集合LASTVT(P)：（1）若有产生式P->…a或P->…aQ，则aLASTVT(P);（2）若有aLASTVT(Q)，且有产生式P->…Q，则aLASTVT(P);\n7/22/202176《编译原理》冶金工业出版社编译原理——第四章4.6.2算符优先关系表的构造1.可直接查看产生式的右部，对形如产生式：A→…ab…A→…aBb…则有a＝∙b2.求出每个非终结符B的FIRSTVT(B)，对形如产生式：A→…aB…，对每一b∈FIRSTVT(B)则有a＜∙b。3.计算每个非终结符B的LASTVT(B)，对形如产生式：A→…Bb…，对每一a∈LASTVT(B)则有a∙＞b。\n7/22/202177《编译原理》冶金工业出版社编译原理——第四章表4-9表达式文法算符优先关系表+*id()$+.><.<.<.<..>.>*.>.><.<.<..>.>.>.><.<.<..>.>id.>.>.>.>.>(<.<.<.<.<.=.).>.>.>.>.>$<.<.<.<.<.=.\n7/22/202178《编译原理》冶金工业出版社编译原理——第四章4.6.3算符优先分析算法的设计由算符文法的性质，可以知道算符文法的任何一个句型应为如下形式：N1a1N2a2…NnanNn+1，其中Ni(1aj+1\n7/22/202179《编译原理》冶金工业出版社编译原理——第四章算符优先文法在归约过程中只考虑终结符之间的优先关系确定句柄，而与非终结符无关，只需知道把当前句柄归约为某一非终结符，不必知道该非终结符的名字是什么。\n7/22/202180《编译原理》冶金工业出版社编译原理——第四章设有文法G，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他素短语。最左边的素短语称最左素短语。一个算符优先文法的最左素短语满足如下条件：ai-1<.ai=.ai+1=…=.aj-1=.aj.>aj+1\n7/22/202181《编译原理》冶金工业出版社编译原理——第四章【算法4-8】算符优先分析算法。输入：输入字符串和优先关系表。输出：如果是一个句子，则输出一个分析树架子，它的所有内结点均由占位非终结符E来标柱；否则，指出错误。方法：初始时，栈中放入$，输入缓冲区放入$。为了进行语法分析，执行下面的程序：\n7/22/202182《编译原理》冶金工业出版社编译原理——第四章令ip指向$的第一个符号；Repeatforeverif$在栈顶而且ip指向$thenreturnelsebegin令a是栈中最上面的终结符，而b是ip所指向的符号；ifa<.b或a=.bthenbegin将b压入栈中；ip指向下一个输入符号；endelseifa.>bthenrepeat从栈中弹出符号Until栈顶终结符与最近弹出的终结符之间满足<.elseerror()end\n7/22/202183《编译原理》冶金工业出版社编译原理——第四章4.6.4优先函数的构造定义两个优先函数f和g，它们把终结符映射为整数。对于符号a和b，选择f和g以满足：（1）f(a)g(b)，如果a.>b。\n7/22/202184《编译原理》冶金工业出版社编译原理——第四章【算法4-9】优先函数的构造。输入：算符优先表。输出：表示输入矩阵的优先函数，或指出它不存在。方法：（1）为每个终结符a或$创建符号fa和ga。画一张以所有符号fa和ga为结点的有向图。对任意的a和b，如果a>=b，那么，就从fa画一箭弧至gb；如果a<=b，就画一条从gb到fa的箭弧。（2）对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点（包括出发结点自身在内）的个数。赋予fa的数作为f(a)，赋予gb的数作为g(b)。（3）检查所构造出来的函数f和g，看它们同原来的关系表是否有矛盾。如果没有矛盾，则f和g就是所要的优先函数。如果有矛盾，那么，就不存在优先函数。\n7/22/202185《编译原理》冶金工业出版社编译原理——第四章表4-13算符优先关系id+*$id.>.>.>+<..><..>*<..>.>.>$<.<.<.\n7/22/202186《编译原理》冶金工业出版社编译原理——第四章4.6.5算符优先分析中的错误恢复错误处理可有两种：1.归约时的错误处理2.处理移动归约错误\n7/22/202187《编译原理》冶金工业出版社编译原理——第四章4.6.6算符优先分析法的局限性由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。通常一个适用语言的文法也很难满足算符优先文法的条件，因而致使算符优先分析法仅适用于表达式的语法分析。\n7/22/202188《编译原理》冶金工业出版社编译原理——第四章4.7LR语法分析器本节将提出一种有效的、自下而上的语法分析技术，它能适用于一大类上下文无关文法的分析，这种技术叫做LR(k)分析，L指大是从左向右扫描输入，R指的是构造最右推导的逆，k指的是在决定分析动作时向前看的符号个数。(k)省略时，表示k是1。\n7/22/202189《编译原理》冶金工业出版社编译原理——第四章LR分析器优点：（1）LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。（2）LR分析方法是已知的最一般的无回溯移动归约方法，它能够和其他移动归约方法一样有效地实现。（3）LR方法能分析的文法类是预测分析法能分析的文法类的真超集。（4）LR分析器能及时察觉语法错误，快到自左向右扫描输入的最大可能。\n7/22/202190《编译原理》冶金工业出版社编译原理——第四章这种分析方法的主要缺点是：对典型的程序设计语言文法，手工构造LR分析器的工作量太大，因而需要专门的工具——LR分析器的生成器。有了这样的生成器，只要写出上下文无关文法，就可以用它自动产生该文法的分析器。如果文法二义或有其他难以自左向右分析的结构，分析器的生成器能定位这些结构，并向编译器的设计者报告这些情况。在讨论LR分析算法之后，提出构造LR分析表的三种技术。第一种方法叫做简单的LR方法（简称SLR），它最容易实现，但功能最弱。对某些文法，用其他两种方法能成功地产生分析表，但用它都会失败。第二种方法称为规范的LR方法，它功能最强，代价也最高。第三种方法叫做向前看的LR方法（简称LALR），它的功能和代价处于前两者之间，LALR方法可用于大多数程序设计语言的文法，它可以高效地实现。\n7/22/202191《编译原理》冶金工业出版社编译原理——第四章4.7.1LR语法分析算法LR语法分析器模型\n7/22/202192《编译原理》冶金工业出版社编译原理——第四章LR分析器的模型如上图所示，它包括输入、输出、栈、驱动程序和包含动作和转移两部分的分析表。驱动程序对所有的LR分析器都一样，不同的分析器仅分析表不同。分析程序每次从输入缓冲区读一个符号，它使用栈，存储形如s0X1s1X2s2…Xmsm的串，其中sm在栈顶，Xi是文法符号，si是状态符号，状态符号概括了栈中它下面的部分所包含的信息。栈顶的状态符号和当前的输入符号用来检索分析表，以决定移动归约分析的动作。实际实现时，文法符号不必出现在栈里，不过下面的讨论中总是包含它们，以帮助解释LR分析器的行为。\n7/22/202193《编译原理》冶金工业出版社编译原理——第四章分析表由动作函数action和转移函数goto两部分组成。驱动程序LR分析器的程序的行为是：它根据栈顶当前的状态sm和当前的输入符号ai访问action[sm,ai]，它可能的4个值如下：（1）移进s，其中s是一个状态。（2）按文法产生式A->归约。（3）接受（4）出错。LR分析器的格局是二元组，它的第一个成分是栈的内容，第二个成分是尚未接收的输入：（s0X1s1X2s2…Xmsm，aiai+1…an$）这个格局代表右句型：X1X2…Xmsmaiai+1…an从这里可以看出，它本质上和一般的移动归约分析器是一样的，只是栈中状态是新出现的。\n7/22/202194《编译原理》冶金工业出版社编译原理——第四章分析器的下一个动作是根据栈顶当前的状态sm和当前的输入符号ai访问分析表的条目action[sm,ai]，4种不同的移动引起的格局变化如下：（1）如果action[sm,ai]=移进s，分析器执行移进动作，进入格局：（s0X1s1X2s2…Xmsmais，ai+1…an$）这里，分析器把当前输入符号v和下一个状态s进栈，s=goto[sm,ai]；ai+1成为当前输入符号。（2）如果action[sm,ai]=归约A->，那么分析器执行归约动作，进入格局：（s0X1s1X2s2…Xm-rsm-rAs，aiai+1…an$）\n7/22/202195《编译原理》冶金工业出版社编译原理——第四章其中，s=goto[sm-r,A]；r是的长度。这里，分析器首先从栈中弹出2r个符号，分别为r个状态符号和r个文法符号，这些文法符号刚好匹配产生式右部A，这时暴露出状态sm-r，然后把产生式左部的符号A和goto[sm-r,A]的状态s推入栈。在归约动作时，当前输入符号没有改变。LR分析器的输出由归约时执行与归约产生式有关的语义动作产生，现在，暂且认为输出就是打印归约产生式。（3）如果action[sm,ai]=接受，分析器完成。（4）如果action[sm,ai]=出错，分析器发现错误，调用错误恢复例程。\n7/22/202196《编译原理》冶金工业出版社编译原理——第四章【算法4-10】LR分析算法。输入：LR分析表和输入字符串。输出：如果是一个句子，得到的自下而上分析，否则报错。方法：最初，初始状态s0在分析器的栈顶，$在输入缓冲区，然后分析器执行下面的程序，直到碰到接受或出错动作。\n7/22/202197《编译原理》冶金工业出版社令ip指向$的第一个符号；Repeatforeverbegin令s是栈顶的状态，a是ip所指向的符号；ifaction[s,a]=“移进状态s’进栈”thenbegin把a和s’依次压入栈顶；让ip指向下一个输入符号endelseifaction[s,a]=“按文法产生式A->进行归约”thenbegin从栈顶弹出2*||个符号；令s’是现在的栈顶状态；把A和goto[s’,A]依次压入栈；endelseifaction[s,a]=“接受”thenreturnelseerror()end\n7/22/202198《编译原理》冶金工业出版社编译原理——第四章表4-17表达式文法的分析表状态动作转移id+*()$ETF0s5s4123s6accr2s7r2r2r4r4r4r4s5s4823r6r6r6r6s5s493s5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r5\n7/22/202199《编译原理》冶金工业出版社编译原理——第四章各类动作的含义是：（1）si表示移进，把当前输入符和状态i压进栈。（2）rj表示按第j个产生式进行归约。（3）acc表示接受。（4）空白表示出错。\n7/22/2021100《编译原理》冶金工业出版社编译原理——第四章4.7.2LR文法一个文法，如果能为它构造出LR分析表，且表的条目都惟一，就说它是LR文法。典型的程序设计语言的结构一般都是LR的。\n7/22/2021101《编译原理》冶金工业出版社编译原理——第四章对于LR(k)文法，要求在看见了产生式右部推导出的所有东西和k个向前看的符号后，能够识别产生式右部的出现。这个要求远不如LL(k)那样严格，LL(k)文法要求在看见了右部推出的前k个符号后就识别所使用的产生式，所以LR文法比LL文法能描述更多的语言。\n7/22/2021102《编译原理》冶金工业出版社编译原理——第四章4.7.3构造SLR语法分析表文法G的LR(0)项目（简称项目）是在右部的某个地方加点的产生式。一族LR(0)项目集合称做规范的LR(0)族，它提供了构造SLR分析表的基础。如果文法G的开始符号是S，那么G的拓广文法G’是在G的基础上增加了新的开始符号S’和产生式S’->S。新产生式的目的是用来指示分析器什么时候它应该停止分析和宣告接受输入，也就是当且仅当分析器执行归约S’->S时，意味着分析成功。\n7/22/2021103《编译原理》冶金工业出版社编译原理——第四章如果I是文法G的项目集，那么closure(I)是由下面两条规则从I构造的项目集：（1）初始时，I的每个项目都加入closure(I)。（2）如果A→a∙Bβ在closure(I)中，且B→γ是产生式，那么如果B→∙γ不在closure(I)中，就把它加入。运用这条规则，直到没有更多的项目可加入closure(I)为止。\n7/22/2021104《编译原理》冶金工业出版社编译原理——第四章函数closure(I)可以用下面的程序来计算：functionclosure(I)beginj:=I;repeatforJ的每个项目A->a∙Bβ和G的每个产生式B→γ，如果B→∙γ不在J中do把B→∙γ加入J；until没有新项目可加入J；returnJend\n7/22/2021105《编译原理》冶金工业出版社编译原理——第四章可以把感兴趣的项目分成两类：（1）核心项目：初始项S’->S和所有点不在左端的项目。（2）非核心项目：点在左端的非初始项目。\n7/22/2021106《编译原理》冶金工业出版社编译原理——第四章goto(I,X)定义为所有项目集[A→αX∙β]（[A→α∙Xβ]在I中）的闭包。直观上讲，如果I是对某个活前缀γ的有效项目集，那么goto(I,X)是对活前缀γX有效的项目集。\n7/22/2021107《编译原理》冶金工业出版社编译原理——第四章现在给出拓广文法G’的规范LR(0)项目集族的构造算法，如下所示：procedureitems(G’)beginC:={closure({[S’->.S]})};repeatforC的每个项目集I和每个文法符号X若goto(I,X)非空且不在C中do把goto(I,X)加入C中until没有更多的项目可以加入Cend\n7/22/2021108《编译原理》冶金工业出版社编译原理——第四章【算法4-11】构造SLR分析表输入：拓广的文法G。输出：G’的SLR分析表函数action和goto。方法：（1）构造C={I0,I1,…,In}，即G’的LR(0)项目集规范族。（2）状态I从Ii构造，它的分析动作以下确定：1）如果[A→α∙aβ]在Ii中，并且goto(Ii,a)=Ij，那么置action[I,a]为sj，其含义是把a和状态j移进栈。这里，a必须是终结符。\n7/22/2021编译原理——第四章2）如果[A→α∙]在Ii中，那么对FOLLOW(A)中的所有a，置action(I,a)=rj，j是产生式A→α的编号。这个动作的意思是按产生式A→α归约。这里，A不能是S’。3）如果[S’->S]在Ii中，那么置action[I,$]为acc，表示接受。（3）对所有的非终结符A，使用下面的规则构造状态I的转移：如果goto(Ii,a)=Ij，那么goto(I,A)=j。（4）不能由规则（2）和规则（3）定义的条目都置为出错。（5）分析器的初始状态是包含[S’->S.]的项目集对应的状态。\n7/22/2021110《编译原理》冶金工业出版社编译原理——第四章【算法4-12】构造LR(1)项目集。输入：拓广文法G’。输出：LR(1)项目集，它们是对G’的一个或多个活前缀有效的项目集。方法：构造项目集的过程closure和goto及主例程items如下：\n7/22/2021111《编译原理》冶金工业出版社编译原理——第四章functionclosure(I);beginrepeatforI中的每个项目[A->∙Bβ,a]，G’中的每个产生式B→γ和FIRST(βa)的每个终结符b，如果[B→∙γ,b]不在I中do把[B→∙γ,b]加入I；until没有新项目可加入I；returnIend\n7/22/2021112《编译原理》冶金工业出版社编译原理——第四章functiongoto(I,X);begin对于I中的每个项目[A->∙Bβ,a]，令J是项目[A->B.β,a]的集合；returnclosure(J)end;\n7/22/2021113《编译原理》冶金工业出版社编译原理——第四章procedureitems(G’)beginC:={closure({[S’->.S,$]})};repeatforC的每个项目集I和每个文法符号X若goto(I,X)非空且不在C中do把goto(I,X)加入C中until没有更多的项目可以加入Cend\n7/22/2021114《编译原理》冶金工业出版社编译原理——第四章【算法4-13】构造规范的LR分析表。输入：拓广文法G’。输出：文法G’的规范LR分析的函数action和goto。方法：（1）构造C={I0,I1,…,In}，即G’的LR(1)项目集规范族。（2）状态I从Ii构造，它的分析动作以下确定：1）如果[A→α∙aβ,b]在Ii中，并且goto(Ii,a)=Ij，那么置action[I,a]为sj，其含义是把a和状态j移进栈。这里，a必须是终结符。\n7/22/2021编译原理——第四章2）如果[A→α∙,a]在Ii中且AS’，那么置action(I,a)=rj。其中，j是产生式A→α的序号。3）如果[S’->S.,$]在Ii中，那么置action[I,$]为acc，表示接受。（3）对所有的非终结符A，使用下面的规则构造状态I的转移：如果goto(Ii,A)=Ij，那么goto(I,A)=j。（4）不能由规则（2）和规则（3）定义的条目都置为出错。（5）分析器的初始状态是包含[S’->S.,$]的项目集对应的状态。\n7/22/2021116《编译原理》冶金工业出版社编译原理——第四章4.7.5构造LALR语法分析表【算法4-14】一个简易但耗空间的LALR表构造法。输入：拓广文法G’。输出：文法G’的LALR分析表的函数action和goto。方法：（1）构造C={I0,I1,…,In}，即G’的LR(1)项目集规范族。（2）对出现在LR(1)项目集中的每个心，找出所有与之同心的项目集，用它们的并集代替它们。\n7/22/2021117《编译原理》冶金工业出版社编译原理——第四章（3）令C’={J0,J1,…,Jm}j合并后的LR(1)项目集。状态I的动作以与【算法4-13】同样的方式从Ji构造。（4）goto表的构造如下：如果J是一个或多个LR(1)项目集的并，即J=I0UI1U…UIm，那么goto(I1,X)，goto(I2,X)，…，goto(Im,X)也同心，因为I0,I1,…，Im都同心，记K为所有与goto(I1,X)同心的项目集的并，那么goto(J,X)=K。\n7/22/2021118《编译原理》冶金工业出版社编译原理——第四章【算法4-15】确定搜索符。输入：一个LR(0)项目集I的核K和一个文法符号X。输出：对于goto(I,X)中的核项目，由I中的项目自生的搜索符，以及对于I中的项目，搜索符从这些项目将会传播goto(I,X)中的核项目中。方法：算法如下，它使用一个哑搜索符#来检测出现超前扫描符号传播的情形。\n7/22/2021119《编译原理》冶金工业出版社编译原理——第四章ForK中每一项B->.dobeginJ’:={closure({[B->.,#]})};if[A→αX∙β,a]J’其中a不是#then对于goto(I,X)中的核项目A→αX∙β，搜索符a是自生的；if[A→αX∙β,#]J’then搜索符从I中的B->.传播到goto(I,X)中的A→αX∙βend\n7/22/2021120《编译原理》冶金工业出版社编译原理——第四章【算法4-16】计算LALR(1)项目集族的核。输入：拓广文法G’。输出：文法G’的LALR(1)项目集族的核。方法：（1）构造G的LR(0)项目集和核。（2）对每个LR(0)项目集的核和文法符号X应用算法【算法4-15】，确定出哪些搜索符对于goto(I,X)中的核项目是自生的，并确定出从哪些I中的项目出发搜索符可以传播到goto(I,X)中的核项目中去。\n7/22/2021121《编译原理》冶金工业出版社编译原理——第四章（3）对每个项目集的核项目，初始化一个表，使之给出与之相联系的各个搜索符。开始时，与每一个项目相联系的搜索符仅是那些在（2）中确定的自生搜索符。（4）反复遍历所有集合中的核项目。当访问一个项目I时，利用（2）中所建立的信息来查看I能将它的搜索符传播到哪些核项目。把I的当前搜索符集合附加到已经与相相关联的各个项目中去，即附加到已已将其搜索符传播到达的那些项目中去。继续遍历核项目，直到没有新的搜索符被传播为止。\n7/22/2021122《编译原理》冶金工业出版社编译原理——第四章4.7.7LR语法分析表的压缩为每个状态的动作创建一个列表可进一步提高空间的利用率，但要以轻微降低语法分析器的速度为代价。列表由（终结符，动作）对组成。\n7/22/2021123《编译原理》冶金工业出版社编译原理——第四章4.9语法分析器的生成器本节介绍分析器的生成器如何用来帮助进行编译器前端的构造。将LALR分析器的生成器YACC作为讨论的基础，因为它实现了前两节讨论的许多概念，并且广泛使用。\n7/22/2021124《编译原理》冶金工业出版社编译原理——第四章小结本章重点掌握的内容有：语法分析的任务：按照文法，从源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。文法二义的本质，在产生句子的过程中某些直接推导有多于一种选择，从而使得下一步分析不确定。\n7/22/2021125《编译原理》冶金工业出版社编译原理——第四章自顶而下分析的基本思想：对于任何一个输入序列，从文法的开始符号开始，进行最左推导，直到得到一个合法句子或者发现一个非法结构。构造分析表的过程可以分为两步走：首先根据文法构造两个集合，FIRST集合与FOLLOW集合；然后根据两个集合构造预测分析表。构造LR分析表的3种技术：第一种方法叫做简单的LR方法（简称SLR）；第二种方法称为规范的LR方法；第三种方法叫做向前看的LR方法（简称LALR）。