表达式语法分析——预测分析法

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 预测分析法是自顶向下分析的一种方法,一个预测分析程序是由三个部分组成:

(1) 预测分析程序

(2) 先进后出栈

(3) 预测分析表

现给出表达式文法:

E→TG

G→+TG | ε

T→FS

S→*FS | ε

     F→(E) | i

该表达式文法是LL(1)文法,其预测分析表为:

请根据该预测分析表构造预测分析程序,完成对表达式的语法分析,对给定的输入串,判断其是否为合法表达式,给出所使用的产生式序列。

 

Input

 

给定输入串(长度不超过50个符号,以#号结束,符号保证是终结符或#)。

例如:

i+i*i# 是合法表达式

i+i*(i+i)# 是合法表达式

ii+i*i# 不是合法表达式

i*(i+i# 不是一个合法的表达式。

Output

要求输出分析过程中使用的所有产生式,产生式按使用顺序各占一行,每行有两个数据,使用顺序号(从1开始编号)及产生式本身,中间用一个空格分开,最后一行表示语法分析是否成功结束,如果成功分析结束输出acc!,表示该输入串是合法表达式,否者输出error!,表示该输入串不是合法表达式。
注:其中^符号代表文法中的ε符号。
针对输入串i+i*i#,因为分析过程使用了11次产生式,且该输入串是合法表达式,输出如下:

1 E->TG

2 T->FS

3 F->i

4 S->^

5 G->+TG

6 T->FS

7 F->i

8 S->*FS

9 F->i

10 S->^

11 G->^

acc!

针对输入串i*(i+i#,因为分析过程使用了14次产生式后,发现语法错误,该输入串不是合法表达式,输出如下:

1 E->TG

2 T->FS

3 F->i

4 S->*FS

5 F->(E)

6 E->TG

7 T->FS

8 F->i

9 S->^

10 G->+TG

11 T->FS

12 F->i

13 S->^

14 G->^

error!

Sample Input

i+i*i#

Sample Output

1 E->TG
2 T->FS
3 F->i
4 S->^
5 G->+TG
6 T->FS
7 F->i
8 S->*FS
9 F->i
10 S->^
11 G->^
acc!

Hint

 

Source