编译原理实验讲义

编译原理实验讲义ver0.4实验一C_minus语言词法剖析器的设计（6学时）【目的】设计一个简单的词法剖析器，进而进一步加深对词法剖析器工作原理的理解。【要求】1、该个词法剖析器要求起码能够辨别以下几类单词：a．重点字：elseifintreturnvoidwhile共6个，全部的重点字都是保存字，而且一定是小写；b．表记符：辨别与C语言词法例定相一致的表记符，经过以下正则表达式定义：ID=letter(letter|digit)*；c．常数：NUM=(+|-|ε)digitdigit*(.digitdigit*|ε)(e(+|-|ε)digitdigit*|ε)，letter=a|..|z|A|..|Z|，digit=0|..|9，包含整数，如123,-123,+123等；小数，如123.45,+123.45,-123.45；科学计数法表示的常数，如+1.23e3，-2.3e-9；d．专用符号：+-*/<<=>>===!==;,( )[]{}/**/；2、剖析器的输入为由上述几类单词组成的程序，输出为该段程序的机内表示形式，即重点字、运算符、界线符变成其对应的机内符，常数使用二进制形式，表记符使用相应的表记符表指针表示。3、词法剖析器应该能够指出源程序中的词法错误，如不行识其他符号、错误的词法等。【方法与参照】第一给出全部单词的正规式（或正规文法）表示，而后将其转变成NFA，再将NFA确立化、最小化，获得最简的DFA，依据DFA编写词法剖析器的代码。【实验环境和工具】本实验不限制现所使用的开发工具以及运转环境。实验二递归降落剖析器的设计（6学时）【目的】使用递归子程序法设计一个语法剖析程序，理解自顶向下剖析方法的原理，掌握手工编写语法剖析程序的方法。【要求】1、使用递归降落剖析算法剖析表达式文法：exp::=expaddopterm|termaddop::=+|-term::=termmulopfactor|factormulop::=*|/factor::=(exp)|number此中number能够是多位的十进制数字串（整数即可），所以这里还需要一个小的词法剖析器来获得number的值。2、该词法剖析器以子程序形式出现，当需要进行词法剖析时进行调用；3、能够辨别正确和错误的表达式；4、在进行语法剖析的过程中，计算输入表达式的值。【方法与参照】第一将上述文法改写成EBNF形式，依据递归降落剖析算法基本思想编写程序。【实验环境和工具】本实验不限制现所使用的开发工具以及运转环境。1实验三算符优先剖析法剖析器的设计（6学时）【目的】设计一个算符优先剖析器，理解优先剖析方法的原理。【要求】使用算符优先剖析算法剖析下边的文法：E’→#E#E→E+T|T→T*F|FF→P^F|PP→(E)|i此中i能够看作是一个终结符，无需作词法剖析。详细要求以下：1.假如输入符号串为正确句子，显示剖析步骤，包含剖析栈中的内容、优先关系、输入符号串的变化状况；假如输入符号串不是正确句子，则指示犯错地点。【方法】第一结构算符优先关系表，而后依据算符优先剖析算法编写程序。【实验环境和工具】本实验不限制现所使用的开发工具以及运转环境。//依据算符优先文法的剖析规则求得终结符优先关系表//+*^i()#//+><<<<>>//*>><<<>>//^>><<<>>//i>>>>>//(<<<<<=//)>>>>>//#<<<<<=#include<stdlib.h>#include<string.h>#include<stdio.h>#include<dos.h>charyouxian[7][7];//算符优先关系数组voidmain( ){{//将算符优先关系寄存在算符优先关系数组里youxian[0][0]='>';youxian[0][1]='<';youxian[0][2]='<';youxian[0][3]='<';youxian[0][4]='<';2youxian[0][5]='>';youxian[0][6]='>';//______________________________________________________________youxian[1][0]='>';youxian[1][1]='>';youxian[1][2]='<';youxian[1][3]='<';youxian[1][4]='<';youxian[1][5]='>';youxian[1][6]='>';//_______________________________________________________________youxian[2][0]='>';youxian[2][1]='>';youxian[2][2]='<';youxian[2][3]='<';youxian[2][4]='<';youxian[2][5]='>';youxian[2][6]='>';//_______________________________________________________________youxian[3][0]='>';youxian[3][1]='>';youxian[3][2]='>';youxian[3][3]='$';//无优先关系的用$表示youxian[3][4]='$';youxian[3][5]='>';youxian[3][6]='>';//_________________________________________________________________youxian[4][0]='<';youxian[4][1]='<';youxian[4][2]='<';youxian[4][3]='<';youxian[4][4]='<';youxian[4][5]='=';youxian[4][6]='$';//_________________________________________________________________youxian[5][0]='>';youxian[5][1]='>';youxian[5][2]='>';youxian[5][3]='$';youxian[5][4]='$';youxian[5][5]='>';youxian[5][6]='>';//__________________________________________________________________youxian[6][0]='<';3youxian[6][1]='<';youxian[6][2]='<';youxian[6][3]='<';youxian[6][4]='<';youxian[6][5]='$';youxian[6][6]='=';//______________________________________