代码之家  ›  专栏  ›  技术社区  ›  user3368561

结构微积分的递归下降解析器

  •  1
  • user3368561  · 技术社区  · 7 年前

    我用一个简单的一元语法分析器在haskell中实现了一个类型检查器和构造微积分还原器。 Megaparsec .现在,我想改进它,以便它能够识别这种语法快捷方式:

    ∀(x:A)->B (with x not free in B)  =  A -> B
    

    此语法的语法如下:

    <expr>
        = "(" <expr> ")"
        | <expr> <expr>
        | "λ" "(" <name> ":" <expr> ")" "→" <expr>
        | "∀" "(" <name> ":" <expr> ")" "→" <expr>
        | <expr> "→" <expr>
        | <name>
        | "*"
    
    <name> = [_A-Za-z][_0-9A-Za-z]*
    

    我当前的解析器使用了这种变化,消除了左递归(没有快捷方式):

    <expr>
        = "(" <appl> ")"
        | "λ" "(" <name> ":" <appl> ")" "→" <appl>
        | "∀" "(" <name> ":" <appl> ")" "→" <appl>
        | <name>
        | "*"
    
    <appl> = <expr>+
    
    <name> = [_A-Za-z][_0-9A-Za-z]*
    

    前面提到的快捷方式保持递归。我不知道如何将它转换为正确的递归语法,这样它就可以由传统的递归下降解析器处理。

    我知道有更强大的解析技术可以处理左递归语法,但是我想让它保持右递归到左开放在不久的将来手工实现解析器的可能性。

    1 回复  |  直到 7 年前
        1
  •  1
  •   user3368561    7 年前

    在短暂的休息之后,答案很明显。使用和我们一样的技巧 <appl> 扩展如下:

    <expr>
        = "(" <appl> ")"
        | "λ" "(" <name> ":" <appl> ")" "→" <appl>
        | "∀" "(" <name> ":" <appl> ")" "→" <appl>
        | <name>
        | "*"
    
    <appl> = <expr>+ ("→" <appl>)?
    
    <name> = [_A-Za-z][_0-9A-Za-z]*
    

    我会把这个问题留着讨论,以防对某人有所帮助。

    推荐文章