• 日期: 2026-04-26
  • 标签: 常规
from collections import deque
first=[[] for i in range(10)]
last=[[] for i in range(10)]
dfirst = {}
dvt={}
stack = deque()
satck_int = deque()
mode=1
def findfirst(l,r):
    for i in range(time+1):
        if left[i] == r:
             for x in range(len(right[i])):
                 if right[i][x] in vt:
                     if right[i][x] not in first[dfirst[l]]:
                        first[dfirst[l]].append(right[i][x])
                        break
                 elif right[i][x] in vn and right[i][x] != left[i]and x==0:
                     findfirst(l, right[i][x])
                     continue
def findlast(l,r):
    for i in range(time+1):
        if left[i] == r:
             for x in range(len(right[i])):
                 if right[i][x] in vt:
                     if right[i][x] not in last[dfirst[l]]:
                        last[dfirst[l]].append(right[i][x])
                     break
                 if right[i][x] in vn and right[i][x] != left[i]and x==0:
                     findlast(l, right[i][x])
                     continue
def getfirstvt(mode):
    for i in range(time+1):
        if left[i] in vn:
            for x in range(len(right[i])):
                if mode==1:
                    if right[i][x] in vt :#非终结符
                        if right[i][x]  not in first[dfirst[left[i]]]:
                            first[dfirst[left[i]]].append(right[i][x])
                            break
                    elif right[i][x] in vn and right[i][x] != left[i] and x==0:#终结符
                        findfirst(left[i],right[i][x])
                        continue
                elif mode==2:
                    if right[i][x] in vt :#非终结符
                        if right[i][x]  not in last[dfirst[left[i]]]:
                            last[dfirst[left[i]]].append(right[i][x])
                        break
                    if right[i][x] in vn and right[i][x] != left[i] and x==0:#终结符
                        findlast(left[i],right[i][x])
                        continue
