1323: 实验2.10 非LL(1)文法的变换 - 消除左递归

时间限制: C/C++ 1 s      Java/Python 3 s      内存限制: 128 MB      答案正确: 26 / 80     

题目描述

布尔表达式文法G[B]

B→BoT|T

T→TaF|F

F→nF|(B)|t|f

1. 消除文法中的左递归?

2. 变换后的文法是否为LL(1)文法?

3. 如果是LL(1)文法,编写预测分析程序。

输入

输入多行布尔表达式,输入EOF结束。

输出

首先输出表达式的预测分析过程, 每列使用TAB键分隔,第2,3列字符宽度为10,第2列左对齐,第3列右对齐。

最后如果分析成功,则输出 "syntax correct",否则输出"syntax error"。

样例输入

taf#
fonfat#

样例输出

Step	Stack     	     Input	Action
1	#B        	      taf#	reduce:B→TB'
2	#B'T      	      taf#	reduce:T→FT'
3	#B'T'F    	      taf#	reduce:F→t
4	#B'T't    	      taf#	match
5	#B'T'     	       af#	reduce:T'→aFT'
6	#B'T'Fa   	       af#	match
7	#B'T'F    	        f#	reduce:F→f
8	#B'T'f    	        f#	match
9	#B'T'     	         #	reduce:T'→ε
10	#B'       	         #	reduce:B'→ε
11	#         	         #	accept
syntax correct
Step	Stack     	     Input	Action
1	#B        	   fonfat#	reduce:B→TB'
2	#B'T      	   fonfat#	reduce:T→FT'
3	#B'T'F    	   fonfat#	reduce:F→f
4	#B'T'f    	   fonfat#	match
5	#B'T'     	    onfat#	reduce:T'→ε
6	#B'       	    onfat#	reduce:B'→oTB'
7	#B'To     	    onfat#	match
8	#B'T      	     nfat#	reduce:T→FT'
9	#B'T'F    	     nfat#	reduce:F→nF
10	#B'T'Fn   	     nfat#	match
11	#B'T'F    	      fat#	reduce:F→f
12	#B'T'f    	      fat#	match
13	#B'T'     	       at#	reduce:T'→aFT'
14	#B'T'Fa   	       at#	match
15	#B'T'F    	        t#	reduce:F→t
16	#B'T't    	        t#	match
17	#B'T'     	         #	reduce:T'→ε
18	#B'       	         #	reduce:B'→ε
19	#         	         #	accept
syntax correct

提示

来源

标签


提交代码






© 2012-2022 JustOJ 中文  English  | l.jiang.1024@gmail.com | System Info