current position:Home>Elimination of grammar left recursion in Python
Elimination of grammar left recursion in Python
2022-02-02 00:59:32 【The CSDN next door is new】
Preface
- After lexical analysis , Then comes the category of grammatical analysis . Several sub problems need to be solved to complete syntax analysis , Complete the elimination of grammar left recursion today .
- Didn't learn from any blogs , Make your own wheels .
Before the start
- The core of grammar left recursion elimination program is the processing of string , Enter the production as a string , Split it 、 Replace and merge operations run through , The logic and thinking of the processing process will be full of loopholes if there are slight mistakes and omissions .
- use Direct rewriting method , It's hard to read the code without understanding the left recursive elimination method .
requirement
- CFG Grammar judgment
- Left recursive type
- Left recursion and indirect recursion
- Interface
Source code
import os
import tkinter as tk
import tkinter.messagebox
import tkinter.font as tf
zhuizhong = ""
wenfa = {" Non left recursive grammar "}
xi_ = ""
huo = ""
window = tk.Tk()
window.title(' Eliminate left recursion ')
window.minsize(500,500)
# The converted coordinates are displayed as tuples
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(" Non left recursive grammar ")
# Handle direct left recursion
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:# Handle A -> Ax The situation of
zhongjie.append(str(x + "'"))
cheng = str(x) + " -> " + "|".join(zhongjie)
zi = str(x) + "'" + " -> " + "|".join(feizhongjie) + "|є"
text_output.insert('insert',' Direct left recursive grammar ','tag1')
text_output.insert('insert','\n')
text_output.insert('insert',cheng,'tag2')
text_output.insert('insert','\n')
text_output.insert('insert',zi,'tag2')
''' In addition, it will judge the output of non recursive production , However, it will lead to indirect left recursion and cannot delete redundant production else: h =" unchanged : " + x + " -> " + y text_output.insert('insert',' Non left recursive grammar ','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(" Non left recursive grammar ")
# Handle direct left recursion
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'," Indirect left recursive grammar ",'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('|')# Separate non terminality from non terminality
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)# Replace
yi_feizhong.append(yi_zhong)
yi_wuhe = "|".join(yi_wu)# Re merger
global zhuizhong
zhuizhong = "|".join(yi_feizhong) + "|" + yi_wuhe
# The function executed after clicking the button
def changeString():
text_output.delete('1.0','end')
text = text_input.get('1.0','end')
text_list = list(text.split('\n'))# Line by line grammar
text_list.pop()
if not text_list[0]:
print(tkinter.messagebox.showerror(title = ' Something went wrong !',message=' Input cannot be empty '))
else:
for cfg in text_list:
x,y = cfg.split('->')# Separate grammar from left and right
x = ''.join(x.split())# Eliminate spaces
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 = ' Something went wrong !',
message=' Non context free grammar ! coordinate %s'%(getIndex(text_input, pos),))
# The return value is :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())# Eliminate spaces
yi = ''.join(yi.split())
xk,yk = text_list[k].split('->')
xk = ''.join(xk.split())# Eliminate spaces
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')
# Create text input boxes and buttons
text_input = tk.Text(window, width=80, height=16)
text_output = tk.Text(window, width=80, height=20)
# Simple style
ft = tf.Font(family=' Microsoft YaHei ',size=12)
text_output.tag_config("tag1",background="yellow",foreground="red",font=ft)
text_output.tag_config('tag2',font = ft)
# Button
button = tk.Button(window,text=" Eliminate left recursion ",command=changeString,padx=32,pady=4,bd=4)
text_input.pack()
text_output.pack()
button.pack()
window.mainloop()
Copy code
Is it difficult to understand , Take a look at the flow chart of half hanging son
- Main process
- Direct left recursion
- Indirect left recursive merge
Run a screenshot
summary
(1) Orient
It's not hard to do one thing , The hardest thing is that there is no direction , I don't know what to do ; I just feel that time goes by, but I don't produce anything . Fortunately, there are specific topics to choose from , This time, after a little entanglement , Decisively choose grammar left recursion to eliminate , Tell the truth , I think this is the simplest .
(2) Start implementation
First, understand the method of eliminating left recursion thoroughly , Found that the essence of the program is the operation of strings . Complete the direct left recursive algorithm very smoothly , I am rigorous and step by step , Hardly any bug, The follow-up test only adds the judgment of some edge conditions , For example, null value , Let the program face complex production easily . The algorithm of merging the production of indirect left recursion is also very smooth , Because I have outlined on the draft paper what I need to get at each step , When writing code, , One output at a time , See if it meets expectations , Subsequent tests slightly improved robustness . The real difficulty lies in the idea , Even the outermost two iterations have been considered for a long time . The logic and thinking of these two algorithms are very complex , The opening and closing of strings , Store separately , Use no less than ten list and string data types , Plus a few global variables , I'm a little proud of my clear thinking .
(3) deficiencies
1、 I hope to achieve , Non left recursive grammar , The input of left recursion and indirect left recursion is recognized and eliminated together , When you encounter a non left recursive grammar, you output “ Non left recursive grammar ”, Then output it without any modification . If you implement this , How to make indirect left recursion not be treated as non left recursion grammar ? I didn't think of a solution . 2、 My judgment of non terminator is whether it contains , No further judgment of location , For example, eliminate D -> Dh|sD|h,D stay s after , This can't be handled well . 3、 The input order of indirect left recursive grammar production is required , I haven't been able to input freely yet .
(4) Problems encountered
The problems I encounter are all about the overall structure and trade-offs , For example, I finally chose to use two loops for input , One is to iterate over one production , Eliminate direct left recursion , The second one combines indirect left recursion with subscript nested two-level loops from the beginning . In addressing deficiencies 1 when , I spent a lot of time , Tried everything , For example, global variables , aggregate , Even back up the code , Make major changes , In the end, they compromised . When writing two core algorithms , What data type do I get at each step , Get what , Are very careful to confirm , Step by step , Didn't show up “bug Find a day ” The situation of . Each step requires a new variable storage , I'll add one at the beginning of the method ,tihuan() This method has six variables , Now that I think about it , The space complexity is very high .
(5) summary
This design is completely independent , No reference to any blog , I also know that some things that I think are very difficult are not worth mentioning in front of Daniel , Perhaps the overall architecture of the program is far from . in any case , I did what the title required , And it doesn't take long , I still have a sense of achievement . however , I will never be proud , There is no proud capital . Draw the interface from , Receive text input , Take the production , Judgment type , Eliminate direct left recursion , Merge indirect left recursion and then eliminate indirect left recursion . properly and logically arranged , One step at a time , Only by doing so can the building rise from the ground .
copyright notice
author[The CSDN next door is new],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/02/202202020059269436.html
The sidebar is recommended
- How IOS developers learn Python Programming 22 - Supplement 1
- Python can meet any API you need
- Python 3 process control statement
- The 20th of 120 Python crawlers, 1637. All the way business opportunity network joined in data collection
- Datetime of pandas time series preamble
- How to send payslips in Python
- [Python] closure and scope
- Application of Python Matplotlib color
- leetcode 1627. Graph Connectivity With Threshold (python)
- Python thread 08 uses queues to transform the transfer scenario
guess what you like
-
Python: simple single player strange game (text)
-
Daily python, chapter 27, Django template
-
TCP / UDP communication based on Python socket
-
Use of pandas timestamp index
-
leetcode 148. Sort List(python)
-
Confucius old book network data collection, take one anti three learning crawler, python crawler 120 cases, the 21st case
-
[HTB] cap (datagram analysis, setuid capability: Python)
-
How IOS developers learn Python Programming 23 - Supplement 2
-
How to automatically identify n + 1 queries in Django applications (2)?
-
Data analysis starts from scratch. Pandas reads HTML pages + data processing and analysis
Random recommended
- 1313. Unzip the coding list (Java / C / C + + / Python / go / trust)
- Python Office - Python edit word
- Collect it quickly so that you can use the 30 Python tips for taking off
- Strange Python strip
- Python crawler actual combat, pyecharts module, python realizes China Metro data visualization
- DOM breakpoint of Python crawler reverse
- Django admin custom field stores links in the database after uploading files to the cloud
- Who has powder? Just climb who! If he has too much powder, climb him! Python multi-threaded collection of 260000 + fan data
- Python Matplotlib drawing streamline diagram
- The game comprehensively "invades" life: Python releases the "cool run +" plan!
- Python crawler notes: use proxy to prevent local IP from being blocked
- Python batch PPT to picture, PDF to picture, word to picture script
- Advanced face detection: use Dlib, opencv and python to detect face markers
- "Python 3 web crawler development practice (Second Edition)" is finally here!!!!
- Python and Bloom filters
- Python - singleton pattern of software design pattern
- Lazy listening network, audio novel category data collection, multi-threaded fast mining cases, 23 of 120 Python crawlers
- Troubleshooting ideas and summary of Django connecting redis cluster
- Python interface automation test framework (tools) -- interface test tool requests
- Implementation of Morse cipher translator using Python program
- [Python] numpy notes
- 24 useful Python tips
- Pandas table beauty skills
- Python tiktok character video, CV2 module, Python implementation
- I used Python to climb my wechat friends. They are like this
- 20000 words take you into the python crawler requests library, the most complete in history!!
- Answer 2: why can you delete the table but not update the data with the same Python code
- [pandas learning notes 02] - advanced usage of data processing
- How to implement association rule algorithm? Python code and powerbi visualization are explained to you in detail (Part 2 - actual combat)
- Python adds list element append() method, extend() method and insert() method [details]
- python wsgi
- Introduction to Python gunicorn
- Python dictionary query key value pair methods and examples
- Opencv Python reads video, processes and saves it frame by frame
- Python learning process and bug
- Imitate the up master and realize a live broadcast room controlled by barrage with Python!
- Essence! Configuration skills of 12 pandas
- [Python automated operation and maintenance road] path inventory
- Daily automatic health punch in (Python + Tencent cloud server)
- [Python] variables, comments, basic data types