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 是有效的老虎。

但是 - 目前 - 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 设计为允许使用算术运算符组合表达式：

+ -> 和
| -> 首先匹配
^ -> 或者（全部尝试，匹配最长）
~ -> 不是
& -> 每个（与 And 相同，但顺序任意）
* -> 多个（如 expr*3 而不是 expr+expr+expr）

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

Answer 2

正如 Paul 已经指出的那样，您应该使用 Not 句法谓词来避免通过 simple_var 规则匹配关键字。另外，我建议不要将 ZeroOrMore 解析表达式包装在 Optional 中，因为它已经暗示了。

琶音的解决方案是

from arpeggio import Not, OneOrMore, ZeroOrMore, Optional, EOF, ParserPython
from arpeggio import RegExMatch as _

keyword = ['let', 'in', 'end']   
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 Not(keyword), id
def let_in_exp(): return 'let', 'in', 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

parser = ParserPython(code, debug=True)
test = 'let in 42 let in "foo" let in end end end'
parse_tree = parser.parse(test)

这将产生以下解析树

PEG递归文法

PEG recursive grammar

python

grammar

parsing

peg