def getchar():
    input('scan your rules(change id to i and end with stop)')
    global vt, vn, left, right, time
    vt = set()
    vn = set()
    k = 1
    time = -1
    left = []
    right = [[0 for i in range(10)] for i in range(10)]
    f = open('rule.txt',encoding='utf-8')
    while True:
        rule = f.readline().strip('
')
        if rule == 'stop':
            break
        case = 0
        time += 1
        y = 0
        for index in range(len(rule)):
            if case == 0 and rule[index] != '→' and rule[index] != '’':
                left.append(rule[index])
            if case == 1:
                right[time][y] = rule[index]
                y += 1
            if rule[index] > 'A' and rule[index] < 'Z':
                vn.add(rule[index])
            elif not (rule[index] == '→' or rule[index] == '’'):
                vt.add(rule[index])

            if rule[index] == '→':
                case = 1
                index += 1
def creat_flvt():
    l_vn=list(vn)
    for i in range(len(l_vn)):
         dfirst[l_vn[i]] = i

    l_vt=list(vt)
    for i in range(len(l_vt)):
         dvt[l_vt[i]] = i
    global lenth_vt
    lenth_vt=len(l_vt)

    for x in range(len(right)):
        while 0 in right[x]:
            right[x].remove(0)
def printvnvt():#对需要查看的内容取消标注
    print('VT and VN:')
    print(vt)
    print(vn)
    print('left and right:')
    print(right)
    print(left)
    #print(time + 1)
    print('VN')
    print(dfirst.keys())
    print('firstvt and lastvt')
    print(first)
    print(last)
    print('VT')
    print(dvt.keys())
    print('TABLE')
    for i in range(len(table)):
        print(table[i])
def gettable():
    global  table
    table = [[0 for i in range(lenth_vt)] for i in range(lenth_vt)]
    for i in range(time+1):
        for x in range(len(right[i])-1):
             rig = right[i][x]
             riger = right[i][x+1]
             if rig in vt and riger in vn:
                  for s in first[dfirst[riger]]:
                      table[dvt[rig]][dvt[s]] = '<'
             if rig in vn and riger in vt:
                  for f in last[dfirst[rig]]:
                      table[dvt[f]][dvt[riger]] = '>'
             if rig in vt and riger in vt:
                 table[dvt[rig]][dvt[riger]] = '='
        for x in range(len(right[i])-2):
            if right[i][x] in vt and right[i][x+1] in vn and right[i][x+2] in vt:
                 if right[i][x]== right[i][x+2]:
                    table[dvt[right[i][x]]][dvt[right[i][x+2]]] = '='
                    table[dvt[right[i][x+2]]][dvt[right[i][x]]] = '='
                 else:
                    table[dvt[right[i][x]]][dvt[right[i][x + 2]]] = '='
def turndown():
    for i in range(time + 1):
        right[i].reverse()  # 反转右侧二维数组
def simplify():
    sentence=input('input your sentence:')
    sentence=list(sentence)
    sentence.append('#')
    stack.append('#')
    x=0
    y=0
    while(len(stack)):
        print()
        print(satck_int)
        print(stack)
        if(sentence[y]>'0'and sentence[y]<'9'):
            num=int(ord(sentence[y])-ord('0'))
            y+=1
            while(sentence[y]>'0'and sentence[y]<'9'):
                num=num*10+int(ord(sentence[y])-ord('0'))
                y+=1
            satck_int.append(num)
        if sentence[y] in {'+','-','*','/','#','(',')'}:  
            t1=stack[len(stack)-1]
            t2=sentence[y]
            z1=dvt[t1]
            z2=dvt[t2]
            if table[z1][z2]=='0':
                print('Error!')
                return
            if table[z1][z2]=='<':
                stack.append(t2)
                x+=1
                y+=1
                continue
            elif table[z1][z2] == '=':
                stack.pop()
                x-=1
                y+=1
            else:#if table[z1][z2]=='>'  
                calculate(t1)
                continue
        else:
            print('Error!')
            return
    out=satck_int.pop()
    print(out)
def count(a,b,c):
    if c=='+':
        return a+b
    elif c=='-':
        return a-b
    elif c=='*':
        return a*b
    elif c=='/':
        return b/a
def calculate(t1):
    d1=satck_int[len(satck_int)-1]
    satck_int.pop()
    d2=satck_int[len(satck_int)-1]
    satck_int.pop()
    satck_int.append(count(d1,d2,t1))
    stack.pop()
def main():
    getchar()
    creat_flvt()
    getfirstvt(1)#mode1下的，正序寻找
    turndown()
    getfirstvt(2)#mode2下的，逆序寻找
    turndown()
    gettable()
    #printvnvt()
    simplify()
    return
main()
'''rule.txt的内容
S→#E#
E→E+T
E→E-T
E→T
T→T*F
T→T/F
T→F
F→(E)
F→i
stop
'''

### 运行程序

1. 将上述代码保存为Python文件，例如`opg_parser.py`
2. 在同一目录下创建一个名为`rule.txt`的文件，并将文法规则写入其中，格式如下：

S→#E# E→E+T E→E-T E→T T→T*F T→T/F T→F F→(E) F→i stop

3. 在命令行中使用Python解释器运行该文件：

```bash
python opg_parser.py
  1. 程序会提示您输入一个算术表达式，例如1+2*3，然后程序会输出分析结果：
[1, 2, 3]
['#', '+', '*', '#']
[1, 2, 3]
['#', '*', '#']
[1, 6]
['#', '#']
[7]
['#']
7

该输出表示输入的表达式合法，并且计算结果为7。

总结

本程序使用Python实现了算符优先分析器，可以对简单的算术表达式进行分析识别，判断其合法性并进行计算。该程序可以作为学习编译原理和文法分析的参考，也可以用于实际的编程语言解析器开发。

算符优先分析器：Python实现简单算术表达式文法分析

原文地址: https://www.cveoy.top/t/topic/pcRr 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录