时间戳

首页 > 解决方案 > 解析算法中解决优先级的方法

python - 解析算法中解决优先级的方法

问题描述

我正在研究解析，更准确地说是解析器组合器，我遇到了优先级和关联性问题。

我找到的第一个解决方案是在语法中表达优先级。但这似乎使语法复杂化。由于我正在处理解析器组合器，因此我希望将语法表达为函数组合。我得到的第一个解决方案是这样的

expr = or(sequence(int, regex("[+-]"), expr),
          int)
int = regex("\d+")

此处or并在 BNF 语法中sequence模拟和多个术语。|

_这是非常假设的，如果有兴趣的话，真正的来源是这里的 Rust。我的问题更具理论性......这里还有一个更易于管理的python版本_

我想知道的另一个选择是。只需按原样解析输入，然后进行第二次运行简化它，简化是指也解决优先级和关联问题。我没有发现有人这样做，所以我来到了这里。

我想做这样的事情，假设我解析这个输入a * b + c并输出这样的东西

[
  a, 
  Op(*, p=0),
  [
     b,
     Op(+, p=1),
     [
       c
     ]
  ]
]

然后使用它p（从优先级）创建正确的树。这样做我可以创建非常声明性的语法，例如sum = or(sequence(term, op('+', 1), sum), term). 我担心这会变得太慢而无法运行，因为树上有多次遍历。

我的第三个想法，而我不知道如何以令人满意的方式实施的这个想法是将两者混合。保留组合器，但在它们中间添加一些简化逻辑，在一些关键点（但在分离的函数中）可以在构建树时修复它，我尝试了类似的方法来删除终端和嵌套序列。

我还缺少其他方法吗？这是一个总结

  1. 在语法中表达优先逻辑
  2. 生成整个树并在后面固定优先级
  3. 生成部分树并在生成树时逐步修复优先级

一些问题：

最后感谢您在这里阅读。

标签： pythonrustcompiler-construction

解决方案

推荐阅读