学习用递归下降算法和YACC工具

《学习用递归下降算法和YACC工具》由会员分享，可在线阅读，更多相关《学习用递归下降算法和YACC工具（11页珍藏版）》请在装配图网上搜索。

1、实验三 学习用递归下降算法和 YACC工具实现 TINY 语言的语法分析器一、实验目的：通过本次实验,进一步加深对递归下降算法与抽象语法树的理解,学习程序设计语言的语法分析器的手工编程方法.二、实验任务：仔细阅读并测试 TINY 语言的语法分析器的相关程序,同时复习递归下降算法与抽象语法 树的相关理论.三、实验内容： 1改写文法与画语法图；2TINY语言的抽象语法树节点的数据类型的定义与说明； 3 TINY 语言的语法分析器源程序的阅读与注释；4TINY语言的语法分析器的 YACC俞入文件阅读与注释；5编译并测试TINY语言的语法分析器；四、实验分析及解答： 1改写文法与画语法图：首先将TIN

2、Y语言的BNF文法参见?编译原理与实践?第 3章改写成EBNF文法,然 后画出相应的语法图.榨序清单3-1 BNF中的TINY的文法rwfram * j；阿卜$珂*曲氓;sjnf/trwu | Ktaiemenr* if !rfml j rrfwat num | ouiH .rtmZ | rttui-tmr wmt-ntnt if-stmt -* if rxp then itmt-urfftencr andI if rv than sugtrtiwv *1 ttmt-squenre ad tvjvaf rrmr t repeat stmt xcquenct until ejcp aigrtp

