parsing - 源代码的抽象语法树,包括表达式
问题描述
我正在构建一种新的简单编程语言(只是为了在空闲时间了解编译器的工作原理)。
我已经构建了一个词法分析器,可以将我的源代码标记为词法。
但是,我现在被困在如何从标记中形成抽象语法树,其中源代码可能包含表达式(具有运算符优先级)。
为简单起见,我将仅包括 4 个基本运算符:+、-、/ 和 * 以及括号 ()。运算符优先级将遵循 BODMAS 规则。
我意识到我可能能够将表达式从中缀转换为前缀/后缀,形成树并替换它。
但是,我不确定这是否可能。即使有可能,我也不确定它的效率如何或实施起来有多么困难。
是否有一些简单的方法可以就地形成树而不必先转换为前缀/后缀?
我遇到了似乎可以做到这一点的 Shutting Yard 算法。但是,我发现它是一个相当复杂的算法。有没有更简单的方法,还是我应该继续实施 Shutting Yard 算法?
目前,我的词法分析器对以下程序进行了标记,如下所示:
我正在演示使用 Java 程序来熟悉语法。
源程序:
public class Hello
{
public static void main(String[] args)
{
int a = 5;
int b = 6;
int c = 7;
int r = a + b * c;
System.out.println(r);
}
}
词法分析器输出:
public
class
Hello
{
public
static
void
main
(
String
[
]
args
)
{
int
a
=
5
;
int
b
=
6
;
int
c
=
7
;
int
r
=
a
+
b
*
c
;
System
.
out
.
println
(
r
)
;
}
}
解决方案
// I know this might look ugly that I use a global variable ret to return parsed subtrees
// but please bear with it, I got used to this for various performance/usability reasons
var ret, tokens
function get_precedence(op) {
// this is an essential part, cannot parse an expression without the precedence checker
if (op == '*' || op == '/' || op == '%') return 14
if (op == '+' || op == '-') return 13
if (op == '<=' || op == '>=' || op == '<' || op == '>') return 11
if (op == '==' || op == '!=') return 10
if (op == '^') return 8
if (op == '&&') return 6
if (op == '||') return 5
return 0
}
function parse_primary(pos) {
// in the real language primary is almost everything that can be on the sides of +
// but here we only handle numbers detected with the JavaScript 'typeof' keyword
if (typeof tokens[pos] == 'number') {
ret = {
type: 'number',
value: tokens[pos],
}
return pos + 1
}
else {
return undefined
}
}
function parse_operator(pos) {
// let's just reuse the function we already wrote insted of creating another huge 'if'
if (get_precedence(tokens[pos]) != 0) {
ret = {
type: 'operator',
operator: tokens[pos],
}
return pos + 1
}
else {
return undefined
}
}
function parse_expr(pos) {
var stack = [], code = [], n, op, next, precedence
pos = parse_primary(pos)
if (pos == undefined) {
// error, an expression can only start with a primary
return undefined
}
stack.push(ret)
while (true) {
n = pos
pos = parse_operator(pos)
if (pos == undefined) break
op = ret
pos = parse_primary(pos)
if (pos == undefined) break
next = ret
precedence = get_precedence(op.operator)
while (stack.length > 0 && get_precedence(stack[stack.length - 1].operator) >= precedence) {
code.push(stack.pop())
}
stack.push(op)
code.push(next)
}
while(stack.length > 0) {
code.push(stack.pop())
}
if (code.length == 1) ret = code[0]
else ret = {
type: 'expr',
stack: code,
}
return n
}
function main() {
tokens = [1, '+', 2, '*', 3]
var pos = parse_expr(0)
if (pos) {
console.log('parsed expression AST')
console.log(ret)
}
else {
console.log('unable to parse anything')
}
}
main()
这是您对调车场表达式解析的基本实现。这是用 JavaScript 编写的。这是你能得到的最简约和简单的。为简洁起见,标记化被省略了,您为解析提供标记数组(您称它们为词素)。
实际的调车场是parse_expr
功能。这是使用堆栈的“经典”实现,这是我的偏好,有些人更喜欢函数递归。
解析各种语法元素的函数通常称为“parselets”。这里我们有三个,一个用于表达,其他用于初级和运算符。如果 parselet 在该位置检测到相应的语法构造,pos
它将在构造之后立即返回下一个位置,并且通过全局变量返回 AST 形式的构造本身ret
。如果 parselet 没有找到它所期望的,它会返回undefined
。
现在添加对括号分组的支持非常简单(
,只需扩展parse_primary
等即可if (parse_group())... else if (parse_number())...
。与此同时,您parse_primary
将真正支持各种事物,前缀运算符,函数调用等。
推荐阅读
- r - R中的重复循环条件
- javascript - Winform Webbrowser 控件 Document.All.GetElementsByName 未找到元素
- python - Python:执行时提供的绑定数量不正确
- c++ - 如何删除由于宏扩展引起的所有 OClint 警告
- flutter - 从状态显示警报对话框
- rs485 - 无法使用 RS485 通信在多个设备之间读取数据
- mysql - Mysql Auto_increment id number 订单缺失
- mysql - Sequelize - 在 where 子句中查询其他表
- python - Pandas read_json() encoding = 'utf-8-sig' 选项不适用于 BytesIO 对象(类文件对象)
- python-3.x - 根据 ipywidget FloatSlider 更新绘图的问题