當前位置：首頁 > 编程语言 > python >内容正文

python

消除左递归c++代码_python实现文法左递归的消除

發布時間：2024/9/30 python 24 豆豆

生活随笔收集整理的這篇文章主要介紹了消除左递归c++代码_python实现文法左递归的消除小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

前言

繼詞法分析后，又來到語法分析范疇。完成語法分析需要解決幾個子問題，今天就完成文法左遞歸的消除。

沒借鑒任何博客，完全自己造輪子。

開始之前

文法左遞歸消除程序的核心是對字符串的處理，輸入的產生式作為字符串，對它的拆分、替換與合并操作貫穿始終，處理過程的邏輯和思路稍有錯漏便會漏洞百出。

采用直接改寫法，不理解左遞歸消除方法很難讀懂代碼。

要求

CFG文法判斷

左遞歸的類型

消除直接左遞歸和間接左遞歸

界面

源碼

import os
import tkinter as tk
import tkinter.messagebox
import tkinter.font as tf

zhuizhong = ""
wenfa = {"非左遞歸文法"}
xi_ = ""
huo = ""

window = tk.Tk()
window.title('消除左遞歸')
window.minsize(500,500)
#轉換坐標顯示形式為元組
def getIndex(text, pos):
return tuple(map(int, str.split(text.index(pos), ".")))

def zhijie(x,y):
if not len(y):
pass
else:
if x == y[0]:
wenfa.discard("非左遞歸文法")
#處理直接左遞歸
zuobian = y.split('|')
feizhongjie = []
zhongjie = []
for item in zuobian:
if x in item:
item = item[1:]
textt = str(item) + str(x) + "'"
feizhongjie.append(textt)
else:
text = str(item) + str(x) + "'"
zhongjie.append(text)
if not zhongjie:#處理A -> Ax的情況
zhongjie.append(str(x + "'"))
cheng = str(x) + " -> " + "|".join(zhongjie)
zi = str(x) + "'" + " -> " + "|".join(feizhongjie) + "|?"
text_output.insert('insert','直接左遞歸文法','tag1')
text_output.insert('insert','\n')
text_output.insert('insert',cheng,'tag2')
text_output.insert('insert','\n')
text_output.insert('insert',zi,'tag2')
'''
加上會判斷輸出非遞歸產生式，但會導致間接左遞歸不能刪除多余產生式
else:
h ="不變：" + x + " -> " + y
text_output.insert('insert','非左遞歸文法','tag1')
text_output.insert('insert','\n')
text_output.insert('insert',h,'tag2')
'''
text_output.insert('insert','\n')

def zhijie2(x,y):
if not len(y):
pass
else:
if x == y[0]:
wenfa.discard("非左遞歸文法")
#處理直接左遞歸
zuobian = y.split('|')
feizhongjie = []
zhongjie = []
for item in zuobian:
if x in item:
item = item[1:]
textt = str(item) + str(x) + "'"
feizhongjie.append(textt)
else:
text = str(item) + str(x) + "'"
zhongjie.append(text)
cheng = str(x) + " -> " + "|".join(zhongjie)
zi = str(x) + "'" + " -> " + "|".join(feizhongjie) + "|?"
text_output.insert('insert',"間接左遞歸文法",'tag1')
text_output.insert('insert','\n')
text_output.insert('insert',cheng,'tag2')
text_output.insert('insert','\n')
text_output.insert('insert',zi,'tag2')

text_output.insert('insert','\n')

def tihuan(xk,yi,yk):
yi_you = []
yi_wu =[]
yi_he = ""
yi_wuhe = ""
yi_zhong = ""
yi_feizhong = []
if xk in yi:
yk_replace = yk.split('|')
yi_fenjie = yi.split('|')#將含非終結與不含分開
for ba in yi_fenjie:
if xk in ba:
yi_you.append(ba)
else:
yi_wu.append(ba)

yi_he = "|".join(yi_you)

for item in yk_replace:
yi_zhong = yi_he.replace(xk,item)#替換
yi_feizhong.append(yi_zhong)
yi_wuhe = "|".join(yi_wu)#再合并
global zhuizhong
zhuizhong = "|".join(yi_feizhong) + "|" + yi_wuhe

#點擊按鈕后執行的函數
def changeString():
text_output.delete('1.0','end')
text = text_input.get('1.0','end')
text_list = list(text.split('\n'))#一行一行的拿文法
text_list.pop()
if not text_list[0]:
print(tkinter.messagebox.showerror(title = '出錯了！',message='輸入不能為空'))
else:
for cfg in text_list:

