运算符优先级解析算法之优先级爬升法——算法原理与实现
在 LLVM 的官方入门教程 My First Language Frontend with LLVM Tutorial 的第二章构造 AST 时涉及到了对运算符优先级解析的内容，使用的算法为 优先级爬升法。尽管教程开篇称“不需要编译原理前置预备知识”，但直接理解代码仍有点吃力，本文为我个人对此方法的理解，难免存在错误，欢迎指正。 算法原理 约定和前置知识 在优先级爬升法中，中缀表达式被分解为主表达式（primary expression）和运算符（operator），例如在表达式 a+b*c-d 中，主表达式为 ['a', 'b', 'c', 'd']，运算符包括 ['+', '*', '-']，每个运算符都有与之对应的优先级和结合性，优先级使用正整数表示相对大小，四则运算中乘除优先级高于加减，均为左结合。在本例中，约定加减的优先级为 10，乘除的为 20。 ...