一直很记得，某篇文章提到了"LISP是工作在抽象语法树(abstract syntax tree)里的"。
当时虽然刚学习了编译原理，但是还是一直对这句话百思不得其解。
最近抽空又想了一下，有了一点点结论。
1. cs(concrete syntax)定义(define)了语言。即规定了一个句子是否是符合该语言的语法(grammar)的。比如，考虑一个很简单的语法：
S->Sa|b
显然ba是符合语法的，而ab是不符合语法的。在计算机读取一个语言的句子时，必须判断该句子是否符合语法，并且通过语法可以构建出这些句子的分析树（parse tree）。
反映了这门语言的具体语法结构。注意定义(definition)与实现(implementation)的区别。往往不同的编译器遵照不同的定义可以编译不同的语言，然而其内部构建的抽象语法树的语义却有可能是相同的。举一个极端的例子：
E->1＋2
显然这个语言的所有句子是1+2。如果我们赋予"+"的语义是数学中的整数加。显然该句子的语义是"一加二"。''eval''的结果应该为整数3。
分析树和语法树为：
E
/|\
1 + 2
+
/ \
1 2
再考虑:
S->(1+2)
显然，这时，1+2这个句子已经不是合法的句子了……然而(1+2)构建出来的抽象语法树，在+符号与上面的例子相同的语义的前提下，却是有相同语法树的。
分析树为：
E
/ / | \ \
( 1 + 2 )
语法树同上例。
语法树与分析树的联系有：语法树是分析树的抽象形式，或压缩形式，它把分析树中对语义无关紧要的成分删除了。
分析树中单个产生的链条在语法树中可以被压缩，括号等为了删除二义性引入的辅助符号亦可不要，因为从语法树的结构已经可以明确得知eval的顺序了。
如S->A->B->(1+2) 这个文法构建出来的语法树中，S->A->B这个链条是废的，两个括号也是废的。构建出来的语法树与上例完全相同。
引用一句话：为了适应语义分析的需要，把语法规则中对语义无关紧要的具体规定去掉，剩下来的本质性的东西叫做抽象语法。
在编译器的编译过程中，会把一个具体的程序翻译成类似抽象语法树的内部表示。即此时已经很明确求值（eval）的具体顺序，而无须多余的语法辅助（如引入括号规定+-*/的优先级以避免二义性）。
说到这里，已经可以模糊地得知为什么说LISP是工作在抽象的语法树上了。
因为它的语法足够简单，完全就是把一些多余的语法糖衣(syntatic sugar)去除，写程序时写出来的具体语法结构，事实上已经与抽象的语法树结构基本一致了（当然还是需要一些括号来分隔/delimit字符的，这就是具体语法）。换句话说，LISP的程序直接就反映了程序的逻辑结构，一个LISP程序就是形如一棵自底向上求值树的东西。（这个名词我临时发明的，希望没有侵犯谁的知识产权……）举例来说，
(+ 1
(* 2
(- 3 4)))
写出来就是一个跟list很像的形式，同时也反映了计算机内部自底向上求值的过程（著名的read-eval-print-loop)
+
|\
1 *
|\
2 -
|\
3 4
当然，这就与自然语言似乎有点不同了，要求我们递归地构造起一颗语法树，因此入门时会觉得有点不习惯。
牛B的是，我们可以说，在LISP里面写的procedure，就已经成了LISP语法的一部分，因为高阶函数(high-order function)的存在。（欲听后事如何，且听下回分解）
好玩的是，这棵树的每个内部节点，可以看作一个谓词(predicate)，而各个叶子节点则是参与谓词逻辑的终端符号。
所以说LISP跟AI太有关系了。
更牛B的是，有一种说法是，为什么音乐比较容易入脑？根据AI的理论，人脑工作原理跟平时的编译、谓词逻辑推导很相似。
我们之所以记忆东西需要一定的脑力和时间，是因为我们需要把它翻译成我们大脑内部表示数据的结构再进行理解。
而音乐正如LISP语言般，直接就是用抽象语法树的方式工作，直接给出了我们大脑内部的抽象语法树，所以少了一个步骤，因此比较容易记忆……orz
http://www.pchristensen.com/blog/articles/music-operates-directly-on-your-abstract-syntax-tree/
当时虽然刚学习了编译原理，但是还是一直对这句话百思不得其解。
最近抽空又想了一下，有了一点点结论。
1. cs(concrete syntax)定义(define)了语言。即规定了一个句子是否是符合该语言的语法(grammar)的。比如，考虑一个很简单的语法：
S->Sa|b
显然ba是符合语法的，而ab是不符合语法的。在计算机读取一个语言的句子时，必须判断该句子是否符合语法，并且通过语法可以构建出这些句子的分析树（parse tree）。
反映了这门语言的具体语法结构。注意定义(definition)与实现(implementation)的区别。往往不同的编译器遵照不同的定义可以编译不同的语言，然而其内部构建的抽象语法树的语义却有可能是相同的。举一个极端的例子：
E->1＋2
显然这个语言的所有句子是1+2。如果我们赋予"+"的语义是数学中的整数加。显然该句子的语义是"一加二"。''eval''的结果应该为整数3。
分析树和语法树为：
E
/|\
1 + 2
+
/ \
1 2
再考虑:
S->(1+2)
显然，这时，1+2这个句子已经不是合法的句子了……然而(1+2)构建出来的抽象语法树，在+符号与上面的例子相同的语义的前提下，却是有相同语法树的。
分析树为：
E
/ / | \ \
( 1 + 2 )
语法树同上例。
语法树与分析树的联系有：语法树是分析树的抽象形式，或压缩形式，它把分析树中对语义无关紧要的成分删除了。
分析树中单个产生的链条在语法树中可以被压缩，括号等为了删除二义性引入的辅助符号亦可不要，因为从语法树的结构已经可以明确得知eval的顺序了。
如S->A->B->(1+2) 这个文法构建出来的语法树中，S->A->B这个链条是废的，两个括号也是废的。构建出来的语法树与上例完全相同。
引用一句话：为了适应语义分析的需要，把语法规则中对语义无关紧要的具体规定去掉，剩下来的本质性的东西叫做抽象语法。
在编译器的编译过程中，会把一个具体的程序翻译成类似抽象语法树的内部表示。即此时已经很明确求值（eval）的具体顺序，而无须多余的语法辅助（如引入括号规定+-*/的优先级以避免二义性）。
说到这里，已经可以模糊地得知为什么说LISP是工作在抽象的语法树上了。
因为它的语法足够简单，完全就是把一些多余的语法糖衣(syntatic sugar)去除，写程序时写出来的具体语法结构，事实上已经与抽象的语法树结构基本一致了（当然还是需要一些括号来分隔/delimit字符的，这就是具体语法）。换句话说，LISP的程序直接就反映了程序的逻辑结构，一个LISP程序就是形如一棵自底向上求值树的东西。（这个名词我临时发明的，希望没有侵犯谁的知识产权……）举例来说，
(+ 1
(* 2
(- 3 4)))
写出来就是一个跟list很像的形式，同时也反映了计算机内部自底向上求值的过程（著名的read-eval-print-loop)
+
|\
1 *
|\
2 -
|\
3 4
当然，这就与自然语言似乎有点不同了，要求我们递归地构造起一颗语法树，因此入门时会觉得有点不习惯。
牛B的是，我们可以说，在LISP里面写的procedure，就已经成了LISP语法的一部分，因为高阶函数(high-order function)的存在。（欲听后事如何，且听下回分解）
好玩的是，这棵树的每个内部节点，可以看作一个谓词(predicate)，而各个叶子节点则是参与谓词逻辑的终端符号。
所以说LISP跟AI太有关系了。
更牛B的是，有一种说法是，为什么音乐比较容易入脑？根据AI的理论，人脑工作原理跟平时的编译、谓词逻辑推导很相似。
我们之所以记忆东西需要一定的脑力和时间，是因为我们需要把它翻译成我们大脑内部表示数据的结构再进行理解。
而音乐正如LISP语言般，直接就是用抽象语法树的方式工作，直接给出了我们大脑内部的抽象语法树，所以少了一个步骤，因此比较容易记忆……orz
http://www.pchristensen.com/blog/articles/music-operates-directly-on-your-abstract-syntax-tree/
No comments:
Post a Comment