表达式语法分析——递归子程序法

题目介绍

题目思路

题目给的表达式文法为:

  • E→TG
  • G→+TG | ε
  • T→FS
  • S→*FS | ε
  • F→(E) | i

例如:i+i*i是文法能生成的一个表达式,输出格式举例:

  • 0 E–>TG
  • 1 T–>FS
  • 2 F–>i
  • 3 S–>&
  • 4 G–>+TG
  • 5 T–>FS
  • 6 F–>i
  • 7 S–>*FS
  • 8 F–>i
  • 9 S–>&
  • 10 G–>&
  • accept

i@i不是文法能生成的表达式,输出格式举例:

  • 0 E–>TG
  • 1 T–>FS
  • 2 F–>i
  • 3 S–>&
  • 4 G–>&
  • error

(i+i*i不是文法能生成的表达式,存在括号不匹配的语法错误,输出格式举例:

  • 0 E–>TG
  • 1 T–>FS
  • 2 F–>(E)
  • 3 E–>TG
  • 4 T–>FS
  • 5 F–>i
  • 6 S–>&
  • 7 G–>+TG
  • 8 T–>FS
  • 9 F–>i
  • 10 S–>*FS
  • 11 F–>i
  • 12 S–>&
  • 13 G–>&
  • error

当你输入符号串的时候:

  • 首先要进行E()函数,该函数的意思是直接输出E所对应的文法E–>TG,可以直接跑到T()和G()
  • 对于T函数来说,直接根据题目输出T–>FS,来进入到F函数和S函数
  • 对于G函数来说,题目给的是G→+TG | ε,所以需要判断当前的字符是否为+号,如果当前字符为+的话,直接输出G–>+TG,num要加一位并且进入T函数和G函数,反之直接输出G–>&
  • 对于F函数来说,题目给的是F→(E) | i,所以需要判断当前的字符是否为i和(,如果当前是i的话,输出F–>i,如果是(的话,输出F–>(E),并且num++和进入E函数,这里需要再一次判断当前的字符串是否为(,防止只有右括号没有左括号的现象
  • 对于S函数来说,题目给的是S→*FS | ε如果当前字符串是,直接输出S→*FS,否则输出S→&*

易错点

  1. 在判断字符的时候忘记进行num++
  2. num++一定要在递归之前

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/*
author:苦酒
QQ:1793929520
blog:huangliangshuai.com
*/
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstring>
#include <stdio.h>

using namespace std;

char str[101];
int sum = 0;
int num = 0;

void E();
void T();
void G();
void F();
void S();

void E()
{
cout<<sum++<<" "<<"E-->TG"<<endl;
T();
G();
}

void T()
{
cout<<sum++<<" "<<"T-->FS"<<endl;
F();
S();
}

void G()
{
if(str[num] == '+')
{
cout<<sum++<<" "<<"G-->+TG"<<endl;
num++;
T();
G();
}
else
{
cout<<sum++<<" "<<"G-->&"<<endl;
}
}

void F()
{
if(str[num] == 'i')
{
cout<<sum++<<" "<<"F-->i"<<endl;
num++;
}
else if(str[num] == '(')
{
cout<<sum++<<" "<<"F-->(E)"<<endl;
num++;
E();
if(str[num] == ')')
{
num++;
}
else
{
printf("error\n");
exit(0);
}
}
else
{
printf("error\n");
exit(0);
}
}

void S()
{
if(str[num] == '*')
{
cout<<sum++<<" "<<"S-->*FS"<<endl;
num++;
F();
S();
}
else
{
cout<<sum++<<" "<<"S-->&"<<endl;
}
}


int main()
{
scanf("%s", str);
E();
if(str[num] != '#')
{
cout<<"error"<<endl;
}
else
{
cout<<"accept"<<endl;
}
}


/***************************************************
User name: jk170631黄良帅
Result: Accepted
Take time: 0ms
Take Memory: 192KB
Submit time: 2019-11-19 19:24:50
****************************************************/
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信