表示BNF的正则表达式

Question

我正在开发一个lexer。我需要识别BNF中的模式，并使用正则表达式指定它们。我知道有TOKENS，例如关键字、标识符、运算符等。到目前为止，我已经定义了正则表达式：

digit=[0-9]
integer={digit}+
letter=[a-zA-Z]

但给定的标识符的BNF规则是：

< id > ::= < letter >
| "_"
| < id > < digit >
| < id > < letter >

由于<id>是由递归模式定义的，如何使用正则表达式来表达此模式。我为上面的BNF规则尝试了这个正则表达式：id={letter}+|"_"|{id}{digit}+，但它给了我一个错误，即正则表达式包含循环。

Answer 1

查看BNF，我们可以看到<id>可以以字母或下划线开头。我们还可以看到，一个<id>后面可以跟一个数字或字母，它仍然是一个有效的<id>。这意味着<id>以字母或下划线开头，后面可以跟0个或多个数字或字母。这表明了以下正则表达式：

id = [a-zA-Z_][0-9a-zA-Z]*

1. [a-zA-Z_]匹配字母或'_'
2. [0-9a-zA-Z]*匹配数字或字母0次或多次

但由于已经将{digital}和{letter}定义为单独的字符类，因此这将使用JFlex(我对JFlex不太熟悉，所以我可能对JFlex语法不完全正确(：

id = ({letter}|_)({digit}|{letter})*

这相当于regex:

([a-zA-Z]|_)([0-9]|[a-zA-Z])*