在递归下降分析器中实现"cut"

Question

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

这个想法是，在cut (!)符号被解析后，不应该在同一级别尝试任何替代选项。

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异常，那么cut将具有正确的作用域。

关于@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可以实现为:

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

这需要在适当的位置捕获该异常。例如，用户定义谓词的每个目标(非终结)现在可以用:

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

这不是实现cut的最有效的方法，因为它在!成功时不会释放资源，但它可能足以满足您的目的。而且，这个方法现在可能会干扰用户对catch/3的使用。但是您可能不想在任何情况下模拟整个Prolog语言。

另外，考虑直接使用Prolog的dcg语法。在另一种语言中实现这个功能时，有很多细节是不明显的。

Answer 2

在我的问题末尾提出的解决方案起作用了:

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

然后，每次求值一个选择值或可选值时，代码如下:

p = self.pos
try:
   # code for the expression
except FailedCut:
    raise
except FailedParse:
    self.goto(p)

编辑

实际的解决方案需要保持"切割堆栈"。源代码是int Bitbucket

Answer 3

看完就知道了。

我建议使用深层cut_seen(如修改解析器的状态)和使用局部变量保存和恢复状态。这将使用线程的堆栈作为" cut_seen堆栈"。

但你有另一个解决方案，我很确定你已经没事了。

BTW:很好的编译器-它正好与我用pyPEG做的相反，所以我可以学到很多东西;-)