OI题库

【问题描述】

兰兰刚学完编译原理，老师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)
首先是一个整数T_x(T_x≤100)，表示状态数。状态是从0开始，即0，1，2，…，T_x-1，然后是T_x行，每行是一个字符串(长度不大于20)，表示该状态所表示的Token的名称(如果是终结状态)，当为非终结状态时，字符串为“-1”，如果该状态不用显示，字符串为“-2”。
接着是T_x行，每行表示每个状态的转移，其中第一行规定为开始状态(即状态0)。每一行第一个是一个数字(T_y≤100)，表示当前状态的射出弧的条数，然后是一共T_y个对，每个对分别由一个字符和一个数字组成，分别是每条弧的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