实验二编写语法分析程序.docx

《实验二编写语法分析程序.docx》由会员分享，可在线阅读，更多相关《实验二编写语法分析程序.docx（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、实验二编写语法分析程序2.1 实验类型设计型实验,6学时2.2 实验目的通过设计、编写、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词 序列进行语法检查和结构分析，掌握递归下降语法分析方法。2.3 背景知识递归下降分析程序的实现思想是：分析程序由一组子程序组成，每个子程序对应于一个 非终结符号。递归下降分析程序实现思想简单易懂，程序结构和文法产生式有直接的对应关 系，添加语义加工工作比较方便。每一个子程序的功能：选择正确的右部，扫描完相应的字符，产生式右部有非终结符号 时，调用该非终结符号对应的子程序来完成。自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能

2、推导 出待检查的符号串，分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生 时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。实现不带回溯的自顶向下分析，文法满足下述条件：(1)文法不含左递归(2)文法的任何一个非终结符A的各个产生式的右部符号串的FIRST集两两不相交，即：若有Af ai|ot2|届，贝1JFIRST (ai) A FIRST (为)=F (i # j，IWiJWn)(3)文法的任何一个非终结符A,若有Af ai|ct2|%且存在柒,有8eFIRST (%),则FIRST ( a j) A FOLLOW (A) = 6( i W j, j

3、=l,2,.,n )文法的左递归消除算法：要求无环路(形如A=+A的推导)和无 -产生式。1、把非终结符按某一顺序排序为A1,A2An o2、fbr(i=l;i=n;i+)fdr(j=l;jUxi|Ux2|.|Uxm|yi|y2|.|yn；其中：Xi在,y都不以U打头。一般形式直接左递归的消除：UyiU1y2U.|ynU，UX1U|X2U| |XmU|回溯的消除前提：文法不得含有左递归，可提左因子来消除回溯。递归下降分析程序的基本架构：先定义：变量：ch：当前符号； 函数：READ (ch)：读输入串下一符号;对于每个非终结符号U-ai|a2|an处理的方法如下：P (U)(ifcheFIRS

4、T(ai )then P(ai) 处理 al 的程序部分。else ifcheFIRST(a2 )then P(a2) 处理 a2 的程序部分。else ifcheFIRST(an )then P(an)else if ch FOLLO W(U)then return 处理空产生式情况。else error)对于每个右部0t=XlX2.Xn的处理架构如下：P(a)(P(X1 );处理XI的程序。P(X2 )；处理X2的程序。 P(Xn)；处理Xn的程序。)对于右部中的每个符号X1；如果Xi为终结符号：i*ch= a)READ (ch)对于终结符，直接将指针前调。elseen*or如果引为非终结

5、符号，直接调用相应的过程：P(Xi)o编写递归下降分析程序一般步骤：1)改写文法，消除二义性；2)消除左递归、提取左因子；3)求 FIRST 集、FOLLOW 集；4)检查是不是LL(1)文法，若不是LL(1),说明文法的复杂性超过自顶向下方法的分析能力5)直接根据产生式设计相应的程序2.4 实验内容1、语法规则本实验的TEST语言的语法规则如下：l):= 2):= | 3):=int ID;4):=| 85):= | |6): if () else 7):= while () 8):= fbr(;)9): :=write ;10):=read ID;1 l):= 12):=;|;13):=

6、lD=|14): :=|(|=|=|=|!=)15):=(+|-)16):=(*| /)17):=()|ID|NUM2、要求：根据递归下降分析方法，完成TEST语言的递归下降语法分析程序的构造，主要完成:1、改造文法，使之满足无回溯的递归下降分析条件，给出改写后的文法（写入实验报告）;2、编写递归下降分析程序；（将statement,，v expression 的程序流程图写入实验报告）3、测试编写的递归下降分析程序。（用实验一的输出作为本实验的测试输入）实验分析与思考1、TEST语言语法规则中哪些不满足无回溯的递归下降分析条件？你是怎么处理的？给出 你的处理方案。2、所有文法都可以改写为满足递归下降分析条件的文法吗？如果不能，请给出一个反例。3、改写文法有什么弊端？