语法分析器编译原理课程设计报告`

LL(1)语法分析器一、课程设计的目的通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析表的构造及分析过程的实现。二、课程设计的要求及其方法语法分析程序要求实现sample语言中几种最常见的、基本的语法单位的分析：算术表达式，逻辑表达式，赋值语句，if语句，for语句，while语句，repeat语句等，各个语法单位的定义如下： Sample语言的定义<字符>::=<字母>|<数字>|<界符><字母>::=a|b|c…|z|A|B|C…|Z<数字>::=0|1|2|3…|9<单界符>::=+|-|*|/|=|<|>|(|)|[|]|:\;|,|’|_|.单词集的定义(1)<单词集>::=<保留字>|<双界符>|<标识符>|<常数>|<单界符>(2)<保留字>::=and|array|begin|bool|call|case|case|char|const|do|dlse|end|false|for|if|input|integer|not|of|or|output|program|read|real|repeat|set|then|to|true|until|var|while|write (3)<双界符>::=/*|*/|<=|>=|<>|:= (4)<标识符>::=<字母>|<标识符><数字>|<标符><字母> (5)<常数>::=<整数>|<布尔常数>|<字符常数>|常数标识符>|<实数> (6)<整数>::=<数字>|<整数><数字> (7)<布尔常数>::=true|false (8)<字符常数>::=’除’以外的任意字符串’ (9)<常数标识符>::=<标识符> (10)<实数>::=<整数>.<整数>数据类型的定义(1)<简单类型>:==integer|bool|char|real表达式的定义 (1)<表达式>::=<算术表达式>|<逻辑表达式> (2)<算术表达式>::=<项>+-<算术表达式>|+-<项>|<项> (3)<项>:==<项>*<因子>|<项>/<因子>|<因子> (4)<因子>::=<算术量> (5)<算术量>::=<标识符>|<整数> (6)<逻辑表达式>::=<布尔项>or<逻辑表达式>|<布尔项> (7)<布尔项>::=<布尔因子>and<布尔项>|<布尔因子> (8)<布尔因子>::=<布尔量>|not<布尔因子> (9)<布尔量>::=<逻辑表达式>|<布尔常数>|<标识符>|<算术表达式><关系符><算术表达式> (10)<关系符>::=<|>|<>|<=|>=|=语句的定义 (1)<语句>::=<说明语句>|<执行语句> (2)<说明语句>::=<常数说明><变量说明> (3)<常量说明>::=const<常数定义>|ε (4)<常数定义>::=标识符=<常数>;<常数定义>|标识符=<常数>;<变量说明>::=var<变量定义>|ε<变量定义>::=<标识符表>:<类型>;|<标识符表>:<类型>;<变量定义><标识符表>::=<标识符>,<标识符表>|<标识符><执行语句>::=<简单句>|<结构句><简单句>::=<赋值句><赋值句>::=<变量>:=<表达式><变量>::=<标识符><结构语句>::=<复合句>|<if语句>|<while语句>|<for语句>|<repeat语句><复合句>::=begin<语句表>end<语句表>::=<执行句>;<语句表>|<执行句><if语句>::=if<布尔表达式>then<执行句><if语句>::=if<布尔表达式>then<执行句1>else<执行句2><while语句>::=while<布尔表达式>do<执行句><for语句>::=for<标识符>::=<算术表达式1>to<算术表达式2>do<执行句><repeat语句>::=repeat<执行句>until<布尔表达式>程序定义(1)<程序>::=program<标识符>;<分程序> (2)<分程序>::=<常量说明><变量说明><复合句>本次语法分析器课程设计采用LL（1）自顶向下析法来实现。三、课程设计的内容根据下面LL(1)文法，对输入串w:(i+i)*(i+i)+i*i进行LL(1)分析,要求如下：先建立LL（1）分析表；分析输入串，判断是否是语法上正确的句子，若正确则输出整个自顶向下分析过程。若是在语法上不正确则报错。四、实现原理语法分析的任务是在词法分析的基础上，主要任务是接受词法分析程序识别出来的单词符号,判断它们是否由某种语言的文法产生,即判断被识别符号串是否为某语法成分.除此之外,还要进行语法检查,为后面的语义分析和代码生成做准备.根据语言的语法规则，把单词符号串分解成各类语法范畴。实现Sample语言中几种最常见的,基本的语法单位的分析:算术表达式.逻辑表达式,赋执语句,IF语句,FOR语句,WHLIE语句REPEAT语句等:通过语法分析，可以确定整个输入串是否构成语法上正确的“程序”。语法分析阶段遵循的是语言的语法规则。该语法分析器的主要组成即常量说明的函数（const），变量说明的函数（varst），以及可执行语句的分析（ST_SORT），各个子函数又调用相应的函数，完成语法分析任务。由于词法分析和语法分析的联系，在编写语法分析程序的过程当中，要联系到词法分析中相应的变量，如设置一个指向Token表的头指针，方便读入单词进行语法分析。语法分析的任务就是根据语言的语法定义判断输入的TOKEN文件是否符合语法规则的定义,如果符合某个语法成分的定义,就是正确的定义.语法分析的过程就是不断地读入TOKEN文件中的单词,根据不同的语法单位,使用不同的方法进行分析,直到TOKEN文件的结束.源程序的组织结构是,程序头部,说明部分和可执行部分.递归下降分析器是当一个分析满足LL(1)条件时,就为他构造一个不带回溯的自上而下分析程序,这个分析程序是由一组递归过程组成的每个过程对应文法的一个非终结符通过语法分析,可以建立相应的语法树.根据建立语法树方式的不同,可以把语法分析过程分为两大类,即自顶向下和自底向上的分析方法.顾名思义,自顶向下的语法分析程序是沿着从树根到树叶的方向建立,而自底向上的方法则是沿着从树叶到树根的方向建立五、算法实现流程图词法分析程序把源程序变成TOKEN串,存放在TOKEN文件中.语法分析的任务就是根据语言的语法定义(产生式)判断输入的token文件是否符合语法规则的定义,如果符合某个语法成分的定义,就是正确的定义.语法分析的过程就是不断地读入token文件中的单词，根据不同的语法单位（语句），使用不同的方法进行分析，直到token文件的结束。源程序的组织结构（去掉了注释等无用部分）是：程序头部，说明部分和可执行部分，所以要分别进行处理。在语法分析过程中,各种语句的处理可以采用不同的语法分析方法:一是对各个语句和布尔表达式采用递归下降翻译法,二是对算术表达式采用自底向上的算符优先分析方法.根据采用的语法分析方法的不同,就得到不同的详细数据流图.如下图是使用算符优先分析方法的数据流.六、测试数据w:(i+i)*(i+i)+i*I七、结果输出及其分析、在次语法分析器中我们所给的测试数据是对输入串w:(i+i)*(i+i)+i*i进行LL(1)分析.当次串满足我们所给出的文法的时候，就按照上面的格式进行输出。当我们所给出的输入穿不满足我们所给出的文法是则包错误.例如:给出输入串w:kjads245dfkjd212,显然我们所给出的串不满足所给出的文法.则报错.显示有：“按任意键继续”字样。八、软件运行环境及限制本程序以VisualC++为开发环境，其功能是对C语言源程序进行语法分析。本程序对源程序中所有信息（包括出错信息）均用链表表示。这样可为后续程序的开发提供比较好的接口。九、参考文献〈〈程序设计语言编译原理〉〉第3版陈火旺等编著国防工