3、ifrmadd&p * | -irm * 加rm mulnp farm尸 Jaetor muit/p * * | / fanar t ( exp ) | mwlwr I改写后的EBNR1序,如下:pro?xanstmt-se quence*sseqia&ne as-ta.ejnerit ; s + atemeni:ztat cincn 七(eKp)診 Ijbl t- S e i-LLLei ice (end) 2|辻 Cexr) stHit-seuenceXelse stmt-seqaence (end)/*lse可选结构用万括号*reneat_5tiMt repeat stm.t-seque

4、n.ee until exr*- assiJgn-strft+ idtn-tii#r sirp*-1 roadj-tint read identificarR wx ite-s IjilLwi i to exu*-1exp simple-exp cow ar i si on-op simple-exp|匚 ciiyp aziwicwi cip siiLple=exp ternEaddo simple-exp/W术运章的结合+Jsddop a.otor mulc fcmtoi算?F：运算的结合*jnul on *. * | 2factor * (exp)|numtexIidentifier1文法

5、规那么:exp simple_exp conwaxision-op simpls-BXp I siJhple-Bitp compu if ienop I =*raTii1 iTiit ii,Viriar,ir,Tsi,Fii iTTr*/w术运算的结合运肖的结合円3iplff-exp texm addop ffirapl-exp 斗日gp +|termtactor( nuJQK factorHiulop 一. *1/*f ac-tor (exp ) liambcr | i den-tifrer 用语法图表示如下:的语法分析树.I(2) TINY语言的抽象语法树节点的数据类型的定义与说明:裡岸淆

6、单吳2布点的匚理闕当把语法分析器作为一遍时,抽象语法树是作为语法分析器的输出而定义的“简化版现在需要将治法树结构的描述用图形表忌II来,并14画岀例如程序的涪法佻 为门故到这 一点,我11使川矩形柜表示语句节点,用圆形框或怖圆形柜表示表达式节点.谄句或表达式的 类型用框中的标记表示,额外的属性在括号中也列出来了.属件指针画在节点惟的右边,而子 描什那么画住世的下面.我们还在图小用二角形表示额外的IE指定的树结构,：It中用点线表示可 能出现也可能不出现的结构.语句序列由同属域连接潜在的子树由点线和三角形表示.贝IJ 该图如下:1111 if语句带冇3个可能的孩了如下所示.else-partre

7、peat 旬有两个孩子.第1个杲表示循环体的语旬序列,第2个足-个测试表达式:assign iSf.J有 个表示其值足被赋予的表达式的孩了彼赋予的变虽名保存在语旬芳点屮:assign ()expression顷檢语句也育一个孩子,它表示要写岀值的表达式:算殺桓达式自鮒个孩rt它们表六在操作数表达式利右操作数表达武:其他所有的节点(Z吾仞、标识符表达式和常量表达式)秤是叶子节点.(3) TINY语言的语法分析器源程序的阅读与注释：阅读源程序PARSE.H PARSE.C以及相关程序,并给出必要的中文注释.头文件PARSE.H:/*定义TIN丫的语法分析函数头文件*/#ifndef _PARSE_

8、H_#define _PARSE_H_TreeNode * parse( void );/*声明语法树节点类型的语法分析函数*/#endif源文件PARSE.C局部代码注释说明：/*字符匹配函数*/static void match(TokenType expected) if (token = expected) token = getToken();else /*岀错时,没有消耗掉当前记号 */syntaxError( unexpected token - );printToken(token,tokenString);fprintf(listing,);TreeNode * stmt_s

9、equence( void ) TreeNode * t = statement(); /* 指向语法树根节点 */TreeNode * p = t; /*指向第一个节点,循环需要对非follow(stmt_sequence)中的记号进行循环*/while (token!=ENDFILE) & (token!=END) &(token!=ELSE) & (token!=UNTIL) TreeNode * q; match(SEMI);q = statement();if (q!=NULL) if (t=NULL) t = p = q; /* 假设根节点为空,回到第一个节点 */ else /*

10、 now p cannot be NULL either */ p-sibling = q;p = q;return t;/* 语句函数 */TreeNode * statement( void ) TreeNode * t = NULL;switch (token) case IF : t = if_stmt(); break ;case REPEAT : t = repeat_stmt(); break ;case ID : t = assign_stmt(); break ;case READ : t = read_stmt(); break ;case WRITE : t = writ

11、e_stmt(); break ;default : syntaxError( unexpected token - );printToken(token,tokenString);token = getToken(); /* 消耗掉当前记号 */break ; /* end case */return t;/*if 语句函数 */TreeNode * if_stmt( void ) TreeNode * t = newStmtNode(IfK);match(IF); /* 消耗掉 if 记号 */if (t!=NULL) t-child0 = exp();match(THEN); /*检查T

12、HEN记号,没有那么出错*/if (t!=NULL) t-child1 = stmt_sequence();if (token=ELSE) match(ELSE);if (t!=NULL) t-child2 = stmt_sequence();match(END);return t; /* 返回 if 语句节点 */(4) TINY语言的语法分析器的YACC俞入文件阅读与注释：阅读源程序YACC/GLOBALS.H YACC/TINY.Y,中文注释局部/* EchoSource 二 TRUE causes the source program to+ te echoed 髦o the list

13、iiig file with line numbers* during pursing-/*EchaSflurce=True在解析泄程中会把源程序以帯行号的方式写入珈反件中*I jstem int EchoS:urea;/+ TracScm = TRUE caus tokwn inEcnrination to* printed to tha Li stiM fil a? wu五 toJcen is* recognized by the scaioier*/八艳拎描誥识别出的单1司符号的信息肓入到luting件中刃extern int TraceScui：/* Tr4eFarse = TRUE

14、?fcin*s th# syntax trss 讥 be* printed to the li it.irLj fil in lin&ri ltd form* (usin indents oy ckilSrn)/-/嗚语适钳以非纯性的方式写入即i玳5茨件中村extern int Tr&ceParse;3/* Trac电iknUy工直 s TRUE causes synbol tabl inserts* uid lookups to be： rep-orted to the listing il-用将异鹤符号完的插丸和萱栈揺作弄报告给口 E m茂件栋eiEt ern irit TraceArLa

15、lyze;il J* TracCoie - TEUE caus es c oMenta to b包 wri tten* to the TH 匚odg ile 丄 cod i s ggneratd*7J碣会唱已产生的colAllTM r皿文件柑芒xterrL ixit TraceCole ;J席 Error = TRUE prevents fur ther passes; i f an err or o ccuur s &astern ixit Erzrr :#en.di fHdefine YYPARSER /+ ffiYacc输出文件和其它文件区别开来+/A头文件*/ttinclude glo

16、bal s. hy#include util, h#include scan. httincliide parse, hdefine YTSTYPE TreeNode +stati c char 水 savedhTame; A for use in assignrnents 半/st at i c int savedLineNo, /* ditto +/static TreeNode 水 savedTree, /* stores syntax tree for later return */%)A定义单词符号Htoken IF THEN ELSE EMD REPEAT UNTIL READ W

17、RITEoken ID NUHtoken ASSIGN EQ LT PLUS MINUS TIMES OVER LPAREN RPAREN SEMItoken ERROR熾/*语法*/program : s*tmt_seq(5) 编译并测试TINY语言的语法分析器:SB 苣瑾気 C:Windows$ys.tem 3 2cmd.exeF: VTIlTYtiziy sample, tnym(Y COMPILATION： snplc.tnyDuildmg Symbol TableSymboil t&bla：畑iabX Name LocationLine Numbers用056910 10 11fact179912Ckeckizig Types.Type Checking Fini shed.