LL(1)文法系列(三)预测分析程序

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知文法G[S]的表达式,通过预测分析表,对输入串进行分析。在文法G[S]中使用’@’代表空。

现在我们规定文法G[S]中每个表达式只包含一个语句,也就是说不会含有S -> A|B这样的表达式。

Input

 第一行输入一个n(n < 10),表示表达式的个数,接下来n行,每行一个表达式。终结符和非终结符的个数都小于10

最后一行输入字符串,长度小于20,输入串以#结尾

Output

 按照示例进行输出,使用\t进行格式控制,保证输入串合法。

为方便表示,将输入串翻转,在当前串中输出。

Sample Input

4
S->ABC
A->a
B->@
C->c
ac

Sample Output

#S	#ca	S->ABC	
#CBA	#ca	A->a
#CBa	#ca	a
#CB	#c	B->@
#C	#c	C->c
#c	#c	c
#	#	#
acc

Hint

Source