如何将正则表达式(12)*[34]+(5[67])*转换为左递归文法？

原正则表达式 #

给定正则表达式：(12)*[34]+(5[67])*，其匹配的字符串规则为：

• 开头是零次或多次重复的"12"
• 中间是至少一次的"3"或"4"（可任意组合）
• 结尾是零次或多次重复的"56"或"57"

你提供的文法问题分析 #

你写出的文法：

G --> GAB34C
A --> A12 | epsilon
B --> B34 | epsilon
C --> C56 | C57 | epsilon

存在两处核心问题：

• 起始产生式G --> GAB34C会导致推导陷入无限循环，且无法生成符合规则的基础串（比如单独的"3"或"4"）
• B的定义只能生成重复的"34"组合，无法匹配单独的"3"、"4"或者"33"、"44"这类情况，不符合[34]+的要求

正确的左递归文法构造 #

我们可以将正则表达式拆分为三个逻辑部分，分别构造左递归产生式后整合为完整文法：

# 起始符号，生成整个符合规则的字符串
G --> G12 | H

# 生成中间的[34]+部分，以及后续的(5[67])*部分
H --> H3 | H4 | I

# 生成结尾的(5[67])*部分
I --> I56 | I57 | ε

文法解释 #

• G的产生式：G --> G12 | H，表示要么在已有合法串前追加"12"（对应(12)*的重复规则），要么直接生成不含前缀"12"的基础合法串H
• H的产生式：H --> H3 | H4 | I，表示要么在已有串前追加"3"或"4"（对应[34]+的重复规则），要么直接生成仅含单个"3"/"4"加结尾部分的基础串I
• I的产生式：I --> I56 | I57 | ε，表示要么在已有结尾串前追加"56"或"57"（对应(5[67])*的重复规则），要么生成空串（即无结尾部分）

该文法为标准左递归结构，生成的语言完全匹配原正则表达式的规则。

内容的提问来源于stack exchange，提问作者kiwi kiwi