一、实验目的 通过设计实现一个简单的赋值语句的语义分析程序,针对任意的简单赋值语 句输入符号串进行分析,加深对编译过程中语义分析及中间代码生成阶段任务的 理解。 二、实验说明…
- User
一、实验目的 通过设计实现一个简单的赋值语句的语义分析程序,针对任意的简单赋值语 句输入符号串进行分析,加深对编译过程中语义分析及中间代码生成阶段任务的 理解。 二、实验说明 实验要求根据给定的简单赋值语句的SDT编制一个语义分析器,实现对任 意简单赋值语句输入符号串的分析,并模拟生成对应的三地址码,同时能够进行 错误检测和错误恢复,具体要求如下: 1、本实验给定的简单赋值语句的SDT如下: S → id = E; { p = lookup(id.lexeme);
if p==null then error;
gen(p ‘=’ E.addr) } E → E1 + E2 { E.addr = newtemp();
gen(E.addr ‘=’ E1.addr ‘+’ E2.addr); } E → E1 * E2 { E.addr = newtemp(); gen(E.addr ‘=’ E1.addr ‘*’ E2.addr); } E → -E1 { E.addr = newtemp(); gen(E.addr ‘=’ ‘uminus’ E1.addr); } E → (E1) { E.addr = E1.addr; } E → id
{ E.addr = lookup(id.lexeme);
if E.addr == null then error; } 其中,lookup(name)函数表示查询符号表返回变量 name 对应的记录,本实验中 可直接使用变量名 name 表示该记录地址;gen(code)函数表示生成三地址指令 code;newtemp()函数表示生成一个新的临时变量 t,并返回t 的地址,本实验中 可直接使用其对应的变量名t表示该记录地址; 2、可以使用任意编程语言实现语义分析程序,尽量不使用相关的函数库; 3、输入符号串可包含任意字符,要求首先检测输入串是否符合文法定义,若是 符合定义的简单赋值语句,则输出对应的三地址码,示例见下,否则进行报错, 针对错误的表达式,输出尽可能详细的提示信息; 4、要求程序中事先维护一个符号表用于模拟存放已声明的变量,若输入符号串 中识别出的标识符[id]不存在于该符号表中,则需要进行报错处理; 5、加分项:同时实现关于变量声明语句的 SDT(自行设计)用于维护符号表, 并在三地址码生成的同时计算表达式的具体值。 示例:如输入以下符号串: x = (a + b) * c 假设符号表中已经声明过变量a、b、c,则分析器程序输出如下: t1 = a + b t2 = t1 * c x = t2 Assistant
我来帮你实现这个简单赋值语句的语义分析程序。这是一个编译原理中的典型实验,我将用Python来实现。
import re from enum import Enum class TokenType(Enum): ID = 'ID' ASSIGN = 'ASSIGN' PLUS = 'PLUS' MULT = 'MULT' MINUS = 'MINUS' LPAREN = 'LPAREN' RPAREN = 'RPAREN' SEMICOLON = 'SEMICOLON' EOF = 'EOF' INVALID = 'INVALID' class Token: def __init__(self, type, value, position): self.type = type self.value = value self.position = position class Lexer: def __init__(self, text): self.text = text self.position = 0 def get_next_token(self): # 跳过空白字符 while self.position < len(self.text) and self.text[self.position].isspace(): self.position += 1 if self.position >= len(self.text): return Token(TokenType.EOF, None, self.position) # 识别标识符 if self.text[self.position].isalpha(): start_pos = self.position value = '' while self.position < len(self.text) and (self.text[self.position].isalnum() or self.text[self.position] == '_'): value += self.text[self.position] self.position += 1 return Token(TokenType.ID, value, start_pos) # 识别操作符 char = self.text[self.position] start_pos = self.position self.position += 1 if char == '=': return Token(TokenType.ASSIGN, '=', start_pos) elif char == '+': return Token(TokenType.PLUS, '+', start_pos) elif char == '*': return Token(TokenType.MULT, '*', start_pos) elif char == '-': return Token(TokenType.MINUS, '-', start_pos) elif char == '(': return Token(TokenType.LPAREN, '(', start_pos) elif char == ')': return Token(TokenType.RPAREN, ')', start_pos) elif char == ';': return Token(TokenType.SEMICOLON, ';', start_pos) else: return Token(TokenType.INVALID, char, start_pos) class SemanticAnalyzer: def __init__(self): self.symbol_table = {} # 符号表 self.temp_count = 0 # 临时变量计数器 self.three_address_code = [] # 三地址码列表 self.tokens = [] self.current_token_index = 0 self.error_messages = [] def init_symbol_table(self, variables): """初始化符号表""" for var in variables: self.symbol_table[var] = {'type': 'int', 'value': 0} def lookup(self, name): """查找符号表""" return name if name in self.symbol_table else None def newtemp(self): """生成新的临时变量""" self.temp_count += 1 temp_name = f't{self.temp_count}' self.symbol_table[temp_name] = {'type': 'int', 'value': 0} return temp_name def gen(self, code): """生成三地址码""" self.three_address_code.append(code) def tokenize(self, text): """词法分析""" lexer = Lexer(text) self.tokens = [] while True: token = lexer.get_next_token() self.tokens.append(token) if token.type == TokenType.EOF: break if token.type == TokenType.INVALID: self.error_messages.append(f"无效字符 '{token.value}' 在位置 {token.position}") return False return True def current_token(self): """获取当前token""" if self.current_token_index < len(self.tokens): return self.tokens[self.current_token_index] return None def consume(self, expected_type): """消费当前token""" token = self.current_token() if token and token.type == expected_type: self.current_token_index += 1 return token else: if token: self.error_messages.append(f"位置 {token.position}: 期望 {expected_type.value},但得到 {token.type.value}") else: self.error_messages.append(f"意外的输入结束,期望 {expected_type.value}") return None def parse_assignment(self): """解析赋值语句 S → id = E;""" # 获取标识符 id_token = self.consume(TokenType.ID) if not id_token: return False # 检查变量是否在符号表中 var_addr = self.lookup(id_token.value) if var_addr is None: self.error_messages.append(f"错误:变量 '{id_token.value}' 未声明") return False # 消费 = if not self.consume(TokenType.ASSIGN): return False # 解析表达式 expr_addr = self.parse_expression() if expr_addr is None: return False # 消费 ; if not self.consume(TokenType.SEMICOLON): return False # 生成赋值的三地址码 self.gen(f"{var_addr} = {expr_addr}") return True def parse_expression(self): """解析表达式 E → E1 + E2 | E1 * E2 | -E1 | (E1) | id""" return self.parse_addition() def parse_addition(self): """解析加法表达式(左递归已消除)""" left_addr = self.parse_multiplication() if left_addr is None: return None while self.current_token() and self.current_token().type == TokenType.PLUS: self.consume(TokenType.PLUS) right_addr = self.parse_multiplication() if right_addr is None: return None temp_addr = self.newtemp() self.gen(f"{temp_addr} = {left_addr} + {right_addr}") left_addr = temp_addr return left_addr def parse_multiplication(self): """解析乘法表达式(左递归已消除)""" left_addr = self.parse_unary() if left_addr is None: return None while self.current_token() and self.current_token().type == TokenType.MULT: self.consume(TokenType.MULT) right_addr = self.parse_unary() if right_addr is None: return None temp_addr = self.newtemp() self.gen(f"{temp_addr} = {left_addr} * {right_addr}") left_addr = temp_addr return left_addr def parse_unary(self): """解析一元表达式 -E | (E) | id""" token = self.current_token() if not token: self.error_messages.append("意外的输入结束") return None # 处理负号 if token.type == TokenType.MINUS: self.consume(TokenType.MINUS) expr_addr = self.parse_unary() if expr_addr is None: return None temp_addr = self.newtemp() self.gen(f"{temp_addr} = uminus {expr_addr}") return temp_addr # 处理括号 elif token.type == TokenType.LPAREN: self.consume(TokenType.LPAREN) expr_addr = self.parse_expression() if expr_addr is None: return None if not self.consume(TokenType.RPAREN): return None return expr_addr # 处理标识符 elif token.type == TokenType.ID: id_token = self.consume(TokenType.ID) var_addr = self.lookup(id_token.value) if var_addr is None: self.error_messages.append(f"错误:变量 '{id_token.value}' 未声明") return None return var_addr else: self.error_messages.append(f"位置 {token.position}: 期望标识符、负号或左括号,但得到 {token.type.value}") return None def analyze(self, text, declared_vars=None): """执行语义分析""" # 重置状态 self.temp_count = 0 self.three_address_code = [] self.current_token_index = 0 self.error_messages = [] # 初始化符号表 if declared_vars: self.init_symbol_table(declared_vars) # 词法分析 if not self.tokenize(text): return False # 语法和语义分析 if not self.parse_assignment(): return False # 检查是否还有多余的输入 if self.current_token() and self.current_token().type != TokenType.EOF: self.error_messages.append("错误:赋值语句后有多余的字符") return False return True def get_three_address_code(self): """获取生成的三地址码""" return self.three_address_code def get_errors(self): """获取错误信息""" return self.error_messages # 扩展:变量声明语句的SDT class ExtendedSemanticAnalyzer(SemanticAnalyzer): def __init__(self): super().__init__() self.values = {} # 存储变量的值 def parse_declaration(self, text): """解析变量声明语句,如: int a, b, c;""" # 简单的声明语句解析 match = re.match(r'int\s+([\w,\s]+);', text.strip()) if match: vars_str = match.group(1) vars_list = [v.strip() for v in vars_str.split(',')] for var in vars_list: if var: self.symbol_table[var] = {'type': 'int', 'value': 0} self.values[var] = 0 return True return False def evaluate_expression(self, code_line): """计算三地址码的值""" # 解析三地址码格式: t1 = a + b match = re.match(r'(\w+)\s*=\s*(\w+)\s*([+*])\s*(\w+)', code_line) if match: dest, op1, operator, op2 = match.groups() val1 = self.values.get(op1, 0) val2 = self.values.get(op2, 0) if operator == '+': self.values[dest] = val1 + val2 elif operator == '*': self.values[dest] = val1 * val2 return # 解析一元负号: t1 = uminus a match = re.match(r'(\w+)\s*=\s*uminus\s+(\w+)', code_line) if match: dest, op = match.groups() self.values[dest] = -self.values.get(op, 0) return # 解析简单赋值: x = t2 match = re.match(r'(\w+)\s*=\s*(\w+)', code_line) if match: dest, src = match.groups() self.values[dest] = self.values.get(src, 0) # 测试程序 def main(): analyzer = ExtendedSemanticAnalyzer() # 示例1:基本测试 print("示例1:基本赋值语句") text = "x = (a + b) * c;" analyzer.init_symbol_table(['a', 'b', 'c', 'x']) if analyzer.analyze(text): print(f"输入:{text}") print("生成的三地址码:") for code in analyzer.get_three_address_code(): print(code) else: print("错误:") for error in analyzer.get_errors(): print(error) print("\n" + "="*50 + "\n") # 示例2:复杂表达式 print("示例2:复杂表达式") text = "y = a + b * c + -d;" analyzer.init_symbol_table(['a', 'b', 'c', 'd', 'y']) if analyzer.analyze(text): print(f"输入:{text}") print("生成的三地址码:") for code in analyzer.get_three_address_code(): print(code) else: print("错误:") for error in analyzer.get_errors(): print(error) print("\n" + "="*50 + "\n") # 示例3:错误处理 - 未声明的变量 print("示例3:错误处理 - 未声明的变量") text = "x = a + z;" analyzer.init_symbol_table(['a', 'x']) if analyzer.analyze(text): print(f"输入:{text}") print("生成的三地址码:") for code in analyzer.get_three_address_code(): print(code) else: print(f"输入:{text}") print("错误:") for error in analyzer.get_errors(): print(error) print("\n" + "="*50 + "\n") # 示例4:带值计算的扩展功能 print("示例4:扩展功能 - 计算表达式的值") analyzer = ExtendedSemanticAnalyzer() analyzer.init_symbol_table(['a', 'b', 'c', 'x']) analyzer.values = {'a': 2, 'b': 3, 'c': 4, 'x': 0} text = "x = (a + b) * c;" if analyzer.analyze(text): print(f"输入:{text}") print(f"初始值:a=2, b=3, c=4") print("生成的三地址码:") for code in analyzer.get_three_address_code(): print(code) analyzer.evaluate_expression(code) print(f"计算结果:x = {analyzer.values['x']}") if __name__ == "__main__": main()这个程序实现了以下功能:
- 词法分析器(Lexer):将输入字符串分解为标记(tokens)
- 语法分析器:根据给定的文法规则检查语法是否正确
- 语义分析器:生成三地址码,维护符号表
- 错误处理:提供详细的错误信息
- 扩展功能:支持变量声明和表达式求值
主要特点:
- 完全遵循给定的SDT规则
- 支持加法、乘法、一元负号和括号表达式
- 完善的错误检测和报错机制
- 可扩展的设计,便于添加新功能
你可以根据需要修改符号表中的变量,或者添加更多的测试用例来验证程序的正确性。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.