4

我想学习如何在 Java 中使用正则表达式并找到了以下任务：编写一个类来检查给定的输入字符串是否是基于 BNF 形式的这些标准的有效算术项：

term = [Vz]summand|[Vz]summand addOp term
summand = factor | factor mulOp summand
factor = number | '('term')'
number = digit | digit number
digit = '0'|'1'|...|'9'
vz = '+'|'-'
addOp = '+'|'-'
mulOp = '*'|'/'

使用这些规则，我编写了一些模式，类似于不同的类型：

static Pattern vz = Pattern.compile("[+-]");
static Pattern addOp = Pattern.compile("[+-]");
static Pattern multOp = Pattern.compile("[*/]");
static Pattern digit= Pattern.compile("[0-9]");
static Pattern number = Pattern.compile(digit.pattern()+"+");
static Pattern factor = Pattern.compile(number.pattern()+"|("+term.pattern()+")");
static Pattern summand = Pattern.compile(factor.pattern()+"|"+factor.pattern()+ multOp.pattern()+"\n");
static Pattern term = Pattern.compile(vz.pattern()+"?"+summand.pattern()+"|"
        +vz.pattern()+"?"+summand.pattern()+addOp.pattern()+"\n");

你已经看到了我的问题：我在 factor 的定义中引用了术语，而没有先定义它。不幸的是，我无法以任何方式切换它。所以我的问题是：

是否有可能以这种方式引用模式？或者任何其他参考模式并在以后定义它？

4

1 回答 1

4

问题是，BNF 定义了一种上下文无关文法（它描述的语言比正则表达式描述的更复杂）。您将不得不想出一种不同的方法，而不是直接将 BNF 规则用作正则表达式模式。

特别是，括号的正确嵌套是不规则的。一些正则表达式引擎支持允许匹配这些的（非常规）功能，但正则表达式通常变得非常长且不可维护。而且我现在不确定Java是否具有这些功能（例如PCRE和.NET）。

如果要解决手头的任务，则必须手动编写解析。如果您想学习正则表达式，您将不得不使用另一种语言或寻找不同的任务。然而，这里有一个很好的资源来提高你的正则表达式技能。

为了它的乐趣（并且向您展示为什么正则表达式不是正确的工具，即使引擎支持必要的功能），这里是对应于上述 BNF 的正则表达式（除了Vz规则，对于某些我无法让它工作的奇怪原因）：

^(((\d+|[(](?1)[)])|(?3)[*\/](?2))|(?2)[+-](?1))$

(?n)递归地尝试匹配子模式（通过nth从左到右打开括号来计算）。

它在 PHP 中不起作用，但我相信他们的 PCRE 实现在使用递归时存在一些回溯问题。一个在线 PCRE 测试仪似乎正确处理了一些示例输入。这里它处于自由间距模式 ( x) 并带有一些注释：

^
(                # term (?1)
  (              # summand (?2)
    (            # factor (?3)
      \d+        # number
    |
      [(](?1)[)] # (term)
    )            # end of factor
  |
    (?3)[*/](?2) # factor mulOp summand
  )              # end of summand
|
  (?2)[+-](?1)   # summand addOp term
)                # end of term
$
于 2012-12-09T22:06:06.140 回答