Абстрактное синтаксическое дерево для исходного кода, включая выражения

Question

Я создаю новый простой язык программирования (просто чтобы узнать, как работают компиляторы в свободное время).

Я уже создал лексер, который может разбивать мой исходный код на лексемы.

Однако теперь я застрял в том, как формировать абстрактное синтаксическое дерево из токенов, где исходный код может содержать выражение (с приоритетом оператора).

Для простоты я включу только 4 основных оператора:+, -, / и * в дополнение к скобкам ().Приоритет оператора будет следовать правилу BODMAS.

Я понимаю, что смогу преобразовать выражение из инфикса в префикс / постфикс, сформировать дерево и заменить его.

Однако я не уверен, еслиэто возможно.Даже если это возможно, я не уверен, насколько эффективно это может быть или насколько сложно это реализовать.

Существует ли какой-то тривиальный способ формирования дерева на месте без необходимости преобразования в префикс / постфикспервый?

Я натолкнулся на алгоритм Shunting Yard, который, кажется, делает это.Однако я обнаружил, что это довольно сложный алгоритм.Есть ли что-то попроще, или я должен продолжить реализацию алгоритма Shunting 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);
    }
}

Вывод Lexer:

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
)
;
}
}

Answer 1

    // 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.Это «классическая» реализация, которая использует стек, это мое предпочтение, некоторые люди предпочитают функциональную рекурсию.

Функции, которые анализируют различные элементы синтаксиса, обычно называются «парселеты».здесь у нас есть три из них, один для выражения, другие для основного и оператора.Если парсет обнаруживает соответствующую синтаксическую конструкцию в позиции pos, он вернет следующую позицию сразу после конструкции, а сама конструкция в форме AST возвращается через глобальную переменную ret.Если парсет не находит того, что он ожидает, он возвращает undefined.

Теперь легко добавить поддержку группировки парней (, просто расширить parse_primary с помощью if (parse_group())... else if (parse_number())... и т. Д. Тем временемВаш parse_primary станет очень большим, поддерживая различные вещи, префиксные операторы, вызовы функций и т. д.