包含表达式的源代码抽象语法树

Question

我正在构建一种新的简单编程语言（只是为了在空闲时间学习编译器的工作原理）。

我已经构建了一个词法分析器，它可以将我的源代码标记为词素。

但是，我现在卡在如何从标记中形成抽象语法树，其中源代码可能包含一个表达式（具有运算符优先级）。

为了简单起见，除了括号 () 之外，我将只包含 4 个基本运算符：+、-、/ 和 *。运算符优先级将遵循 BODMAS 规则。

我意识到我可以将表达式从中缀转换为 prefix/postfix，形成树并替换它。

但是，我不确定这是否可行。即使有可能，我也不确定它的效率如何或实施起来有多困难。

是否有一些无需先转换为 prefix/postfix 就地形成树的简单方法？

我遇到了似乎可以做到这一点的调车场算法。但是，我发现它是一个相当复杂的算法。有没有更简单的东西，或者我应该继续实施调车场算法？

目前，我的词法分析器对以下程序进行了如下标记：

我正在演示使用 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
)
;
}
}

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中的。这是尽可能简约和简单的。为了简洁起见，标记化被省略了，你给解析器一个标记数组（你称它们为 lexemes）。

真正的调车场是parse_expr功能。这是使用堆栈的 "classic" 实现，这是我的偏好，有些人更喜欢函数递归。

解析各种语法元素的函数通常称为"parselets"。这里我们有三个，一个用于表达式，其他用于主要和运算符。如果 parsetet 在 pos 位置检测到相应的语法结构，它将 return 结构之后的下一个位置，并且 AST 形式的结构本身是通过全局变量 returned return =13=]。如果 parlet 没有找到它所期望的 returns undefined.

现在添加对括号分组 ( 的支持非常简单，只需将 parse_primary 扩展为 if (parse_group())... else if (parse_number())... 等。与此同时，您的 parse_primary 会变得非常大支持各种事物，前缀运算符，函数调用等

包含表达式的源代码抽象语法树

Abstract Syntax Tree for Source Code including Expressions

compiler-construction

parsing

abstract-syntax-tree

lexer