克服TextX解析器中的无限左递归

Question

我正在使用TextX Python (基于弓箭手 弓箭手解析器)为现有语言编写一个解析器。

但是，当我试图使用它来解析一个文件时，我得到了异常：

RecursionError: maximum recursion depth exceeded while calling a Python object

下面是一个引发此异常的最小示例：

#!/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这样的规则，应该将其转换为没有递归的规则。

因此，我的问题是:是否可以以不使用左递归的方式重写上面的Expr := Expr '+' Expr 规则？注意，真正的Expr规则要复杂得多。它的一个稍微不那么简单的版本是：

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

Answer 1

这里是textX作者。除了保罗的出色答案外，还有表达式示例，它应该为您提供一个良好的开端。

自顶向下的解析器通常不会处理左递归规则，而不会像这样的黑客攻击。如果您的语言将是复杂的、面向表达式的，那么最好尝试一些自下而上的解析器，它允许左递归，并提供声明性优先级和相关性规范。如果您喜欢textX，那么我建议您看看白兰地，它具有类似的设计目标，但是使用了自下而上的解析技术(特别是LR和GLR)。快速入门示例是您正在构建的确切语言。

在这个职位中，我写了一些关于启动parglare项目的理由以及与textX/Arpeggio的不同之处。

Answer 2

这更典型地写成：

multop: '*' | '/'
addop: '+' | '-'
Factor: INT | STRING | '(' Expr ')' ;
Term: Factor [multop Factor]... ;
Expr: Term [addop Term]... ;

现在，Expr在第一次匹配前导“(”)之前不会直接恢复自身。您还将获得与操作优先级相对应的组。(请注意，对Expr和Term的重复将产生像['1', '+', '1', '+', '1']这样的组，而您可能期望使用左递归解析器所提供的[['1', '+', '1'], '+', '1']。)