在Python中实现运算符优先级的一般方法是什么

Question

假设我想编写一个相当简单的编程语言,我想实现像2 + 3*2 = 8这样的运算符

实现这样的事情的一般方法是什么？

Answer 1

我不确定你对多少细节感兴趣,但听起来你正在寻找实现一个解析器.通常有两个步骤:

该词法分析器读了文本,并将其转换为记号.例如,它可能显示为"2 + 3*2"并将其转换为INTEGER PLUS INTEGER STAR INTEGER

该分析器在令牌读取并尝试将其匹配规则.例如,您可能有以下规则:

Expr := Sum | Product | INTEGER;
Sum := Expr PLUS Expr;
Product := Expr STAR Expr;

它读取令牌并尝试应用规则,以便启动规则映射到其读入的令牌.在这种情况下,它可能会:

Expr := Sum
Expr := Expr PLUS Expr
Expr := INTEGER(2) PLUS Expr
Expr := INTEGER(2) PLUS Product
Expr := INTEGER(2) PLUS Expr STAR Expr
Expr := INTEGER(2) PLUS Integer(3) STAR Expr
Expr := INTEGER(2) PLUS Integer(3) STAR Integer(2)

解析器有很多种类型.在这个例子中,我从左到右阅读,并从初始表达式开始,一直工作直到我用一个标记替换所有内容,所以这将是一个LL解析器.在进行此替换时,它可以生成表示数据的抽象语法树.这个树可能看起来像这样:

AST http://so.mrozekma.com/parser1.png的屏幕截图

您可以看到Product规则是Sum规则的子规则,因此它最终将首先发生:2 + (3 * 2).如果表达式的解析方式不同,我们可能最终得到了这棵树:

AST http://so.mrozekma.com/parser2.png的屏幕截图

现在我们正在计算(2 + 3) * 2.这一切都归结为解析器生成树的方式

如果你真的想解析表达式,你可能不想手动编写解析器.有一些解析器生成器采用类似于我上面使用的配置(称为语法),并生成实际的解析器代码.分析器生成器将允许您指定应优先考虑哪个规则,例如:

Expr := Sum | Product | INTEGER;
Sum := Expr PLUS Expr; [2]
Product := Expr STAR Expr; [1]

我将产品规则标记为优先级1,将Sum标记为优先级2,因此,如果选择,生成的解析器将支持Product.您还可以设计语法本身,以便内置优先级(这是更常用的方法).例如:

Expr := Sum | INTEGER;
Sum := Expr PLUS Product;
Product := Term STAR INTEGER;

这会强制产品处于AST的总和之下.当然这个语法是非常有限的(例如,它不匹配2*3 + 2),但是可以编写一个综合语法,它仍然自动嵌入一个操作顺序