上下文无法语法识别正则表达式的问题

Question

ltr代表字母 lpar代表左括号 rpar代表右括号 star代表*  eps代表ε bar 代表|

题目是使用CFG去识别合法正则表达式输入： ab* 被识别成 lts lts star 能被CFG接受 *εa|b 被识别成 star eps ltr bar ltr，但是不被接受

我的CFG是：S-> ltr| S | lpar * S * rpar | ltr * star | S * eps * S | ε

Answer 1

参考GPT和自己的思路：

你的CFG看起来能够识别一个正则表达式的基本结构，但是有些地方需要做些改善。首先，对于左右括号的处理，应该在递归S时判断左右括号的位置。其次，在识别a|b这种选择结构时，你的CFG中没有考虑到将选择结构展开的情况。最终，你的CFG中需要添加一些终止符号的定义。

下面是一个更完整的、使用CFG识别正则表达式的例子:

S -> E | E bar S
E -> T | T star | T E
T -> ltr | lpar S rpar

其中，S表示正则表达式，E表示基本表达式，T表示因子（单元或组）。

对于终止符，你可以定义:

ltr -> 'a' | 'b' | ... | 'z' | 'A' | 'B' | ... | 'Z'
lpar -> '('
rpar -> ')'
star -> '*'
bar -> '|'
eps -> 'ε'

这样，对于输入的正则表达式，经过CFG的处理输出的结果就是2种情况，一个是能被接受的，一个是不能被接受的，这样就可以满足题目需求了。