词法分析程序

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 lex.in 输出文件 lex.out
【问题描述
兰兰刚学完编译原理,老师Max布置了一个作业,就是编写一个词法分析程序。
所谓的词法分析程序,就是对一个程序进行词法分析。词法规则可以用一个所谓的DFA(确定的有限自动机)表示,DFA是用来识别词法的单元(Token)的工具。如图为一个DFA的示意图。
“开始状态”表示识别的开始,所有的分析都是从这里开始,而且当前的字符串(Token)为空串。然后进行状态转移,转移的方法有很多种。我们的词法分析器是建立在预测分析的基础上的。所以只需要看下一个字符(编译原理中称这个字符为Lookahead)。
如图所示,如果Lookahead是数字,就会转移到数字状态,并且把Lookahead加入到Token的尾部,然后Lookahead指向下一个字符,继续进行分析;如果是字母,那么当前Token就是一个由Lookahead组成的字母。图中双圈就表示是一个结束状态,每个Token的分析都必须在结束状态结束(但到达结束状态不表示Token分析结束)。如果当前状态对于当前读入的字符串无法匹配(也就是没有一个射出弧上的字母等于当前读入的字符),那么就表示当前的Token分析结束,输出该Token及它的名称,并且返回开始状态进行处理(注意,此时的Lookahead是参与下一次识别)。
显然,DFA可以看成是一幅有向图G,每个状态就是图上的顶点V,每次识别的字符就是图上的边E,而每次的状态转移就是从一个顶点到达相应的下一顶点的过程。
兰兰很有耐性,把老师需要分析的程序的DFA已经画出来了,现在请你读入她所写的DFA,帮她进行词法分析。
输入格式】
输入格式(输入文件名lex.in)
首先是一个整数Tx(Tx≤100),表示状态数。状态是从0开始,即0,1,2,…,Tx-1,然后是Tx行,每行是一个字符串(长度不大于20),表示该状态所表示的Token的名称(如果是终结状态),当为非终结状态时,字符串为“-1”,如果该状态不用显示,字符串为“-2”。
接着是Tx行,每行表示每个状态的转移,其中第一行规定为开始状态(即状态0)。每一行第一个是一个数字(Ty≤100),表示当前状态的射出弧的条数,然后是一共Ty个对,每个对分别由一个字符和一个数字组成,分别是每条弧的LookAhead(任意非空白的可显示的字符),以及转移到的状态(x)。每个字符与数字之间都有一个空格分隔。接着是只有一个$的一行,表示需要分析的源程序的开始。然后就是需要分析的源程序。最后是只有一个$的一行,表示分析结束。
输出格式】
输出Token名字和对应的Token,中间由冒号和一个空格分隔。如果到达了一个非终止状态并且无法继续进行分析,显示一行"Lexer Error"。并把Token显示出来,然后回到初始状态,继续进行词法分析。所有的空白字符都强制作为Token的分隔符(空格,回车,制表符)。每个Token的长度都不会超过100.
输入输出样例】
输入(lex.in)
3
-1
Digit
Letter
10 0 1 1 1 2 1 3 1 4 1 a 2 b 2 c 2 d 2 e 2
0
0
$
123 abc
9
e1
$
输出(lex.out)
Digit: 1
Digit: 2
Digit: 3
Letter: a
Letter: b
Letter: C
Lexer Error: 9
Letter: e
Digit: 1