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

Question

我正在为现有语言编写解析器，使用 TextX Python Library (based on the Arpeggio PEG 解析器)

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

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 的 left recursion issue，其中声明不支持 A := A B 之类的规则，应将其转换为不存在此类递归的规则。

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

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

Answer 1

通常写为：

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

现在 Expr 将不会直接递归到自身，直到第一次匹配前导 '('。您还将获得与操作优先级相对应的组。（请注意 Expr 和Term 最终会产生像 ['1', '+', '1', '+', '1'] 这样的组，而你可能已经预料到了 [['1', '+', '1'], '+', '1']，这是左递归解析器会给你的。）

Answer 2

这里是textX作者。除了 Paul 的出色回答之外，expression example 应该可以为您提供一个良好的开端。

自上而下的解析器一般不会处理左递归规则，除非像这样的黑客攻击。如果您的语言将变得复杂并且严重面向表达式，那么尝试一些允许左递归并提供声明性优先级和关联性规范的自下而上的解析器可能会更好。如果您喜欢 textX，那么我建议您看看 parglare，它具有相似的设计目标，但使用自下而上的解析技术（特别是 LR 和 GLR）。快速介绍示例正是您正在构建的语言。

在 this post 中，我在博文中介绍了启动 parglare 项目的基本原理以及与 textX/Arpeggio 的区别。

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

Overcoming infinite left recursion in TextX parser

python

parsing

peg

left-recursion

textx