语法分析程序2
26页1、语法分析和语法分析程序4.1重点和难点4.1.1语法分析程序的功能语法分析程序乂简称称为分析器,它以单词串形式的源程序作为输入或分析的对象, 其基本任务是:根据程序设计语言的语法规则(即定义该语言的前厉文无关文法),分析 源程序的语法结构,即分析如何由这些单词纟fl成该源程序的各种语法成分(如下标变量、 函数、各种表达式、各程语句等等),并在分析过程中进行语法正确性检查,产生内部形 式的中间代码,供编译程序后续阶段处理。日前,已存在许多语法分析方面的方法,但就产生语法树的方向而言,可人致把它们 分为自顶向下分析和自底向上分析两人类。4.1.2自顶向下的语法分析所谓自顶向卜的语法分析,是指对于给定输入串w,试图为其构造一个从文法开始符 号到w的最左推导S n w,或为w自上而下地构造一棵以S为根结点的语法树。如果这 -尝试得到成功,则证明w是相应文法的一个句子;反Z,则不是。在进行白顶向下的语法分析时,通常有下列两个障碍须加以解决:(1)由于采取了最左推导,故当相应方法法G中含有左递归的非终结符号时,便会 使语法分析过程陷入循环不己的状况。(2)采用最左推导以实现对符号串w的匹配,实际上
2、杲一个用文法产生式的诸候选 式反复进行试探的过程,这势必会出现人量的冋溯,从而导致语法分析效率的大幅度下降。因此,欲实现白顶向下的语法分析,其首要任务是改造程序设计语言的文法,以消除 其中的左递归和避免冋溯的出现。1. 消除文法的左递归如果一个文法GS=(Vn, Vt, P, S)中的A产生式具有如下的形式:A-*A ci |IA a 2IIA aB il B 2II B m其中每个B i均不以A打头,则A是一个直接左递归的非终结符号。为消除此种左递归, 可引入一个新的非终结符号A,,并将上述A产生式改写为A-P1A,IP2A,l-l3mA,A-a 】AlgAITcinA即可。如果一个非终结符号A是经多步推导而出现的左递归,则可对相关产生式作代入操 作,将A产生式化成胃接左递归的,再按上面的方法将左递归消除。下面,再给出-种通过将文法G=(Vn, Vt, P, S)表示成矩阵形式而一次消除G的全部左递归的方法。 首先,令Vn=X, X2,,Xn),且对G的每个产生式Xjf Y |l Y 2I 丫 m(i=1,2,!)可将其写成Xi=Xi a 1 汁X2(I 2汁+Xna n汁Bi(i=
3、l,2,n)其中:“二”和“ + ”分别代表原产生式中的“一”和若原产生式中不含以Xj开头的 候选式,则相应的aji=(b; “是原产生式中以终结符号开头的诸候选式之“和”。于是, 文法G的诸产生式便可写成如下的矩阵方程X,X2,,XJ=(X,X2,Xalla12alna21 a22 a2n anlan2 ann+ |PpP2,Pn或X=AB+B此方程有形如X=BA*的最小解,由于A*=I+AA若令Z11Z12InZ21Z22Z2nZnlZn2Znn则有其中X=BZZ=I+AZe e e将上述两矩阵式写成分量式,便得到一纟fl新的产生式,设它们所构成的文法为G,,则有 L(GO=L(G)0另外,由于向量B的各元素的每一项均是以终结符号打头的符号串,故矩阵 式X=BZ相应的齐产生式不含左递归的非终结符号;与矩阵式Z=I+AZ相应的各产生式显 然也不是左递归的。也就是说,通过两述两矩阵式,我们L1消除了原文法G的一切左递归。2. 消除回溯对于给定的文法GS=(Vn, Vt, P, S)和给定的输入符号串w=a】a2an(aVT),为 判断w是否为L(G)中的句子,现试图为w建立一个从S出发
4、的最左推导,设经过若干步 推导后,得到S=”A0 AevN P e(VNUVT)* 其中wI=a1a2-ai.1,即w的一个前缀切已从上而的推导得到匹配,现需对A B继续进行推 导,以期使余下的输入$ aiai+1-an也获得匹配。此时应使用A产生式进行推导,现设G 中的全部A产生式为A-* Y |l Y 2卜诃 Y m且对这m个候选式Yk (lWkWm),要么全部Y k B均不能推岀以舛打头的符号串(此时 wEL(G),要么若存在一个Y”能使丫沖推导出以舛打头的符号串,而其余的丫汁(lWkWm, kHj)则不能推出,这样,上述推导过程在产生式选择上的试探将可避免. 如果文法G中的全部产生式均满足上述要求,则消除冋溯的问题白然就解决了。可见,要实现无冋溯的白顶向下语法分析,对相应文法须有一定的要求。为导出文法 应满足的条件,需定义候选式y的终结首符集和非终结符号A的后继终结符号集如K:FIRST(y)二al Y,且 aevT, WFOLLOW(A)=alS#=f a A a S ,且 aeVTU#); a , B eV*于是,对于一个己化简的非左递归文法G,在进行白顶向下语法分析时,不
《语法分析程序2》由会员gg****m分享,可在线阅读,更多相关《语法分析程序2》请在金锄头文库上搜索。
魔芋栽培及防病技术
黄土之上的人为地貌区思考
鸿海白瓜栽培技术
鲁科版高一化学必修一单元测试题全套及答案
鹿特丹规则论文
鲁人版高中语文必修一模块综合测评含解析
鱼馆开业营销策划方案和鸭丫特色玩具网上商城策划书汇编
高速电脑绣花机项目可行性研究报告
军民两用碳纤维复合材料项目计划书
黄州中学期中考试题
鲁棒故障诊断及容错控制方法研究贾克明
鸡肉调理品项目建议书
鲜花网店电子商务创业策划
内蒙古高三月考模拟地理试测试卷及答案解析
内江中考物理模拟试题三
龙湖景区管理存在问题及对策
龙诚金属制品有限公司产品标识和可追溯性控制程序
龙诚金属制品有限公司产品检验和试验状态控制程序
龙泉窑的发展简史
龙椒八号栽培技术要点
2024-04-18 4页
2024-04-18 2页
2024-04-18 2页
2024-04-18 2页
2024-04-18 5页
2024-04-18 2页
2024-04-18 4页
2024-04-18 3页
2024-04-18 2页
2024-04-18 2页