java - 如何使用正则表达式在 LaTeX 中查找嵌套标签

Question

我正在尝试使用 java 从 LaTeX 源中提取定理。我的代码几乎可以工作，但一个测试用例失败了——嵌套定理。

@Test
public void testNestedTheorems() {
    String source = "\\begin{theorem}" +
                    "this is the outer theorem" +
                    "\\begin{theorem}" +
                    "this is the inner theorem" +
                    "\\end{theorem}" +
                    "\\end{theorem}";

    LatexTheoremProofExtractor extractor = new LatexTheoremProofExtractor(source);
    extractor.parse();

    ArrayList<String> theorems = extractor.getTheorems();
    assertNotNull(theorems);
    assertEquals(2, theorems.size()); // theorems.size() is 1
    assertEquals("this is the outer theorem", theorems.get(0)); 
    assertEquals("this is the inner theorem", theorems.get(1)); 
}

这是我的定理提取器，由 LatexTheoremProofExtractor#parse 调用:

private void extractTheorems() {

    // If this has been called before, return
    if(theorems != null) {
        return;
    }

    theorems = new ArrayList<String>();

    final Matcher matcher = THEOREM_REGEX.matcher(source);

    // Add trimmed matches while you can find them
    while (matcher.find()) {
        theorems.add(matcher.group(1).trim());
    }   
}

和THEOREM_REGEX定义如下:

private static final Pattern THEOREM_REGEX = Pattern.compile(Pattern.quote("\\begin{theorem}")
                                                    + "(.+?)" + Pattern.quote("\\end{theorem}"));

有人对处理嵌套标签有建议吗？

Answer 1

如果您只想匹配双重嵌套的定理，您可以为它写下一个显式的正则表达式。我想它看起来会是这样的。

Pattern.compile(
      Pattern.quote("\\begin{theorem}")
        + "("
            + "(.+?)"
            + Pattern.quote("\\begin{theorem}")
                + "(.+?)"
            + Pattern.quote("\\end{theorem}")
        + ")*"
     + Pattern.quote("\\end{theorem}"));

(这段代码应该给你一个想法，但它未经测试，可能无法像编写的那样工作。这不是我想要说的重点。)

您可以继续此操作进行三重嵌套，依此类推，获得您想要的任何固定数量的嵌套。不用说，很快就会变得相当尴尬。

但是，如果您的目标是匹配任意深层嵌套，那么使用正则表达式就根本不可能。问题是您要匹配的语言不是常规的(而是上下文无关的)。上下文无关语言严格来说比常规语言更强大，并且正则表达式只能精确匹配常规语言。一般来说，如果你想匹配上下文无关语言，你需要构造一个下推自动机。

进一步阅读:

• Chomsky hierarchy
• What is meant by “Now you have two problems”?