资源描述：
《语法分析程序2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、语法分析和语法分析程序4.1重点和难点4.1.1语法分析程序的功能语法分析程序乂简称称为分析器，它以单词串形式的源程序作为输入或分析的对象，其基本任务是：根据程序设计语言的语法规则（即定义该语言的前后文无关文法），分析源程序的语法结构，即分析如何由这些单词组成该源程序的各种语法成分（如下标变量、函数、各种表达式、各程语句等等），并在分析过程屮进行语法正确性检查，产生内部形式的中间代码，供编译程序后续阶段处理。日前，已存在许多语法分析方面的方法，但就产生语法树的方向而言，可大致把它们分为自顶向卜•分析和自底向上分析
2、两大类。4.1.2自顶向下的语法分析所谓口顶向下的语法分析，是指对于给定输入串w,试图为其构造一个从文法开始符号到w的最左推导Snw,或为w自上而下地构造一棵以S为根结点的语法树。如果这一尝试得到成功，则证明w是相应文法的一个句子；反之，则不是。在进行自顶向下的语法分析时，通常冇下列两个障碍须加以解决：（1）由于采取了最左推导，故当相应方法法G中含有左递归的非终结符号时，便会使语法分析过程陷入循环不已的状况。（2）采用最左推导以实现对符号串w的匹配，实际上是一个用文法产生式的诸候选式反复进行试探的过程，这势必会出
3、现大量的冋溯，从而导致语法分析效率的大幅度下降。因此，欲实现自顶向下的语法分析，其首要任务是改造程序设计语言的文法，以消除其中的左递归和避免回溯的出现。1.消除文法的左递归如果一个文法G[S]=（Vn,Vt,P,S沖的A■产生式具有如下的形式：A-*Au）IAa2ZTAan
4、p）
5、p…IBm其中每个Bi均不以A打头，则A是一个直接左递归的非终结符号。为消除此种左递归，nJ引入一个新的非终结符号A，,并将上述A・产牛式改第为A-*P1A,IP2A,l-l3mA,A'—a]A'la2A'l・・・la*A'即可。如果一
6、个非终结符号A是经多步推导而出现的左递归，则可对相关产生式作代入操作，将A-产生式化成直接左递归的，再按上面的方法将左递归消除。下面，再给种通过将文法G=(Vn,Vt，P,S)表示成矩阵形式而一次消除G的全部左递归的方法。首先,令VN={XpX2,…，Xn},且对G的每个产生式Xi—Y
7、lY2丨…I丫m(i=l,2,•••,!!)可将其写成Xi=Xiah+X2a2汁…+Xnani+B,(i=l,2,…,n)其中：“二”和“+”分别代表原产生式中的“一”和“I”；若原产生式中不含以务开头的候选式，则相应的Bi是原产
8、牛式中以终结符号开头的诸候选式Z“和”。于是，文法G的诸产生式便可写成如下的矩阵方程x1,x2,-.,xn)=(x1,x2,-,xnalla12…alna21••■a22•••…a2n••••••anlan2…ann+(卩1’卩2,…，卩n)X=AB+B此方程有形如X=BA*的最小解，由于A*=I+AA若令A=Z=znZ21InZnnZX=BZZ=I+AZ则有其中£(
9、)(
10、)•••(
11、)(
12、)£(
13、)•••(
14、)•••••••••••(
15、)(
16、)(]).••£将上述两矩阵式写成分量式，便得到一组新的产生式,设
17、它们所构成的文法为G则冇L(G^)=L(G)O另外，由于向量B的各元素的每一项均是以终结符号打头的符号串，故矩阵式X=BZ相应的各产生式不含左递归的非终结符号；与矩阵式Z=I+AZ相应的各产生式显然也不是左递归的。也就是说，通过两述两矩阵式，我们已消除了原文法G的一切左递归。1.消除回溯对于给定的文法G[S]=(Vn,Vt,P,S)和给定的输入符号串¥之曲・・玄(ai$VT),为判断w是否为L(G)中的句子，现试图为w建立一个从S岀发的最左推导，设经过若干步推导后，得到S=>W]A0AEVnBW(VnUVt)
18、其中w1=a1a2-ai.1,B
19、Jw的一个前缀w】已从上面的推导得到匹配，现需对AB继续进行推导，以期使余下的输入串昭+
20、••伽也获得匹配。此时应使用A-产牛式进行推导，现设G中的全部A-产生式为A-*YilY2丨…IYm且对这m个候选式Yk(lWkWm),要么全部TkB均不能推出以外打头的符号串(此时w《L(G)),要么若存在一个Yj,能使YjB推导出以缶打头的符号串，而其余的SB(lWkWm,kHj)则不能推出，这样，上述推导过程在产牛式选择上的试探将可避免。如果文法G小的全部产生式均满足上述要求，则消除冋
21、溯的问题口然就解决了。可见，要实现无冋溯的自顶向下语法分析，对相应文法须有一定的要求。为导出文法应满足的条件，需定义候选式y的终结首符集和非终结符号A的后继终结符号集如F：FIRST(Y)={alY，且aevT,Sev'}FOLLOW(A)={alS#^>VuAa8,且aeVTU{#};u,p8FV+)于是，对于一个己化简的非左递归文法G,在进行自顶向卜•语法分析时，不出
