克服TextX解析器中的无限左递归 [英] Overcoming infinite left recursion in TextX parser

问题描述

我正在使用 TextX Python库(基于琶音 PEG解析器)

I am writing a parser for an existing language, using the TextX Python Library (based on the Arpeggio PEG parser)

但是当我尝试使用它来解析文件时，出现了异常:

But when I try to use it to parse a file, I get the exception:

RecursionError: maximum recursion depth exceeded while calling a Python object

这是引发此异常的最小示例:

Here is a minimal example that raises this exception:

#!/usr/bin/env python
from textx import metamodel_from_str

meta_model_string = "Expr: ( Expr '+' Expr ) | INT ;"
model_string      = "1 + 1"

mm = metamodel_from_str(meta_model_string, debug=True)
m = mm.model_from_str(model_string, debug=True)

我将其追溯到Arpeggio的左递归问题，其中指出不支持A := A B之类的规则，应将其转换为不存在此类递归的规则.

I tracked it down to Arpeggio's left recursion issue, where it state that a rule like A := A B is unsupported and should be converted to a rule where there is no such recursion.

所以我的问题是:是否可以使用不使用左递归的方式重写上面的Expr := Expr '+' Expr规则?请注意，真正的Expr规则要复杂得多.稍微简化一点的版本将是:

So my question is: Is it possible to rewrite the Expr := Expr '+' Expr rule above in a way that does not use left recursion? Note that the real Expr rule is much more complicated. A slightly less simplified version of it will be:

Expr: '(' Expr ')' | Expr '+' Expr | Expr '*' Expr' | '!' Expr | INT | STRING ;

推荐答案

textX作者在此处.除了Paul的出色回答之外，还有表达式示例这应该为您提供一个良好的开端.

textX author here. In addition to Paul's excellent answer, there is expression example which should provide you a good start.

自上而下的解析器通常不会在没有此类黑客的情况下处理左递归规则.如果您的语言将变得复杂且以表达为主，那么最好尝试一些自下而上的解析器，该解析器允许左递归并提供声明性优先级和关联性规范.如果您喜欢textX，那么我建议您看一下 parglare ，它的设计目标相似，但使用底部解析技术(特别是LR和GLR).快速的入门示例是您正在构建的确切语言.

Top-down parsers in general are not handling left-recursive rules without hacks like this. If your language is going to be complex and heavily expression oriented it might be better to try some bottom-up parser that allows for left recursion and provides declarative priority and associativity specification. If you liked textX then I suggest to take a look at parglare which has similar design goals but uses bottom-up parsing technique (specifically LR and GLR). Quick intro example is the exact language you are building.

在这篇文章中，我写了有关基本原理的博客启动parglare项目的过程以及与textX/Arpeggio的区别.

In this post I blogged about rationale of starting parglare project and differences with textX/Arpeggio.

这篇关于克服TextX解析器中的无限左递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！