本文内容:
1、给出文法如下:
G[E]
E->T|E+T;
T->F|T*F;
F->i|(E);
可以构造算符优先表如下:
+ | * | ( | ) | i | |
+ | > | < | < | > | < |
* | > | > | < | > | < |
( | < | < | < | = | < |
) | > | > | > | ||
i | > | > | > |
2、计算机中表示上述优先关系,优先关系的机内存放方式有两种1)直接存放,2)为优先关系建立优先函数,这里由学生自己选择一种方式;
3、给出算符优先分析算法如下:
k:=1;S[k]:='#';
REPEAT
把下一个输入符号读进a中;
IF S[k]属于Vt THEN j:=k ELSE j:=k-1;WHILE S[j]>a DO
BEGIN
REPEATQ:=S[j];
IF S[j-1]属于Vt THEN j:=j-1 ELSE j:=j-2UNTIL s[j]<Q
把S[j+1]...S[k]归约为某个N;k:=j+1;
S[k]:=N;
END OF WHILE;
IF S[j]<a OR S[j]=a THENBEGIN
k:=k+1;S[k]:=a
END
ELSE ERRORUNTIL a=‘#'
样例:
文章来源:https://www.toymoban.com/news/detail-467119.html
代码如下:
# 输出结果
def output(str, a, b, type):
global program
program.append([type, str[a:b + 1]])
# 判断字符串一部分是否属于关键字
# 是返回1不是返回2
def iskeywords(str, a, b):
# 关键字
keywords = {"if", "int", "for", "while", "do", "return", "break", "continue"}
s = str[a:a + b + 1] # 拷贝字符
if s in keywords: # 判断是否存在,存在返回1,否则返回2
return 1
else:
return 2
# 判断字符是否属于运算符或分隔符的一部分。
# 不是返回0,是返回1,是且后面能跟=号返回2
def belong_to(str, type):
if type == 4: # 选择运算符
library = "+-*/=><!" # 运算符
else: # 选择分隔符
library = ",;{}()" # 分隔符
if str in library: # 存在
# 是可能后面跟=号的几个符号
if type == 4 and library.index(str) >= 4:
return 2
else:
return 1
return 0
# 递归的词法分析函数,读入一行str字符串,初始位置 n = 0
# 分离+判断,打印输出类型
# 由之前的c语言版本改写而成
def scan(str, n):
# 7 种类型(最后输出1 - 5)
# -1
# 0: 初始
# 1: 关键字, 在keywords中
# 2: 标识符
# 3: 常数(无符号整型)
# 4: 运算符和界符:+ - * / = > < >= <= !=
# 5: 分隔符:, ; {}()
i = n
type = 0
while i < len(str):
if type == 0: # 初始态
if str[i] == ' ': # 空格跳过
n += 1
i += 1
continue
elif str[i] == '\0' or str[i] == '\n': # 是结束
return
elif ('a' <= str[i] <= 'z') or ('A' <= str[i] <= 'Z'):
type = 1 # 是字母,
elif '0' <= str[i] <= '9':
type = 3 # 是数字,常数
else:
type = belong_to(str[i], 4)
if type > 0: # 是运算符
# 是能跟=号的运算符,后面是=号
if type == 2 and str[i + 1] == '=':
i = i + 1 # 结束位置后移
output(str, n, i, 4) # 输出 + 递归 + 结束
scan(str, i + 1)
return
elif belong_to(str[i], 5): # 是分隔符
output(str, n, i, 5) # 输出 + 递归 + 结束
scan(str, i + 1)
return
else:
print("失败:", str[i])
return
elif type == 1: # 关键字或标识符
if not (('a' <= str[i] <= 'z') or ('A' <= str[i] <= 'Z')): # 不是字母了
if '0' <= str[i] <= '9': # 是数字,只能是标识符
type = 2
else: # 非字母数字
type = iskeywords(str, n, i - 1)
output(str, n, i - 1, type) # 输出 + 递归 + 结束
scan(str, i)
return
elif type == 2: # 标识符
if not (('a' <= str[i] <= 'z') or ('A' <= str[i] <= 'Z')):
# 不是字母了
if not ('0' <= str[i] <= '9'):
# 不是数字
output(str, n, i - 1, type) # 输出 + 递归 + 结束
scan(str, i)
return
elif type == 3:
if not ('0' <= str[i] <= '9'):
# 不是数字
output(str, n, i - 1, type) # 输出 + 递归 + 结束
scan(str, i)
return
else:
print("%d失败" % type)
i += 1
# 添加S->;E;,形成句子括号
# S->;E; ; ;
# E->T|E+T +,*,i,( +,*,i,)
# T->F|T*F *,i,( *,i,)
# F->i|(E) i,( i,)
# A-> ···aB··· b∈FIRSTVT(B) a<b
# A-> ···Bb··· a∈LASTVT(B) a>b
# + * ( ) i ;
# + > < < > < >
# * > > < > < >
# ( < < < = <
# ) > > > >
# i > > > >
# ; < < < < =
# 算符分析函数
def Operator_Analysis():
priority_relationship = { # 优先关系
'+': {'+': '>', '*': '<', '(': '<', ')': '>', 'i': '<', ';': '>'},
'*': {'+': '>', '*': '>', '(': '<', ')': '>', 'i': '<', ';': '>'},
'(': {'+': '<', '*': '<', '(': '<', ')': '=', 'i': '<', ';': None},
')': {'+': '>', '*': '>', '(': None, ')': '>', 'i': None, ';': '>'},
'i': {'+': '>', '*': '>', '(': None, ')': '>', 'i': None, ';': '>'},
';': {'+': '<', '*': '<', '(': '<', ')': None, 'i': '<', ';': '='}}
p = program.copy() # 剩余输入串
s = [';'] # 栈
a = None # 当前符号
k = 0
j = 0
while 1:
# 读入下一个符号
a = p.pop(0)
if a[0] == 2 or a[0] == 3:
a = 'i'
else:
a = a[1]
if not s[k] == 'F': # 找找终结符
j = k
else:
j = k - 1
while priority_relationship[s[j]][a] == '>': # 规约
while 1:
Q = s[j]
if not s[j - 1] == 'F':
j = j - 1
else:
j = j - 2
if priority_relationship[s[j]][Q] == '<': # 找到左括号结束
break
if len(s[j + 1:k + 1]) % 2 == 0: # 如果不是奇数就不是 a op b,a,(a),这几种形式,
print("错误")
return -1
s = s[0:j + 1]
s.append('F')
k = j + 1
if priority_relationship[s[j]][a] == '<' or priority_relationship[s[j]][a] == '=':
s.append(a) # 入栈
k = k + 1
else:
print("错误")
return -1
if a == ';':
break
print("正确")
return 1
file = "program.txt"
file = open(file) # 读取文件
while i := file.readline():
program = [] # 记录读到的句子
scan(i, 0)
print(i, end='')
Operator_Analysis()
file.close()
结果:文章来源地址https://www.toymoban.com/news/detail-467119.html
10;
正确
1+2;
正确
(1+2)*3+(5+6*7);
正确
((1+2)*3+4;
错误
1+2+3+(*4+5);
错误
(a+b)*(c+d);
正确
((ab3+de4)**5)+1;错误
到了这里,关于python 算符优先分析法的设计实现 编译原理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!