python - PEG递归文法

Question

我正在尝试编写一个 Tiger 解析器。我最初使用 PyPEG，但由于一些困难，我选择了 Arpeggio。

我的语法真的很简单。

def number(): return _(r'[0-9]+')
def string(): return _(r"\".*?\"")
def id(): return _(r'[a-zA-Z][a-zA-Z0-9_]*')

def literal(): return [number, string]

def simple_var(): return id

def let_in_exp(): return 'let', 'in', Optional(ZeroOrMore(exp)), 'end'

param = [number, string]
params = Optional(param, ZeroOrMore(',', param))

def function_call(): return id, '(', params, ')'

exp = [let_in_exp, simple_var, literal, function_call]

def code(): return OneOrMore(exp), EOF

困难在于 let-in-exp 表达式。let in let in let in end end end 是有效的 Tiger。

但是 - 目前 - Arpeggio 不能按原样识别 let-in-exp，而是识别三个 simple-var。实际上，进入 ZeroOrMore(exp) 时，它会消耗 end，因此不会为 let-in-exp 找到它。

如何解决这样的问题？

Answer 1

不是琶音解决方案，但也许更符合您的口味？

from pyparsing import (CaselessKeyword,Word,nums,QuotedString,alphas,alphanums,
    Forward,Group,Optional,OneOrMore,ZeroOrMore,delimitedList)

LET,IN,END = map(CaselessKeyword, "let in end".split())

number = Word(nums).setName("number")
string = QuotedString('"')
ident = ~(LET | IN | END) + Word(alphas, alphanums+'_')
ident.setName("ident")

literal = number | string

simple_var = ident

exp = Forward().setName("exp")
let_in_exp = Group(LET + IN + ZeroOrMore(exp) + END).setName("let_in_exp")

param = number | string
params = delimitedList(param)
function_call = ident() + '(' + Optional(params) + ')'

exp <<= let_in_exp | simple_var | literal | function_call

code = OneOrMore(exp)

tests = """\
    let in let in let in end end end
    let in let in let in "blah" end end end
    let in let in let in "blah" end 1729 end end
    """
code.runTests(tests)

我设计的 pyparsing 允许使用算术运算符组合表达式:

• + -> 和
• | -> 先匹配
• ^ -> 或者(尝试所有，匹配最长)
• ~ -> 不是
• & -> Each(与 And 相同，但顺序任意)
• * -> 多个(如 expr*3 而不是 expr+expr+expr)

我相信这些运算符和像 OneOrMore 这样的通俗易懂的语言类名让这些解析器更容易理解，并且随着时间的推移更易于维护。