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

在保持左关联性的同时避免左递归解析Lambda演算

left-recursion peg lambda-calculus node.js javascript

2

akaphenom · 技术社区 · 7 年前

/*****************************************************************
        t ::=
                x                                       variable
                Î»x.t                                    abstraction
                t t                                     application
*****************************************************************/

从中我已经编码出钉:

TERM "term"
    = ABSTRACTION
    / APPLICATION
    / VARIABLE

APPLICATION "application"
    /*****************************************************************
        application ::= t t
    *****************************************************************/
    = APPLICATION_W_PARENS
    / APPLICATION_WO_PARENS

ABSTRACTION "abstraction"
    /*****************************************************************
        abstraction ::= Î»x.t
    *****************************************************************/
    = ABSTRACTION_W_PARENS
    / ABSTRACTION_WO_PARENS

VARIABLE "variable"
    /*****************************************************************
        variable ::= x
    *****************************************************************/
    =  x:CHARACTER
    {
        return Variable(location(), x)
    }

//////////////////////////////////////////////////////////////////////
// Application
//////////////////////////////////////////////////////////////////////

ABSTRACTION_OR_VARIABLE
    //////////////////////////////////////////////////////////////////
    // "Left recursive grammar" workaround "term term" enters a loop
    //      assuming the left side cannot match Application
    //      remediates the left recursion issue
    //////////////////////////////////////////////////////////////////
    = ABSTRACTION / VARIABLE

APPLICATION_W_PARENS
    /*****************************************************************
        '(' -> Abstraction | Variable -> Term -> ')'
    *****************************************************************/
    = L_PARENS lhs:ABSTRACTION_OR_VARIABLE rhs:TERM R_PARENS
    {
        return Application(location(), lhs, rhs, true)
    }

APPLICATION_WO_PARENS
    /*****************************************************************
        Abstraction | Variable -> Term
    *****************************************************************/
    = lhs:ABSTRACTION_OR_VARIABLE rhs:TERM
    {
        return Application(location(), lhs, rhs, false)
    }

//////////////////////////////////////////////////////////////////////
// Abstraction
//////////////////////////////////////////////////////////////////////

ABSTRACTION_W_PARENS "abstraction"
    /*****************************************************************
            '(' -> 'Î»' -> Variable -> '.' -> TERM -> ')'
    *****************************************************************/
    = L_PARENS LAMBDA x:CHARACTER DOT term:TERM R_PARENS
    {
        return Abstraction(location(), x, term, true)
    }

ABSTRACTION_WO_PARENS
    /*****************************************************************
            'Î»' -> Variable -> '.' -> Term
    *****************************************************************/
   = LAMBDA x:CHARACTER DOT term:TERM
   {
        return Abstraction(location(), x, term, false)
   }

//////////////////////////////////////////////////////////////////////
// Atoms
//////////////////////////////////////////////////////////////////////

LAMBDA "lambda"
    = 'Î»'

L_PARENS "lParens"
    = '('

R_PARENS "rParens"
    = ')'

DOT "dot"
    = [\.]

CHARACTER "character"
    = [A-Za-z]
    {
        return text().trim() ;
    }

它可以在简单的输入下编译并运行良好。当我开始通过示例来测试实现时,我发现了一些问题。根据条款

Î»l.Î»m.Î»n.lmn

{
    "expr": "Î»l.Î»m.Î»n.lmn",
    "ast": " Abstraction( l,  Abstraction( m,  Abstraction( n, Application(  Variable( l ), Application(  Variable( m ),  Variable( n ) ) ) ) ) )"
}

问题出在米应适用于一然后为了这个结果。从AST的打印件上可以看出适用于米这个结果适用于一

如果我更改了现有的规则以防止左递归问题,而应用程序假设左侧只是变量或抽象以包含应用程序的可能性,则存在递归问题。

我们能在PEG.JS中解决这个问题吗?
或者我应该重写应用程序对象的构造(hack)?
或者有更好的方法来解析它-例如滚动一个自定义解析器?

1 回复 | 直到 7 年前

1

0

akaphenom 7 年前

有缺陷的方法 :我尝试过的一种方法是强制一行中两个以上的变量|抽象的匹配,然后左键应用它们

APP_2
    = lhs:ABSTRACTION_OR_VARIABLE rhs:ABSTRACTION_OR_VARIABLE
    {
        return Application(location(), lhs, rhs, false, "APP2")
    }

APP_3
    = lhs:APP_2 rhs:TERM
    {
        return Application(location(), lhs, rhs, false, "APP3")
    }

APPLICATION_WO_PARENS
    = APP_3
    / APP_2

{
    "expr": "lmno",
    "ast": "Application::APP3( 
              Application::APP2(  Variable(l),  Variable(m) ),
              Application::APP2(  Variable(n),  Variable(o) ) 
            )"
}

所以我可以建立任何数量的应用程序。。。APP_99规则并强制左边的应用程序。在我超过99份(或其他)申请之前,这是可行的。解决方案将是一个真正的黑客和脆弱的。

:我想把一些东西拼凑在一起,于是改变了将一系列术语作为应用程序进行匹配的方法:

APP_ARR
    = terms:ABSTRACTION_OR_VARIABLE*
   {
        return reduceTerms(location(), terms)
   }

APPLICATION_WO_PARENS
    = APP_ARR

这种方法要求我编写一些代码来构建我试图避免的结构(reduceTerms)。代码如下:

const reduceTerms = function(info, terms){
    const initialLhs = terms.shift()
    const initialRhs = terms.shift()
    const initialApp = Application(info, initialLhs, initialRhs, false, 'reduceTerms')

    const appAll = terms.reduce(
        (lhs, rhs) => Application(info, lhs, rhs, false, 'reduceTerms'),
        initialApp
    )

    return appAll ;
}

请忽略布尔和“reduceTerms”字符串。布尔值用于指示此应用程序是否包含在parens中(在本书稍后的部分中遇到parens概念之前,将删除它)。字符串是关于如何/在何处构造应用程序节点的实例的标签(用于调试解析器如何应用规则)。

条款阵列。还原函数将以初始对象作为下学期 右手侧 工作

{
    "expr": "lmno",
    "ast": "Application::reduceTerms( 
              Application::reduceTerms( 
                Application::reduceTerms(  Variable(l),  Variable(m) ),  
              Variable(n) ),  
            Variable(o) )"
}

这里的一个问题是我需要做一些额外的工作信息对象以准确反映匹配。在这个版本中信息

因此,我仍然在寻找一个解决方案,在PEG内部执行此操作,而不在数组上进行匹配,并将其还原为一棵树。

:使用发布的方法翻译

A -> A Î± | Î²

到

A -> Î² A'
A' -> Î± A' | Îµ

我已经知道了

TERM_OR_VARIABLE
    = L_PARENS TERM R_PARENS
    / VARIABLE

APP
   = lhs:TERM_OR_VARIABLE rhs:APP_
   {
       return Application(location(), lhs, rhs, false, "APP")
   }

APP_
    = lhs:TERM_OR_VARIABLE rhs:APP_
    {
        return Application(location(), lhs, rhs, false, "APP_")
    }
    / lhs:TERM_OR_VARIABLE END
    {
        return lhs
    }
    / END

END
    = !.

APPLICATION_WO_PARENS
    = APP

lmno公司

Application::APP(  
    Variable(l), 
    Application::APP_(  
       Variable(m), 
       Application::APP_(  
          Variable(n),  
          Variable(o) 
       ) 
    ) 
)