我已经编写了一个解析器,它正确地接受一个表达式并从中创建一个AST。然后,我的解释器接受AST,计算它,然后返回一个解决方案。但是,我希望解析器(或解释器)解释表达式中的歧义(缺少括号)。你知道吗
例如,如果我编写类似R∩G-B的表达式,我希望看到(R∩G)-B和R∩(G-B)的ast都返回。我见过许多在解析表达式时消除歧义的解决方案,但我希望能够看到表达式的所有可能解释。你知道吗
下面是我的解析器类的一个片段:
def eat(self, token_type):
if self.current_token.type == token_type:
self.current_token = self.lexer.get_next_token()
else:
self.error()
def factor(self):
token = self.current_token
if token.type in (COLOR, EMPTY_S, UNIVERSE_OP):
self.eat(token.type)
return Num(token)
elif token.type == L_PAREN:
self.eat(L_PAREN)
node = self.expr()
self.eat(R_PAREN)
return node
def term(self):
node = self.factor()
while self.current_token.type is COMPLIMENT:
token = self.current_token
self.eat(COMPLIMENT)
node = BinOp(left = node, op = token, right = self.expr())
return node
def expr(self):
node = self.term()
while self.current_token.type in (UNION, INTERSECT, MINUS, SUBSET, EQUALS):
token = self.current_token
if token.type == UNION:
self.eat(UNION)
elif token.type == INTERSECT:
self.eat(INTERSECT)
elif token.type == MINUS:
self.eat(MINUS)
elif token.type == SUBSET:
self.eat(SUBSET)
elif token.type == EQUALS:
self.eat(EQUALS)
else:
self.error()
node = BinOp(left = node, op = token, right = self.expr())
return node
def parse(self):
return self.expr()
在我当前的设置中,解析器只返回R∩(G-B)的AST。你知道吗
有一些解析算法,对于一个模棱两可的语法,可以找到所有可能的方法来解析一个给定的字符串:Earley、CYK、Tomita、GLR、GLL。但它们都离现在的递归下降解析器很远。(GLL声称是递归下降式的,但这似乎有点夸张。)
实现这一点的“明显”方法是向解析器接受的语言添加额外的语法规则。我的意思是,首先写下递归解析器接受的语法;目前它只接受表达式的解释。为其他解释添加明确的规则;这定义了歧义。你知道吗
比如:
现在“只是”调整解析器以接受这些规则。要做到这一点,您的解析器可能必须在遇到其他方法时实现对解析状态的保存,以便它可以恢复(“回溯”)并尝试其他方法。这包括输入流在备选位置的点。可以通过缓冲输入文本和/或输入标记来实现这一点。你知道吗
michaeldyck列出了各种各样的解析引擎/方法,它们以一种更为常规的方式来实现这一点,但是它们都是从假设语法显式地包含歧义替代项开始的。你知道吗
相关问题 更多 >
编程相关推荐