问题 4531 --H(2013校内赛)

4531: H(2013校内赛)

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

蕾蕾小朋友刚学完编译原理,马老师布置了一个作业,就是编写一个词法分析程序。

所谓的词法分析程序,就是对一个程序进行词法分析。词法规则可以用一个所谓的DFA(确定性有限自动机)表示,DFA是用来识别词法的单元(Token)的工具。下图为一个DFA示意图。

 

“开始状态”表示识别的开始,所有的分析都是从这里开始,而且当前的字符串(Token)为空。然后进行状态转移,转移的方法有很多种。蕾蕾的词法分析器是建立在预测分析的基础上。所以只需要看下一个字符(Lookahead)。如上图所示,如果Lookahead是数字,就会转移到数字状态,并且把Lookahead加入到Token的尾部,然后Lookahead指向下一个字符,继续进行分析;如果是字母,那么当前Token就是一个由Lookahead组成的字母。图中的多边形就表示了一个结束状态,每个Token的分析都必须在结束状态结束(但到达结束状态并不意味着Token分析一定结束)。如果当前状态对于当前读入的字符串无法匹配,也就是没有一个射出弧上的字母等于当前读入的字符,那么就表示当前的Token分析结束,输出该Token以及它的名称,并且返回开始状态进行处理(注意此时的Lookahead是参与下一次识别)。

显然DFA可以看成是一副有向图G<V, E>,每个状态就是图上的顶点V,每次识别的字符就是图上的边E,而每次的状态转移就是从一个顶点到达相应下一个顶点的过程。

蕾蕾很有耐心,她把老师需要分析的程序的DFA已经画了出来,现在请你读入她所写的DFA,帮她进行语法分析。

输入

首先是一个整数Tx(≤100),表示状态数。状态从0开始,即012,…Tx-1,然后是Tx行,每行是一个字符串(长度不大于20),表示该状态所表示的Token的名称(如果是终结状态),当为非终结状态,字符串为“-1”,如果该状态不用显示,字符串为“-2”。接着是Tx,每行表示每个状态的转移,其中第一行规定为开始状态(即状态0)。每一行第一个是一个数字,(Ty  ≤ 100),表示当前状态的射出弧的条数,然后一共是Ty个对,每个对分别由一个字符和一个数字组成,分别是每条弧的Lookahead(任意非空白可显示字符),以及转移到的状态(< Tx)。每个字符与数字之间都有一个空格分隔。接着是只有一个$的一行,表示需要分析的源程序的开始。然后就是需要分析的源程序。最后是一个只有一个$的一行,表示分析结束。

输出

输出Token名字和对应的Token,中间由冒号和一个空格分隔。如果到达了一个非终止状态并且无法继续分析,显示一行Lexer Error。并把Token显示出来,然后回到初始状态,继续进行词法分析。所有的空白字符都强制为Token的分隔符(空格,回车,制表符)。每个Token的长度都不会超过100

样例输入

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
$

样例输出

Digit: 1
Digit: 2
Digit: 3
Letter: a
Letter: b
Letter: c
Lexer Error: 9
Letter: e
Digit:1
9
e1
$ 

来源

[提交][状态]