编译原理课学院的方法#

Pratt解析器#

双栈法#

ops := []
nums := []
while Some(token) = lexer.next() {
	match token {
		Num(num) => nums.push(num),
		LParen => ops.push("("),
		RParen => while op := ops.pop(); op !== "(" {
			rhs := nums.pop()
			lhs := nums.pop()
			res := op.eval(lhs, rhs)
			nums.push(res)
		},
		Op(op) => {
			while !ops.empty() 
				and ops.peek() !== "(" 
				and ops.peek().prec() >= op.prec() {
				peek = ops.pop()
				rhs := nums.pop()
				lhs := nums.pop()
				res := peek.eval(lhs, rhs)
				nums.push(res)
			}
			ops.push(op)
		},
		Eof => while Some(op) := ops.pop() {
			rhs := nums.pop()
			lhs := nums.pop()
			res := op.eval(lhs, rhs)
			nums.push(res)
		}
	}
}
assert(nums.len === 1)
print(nums.first())

转后缀#

ops := []
postexpr := ""
while Some(token) = lexer.next() {
	match token {
		Num(num) => postexpr += num,
		LParen => ops.push("("),
		RParen => while op := ops.pop(); op !== "(" {
			postexpr += op
		},
		Op(op) => {
			while !ops.empty() 
				and ops.peek() !== "(" 
				and ops.peek().prec() >= op.prec() {
				postexpr += ops.pop()
			}
			ops.push(op)
		},
		Eof => while Some(op) := ops.pop() {
			postexpr += op
		}
	}
}
print(postexpr)

三种方法对比#