我想解析
PHP中的布尔表达式.如：
A and B or C and (D or F or not G)
这些术语可以被认为是简单的标识符.他们会有一点点的结构,但解析器不用担心.它应该只是识别关键字,否则().一切都是一个术语.
我记得我们在学校写了简单的算术表达式评估者,但我不记得如何做完了.也不知道在Google / SO中要查找哪些关键字.
一个现成的图书馆会很好,但是我记得算法很简单,所以自己重新实现它可能是有趣和有教益的.
递归下降解析器很有趣,易于阅读.第一步是写出你的语法.
也许这是你想要的语法.
expr = and_expr ('or' and_expr)*
and_expr = not_expr ('and' not_expr)*
not_expr = simple_expr | 'not' not_expr
simple_expr = term | '(' expr ')'
将其转化为递归下降解析器是非常简单的.只要每个非终结符写一个函数.
def expr():
x = and_expr()
while peek() == 'or':
consume('or')
y = and_expr()
x = OR(x,y)
return x
def and_expr():
x = not_expr()
while peek() == 'and':
consume('and')
y = not_expr()
x = AND(x,y)
return x
def not_expr():
if peek() == 'not':
consume('not')
x = not_expr()
return NOT(x)
else:
return simple_expr()
def simple_expr():
t = peek()
if t == '(':
consume('(')
result = expr()
consume(')')
return result
elif is_term(t):
consume(t)
return TERM(t)
else:
raise SyntaxError("expected term or (")
这还不完整.你必须提供一些更多的代码：
>输入功能.消费,偷看和is_term是您提供的功能.他们将很容易使用正则表达式实现.消耗(s)读取输入的下一个标记,如果与s不匹配则会抛出错误. peek()只是简单地返回一个窥视下一个令牌而不消耗它.如果s是一个术语,则is_term(s)返回true.
>输出功能.每次一个表达式成功解析时,都会调用OR,AND,NOT和TERM.他们可以做任何你想要的.
>包装功能.而不是直接调用expr,您将需要编写一个包装函数,该函数初始化由consume和peek使用的变量,然后调用expr,最后检查以确保没有剩余的输入不被使用.
即使这样,它仍然是一个微小的代码量. In Python,the complete program is 84 lines,包括几个测试.
