### Python 实现 LL(1) 词法分析器 LL(1) 文法是一种上下文无关文法，其中 L 表示从左到右扫描输入字符串，第一个 L 表示最左侧推导，而数字 1 则表示只需查看下一个输入符号即可决定应用哪个产生式。以下是基于 Python 的 LL(1) 词法分析器的实现方法。 #### 1. 构建 LL(1) 分析器的核心逻辑 为了构建一个完整的 LL(1) 分析器，需要以下几个部分： - **定义终结符和非终结符集合** - **计算 FIRST 集合和 FOLLOW 集合** - **生成预测分析表** - **编写解析函数** 以下是一个简单的实现案例： ```python class LL1Parser: def __init__(self, productions): self.productions = productions self.non_terminals = list(productions.keys()) self.terminals = set() for production in productions.values(): for p in production: for symbol in p: if not symbol.isupper() and symbol != 'ε': self.terminals.add(symbol) self.first_set = {} self.follow_set = {} self.parse_table = {} def compute_first(self): """ 计算 FIRST 集 """ changed = True while changed: changed = False for nt in self.non_terminals: if nt not in self.first_set: self.first_set[nt] = set() for prod in self.productions[nt]: if prod == 'ε': self.first_set[nt].add('ε') continue for sym in prod: if sym in self.terminals: if sym not in self.first_set[nt]: self.first_set[nt].add(sym) changed = True break elif sym in self.non_terminals: for f in self.first_set.get(sym, []): if f != 'ε' and f not in self.first_set[nt]: self.first_set[nt].add(f) changed = True if 'ε' not in self.first_set.get(sym, []): break else: if 'ε' not in self.first_set[nt]: self.first_set[nt].add('ε') changed = True def compute_follow(self, start_symbol='S'): """ 计算 FOLLOW 集 """ for nt in self.non_terminals: self.follow_set[nt] = set() self.follow_set[start_symbol].add('$') changed = True while changed: changed = False for nt in self.non_terminals: for prod in self.productions.items(): lhs, rhs_list = prod for rhs in rhs_list: for i, sym in enumerate(rhs): if sym == nt: following_symbols = rhs[i + 1:] first_of_following = set() all_epsilon = True for s in following_symbols: if s in self.terminals: first_of_following.add(s) all_epsilon = False break elif s in self.non_terminals: first_of_s = self.first_set[s] first_of_following.update(first_of_s.difference({'ε'})) if 'ε' not in first_of_s: all_epsilon = False break if all_epsilon: first_of_following.update(self.follow_set[lhs]) new_elements = first_of_following.difference(self.follow_set[nt]) if new_elements: self.follow_set[nt].update(new_elements) changed = True def build_parse_table(self): """ 建立预测分析表 """ for non_terminal in self.non_terminals: for terminal in self.terminals.union({'$'}): self.parse_table[(non_terminal, terminal)] = [] for production in self.productions[non_terminal]: first_of_production = set() if production == 'ε': first_of_production.update(self.follow_set[non_terminal]) else: for symbol in production: if symbol in self.terminals: first_of_production.add(symbol) break elif symbol in self.non_terminals: first_of_production.update(self.first_set[symbol].difference({'ε'})) if 'ε' not in self.first_set[symbol]: break for symbol in first_of_production: self.parse_table[(non_terminal, symbol)].append((non_terminal, production)) def parse(self, input_string): stack = ['$', self.non_terminals[0]] index = 0 output = [] while stack[-1] != '$': top = stack[-1] current_input = input_string[index] if index < len(input_string) else '$' if top in self.terminals or top == '$': if top == current_input: stack.pop() index += 1 else: return None # Error elif (top, current_input) in self.parse_table: rule = self.parse_table[(top, current_input)][0][1] output.append(rule) if rule != 'ε': symbols_to_push = list(reversed(rule)) if isinstance(rule, str) else reversed(rule.split()) for symbol in symbols_to_push: stack.append(symbol) stack.pop() else: return None # Error return output # 定义文法规则 productions = { 'E': ['Te', 'T'], 'e': ['+Te', '-Te', 'ε'], 'T': ['Ft', 'F'], 't': ['*Ft', '/Ft', 'ε'], 'F': ['(E)', 'i'] } parser = LL1Parser(productions) parser.compute_first() parser.compute_follow() parser.build_parse_table() input_str = "i+i*i" result = parser.parse(input_str) if result is not None: print("Parse successful:", result) else: print("Parsing failed.") ``` 此代码实现了 LL(1) 解析器的主要功能[^3]。 --- ### 关键概念解释 1. **FIRST 和 FOLLOW 集** - `FIRST` 是指某个非终结符可能派生的第一个终端符号集合。 - `FOLLOW` 是指某非终结符之后可能出现的终端符号集合。 2. **预测分析表** 使用 `FIRST` 和 `FOLLOW` 来填充预测分析表，用于指导解析过程中的动作选择。 3. **解析栈** 栈顶始终是非终结符或特殊标记 `$`，当匹配成功时逐步弹出并替换为相应的产生式右侧内容。 ---