[コンパイラ]文法記述方法と再帰下降構文解析

*, /, ()を言語に追加するには演算子の優位順位を決めなければならない

– パーサの実装
入力はフラットなトークンの列で出力は入れ子構造を表す木にする

単純な生成規則
expr = num(“+” num | “-” num)*
mul = num(“*” num | “/” num)*
具象構文木(concrete syntax tree)

再帰を含む生成規則
expr = mul(“+” mul | “-” mul)*
mul = primary(“*” primary | “/” primary)
primary = num | “(” epr “)”

再帰下降構文解析
expr = mul(“+” mul | “-” mul)*
mul = primary(“*” primary | “/” primary)*
primary = num | “(” epr “)”

typedef enum {
	ND_ADD,
	ND_SUB,
	ND_MUL,
	ND_DIV
	ND_NUM,
} NodeKind;

typedef struct Node Node;

struct Node {
	NodeKind kind;
	Node *lhs;
	Node *rhs;
	int val;
};

Node *new_node(NodeKind kind, Node *lhs, Node *rhs){
	Node *node = calloc(1, sizeof(Node));
	node->kind = kind;
	node->lhs = lhs;
	node->rhs = rhs;
	return node;
}

Node *new_node_num(int val) {
	Node *node = calloc(1, sizeof(Node));
	node->kind = ND_NUM;
	node->val = val;
	return node;
}

Node *expr(){
	Node *node = mul();

	for(;;){
		if(consume('+'))
			node = new_node(ND_ADD, node, mul());
		else if(consume('-'))
			node = new_node(ND_SUB, node, mul());
		else
			return node;
	}
}

Node *mul(){
	Node *node = primary();

	for(;;){
		if(consume('*'))
			node = new_node(ND_MUL, node, mul());
		else if(consume('/'))
			node = new_node(ND_DIV, node, mul());
		else
			return node;
	}
}

Node *primary(){
	if(consume('(')){
		Node *node = expr();
		expect(')');
		return node;
	}

	return new_node_num(expect_number());
}