parsing - 在递归下降解析器中实现 "cut"

Question

我正在用 Python 实现一个 PEG 解析器生成器，到目前为止我已经取得了成功，除了“cut”功能，任何了解 Prolog 的人都必须知道。

这个想法是，在解析了剪切 ( ! ) 符号后，不应在同一级别尝试其他选项。

expre = '(' ! list ')' | atom.

意味着在 (之后可见，解析必须成功，否则不尝试第二个选项就失败。

我正在使用 Python 的(非常有效的)异常系统来强制回溯，所以我尝试使用一个特殊的 FailedCut异常会中止封闭选择，但这不起作用。

任何有关如何在其他解析器生成器中实现此功能的指针都会有所帮助。

也许我遇到的问题是缺乏本地化。为规则左侧部分生成的代码类似于:

cut_seen = False
try:
    self.token('(')
    cut_seen = True 
    self.call('list')
    self.token(')')
except FailedParse as e:
    if cut_seen:
         raise FailedCut(e)
    raise

然后为选择( | )运算符生成的代码如果捕获到 FailedCut 将跳过以下选择.我所说的缺乏局部性的意思是选择捕捉 FailedCut可能在电话深处，因此产生难以辨别的影响。

与其让为序列生成的代码试图通知切割的封闭选择，我可以让为选择生成的代码提防它们。这将使切割的范围非常局部，与 Prolog 不同，但足以满足我在 PEG 解析器中想要的功能，即在看到某个标记序列后提交一个选项，因此错误报告是指该位置在源中，而不是到另一个可能有其他选项的位置。

我突然想到，如果为规则/谓词生成的代码捕获 FailedCut并将其转换为正常的 FailedParse异常(exception)，那么削减将具有正确的范围。

关于@false 的问题，这是我想要工作的完整示例:

start = expre ;

expre = named | term ;

named = word ':' ! term;

term = word ;

在那个语法中， word可以通过 named联系或 term ，但我希望解析器致力于 named看到 : 后的分支.

解决方案

公平地说，到目前为止，我已经在 https://bitbucket.org/apalala/grako/ 上发表了我的作品。 .

在最终解决方案中，序列包含在此上下文管理器中:

@contextmanager
def _sequence(self):
    self._push_cut()
    try:
        yield
    except FailedParse as e:
        if self._cut():
            self.error(e, FailedCut)
        else:
            raise
    finally:
        self._pop_cut()

选择函数中的选项包含在这个中:

@contextmanager
def _option(self):
    p = self._pos
    try:
        self._push_ast()
        try:
            yield
            ast = self.ast
        finally:
            self._pop_ast()
        self.ast.update(ast)
    except FailedCut as e:
        self._goto(p)
        raise e.nested
    except FailedParse:
        self._goto(p)

这迫使退出选择而不是返回尝试下一个选项。

削减本身是这样实现的:

def _cut(self):
    self._cut_stack[-1] = True

完整的源代码可以在 Bitbucket 上找到.

Answer 1

在带有 ISO Prolog 异常处理( catch/3 和 throw/1 )的 Prolog 中，切割可以实现为:

cut. % Simply succeeds
cut :-
   throw(cut). % on backtracking throws an exception

这需要在适当的地方捕获该异常。例如，用户定义谓词的每个目标(即非终端)现在可以用以下内容包装:

catchcut(Goal) :-
   catch(Goal,cut,fail).

这不是实现 cut 的最有效方法，因为它不会在 ! 成功后释放资源。 ，但这可能足以满足您的目的。此外，此方法现在可能会干扰 catch/3 的用户定义使用。 .但是您可能无论如何都不想模拟整个 Prolog 语言。

另外，考虑使用 Prolog 的 dcg - 直接语法。当用另一种语言实现它时，有很多细节并不明显。