x,y = cfg.split('->')#將文法左右分開
x = ''.join(x.split())#消除空格
y = ''.join(y.split())
if not (len(x) == 1 and x >= 'A' and x <= 'Z'):
pos = text_input.search(x, '1.0', stopindex="end")
result = tkinter.messagebox.showerror(title = '出錯了！',
message='非上下文無關文法!坐標%s'%(getIndex(text_input, pos),))
# 返回值為：ok
print(result)
return 0
else:
zhijie(x,y)

for i in range(len(text_list)):
for k in range(i):
xi,yi = text_list[i].split('->')
xi = ''.join(xi.split())#消除空格
yi = ''.join(yi.split())

xk,yk = text_list[k].split('->')
xk = ''.join(xk.split())#消除空格
yk = ''.join(yk.split())

tihuan(xk,yi,yk)
tihuan(xk,zhuizhong,yk)
global xi_
xi_ = xi
zhijie2(xi_,zhuizhong)

for item in wenfa:
text_output.insert('insert',item,'tag1')

#創建文本輸入框和按鈕
text_input = tk.Text(window, width=80, height=16)
text_output = tk.Text(window, width=80, height=20)
#簡單樣式
ft = tf.Font(family='微軟雅黑',size=12)
text_output.tag_config("tag1",background="yellow",foreground="red",font=ft)
text_output.tag_config('tag2',font = ft)
#按鈕
button = tk.Button(window,text="消除左遞歸",command=changeString,padx=32,pady=4,bd=4)

text_input.pack()
text_output.pack()
button.pack()
window.mainloop()

是不是很難懂，看看半吊子流程圖

主要流程
直接左遞歸
間接左遞歸合并

運行截圖

總結

(1)確定方向
做一件事并不難，最難的是沒有方向，不知道要做什么；只是感覺時光流逝自己卻一點東西都沒產出。幸好有具體的題目可供選擇，這一次我稍有糾結之后，果斷選擇文法左遞歸消除，說實話，我認為這個最簡單。(2)開始實現
首先將消除左遞歸的方法理解透徹，找到了程序的本質就是對字符串的操作。
完成直接左遞歸算法非常順利，我思路嚴謹步步為營，幾乎沒有bug，后續測試僅僅加上一些邊緣情況的判斷，比如空值，讓程序面對復雜產生式也游刃有余。
將間接左遞歸的產生式合并的算法也很順利，因為我在草稿紙上已經勾勒好了每一步需要得到什么，寫代碼時，一步一個輸出，看是否符合預期，后續測試稍微小補增強健壯性。真正難點在于構思思路，就連最外層兩個迭代都考慮了很久。
這兩個算法的邏輯和思路是很復雜的，字符串的分分合合，分別存儲，使用列表和字符串數據類型不下十個，再加上幾個全局變量，我對自己清晰的思路略感自豪。(3)不足之處
1、我希望能夠實現，非左遞歸文法，左遞歸和間接左遞歸的一起輸入一起識別一起消除，碰到非左遞歸文法就輸出“非左遞歸文法”，然后將其不做任何修改輸出。如果實現這個，如何讓間接左遞歸不被當做非左遞歸文法處理呢？我沒想到解決方案。
2、我對非終結符的判斷采用的是是否包含，沒有更進一步判斷位置，比如消除 D -> Dh|sD|h，D在s后，這就不能很好的處理。
3、對于間接左遞歸文法產生式的輸入順序是有要求的，還沒能做到隨意輸入。(4)遇到的問題
我遇到的問題都是關于整體結構和取舍妥協，比如我最終選擇將輸入使用兩個循環，一個是對一個個產生式進行迭代，消除直接左遞歸，第二個再從頭采用下標嵌套兩層循環來合并間接左遞歸。
在解決不足之處1時，我花了不少時間，用盡了方法，比如全局變量，集合，甚至還將代碼備份，進行較大改動，最后還是妥協了。
在寫兩個核心算法的時候，我每一步拿到什么數據類型，拿到什么內容，都很小心的確認，一步一步推進，沒出現“bug找一天”的情況。每到一步需要一個新的變量存儲，我就在方法最開始加一個，tihuan()這個方法就有六個變量，現在想來，空間復雜度挺高。(5)總結
這次的設計完全自主，沒有借鑒任何博客，我也知道可能有些我認為很難的東西在大牛面前都不值一提，或許程序整體架構就差之甚遠。無論如何，題目要求的東西我做到了，而且花的時間不算長，還是挺有成就感。但是，我絕對不會驕傲，根本沒有驕傲的資本。
從畫出界面，接收文本輸入，取到產生式，判斷類型，消除直接左遞歸，合并間接左遞歸再到消除間接左遞歸。有條有理，一步一個腳印，方能萬丈高樓平地起。

總結

以上是生活随笔為你收集整理的消除左递归c++代码_python实现文法左递归的消除的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： android activity启动流程
下一篇： java调用其他方法中的变量_Uipat