7

我正在用 Python 实现一个 PEG 解析器生成器，到目前为止我已经取得了成功，除了“剪切”功能，任何知道 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

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

我可以让为选择生成的代码提防它们，而不是让为序列生成的代码尝试通知封闭选择cut 。与 Prolog 不同，这将使削减的范围非常本地化，但对于我在 PEG 解析器中想要的东西来说已经足够了，即在看到某个标记序列后提交一个选项，因此错误报告是指该位置在源中，而不是到另一个可能有其他选项的位置。

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

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

start = expre ;

expre = named | term ;

named = word ':' ! term;

term = word ;

在该语法中，word可以通过namedor到达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上找到。

4

3 回答 3

3

在具有 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 的 -grammars。在用另一种语言实现时，有很多细节并不明显。

于 2013-01-03T19:08:50.993 回答
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 。

于 2013-01-11T21:30:43.350 回答
1

就读吧。

我建议使用深度cut_seen（比如修改解析器的状态）以及使用局部变量保存和恢复状态。这将线程的堆栈用作“cut_seen堆栈”。

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

顺便说一句：不错的编译器——这与我用 pyPEG 做的正好相反，所以我可以学到很多东西 ;-)

于 2013-01-21T23:33:16.560 回答