build your own lisp ch7 笔记

不念不忘少年蓝@ 2022-09-21 01:28 100阅读 0赞

# 求值 #

## 抽象语法树(AST) ##

**它根据用户的输入来表示程序的结构。叶子是数字和操作符－(实际要处理的数据), 分支是用来产生关于如何遍历和求值的规则的。**

### mpc\_ast\_t ###

`typedef struct mpc_ast_t { char* tag; char* contents; mpc_state_t state; int children_num; struct mpc_ast_t** children; } mpc_ast_t;`

`tag` : 包含一个规则列表的字符串。  
`contens`: 包含结点的实际内容，例如：’(‘, ‘\*’, ‘5’  
`state`: 当语法分析器找到这个结点的时候，它是什么状态  
`children_num`: 这个结点含有多少子结点。  
`children`: 子结点数组.

## 递归 ##

递归就是函数自己调用自己。首先定义一种结束递归的情况，然后在其他情况下调用自己。  
一个基本的最简单的情况是输入的树没有子结点，那么结果只有一个。然后在复杂的，就是树有多个子结点，结果就是结点本身加上它的子结点的结果。子结点的结果又是子结点本身加上它的子结点的结果，如此递归下去。  
统计子结点个树的例子

`int number_of_nodes(mpc_ast_t* t) { if (t->children_num == 0) { return 0; } if (t->children_num >= 1) { int total = 0; for (int i=0; i<t->children_num; i++) { total = total + number_of_nodes(t->children[i]); } return total; } return 0; }`

## 求值 ##

通过观察抽象语法树，发现如果一个节点的tag被标识为`number`, 那么这个结点就是一个数字，没有子结点，直接将它转换为整数。这个是我们递归中最基本的情况。  
如果一个结点被标识为`expr`而且不是`number`, 就去查看它的第二个子结点是什么操作符，然后将这个操作符应用于剩下的子结点的值(最后一个结点总是`')'`)，这个就是我们的递归的情况。

`atoi`: 将char\* convert to long  
`strcmp`: 判断两个char\*是否相等  
`strstr`: 判断第二个字符串是否是第一个的子串.