目录
一、实验目的和要求
二、实验内容
三、实验环境
四、实验步骤
1、语法分析所依据的文法；
2、给出消除左递归及提取左公因子的文法；
五、测试要求
六、实验步骤
1、语法分析所依据的文法
2、给出消除左递归及提取左公因子的文法；
3、关键代码
七、实验结果与分析
一、实验目的和要求
- 理解自顶向下语法分析方法；
- 用递归下降技术实现语法分析器；
二、实验内容
算术表达式的文法是G[E]：
E→E+T| E-T| T
T→T*F| T/F| F
F→(E)| i
用递归下降分析法按文法G[E]对算术表达式（包括+、-、*、/、（）的算术表达式）进行语法分析，判断该表达式是否正确。
三、实验环境
处理器 AMD Ryzen 7 5800H with Radeon Graphics3.20 GHz
机带RAM 16.0 GB(13.9 GB可用)
Win10家庭版20H2 X64
PyCharm 2012.2
Python 3.10
四、实验步骤
1、准备：阅读课本有关章节，将上述算术表达式的文法改造成LL(1)文法（即消除左递归和提取左公因子）；
2、参考课件P52编写递归下降分析程序。
1、语法分析所依据的文法；
算术表达式的文法是G[E]：
E→E+T| E-T| T
T→T*F| T/F| F
F→(E)| i
2、给出消除左递归及提取左公因子的文法；
将文法G[E]改造为LL(1)文法如下：
G’[E]：
E → TE’
E’ → +TE’| -TE’|ε
T → FT’
T’→ *FT’|/FT’|ε
F → (E)| i
五、测试要求
1、为降低难度，表达式中不含变量，只含单个无符号整数或i；
2、如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3、测试用的表达式建议事先放在文本文件中，一行存放一个表达式，以分号结束。而语法分析程序的输出结果写在另一个文本文件中；
4、程序输入/输出示例：
输入如下表达式（以分号为结束）和输出结果：
（a）i; 或 1;
输出：正确
（b）i+i; 或 1+2;
输出：正确
（c）(i+i)*i+i-(i+i*i); 或 (1+2)*3+4-(5+6*7);
输出：正确
（d）((i+i)*i+i; 或 ((1+2)*3+4;
输出：错误，缺少右括号
（e）i+i+i+(*i/i); 或 1+2+3+(*4/5)
输出：错误
5、选作：对学有余力的同学，可增加功能：当判断一个表达式正确时，输出计算结果。
六、实验步骤
1、语法分析所依据的文法
算术表达式的文法是G[E]：
E→E+T| E-T| T
T→T*F| T/F| F
F→(E)| i
2、给出消除左递归及提取左公因子的文法；
将文法G[E]改造为LL(1)文法如下：
G’[E]：
E → TE’
E’ → +TE’| -TE’|ε
T → FT’
T’→ *FT’|/FT’|ε
F → (E)| i
3、关键代码
<!--BianYiYuanLiShiYan/yufafenxi_rtda.py-->
复制代码
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152''' 在实验一的基础上进行语法分析 递归下降分析法 E→TE' E'→+TE'| -TE' |ε T→FT' T'→*FT'| /FT' |ε F→(E) | id |num 保留关键字及种别编码 Static_word = {"begin": 1, "end": 2, "if": 3, "then": 4, "while": 5, "do": 6, "const": 7, "var": 8, "call": 9, "procedure": 10} 算符和界符及种别编码 Punctuation_marks = {"+": 11, "-": 12, "*": 13, "/": 14, "odd": 15, "=": 16, "<>": 17, "<": 18, ">": 19, "<=": 20, ">=": 21, ":=": 22, "(": 23, ")": 24, ".": 25, ",": 26, ";": 27} 常数的种别编码为28，标识符的种别编码为29，非法字符的种别编码为30 ''' # 导入词法分析的程序 from cifafenxi_rtda import * # 由于实验二的特殊性，单独把i(id)当做保留字处理 Static_word["i"] = 0 # i + - * 、 ( ) num的种别编码 Lab2_word = [0, 11, 12, 13, 14, 23, 24, 28] # 出错标志 Err = 0 # 位置标志 Index = 0 # 算术表达式是否符合文法 Correct = "***************正确！" Error = "*************错误!" # 语法分析结果写入文件 def WriteFile(string): fW = open(pathW, 'a') fW.write(string + "n") fW.close() # 开始正式语法分析前首先判断该算术表达式中的各个字符以及首尾字符是否符合要求 def First(): index = 0 if (Result_Lex[0][0] in [0, 23, 28]) and (Result_Lex[0][-1] in [0, 24, 28]): for i in Result_Lex[:-2]: if i not in Lab2_word: index += 1 break else: continue else: index += 1 return index # E→TE' def E(): global Err if Err == 0: T() E1() # E'→+TE'| -TE' |ε def E1(): global Err, Index if Err == 0 and Index != len(Result_Lex[0]): if Result_Lex[0][Index] in [11, 12]: Index += 1 if Index != len(Result_Lex[0]) - 1: T() E1() else: Index = len(Result_Lex[0]) elif Result_Lex[0][Index] != 24: Err = 1 # T→FT' def T(): global Err if Err == 0: F() T1() # T'→*FT'| /FT' |ε def T1(): global Err, Index if Err == 0 and Index != len(Result_Lex[0]): if Result_Lex[0][Index] in [13, 14]: Index += 1 if Index != len(Result_Lex[0]) - 1: F() T1() else: Index = len(Result_Lex[0]) elif Result_Lex[0][Index] not in [11, 12, 24]: Err = 1 # F→(E) | id |num def F(): global Err, Index if Err == 0: if Result_Lex[0][Index] in [0, 28]: Index += 1 elif Result_Lex[0][Index] == 23: Index += 1 E() if Result_Lex[0][Index] != 24: Err = 1 Index += 1 else: Err = 1 # 分析主程序 def Analysis_Gs(): global Err, Index if First() == 0: F() while Index < len(Result_Lex[0]): if Result_Lex[0][Index] in [11, 12]: E1() elif Result_Lex[0][Index] in [13, 14]: T1() else: Index = len(Result_Lex[0]) Err = 1 if Err == 0: print("语法分析结果：" + Correct) else: print("语法分析结果：" + Error) else: print("语法分析结果：" + Error) if __name__ == '__main__': # 首先运行词法分析程序 Lex_main() # 运行语法分析程序 Analysis_Gs()
<!--BianYiYuanLiShiYan/cifafenxi_rtda.py-->
复制代码
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236""" PL/0程序大纲： 1、PL/0语言的单词结构 关键字(10个)：begin, end ,if ,then, while, do, const, var,call,procedure 标识符：字母序列，最大长度10 常数：整型常数 算符和界符（17个）：+， -， *，/，odd，=，<>，<，>，<=，>=，:=，(，) ，, ，.，; 2、单词的种别划分 标识符 作为一种 常数 作为一种 算符和界符每个单词作为一个单独种别 3、PL/0的语言的词法分析器将要完成以下工作： （1）跳过分隔符（如空格，回车，制表符）； （2）识别诸如begin，end，if，while等保留字； （3）识别非保留字的一般标识符。 （4）识别数字序列。 （5）识别:=，<=，>=之类的特殊符号。 """ # 输入文件路径 pathR = "" # 输出文件路径 pathW = "" # 保存所有字符 strAll = [] # 保存词法分析后的字符及种别编码 Result_Lex = [[], []] # 保留关键字及种别编码 Static_word = {"begin": 1, "end": 2, "if": 3, "then": 4, "while": 5, "do": 6, "const": 7, "var": 8, "call": 9, "procedure": 10} # 算符和界符及种别编码 Punctuation_marks = {"+": 11, "-": 12, "*": 13, "/": 14, "odd": 15, "=": 16, "<>": 17, "<": 18, ">": 19, "<=": 20, ">=": 21, ":=": 22, "(": 23, ")": 24, ".": 25, ",": 26, ";": 27} # 常数的种别编码为28，标识符的种别编码为29，非法字符的种别编码为30 # 空格或换行 Blank = {" ", "n"} # 中文说明 Explanation = ["保留字", "加号", "减号", "乘号", "除号", "odd运算符", "等于号", "不等于号", "小于号", "大于号", "小于等于号", "大于等于", "赋值符号", "左括号", "右括号", "点号", "逗号", "分号", "常数", "标识符"] # 判断字符数否为保留关键字 def Is_static(string): if string in Static_word: return True else: return False # 判断字符是否为算符或者界符 def Is_marks(string): if string in Punctuation_marks: return True else: return False # 判断是不是空格或者换行 def Is_blank(string): if string in Blank: return True else: return False # 读取文件所有字符并保存在一个列表中 def Scanner(): fR = open(pathR) # 返回一个文件对象 lines = fR.readlines() # 调用文件的 readline()方法 for line in lines: for i in line: strAll.append(i) fR.close() # strAll.pop() # 多次重复的操作语句 def Option(num, temp, explanation): fW = open(pathW, 'a') txt = '%-20s%s' % ("（" + str(num) + "，" + temp + "）", explanation + ":" + temp) # txt = "({0}，{1}）t{2}:{3}".format(num, temp, explanation, temp) print(txt) fW.write(txt + "n") fW.close() Result_Lex[0].append(int(num)) Result_Lex[1].append(temp) # 结束 def End(id): if id >= len(strAll): return True # 词法分析主方法 def Analysis_Lex(): """ 共分为四大块，分别是标识符、常数、算符或界符、空格或换行、非法字符，对应下面的 if, elif, elif, elif和 else """ # 索引值 id = 0 # 忽略代码段开头的空格或换行 while Is_blank(strAll[id]): id += 1 # 从第一个有意义的字符开始循环识别直至最后一个字符 while id < len(strAll): # 保存临时结果 temporary = "" # 判断是否为保留字或者标识符 if ('a' <= strAll[id] <= 'z') or ('A' <= strAll[id] <= 'Z'): while ('0' <= strAll[id] <= '9') or ('a' <= strAll[id] <= 'z') or ( 'A' <= strAll[id] <= 'Z'): temporary += strAll[id] id += 1 if End(id): break # 判断是否未保留字 if Is_static(temporary): num = Static_word[temporary] Option(num, temporary, Explanation[0]) # 判断是否为特殊运算符odd elif temporary == "odd": num = Punctuation_marks[temporary] Option(num, temporary, Explanation[num - 10]) # 否则为非保留字标识符 else: Option("29", temporary, Explanation[-1]) # 判断是否为常数（正数或小数） elif '0' <= strAll[id] <= '9': while ('0' <= strAll[id] <= '9') or strAll[id] == ".": if strAll[id] != ".": temporary += strAll[id] id += 1 if End(id): break elif strAll[id] == "." and ('0' <= strAll[id + 1] <= '9'): temporary += strAll[id] id += 1 if End(id): break else: break Option("28", temporary, Explanation[-2]) # 判断是否为运算符或界符 elif Is_marks(strAll[id]) or strAll[id] == ":": temporary += strAll[id] # 判断小于号三种情况：小于、小于等于、不等于 if strAll[id] == "<": if strAll[id + 1] == ">" or strAll[id + 1] == "=": temporary += strAll[id + 1] id += 2 num = Punctuation_marks[temporary] Option(num, temporary, Explanation[num - 10]) else: id += 1 num = Punctuation_marks[temporary] Option(num, temporary, Explanation[num - 10]) # 判断大于号两种情况：大于、大于等于 elif strAll[id] == ">": if strAll[id + 1] == "=": temporary += strAll[id + 1] id += 2 num = Punctuation_marks[temporary] Option(num, temporary, Explanation[num - 10]) else: id += 1 num = Punctuation_marks[temporary] Option(num, temporary, Explanation[num - 10]) # 判断赋值符号特殊情况 elif strAll[id] == ":": if strAll[id + 1] == "=": temporary += strAll[id + 1] id += 2 num = Punctuation_marks[temporary] Option(num, temporary, Explanation[num - 10]) # 单独的冒号不是运算符或界符，当非法字符处理 else: id += 1 Option("30", temporary, "非法字符") # 其他运算法或界符 else: id += 1 num = Punctuation_marks[temporary] Option(num, temporary, Explanation[num - 10]) # 对空格、换行过滤 elif Is_blank(strAll[id]): id += 1 continue # 对非法字符的处理 else: temporary += strAll[id] id += 1 Option("30", temporary, "非法字符") def Lex_main(): # 获取代码文件 print("请输入要分析的代码文件(.txt)路径及完整名称：", end='') global pathR, pathW pathR = input() # 读入代码文件 Scanner() # 读入保存结果文件 print("请输入保存结果的文件(.txt)路径及完整名称：", end='') pathW = input() # 开始分析代码文件及结果写入 # print(strAll) print('%-16s%s' % ("（种别编码，字符）", "中文介绍:字符")) print("-------------词法分析结果为-------------n") # 打开需要写入结果的文档（不存在则创建）并开始写入！ f = open(pathW, 'a') f.write('%-16s%s' % ("（种别编码，字符）", "中文介绍:字符n")) f.write("-------------词法分析结果为-------------n") f.close() # 程序实现主方法 Analysis_Lex() # 程序运行点 if __name__ == '__main__': Lex_main()
七、实验结果与分析
最后
以上就是明亮钢笔最近收集整理的关于编译原理实验--实验二 递归下降法判断算术表达式的正确性--Python实现的全部内容，更多相关编译原理实验--实验二内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复