regex - 与此正则表达式等效的形式语法是什么？

Question

正则表达式是 (a+)+ 。使用 NFA 这会给更长的字符串带来reDOS 攻击。这个正则表达式的等效语法是什么？

现在我试图在多个步骤中确定语法。

a+ 将转换为

S -> a
S -> aS 

(a+)+ 将转化为

G -> S
G -> SG

我不确定如何进一步简化它是 CFG 还是 CSG ？任何建议都会有很大帮助

Answer 1

(a+)+相当于a+。一个可能的语法是

• S → A
• 一→一
• 一个 → 一个

语法是正则的（必须存在这样的语法，因为它是从正则表达式派生的）。因此，它也是上下文无关的，因此也是上下文相关的。