在递归下降解析器中实现"剪切"

Question

我正在用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可能会在通话中深入,因此产生的效果太难以辨别.

而不是为序列生成代码尝试通知封闭的切割选择,我可以让选择生成的代码提防它们.这会使剪辑的范围非常局部,与Prolog不同,但足以满足我在PEG解析器中的需求,即在看到某个令牌序列后提交选项,因此错误报告指的是该位置在源中,而不是可能已有其他选项的另一个位置.

我刚刚想到,如果为规则/谓词生成的代码捕获FailedCut并将其转换为正常FailedParse异常,则剪切将具有正确的范围.

在提到@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

我的问题末尾提出的解决方案有效：

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。