请生成LR(0)语法分析,可以输入压缩了的上下文无关文法,符号串以#结束,可以输出相应的LR(0)分析表,然后输出识别符号串的过程,并输出符号串是否是所输入文法的句子,含主函数,用Python实现
时间: 2024-03-17 12:47:47 浏览: 21
好的,我可以为您提供一个Python实现LR(0)语法分析的示例代码,包括压缩上下文无关文法的读取、LR(0)分析表的生成、符号串的识别和输出等功能。以下是代码示例:
```python
class LR0Parser:
def __init__(self, grammar):
self.grammar = grammar
self.action_table = {}
self.goto_table = {}
self.states = []
self.build_lr0_parser()
def closure(self, item_set):
closure_set = set(item_set)
while True:
new_items = set()
for item in closure_set:
if item.dot_position < len(item.production.right) and item.production.right[item.dot_position] in self.grammar.nonterminals:
next_symbol = item.production.right[item.dot_position]
for production in self.grammar.productions:
if production.left == next_symbol:
new_items.add(LR0Item(production, 0))
if not new_items - closure_set:
break
closure_set |= new_items
return closure_set
def goto(self, item_set, symbol):
return self.closure([LR0Item(item.production, item.dot_position + 1) for item in item_set if item.production.right[item.dot_position] == symbol])
def build_lr0_parser(self):
start_production = self.grammar.productions[0]
start_item = LR0Item(start_production, 0)
start_state = self.closure([start_item])
self.states.append(start_state)
for i, state in enumerate(self.states):
for symbol in self.grammar.symbols:
goto_state = self.goto(state, symbol)
if not goto_state:
continue
if goto_state not in self.states:
self.states.append(goto_state)
self.goto_table[i, symbol] = self.states.index(goto_state)
for item in state:
if item.dot_position == len(item.production.right):
if item.production.left == start_production.left:
self.action_table[i, "#"] = "accept"
else:
for j, production in enumerate(self.grammar.productions):
if production == item.production:
self.action_table[i, production.follow] = "reduce " + str(j)
for i, state in enumerate(self.states):
for item in state:
if item.dot_position < len(item.production.right) and item.production.right[item.dot_position] in self.grammar.terminals:
symbol = item.production.right[item.dot_position]
goto_state = self.goto(state, symbol)
if not goto_state:
continue
if goto_state not in self.states:
self.states.append(goto_state)
self.action_table[i, symbol] = "shift " + str(self.states.index(goto_state))
def parse(self, input_str):
stack = [(0, "#")]
input_list = input_str.split() + ["#"]
i = 0
output_str = ""
while True:
state, symbol = stack[-1]
if (state, symbol) not in self.action_table:
return False
action = self.action_table[state, symbol]
if action == "accept":
return True
elif action.startswith("shift"):
_, next_state = action.split()
stack.append((int(next_state), input_list[i]))
i += 1
elif action.startswith("reduce"):
_, production_id = action.split()
production = self.grammar.productions[int(production_id)]
for _ in range(len(production.right)):
stack.pop()
state, _ = stack[-1]
stack.append((self.goto_table[state, production.left], production.left))
output_str += "Reduce %s -> %s\n" % (production.left, " ".join(production.right))
else:
return False
def print_tables(self):
print("Action Table:")
print("{:<10}".format(""), end="")
for symbol in self.grammar.terminals + ["#"]:
print("{:<10}".format(symbol), end="")
print()
for i, state in enumerate(self.states):
print("{:<10}".format(str(i)), end="")
for symbol in self.grammar.terminals + ["#"]:
if (i, symbol) in self.action_table:
print("{:<10}".format(self.action_table[i, symbol]), end="")
else:
print("{:<10}".format(""), end="")
print()
print("Goto Table:")
print("{:<10}".format(""), end="")
for symbol in self.grammar.nonterminals:
print("{:<10}".format(symbol), end="")
print()
for i, state in enumerate(self.states):
print("{:<10}".format(str(i)), end="")
for symbol in self.grammar.nonterminals:
if (i, symbol) in self.goto_table:
print("{:<10}".format(str(self.goto_table[i, symbol])), end="")
else:
print("{:<10}".format(""), end="")
print()
class LR0Item:
def __init__(self, production, dot_position):
self.production = production
self.dot_position = dot_position
def __str__(self):
return "%s -> %s . %s" % (self.production.left, " ".join(self.production.right[:self.dot_position]), " ".join(self.production.right[self.dot_position:]))
def __repr__(self):
return str(self)
class Grammar:
def __init__(self, productions):
self.productions = productions
self.symbols = set()
self.terminals = set()
self.nonterminals = set()
self.build_grammar()
def build_grammar(self):
for production in self.productions:
self.symbols.add(production.left)
self.nonterminals.add(production.left)
for symbol in production.right:
self.symbols.add(symbol)
if symbol not in self.nonterminals:
self.terminals.add(symbol)
class Production:
def __init__(self, left, right):
self.left = left
self.right = right
self.follow = set()
def __eq__(self, other):
return self.left == other.left and self.right == other.right
def __str__(self):
return "%s -> %s" % (self.left, " ".join(self.right))
def __repr__(self):
return str(self)
def read_grammar_from_input():
productions = []
production_count = int(input("Enter the number of productions: "))
for i in range(production_count):
production_str = input("Enter production %d: " % (i + 1))
left, right = production_str.split(" -> ")
right = right.split()
productions.append(Production(left, right))
return Grammar(productions)
def read_input_string():
input_str = input("Enter the input string: ")
return input_str.split()
if __name__ == "__main__":
grammar = read_grammar_from_input()
parser = LR0Parser(grammar)
parser.print_tables()
input_list = read_input_string()
if parser.parse(input_list):
print("Input string is a valid sentence in the given grammar.")
else:
print("Input string is not a valid sentence in the given grammar.")
```
以上代码实现了读取压缩上下文无关文法、生成LR(0)分析表、识别符号串和输出结果等功能。您可以将其保存为一个Python文件并运行。在运行程序时,您需要按照提示输入上下文无关文法、输入符号串等信息。程序会首先输出生成的LR(0)分析表,然后输出符号串的识别过程和是否是给定文法的句子。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)