0

这是一个大型解析器的简化版本。我一直让我有点发疯，因为我似乎无法让它始终如一地工作。较大的版本可以工作，但有很多边缘情况，它不能很好地工作，我发现自己必须教 python 整个语法，我想要的只是#ifdef 预处理器指令。

我试图简化它并得到这个（下），但它从来没有找到 ifdef / endif。为什么？

from parsimonious.grammar import Grammar
CPP = Grammar(r"""
    file  = (code_block / nl / ws)+
    label = ~"[A-z_]+\w*"                         # Alpha or _ followed by alphanumeric or _
    
    ifdef = "#ifdef" ws+ label nl
    else  = "#else" nl
    endif = "#endif" nl
    
    line = ~r".+" nl
    lines = line+
    
    ws    = ~r"[\s\t]+"                           # One or more whitespace
    nl    = ~r"[\s\t]*[\n\r]+"                    # Zero or more whitespace followed by a newline
    
    if_block = ifdef code_block* endif
    if_else_block = ifdef code_block* else code_block* endif
    
    code_block = (if_block / if_else_block / lines)
    """)

code = """
int a;

#ifdef test1

a += 2;

#ifdef test2
a--;
#endif

#else

a += 20;

#endif

"""

res = CPP.parse(code)
print(res)

它找到了许多“行”，但从来没有找到一个“if”块。（注意“代码”不应该做任何有用的事情，它只是一些示例文本）

4

1 回答 1

0

PEG 解析本质上是贪婪的，正如其文档中的简约注释。（这不是特定于简约的。任何 PEG 解析器都会遇到同样的问题。）

things*
   零个或多个things。这是贪婪的，总是尽可能多地重复。

所以你有一个模式code_block：

code_block = (if_block / if_else_block / lines)

假设解析器试图在输入中的某个点匹配它。如果相应的文本以if_blockor开头if_else_block（稍后会详细介绍），那很好。但是假设它从其他东西开始，比如int a;？在这种情况下，解析器将根据上面的文档尝试匹配lines，也就是说line*，也就是说尽可能多地重复。line

现在，line只是一行：任何在第一个换行符处终止的任意字符序列。所以line会很高兴地匹配#ifdef test1或#endif其他什么。

换句话说，如果code_block在输入中的某个点尝试匹配 for 并且输入中的第一件事不是 anif_block或 an if_else_block，那么code_block将贪婪地匹配输入的其余部分。

现在，让我们回到匹配if_block（并注意相同的注释将适用于匹配if_else_block）。的规则if_block是：

if_block = ifdef code_block endif

ifdef是以#ifdef[注1]开头的一行。接下来是 a code_block，正如我们刚刚看到的，它将贪婪地匹配到输入的末尾（除非它恰好立即匹配一个嵌套的#ifdef）。换句话说，code_block不在乎您是否希望它在到达#endif;时停止 它一无所知#endif。这是一个贪婪的小怪物，在你的输入中大吃一惊。即使是下一行，它也会与输入的其余部分一起#endif被 吸收。lines

由于#endif永远无法识别，if_block永远无法匹配，解析器将不得不退回到下一个可能性，if_else_block. 但这也永远无法匹配，所以它必须回到贪婪的怪物身上。

简而言之，这种语法模型行不通，这不是吝啬的错。如果你坚持这个模型，不管你使用哪个 PEG 解析器，你最终都会遇到同样的问题。

从上面的分析可以看出，任何重复的行匹配都需要注意预处理器指令，以便不匹配它们[注 2]。这是可以做到的，但它使事情变得更复杂，因为它迫使我们对可能的输入进行分类，而不仅仅是依赖于有序的替代方案 [注 3]。

所以关键是有两种输入行：预处理指令（至少是我们感兴趣的指令）和其他所有指令。（这是一个彻底的简化，因为“其他所有内容”包括注释和引用文字，它们需要单独处理。但我们现在将忽略它。）很容易看出如何识别预处理器指令，所以让我们关注识别不是预处理器指令的行。幸运的是，简约（像许多 PEG 解析器生成器一样）有一个负前瞻运算符，我们可以在这里使用它来为我们带来好处：

line = ws? !("#" ws? ("ifdef" / "else" / "endif")) ~".*" nl

（下面，对ws和的定义进行了更正nl）

没有必要lines，因为我上面没有提到的另一个问题。在定义中

code_block = (if_block / if_else_block / lines)

acode_block可以是任意数量的行，但只能是一个预处理器块。这是不对的：acode_block可以是任意数量的行和嵌套块的任意组合。正确的定义是：

code_block = (if_block / if_else_block / line)*

在我看来，使用条件来避免有两个不同的预处理器块定义似乎更简单。毕竟，它们都以 开头#ifdef，并且在回退之后尝试再次扫描它是没有意义的，即使 parsimonious 设法通过打包有效地进行重新扫描。所以我提出以下建议：

ifdef = ws? "#" ws? "ifdef" ws label nl
else  = ws? "#" ws? "else" nl
endif = ws? "#" ws? "endif" nl

code_block = (if_block / line)*
if_block = ifdef code_block (else code_block)? endif

（我删除了多余+的部分，ifdef因为ws已经包含了一个重复运算符。）

在这一点上，一个小题外话来修复你的正则表达式模式。这里的目标是ws匹配任何水平空白（不包括换行符），同时nl匹配可能的水平空白，后跟一系列换行符。但是您的ws模式 include \s，它在 Python 正则表达式中匹配任何空格，包括换行符，这有点过于慷慨了。虽然我们正在修复正则表达式，[A-z]但与[A-Za-z]因为a没有立即遵循不一样Z；它们由几个标点符号分隔（包括_, 碰巧，但也[]包括其他）。以下内容也不完美，但这是一个开始：

label = ~"[A-Za-z_]\w*"
ws    = ~"[ \t]+"
nl    = ~"\s*[\n\r]+"

所以，把所有这些放在一起：

file  = code_block

label = ~"[A-Za-z_]\w*"
ws    = ~"[ \t]+"
nl    = ~"\s*[\n\r]+"

ifdef = ws? "#" ws? "ifdef" ws label nl
else  = ws? "#" ws? "else" nl
endif = ws? "#" ws? "endif" nl

line  = ws? !("#" ws? ("ifdef" / "else" / "endif")) ~".*" nl

code_block = (if_block / line)*
if_block = ifdef code_block (else code_block)? endif

至少，这似乎可以处理您的示例代码。

笔记

  1. 这并不正确，因为在 C 中，预处理器指令可以以空格开头，并且不需要#紧跟指令名称。但这不是这里的问题。

  2. 警告：意见如下。与经常重复的广告相反，即 PEG 解析器通过不强制划分词法分析和句法来“简化语法”，在我看来，在许多情况下（例如这个），关注点的系统分离实际上是最简单的。

  3. 有一个订购替代品的地方。例如，它们在词法分析中工作得很好。但这远远超出了这个答案的范围。

于 2021-08-05T17:03:29.527 回答