代码之家  ›  专栏  ›  技术社区  ›  Chen Levy

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

  •  0
  • Chen Levy  · 技术社区  · 6 年前

    我正在使用 TextX Python库(基于 Arpeggio

    但是当我试图用它来解析一个文件时,我得到了一个例外:

    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)
    

    我查到了琶音 left recursion issue A := A B 不受支持,应转换为不存在此类递归的规则。

    所以我的问题是: 有没有可能重写 Expr := Expr '+' Expr Expr 规则要复杂得多。略为简化的版本为:

    Expr: '(' Expr ')' | Expr '+' Expr | Expr '*' Expr' | '!' Expr | INT | STRING ;
    
    2 回复  |  直到 6 年前
        1
  •  3
  •   Igor Dejanović    6 年前

    expression example 这会给你一个好的开始。

    如果没有像这样的黑客,自顶向下的解析器通常不会处理左递归规则。如果您的语言将是复杂的,并且非常面向表达式,那么最好尝试一些允许左递归并提供声明性优先级和关联性规范的自底向上解析器。如果你喜欢textX,我建议你看看 parglare

    this post 我在博客上讨论了启动parglare项目的基本原理以及与textX/Arpeggio的区别。

        2
  •  1
  •   PaulMcG    6 年前

    这更典型地写为:

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

    Expr 在第一次匹配前导“(”之前不会直接递归到自身。您还将获得与操作优先级相对应的组(请注意,对于 出口 Term 最终会产生像 ['1', '+', '1', '+', '1'] ,你可能已经预料到了 [['1', '+', '1'], '+', '1']