资源描述：
《编译原理基础——习题与上机题解答 教学课件 作者 刘坚 第6-10章第8章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第8章递归子程序方法的参考解决方案8.1词法分析器的构造 词法分析器的构造一般有以下几大步骤：用正规式对模式进行描述；由正规式构造NFA；将NFA转化为DFA且最小化；根据最小DFA编写程序并进行测试。8.1.1记号的设计 源程序实际上是一个字符序列，词法分析器读取该序列并根据构词规则将其转换为记号流。函数绘图语言的词法分析器至少需完成以下三个任务：(1)滤掉源程序中的注释和无用成分(空格、TAB等)；(2)输出记号,供语法分析器使用；(3)识别非法输入，并将非法输入作为出错记号提供给语法分析器，以便进行出错处理。记号一般由两部分组成：记号的类别和记号的属性。根
2、据函数绘图语言的特点，可以为记号设计如下的数据结构，其中记号的类别和第一个属性是每个记号都必须有的信息，而后两个属性，则分别是为常数和函数设计的。structToken//记号的数据结构{Token_Typetype;//类别char*lexeme;//属性，原始输入的字符串doublevalue;//属性，若记号是常数则是常数的值double(*FuncPtr)(double);//属性，若记号是函数则是函数的指针};根据上节对记号的分析，可以将函数绘图语言的记号类别进行如下划分，且用枚举类型表示它们。enumToken_Type//记号的类别{ORIGIN,SCAL
3、E,ROT,IS,//保留字TO,STEP,DRAW,FOR,FROM,//保留字T,//参数SEMICO,L_BRACKET,R_BRACKET,COMMA,//分隔符PLUS,MINUS,MUL,DIV,POWER,//运算符FUNC,//函数CONST_ID,//常数NONTOKEN,//空记号ERRTOKEN//出错记号};对于源程序中出现的保留字、参数、分隔符和运算符等，采用“一字一码”的形式，即一个记号仅有一个实例；函数和常数的记号可以有多于一个的实例，如FUNC的实例可以是sin，也可以是cos等；空记号用于标记源程序文件的结束，即遇到文件结束符，词法分析
4、器就返回一个空记号，以通知语法分析器所分析的源程序已经结束；出错记号用于标记非法输入，当分析到非法字符或字符串时，词法分析器就返回一个出错记号，以便语法分析器进行相应的语法错误处理。8.1.2模式的正规式表示 函数绘图语言的词法可用下述正规式集合表示，其中的letter和digit是辅助定义。 描述词法的正规式----------------------------------------------------------------------letter=[a–zA–Z]digit=[0–9]COMMENT="//"
5、"--"WHITE_SPACE=(""
6、
7、t
8、)+SEMICO=";"L_BRACKET="("R_BRACKET=")"COMMA=","PLUS="+"MINUS="–"MUL="*"DIV="/"POWER="**"CONST_ID=digit+("."digit*)?ID=letter+(letter
9、digit)*----------------------------------------------------------------------正规式COMMENT和WHITE_SPACE用于过滤源程序中的注释和白空(空格、Tab、回车等)，由于注释和白空并不需要出现在语法分析以后的部分
10、，因此仅在词法分析器中处理它们，没有对应的记号供语法分析器使用；从SEMICO到POWER的正规式规定了分隔符和运算符；CONST_ID描述了字面量形式的常数；而ID给出了函数绘图语言中所有的标识符的模式。 特别值得提出的是CONST_ID和ID的设计。由于我们是手工构造词法分析器，而正规式个数越少越便于程序的编写，因此设计上采用相同模式的记号共用一个正规式的方法。常数的字面量部分设计为CONST_ID，而常量名则合并到ID中。这就带来一个问题，函数绘图语言中的保留字、常量名、参数名，以及函数名均被描述为ID，当识别出ID时，如何再细分它们？8.13区分记号的符号表
11、 为解决上述问题，可以设计一个预定义的符号表，将所有符合ID模式的保留字、常量名、参数名和函数名等，均放进符号表中。符号表是一个数组，数组元素的类型与记号的类型相同，具体内容可如下：staticTokenTokenTab[]={{CONST_ID,"PI",3.1415926,NULL},{CONST_ID,"E",2.71828,NULL},{T,"T",0.0,NULL},{FUNC,"SIN",0.0,sin},{FUNC,"COS",0.0,cos},{FUNC,"TAN",0.0,tan},{FUNC,"LN",0.0,lo
