使用python GUI实现任意文法消除左递归和回溯的算法程序

以下是使用Python Tkinter GUI实现任意文法消除左递归和回溯算法的示例代码：

from tkinter import *

# Function to eliminate left recursion from grammar
def eliminate_left_recursion(grammar):
    non_terminals = list(grammar.keys())
    for i in range(len(non_terminals)):
        for j in range(i):
            A = non_terminals[i]
            B = non_terminals[j]
            productions = grammar[A]
            new_productions = []
            old_productions = []
            for production in productions:
                if production.startswith(B):
                    new_productions.append(production[1:] + A + "'")
                else:
                    old_productions.append(production + A + "'")
            if new_productions:
                grammar[A] = old_productions
                grammar[A + "'"] = new_productions
    return grammar

# Function to eliminate left recursion and left factoring from grammar
def eliminate_left_recursion_and_left_factoring(grammar):
    # Eliminate left recursion first
    non_terminals = list(grammar.keys())
    for i in range(len(non_terminals)):
        for j in range(i):
            A = non_terminals[i]
            B = non_terminals[j]
            productions = grammar[A]
            new_productions = []
            old_productions = []
            for production in productions:
                if production.startswith(B):
                    new_productions.append(production[1:] + A + "'")
                else:
                    old_productions.append(production + A + "'")
            if new_productions:
                grammar[A] = old_productions
                grammar[A + "'"] = new_productions
    # Eliminate left factoring next
    non_terminals = list(grammar.keys())
    for A in non_terminals:
        productions = grammar[A]
        new_productions = []
        old_productions = []
        while len(productions) > 1:
            alpha = set()
            for production in productions:
                alpha.add(production[0])
            common_prefix = ''
            for i in range(len(productions[0])):
                if all(production[i] == productions[0][i] for production in productions):
                    common_prefix += productions[0][i]
                else:
                    break
            if common_prefix:
                new_non_terminal = A + "'"
                new_production = common_prefix + new_non_terminal
                new_productions.append(new_production)
                old_productions = [production[len(common_prefix):] for production in productions]
                old_productions.append('')
                grammar[A] = old_productions
                grammar[new_non_terminal] = new_productions
                productions = old_productions
            else:
                new_productions.append(productions.pop(0))
        if productions:
            new_productions.append(productions[0])
        grammar[A] = new_productions
    return grammar

# Function to display the grammar in the GUI
def display_grammar(grammar, text_widget):
    text_widget.delete(1.0, END)
    for non_terminal, productions in grammar.items():
        text_widget.insert(END, non_terminal + " -> ")
        for production in productions:
            text_widget.insert(END, production + " | ")
        text_widget.delete("end-2c", "end")
        text_widget.insert(END, "\n")

# Function to handle button click event
def handle_click(grammar_textbox, result_textbox, eliminate_left_recursion_var, eliminate_left_factoring_var):
    # Parse the grammar input
    input_text = grammar_textbox.get(1.0, END).strip()
    grammar = {}
    for line in input_text.split('\n'):
        non_terminal, productions = line.split(' -> ')
        grammar[non_terminal] = [p.strip() for p in productions.split('|')]
    # Eliminate left recursion and/or left factoring as requested
    if eliminate_left_recursion_var.get():
        grammar = eliminate_left_recursion(grammar)
    if eliminate_left_factoring_var.get():
        grammar = eliminate_left_recursion_and_left_factoring(grammar)
    # Display the result
    display_grammar(grammar, result_textbox)

# Create the GUI
root = Tk()
root.title("Eliminate Left Recursion and Left Factoring")

# Create the input box for the grammar
grammar_label = Label(root, text="Enter the grammar:")
grammar_label.pack()
grammar_textbox = Text(root, height=10)
grammar_textbox.pack()

# Create the checkboxes for left recursion and left factoring
eliminate_left_recursion_var = BooleanVar()
eliminate_left_recursion_checkbox = Checkbutton(root, text="Eliminate Left Recursion", variable=eliminate_left_recursion_var)
eliminate_left_recursion_checkbox.pack()
eliminate_left_factoring_var = BooleanVar()
eliminate_left_factoring_checkbox = Checkbutton(root, text="Eliminate Left Factoring", variable=eliminate_left_factoring_var)
eliminate_left_factoring_checkbox.pack()

# Create the button to perform the elimination
eliminate_button = Button(root, text="Eliminate", command=lambda: handle_click(grammar_textbox, result_textbox, eliminate_left_recursion_var, eliminate_left_factoring_var))
eliminate_button.pack()

# Create the output box for the result
result_label = Label(root, text="Result:")
result_label.pack()
result_textbox = Text(root, height=10)
result_textbox.pack()

# Start the GUI
root.mainloop()

该程序使用Tkinter库创建了一个简单的GUI窗口，其中包含一个文本框用于输入文法，两个复选框用于选择要执行的算法，一个按钮用于执行算法，并且另一个文本框用于显示结果。

算法本身实现为两个函数，一个用于仅消除左递归，另一个用于同时消除左递归和左公共因子。这些函数接受一个文法字典作为输入，并返回一个修改后的文法字典作为输出。

处理点击事件的函数从输入文本框中解析文法，根据复选框的状态选择要执行的算法，并将结果显示在输出文本框中。

最后，使用mainloop()函数启动GUI。