词法分析器的设计和实现-编译原理
项目1 手动设计词法分析器
一、 目的与要求：
项目1：
１）目的
通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；加深对课堂教学的理解；提高词法分析方法的实践能力。
２）要求
掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。
掌握词法分析的实现方法。
上机调试编出的词法分析程序。
二、 说明：
1、 TINY语言的特证
1) TINY语言无过程定义，无声明语句，所有的变量都是整型。
2) 它只有两个控制语句：if语句和repeat语句。if语句有一个可选的else部分且必须由关键字end结束。
3) read和write完成输入和输出
4) "{"和"}"中的语句为注释，但注释不能嵌套
Tiny语言的文法定义：
程序清单1是该语言的一个求阶乘的编程示例。
程序清单1
{ Sample program
in TINY language -
computes factorial
}
read x; { input an integer }
if 0 < x then { don't compute if x <= 0 }
fact := 1;
repeat
fact := fact * x;
x := x - 1
until x = 0;
write fact { output factorial of x }
end
2、 TINY语言的单词的种类和词法分析程序设计
2.1单词种类为5类：关键字，运算符，标识符，常整数，界限符或不可见字符
1) 关键字: if, then, else, end, repeat, until, read, write.（所有的关键字都是保留字，且全部小写）
2) 运算符： + - * / = < ( ) := （这里只用了小于符号<，没有使用大于符号> , :=为赋值符号）
3) 标识符和常整数：ID和NUM, 通过下列正则表达式定义：
ID = [a-zA-Z_]+[a-zA-Z0-9_]* //注意：大写和小写有区别
NUM = ([1-9][0-9]*)|([0-9]) //存疑，可改为[0-9]+
4) 不可见字符是由空白、制表符组成。它通常被忽略，但可以用来分开ID、NUM关键字。表达式结束符“;”是一种界限符，用来区分不同的语句。另外小括号在C语言中是一种界限符，用来区分句子的成分，但在Tiny语言中由于只用于表达式，不算作界限符。注释用{...}围起来，且不能嵌套，其中花括号也是界限符。
2.2 TINY语言词法分析程序设计
所有单词对应的DFA:
PS：思考一下，这正确吗？里面有没有bug？
考虑下面问题：
问题1：应设置多少种单词？
理论上应设置5类单词（参见书或课件PPT），但为了方便起见，可以直接把if, then, else, end, repeat, until, read, write，+ ， - ， * ， / ， = ， < ， ( ， )， ; ， :=，ID，NUM分别当做一类单词，共20类。
问题2：在识别字母串构成的单词后，如何区分是标识符还是保留字？
可以预设一张保留字表，通过查找保留字表来确定是保留字还是标识符。
PS：思考一下，除了这个方法，还能怎么做？
答：超前搜索和预处理。
问题3：和语法分析程序用什么形式的接口，返回的信息应包含什么？
词法分析和语法分析的接口是函数接口，即词法分析程序提供一个函数TokenType getToken(void)提供给语法分析调用，此函数每调用一次识别出一个单词，返回值为单词种别码，单词属性值放在全局变量char tokenString[MAXTOKENLEN + 1]中。其中，除了标识符和无符号整数外，其余单词只有种别码，没有单词属性值，标识符的单词属性值是字符串，无符号整数的单词属性值是整数值。
三、实验要求
（1）读懂源代码，添加注释，补充空白处的代码
（2）根据DFA设计单词扫描程序，输出单词流。源代码作为输入举例
例1： 源代码一：求阶乘
例2： 源代码二：求最大公约数
填充代码：
else if (c == '{')
{
//代码一： 填充代码
save = FALSE;
state = INCOMMENT;
}
case INASSIGN:
{
//代码二：补充此代码
if(c == '=')
{
state=DONE;
currentToken = ASSIGN;
}
else
{
state = DONE;
save = FALSE;
}
}
break;
需要修改的两处bug：一处在START是’_’不被算入INID，另一处是在INID读到’_’或数字不被算入INID
（1）第一处bug：
在case START中加入一下代码
else if (c == '_')
state = INID;
（2）第二处bug：
case INID:
if (!isalpha(c))
{
if (isdigit(c))
state = INID;
else if (c == '_')
state = INID;
else
{
ungetNextChar();
save = FALSE;
state = DONE;
currentToken = ID;
}
}
求阶乘的输出结果如下：
求最大公约数的输出结果如下：
项目2~3使用lex构建词法分析器
一、目的与要求
１）目的
通过lex工具构建调试词法分析程序，实现从源程序中分出各种单词的方法；加深对课堂教学的理解；提高词法分析方法的实践能力。
２）要求
掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。
掌握词法分析的实现方法。
掌握lex代码生成工具的使用
二、说明
2.1lex生成代码的过程
2.2Lex输入文件的格式
{
definition //定义集
1)必须插入的任何函数之外的代码段(以%{, %}作为开始、结束标记)，比如变量说明，常量说明等
2)正规式定义
}
%%
{
rules //规则集合
形如：{正规式} { 用C代码表示的语义动作}
{line} {printf(“%5d%s”,lineno++,yytext);}
}
%%
{
auxiliary routines//辅助部分：在规则部分被调用且不在任何地方被定义的辅助程序
main()
{yylex();return(0)}
}
2.3Lex使用的几点说明
（1）Lex 的常规表达式
（2）常规表达式举例
（3）标记声明举例
（4）lex常用变量和函数
三、实验要求
修改上面的文件内容，完成单词个数统计功能，例如对如下输入：
{ Sample program
in TINY language -
computes factorial
}
read x; { input an integer }
if 0 < x then { don't compute if x <= 0 }
fact := 1;
repeat
fact := fact * x;
x := x - 1
until x = 0;
write fact { output factorial of x }
end
输出为：
if 1
then 1
else 0
end 1
repeat 1
until 1
read 1
write 1
ID 10
NUM 4
:= 3
= 1
< 1
+ 0
- 1
* 1
/ 0
( 0
) 0
; 5
ERROR 0
项目二：
补充代码1：
"=" { return EQ; }
补充代码2：
{ "write", WRITE }
补充代码3：
case LT:
printf("line%2d: %-6d%-10s%s\n",lineno, LT,"LT", "<");
break;
测试用例运行结果如下：
Test1：
Test2：
项目三：
需要填的代码的作用是记录符号的个数，因此设置其对应数量+1
":=" { count[ASSIGN]++; }
"=" { count[EQ]++; }
"<" { count[LT]++; }
"+" { count[PLUS]++; }
"-" { count[MINUS]++; }
"*" { count[TIMES]++; }
"/" { count[OVER]++; }
"(" { count[LPAREN]++; }
")" { count[RPAREN]++; }
";" { count[SEMI]++; }
{num} { count[NUM]++; }
. { count[ERROR]++; }
测试用例运行结果：
Test1：
Test2：
