关于 形式语言 自动机模型 乔氏文法 编程语言 现代计算机的碎碎

欢迎入坑。形式语言、自动机模型、lambda演算，都是计算理论的范畴，探讨的是什么可以计算，什么不能计算，以及时间、空间复杂度等。 上下文无关文法只是编译器前端。编程语言的语法经常用上下文无关文法定义，只是因为方便。编译器里的语法解析器仅仅是编译器的前端。编程语言还有语义、类型系统等。编译器中间段还有“中间语言”（intermediate representation）、变换、优化，后段还有机器码（汇编也行）生成，包括指令选择、寄存器分配，到运行时还有运行环境、垃圾回收、多线程的支持、动态装载、异常处理等一系列的问题。 现代的计算机是有限状态自动机（除非你有无限的内存），但人们都把它们当图灵机用，只要内存不溢出，你就永远发现不了它其实是假装的图灵机。 汇编语言是机器语言的人类可读的表示。但是，实际的汇编代码和汇编器不仅可以表示机器指令，还可以表示简单的数据，还可以表示各种可执行文件里需要的元数据，比如有哪些函数，有哪些段，这些段装载到内存里哪个位置，是否需要清零，是否可读、写、执行，有没有运行时可以查询的符号表，有没有装载时期的依赖，编译器的版本是什么，如何在异常抛出的时候回退一个函数的帧，垃圾回收如何扫描某个对象等。现代的汇编代码其实描述的是一个可执行文件（或者是库、没链接好的程序模块等）的内容结构，机器指令只是其中的一部分。 c语言和java语言都是高级语言，层次比汇编高。汇编和高级语言都有对方无法描述的概念，比如汇编可以描述“rotate right”这样的机器指令（如果机器提供），而c没有这样的基本运算；c能够描述复杂的数据类型，而汇编的数据类型只有简单的机器类型；java能描述“引用”和垃圾回收的语义，而c和汇编都不能描述。但高级语言程序要执行，要么把它翻译成机器语言（可以途径汇编语言）直接在机器上执行，或者用一个已经用机器语言写好（或者已经翻译成机器语言了）的解释器去执行，或者用混合型的策略。低层不能描述的概念（比如c的struct类型），要翻译成低层可以描述的概念（如struct的内存布局，即每个字段相对起始位置的地址偏移量，及其占的空间大小）。这种翻译总是会丢失信息的（比如把对struct的分配变成对内存的分配，把对字段的读写变成地址运算加上内存读写指令之后，汇编码里就再也看不到struct类型了，各个字段的类型、名称也都丢了）。如果运行时必须知道一些高层的信息（比如java的垃圾回收必须知道哪些字段是“引用”，哪些不是，那就必须把类型信息编码成字节串，用汇编或者自己定义的二进制数据表示出来，和可执行文件一起保留到运行时（对于解释器和jit编译器来说，就是运行时产生的），然后解码。所以那几种语言不等价，但从计算理论的角度看，计算能力都和图灵机一样（只要有无穷多的内存）。 编译器的解析器可以用自动机实现，也可以不用（其实每个程度都相当于一个自动机）。 语言实现=编译器 与/或 解释器 加上 运行环境，运行环境包括解释器、jit编译器本身（如果适用），以及运行时的库（包括语言的标准库以及系统提供的和操作系统打交道的库，还有操作系统内核，还有硬件等）。语言的实现，按照语言的定义去做，是语言定义的具体化，可以涉及语言定义中故意不规定的部分（比如java没有规定用什么垃圾回收算法，java虚拟机就既可以用mark-sweep，又可以用semi-space）。 什么才叫“真正的”lambda演算呢？ 为什么能在现代的机器上跑？这个问题嘛，只要看看函数怎么翻译成机器指令序列，以及“闭包”如何表示，就可以了。为什么要阉割呢？阉割之前是什么样的呢？

话说这些问题楼主是不是问过，这么熟悉。

【 在 nuanyangyang 的大作中提到: 】 : 欢迎入坑。形式语言、自动机模型、lambda演算，都是计算理论的范畴，探讨的是什么可以计算，什么不能计算，以及时间、空间复杂度等。 : 上下文无关文法只是编译器前端。编程语言的语法经常用上下文无关文法定义，只是因为方便。编译器里的语法解析器仅仅是编译器的前端。编程语言还有语义、类型系统等。编译器中间段还有“中间语言”（intermediate representation）、变换、优化，后段还有机器码（汇编也行）生成，包括指令选择、寄存器分配，到运行时还有运行环境、垃圾回收、多线程的支持、动态装载、异常处理等一系列的问题。 : 现代的计算机是有限状态自动机（除非你有无限的内存），但人们都把它们当图灵机用，只要内存不溢出，你就永远发现不了它其实是假装的图灵机。 : ................... 暖神，站在坑边，欲疯欲癫，save me 基于我对上述名词的浅薄理解，引发了我出于片面的阅读内对这个领域隐约的“悖论“困惑，这种”悖论“感觉目前是我无法用直观形式的语言去描述的，但大概齐是关于 理论 、模型、应用三者界限的模糊划分导致的。 比如图灵机是种理论，模型是自动机，但真正实现应用的计算机又另当别论。说不清楚这三者的界限和区别，概念划分的依据是什么。 如果编程语言都是图灵完备的，这句话从可计算性的角度来说的，那么完成同一个任务每个语言的能力是相同的，那么各语言的特性又是从哪个方面来差异化的，这种差异化背后的理论依据是什么，语言的特性是必须的么？ 编译器=编程语言实现?=编程语言，如果相等的话，编译器就应该是个图灵机，但是图灵机怎么可能造出来呢？如果不等的话，编译器哪些地方没有等价于语言？ 编译器中语义分析实现依据的理论是什么，语义分析有形式语言的背景知识么？这些语义分析和自然语言处理中的语义分析也是同宗吧 其实这些困惑的出发点源自于对函数式语言，惰性求值，记忆化的如何定义和实现，如果λ演算才是编程的正统，为何如今函数式编程的式微，编程语言的发展背后的规律究竟是什么？

【 在 henceman 的大作中提到: 】 : 暖神，站在坑边，欲疯欲癫，save me : 基于我对上述名词的浅薄理解，引发了我出于片面的阅读内对这个领域隐约的“悖论“困惑，这种”悖论“感觉目前是我无法用直观形式的语言去描述的，但大概齐是关于 理论 、模型、应用三者界限的模糊划分导致的。 : 比如图灵机是种理论，模型是自动机，但真正实现应用的计算机又另当别论。说不清楚这三者的界限和区别，概念划分的依据是什么。 内存有限和内存无限啊，这么明显的区别 : 如果编程语言都是图灵完备的，这句话从可计算性的角度来说的，那么完成同一个任务每个语言的能力是相同的，那么各语言的特性又是从哪个方面来差异化的，这种差异化背后的理论依据是什么，语言的特性是必须的么？ 从北京到广州，走路可以到，骑自行车可以到，骑摩托车可以到，坐火车可以到，坐飞机可以到。同样是坐火车，坐硬座可以到，坐硬卧可以到，坐软卧可以到。同样坐飞机，坐经济舱能到，坐头等舱也能到。同样坐汽车，自己开车可以到，找人帮你开车可以到。所以你是喜欢走路去广州还是坐头等舱去广州呢？想自己开车自己选择最佳路径，还是让别人来开自己省点事呢？你有专业司机选路选得好吗？反正都是能到，所以走路去广州、坐汽车去广州、坐飞机去广州都是一样的吧？有什么差异呢？别的方法都能去广州，飞机这个东西还有存在的必要吗？ : 编译器=编程语言实现?=编程语言，如果相等的话，编译器就应该是个图灵机，但是图灵机怎么可能造出来呢？如果不等的话，编译器哪些地方没有等价于语言？ 过大的源文件会把GCC也崩掉。编译器无法处理太大的源文件。有的语言也对程序的复杂性做了限制，比如C语言限制块的嵌套数（63层）；JVM会限制每个函数里局部变量的个数（65536个）。所以，人们一直在自欺欺人，自以为计算机是图灵机，直到机器崩掉。 : 编译器中语义分析实现依据的理论是什么，语义分析有形式语言的背景知识么？这些语义分析和自然语言处理中的语义分析也是同宗吧 语义这个东西，语言随便规定，什么都可以算是语义。比如类型系统本身也是一个领域。还有比如面向对象编程的继承、封装、多态，都是语义；多线程里的内存模型也是语义；Rust这种基于“所有制”的语言里，“所有制”也是语义。还有协程之间的切换、浮点数运算、数组操作……全都是语义。不一定非得是形式语言才是语义。如果有人发明一种领域专门语言，比如开汽车的语言，那么汽车驾驶也是语言语义的一部分。 : 其实这些困惑的出发点源自于对函数式语言，惰性求值，记忆化的如何定义和实现，如果λ演算才是编程的正统，为何如今函数式编程的式微，编程语言的发展背后的规律究竟是什么？ 编程语言是为生产服务的。人们觉得什么样的语言好用，就会设计什么样的语言。C语言的历史就可以看出，人们或许觉得BCPL的只有一种类型的类型系统不好用，才发明了B和C；松本行弘决定现有的编程语言对程序猿太不友好了，才设计出对人类友好的ruby语言；Rasmus Lerdorf本来想做一个个人主页（personal home page）预处理器，做了一套宏，本来没想做语言，结果用户不断往里加特性，于是就成了PHP语言；后来Facebook被PHP这个设计混乱，根本无法高效实现的语言坑了，想设计一个和PHP有一定兼容性又可以高性能实现的语言，于是就设计了HHVM虚拟机和Hack语言；当初ML语言的发明也是为了展示一下algebraic type system；Haskell是参加会议的一些研究人员喜欢惰性求值，但又不喜欢闭源的Miranda，而提出设计的。java语言到1.8才加上lambda表达式，还不是因为lambda表达式好用？ 至于如何实现惰性求值，建议看一看spineless tagless g-machine。这是实现惰性求值的一种方法。其实没什么神秘的。可以认为每个表达式创建一个对象。它没被求值的时候存着指向“如何求值”的操作的函数；第一次求值就是调用这个函数；被求值以后里面存着值，顺便存一个标记说“已经求过了”。这样每个表达式就不会被求两次值。当然这种表示方法除非进行大量的优化否则不会太高效。

【 在 nuanyangyang 的大作中提到: 】 : 从北京到广州，走路可以到，骑自行车可以到，骑摩托车可以到，坐火车可以到，坐飞机可以到。同样是坐火车，坐硬座可以到，坐硬卧可以到，坐软卧可以到。同样坐飞机，坐经济舱能到，坐头等舱也能到。同样坐汽车，自己开车可以到，找人帮你开车可以到。所以你是喜欢走路去广州还是坐头等舱去广州呢？想自己开车自己选择最佳路径，还是让别人来开自己省点事呢？你有专业司机选路选得好吗？反正都是能到，所以走路去广州、坐汽车去广州、坐飞机去广州都是一样的吧？有什么差异呢？别的方法都能去广州，飞机这个东西还有存在的必要吗？ 暖神，我理解这个列子中，"从北京到广州"这个问题首先是个能不能完成的问题（可计算性），一定有人证明了在三维时空的限度下，他是可以完成的，而自行车，摩托车，火车，飞机是实际上的计算模型（自动机），这些机器的计算能力有强有弱，但是并不能改变这个问题的可计算性，造成这些机器计算能力强弱的原因是能量释放效率的研究（等同于0~2形式文法的规约），而这些都不是编译器的范畴，假如人体中化学能释放够快的话，没准也不需要飞机火车。我理解的编译器在这个例子中角色应该是，假如飞机是解决目前行程问题的最强自动机，那么在这个前提下，编译器就是那些飞机场，航空公司，机票代理商，飞机上的座椅，杂志，视频，难吃的飞机餐等等，都是为了做飞机更舒服，没有这些呢，半个世纪前的飞机同样也能到达广州，没准比现代更快。另外还想到一点，高维空间，黑洞什么的代表着计算复杂度的问题，三维世界里就只能做飞机了。 : 语义这个东西，语言随便规定，什么都可以算是语义。比如类型系统本身也是一个领域。还有比如面向对象编程的继承、封装、多态，都是语义；多线程里的内存模型也是语义；Rust这种基于“所有制”的语言里，“所有制”也是语义。还有协程之间的切换、浮点数运算、数组操作……全都是语义。不一定非得是形式语言才是语义。如果有人发明一种领域专门语言，比如开汽车的语言，那么汽车驾驶也是语言语义的一部分。 暖神，语义分析是在语法树建立之后，我理解的，语义是种对语法的进一步约束，在语法分析对应于乔氏文法的条件下，语义分析后的语言就递归可枚举语言的一个更小子集，语义/特性加入的越多，约束越多，那么这个语言能表达/计算的能力越弱。 有个问题是各种语义的约束是怎么去形式化的呢？这些语义特性都是正交的么，语义/特性的加入会影响到图灵完备性吗？ 语义的实现(编译器语义分析)有通用的吗？我看有些地方讲到语义分析往往是手工完成的，根据各自语言的语义特性去完成编译器开发。 : 编程语言是为生产服务的。人们觉得什么样的语言好用，就会设计什么样的语言。C语言的历史就可以看出，人们或许觉得BCPL的只有一种类型的类型系统不好用，才发明了B和C；松本行弘决定现有的编程语言对程序猿太不友好了，才设计出对人类友好的ruby语言；Rasmus Lerdorf本来想做一个个人主页（personal home page）预处理器，做了一套宏，本来没想做语言，结果用户不断往里加特性，于是就成了PHP语言；后来Facebook被PHP这个设计混乱，根本无法高效实现的语言坑了，想设计一个和PHP有一定兼容性又可以高性能实现的语言，于是就设计了HHVM虚拟机和Hack语言；当初ML语言的发明也是为了展示一下algebraic type system；Haskell是参加会议的一些研究人员喜欢惰性求值，但又不喜欢闭源的Miranda，而提出设计的。java语言到1.8才加上lambda表达式，还不是因为lambda表达式好用？ 飞机和编译器的发展都是为了人类能够更懒，掩饰人的弱点，满足各种欲望，如果飞机是为了满足人的各种感官刺激，那编译器是为了满足哪些需求呢？这些需求直观上是人的思维逻辑层次上的，这些思维逻辑有什么规律或者形式化的解释么？这些语言特性有没有编译器不能实现的。 关于函数式编程，哪些特性是需要必须实现的？

我觉得你混淆了两个概念： 1. 文本代码解析器 2. 编译器 前者指的是如何让程序去把用字符串书写出来的程序转换成一个结构化的表示形式。后者是把程序由一种形式转换成另一种形式（如字节码到机器码，或者源代码到机器码，或者源代码到中间代码）的工具。两者不一定有交集。举两个极端的例子： 1. XML的语法可以用正则表达式和上下文无关文法来描述，也可以基于这种文法来构造解析器，但这不是编译器，因为XML不是程序。 2. Scratch（如下图）是个完全没有源代码的“编程语言”，但它却有一个真正的编译器，因为要对程序进行变形并执行。 [upload=1][/upload] 确实，传统的程序都是用文本来写的。而描述程序的语法，一种最合适的方法就是用上下文无关文法。一个程序的语法解决的问题是：什么样的程序是合法的程序？（就是语法能否接受这个输入）以及如果是合法的程序，它对应的语法树是什么样子的？（就像自然语言有主谓宾，主语有定语和中心语一样）形式文法碰巧很擅长这个工作：文法的不断展开的过程就可以形成一个树形结构，稍加变换就能由具体的文法驱动的语法树，变成更贴近程序的抽象结构的的抽象语法树。而“语法制导翻译”（grammar-directed translation）在当初内存不是很充足，不能把整棵树放进内存的时代，是一种很合适的翻译思想，就是给语法树的每个节点赋予“语义”，这个语义可以是整数的值、变量的类型，也可以是算术运算符的指令以及操作数。同时也能拒绝语法恰当而语义有问题（比如“整数加字符串”）。这就让人感觉到“语义就是对语法的限制”。从这个一切由语法出发，语义依附于语法的这种实现方法的角度上看，这也没错。 但是时代变了。语法制导的翻译让人觉得只要扫一遍代码就能把源代码翻译成汇编（或者直接翻译成机器码）。或许上编译原理课的时候还做过练习，做一个计算器，扫一遍表达式就能算出表达式的值。但是这种思想已经陈旧了。虽然一边扫描编译速度很快，但对语法的设计有限制。比如 1. 为什么C语言函数要先声明、或者先定义，后使用？就像下面的程序为什么是错的： int foo() { return bar(); // Undefined identifier "bar" } int bar() { return 42; } 但是同样的程序在Java里却可以跑？ 2. 为什么C语言里构造不出来两个互为参数的函数？ typedef int CallBackFuncType1(CallBackFuncType2 arg); // undefined identifier CallBackFuncType2 typedef int CallBackFuncType2(CallBackFuncType1 arg); 3. 为什么C++11里，传统语法定义的函数的返回值不能通过参数推导类型，而新的auto语法就可以？ template<typename T, typename U> decltype(t + u) AddGeneric(T t, U u) { // error: undefined identifier 't' return t + u; } template<typename T, typename U> auto AddGeneric(T t, U u) -> decltype(t + u) { // OK return t + u; } 实际上都是语言的设计向一边扫描的实现策略妥协的结果。第一个是因为语法导向的编译器看到foo的时候还不能从之前读入的程序中推断出bar的类型；第二个也是因为之前的程序没有提到CallBack2；第三个就更有意思了：编译器要是先看到参数，就知道它们的类型，也就能推断返回值的类型了，而如果先看到返回值类型而没有看到参数，就无法进行类型推到了，这就是为什么C++11要进行一个如此微妙的语法修改，才能实现这种语义。都是一遍扫描的要求引发的。 但是，如果我们不这么早地引入语义，而是先把抽象语法树生成，然后再去考虑语义，我们就可以自由地设计程序的语法了，然后自由地分析语义。Java里，函数可以以任何顺序定义，随意互相调用；Java类可以互相循环引用，没有问题。 现代的编译器都会有很多个步骤。语法解析器（以及它设计的上下文无关文法什么的）仅仅是编译器的最前端，甚至还不能算作整个“前端”。编译器一般会有好几种中间表示形式。在前端有和语言相关的抽象语法树、控制流图等，可以在高层的语义上对程序进行变换，比如将virtual函数变成非virtual的。到了中端，还有语言无关的的表示形式，层次会稍微低一些，但可以进行另外一批变换，比如将循环中的不变量提到循环外面。到后端还有和机器相关的形式，可以针对具体的机器进行代码生成，包括指令选取、寄存器分配等。还有一些，比如死代码消除，在任何层次都可以做。现实中的编译器，比如clang，有自己的C/C++解析器，前端很简单，稍作翻译就交给LLVM作为中端，LLVM进行大量的优化，用它的后端生成机器码。整个过程步骤非常多，涉及的“语义”也非常的丰富（比如java里那个“一个线程看到y==2是否一定看到x==1“这种的），绝不仅仅是“对语法进行限制”就可以表达的。所以，手工完成，是真的。在有了语法树或者各种中间表示形式以后，写个程序随便怎么分析都可以。 要跳过语法解析也是可以的。比如如果要解析brainfuck语言的程序，最好的工具绝不是用ebnf写出brainfuck的语法，而是直接用getchar读。 所以，“编译器”和“形式语言的文法”之间的关系，仅仅停留在源代码层级。“编程语言”和“图灵完备性”之间的关系是可计算性上的，而编程语言、编译器和具体机器的实现更接近，而图灵机和lambda演算则是抽象的、数学的理论计算模型。 我举的交通工具的例子是想说明：不同的语言从可计算性上看是同一种计算模型，在可计算性方面是等价的，但实现出来效率以及舒适程度大相径庭。注意0-3型文法的表达能力是不同的！它们真的不等价！你可以证明“括号匹配”问题可以用上下文无关文法表示，但无论如何也不能用正则表达式解决。如果要比喻的话，如果走路是0型文法，可以让你走到广州，那么私家车也是0型文法，也可以让你去广州，但北京地铁就是3型文法：虽然快，但不能去广州。 【 在 henceman 的大作中提到: 】 : 暖神，我理解这个列子中，"从北京到广州"这个问题首先是个能不能完成的问题（可计算性），一定有人证明了在三维时空的限度下，他是可以完成的，而自行车，摩托车，火车，飞机是实际上的计算模型（自动机），这些机器的计算能力有强有弱，但是并不能改变这个问题的可计算性，造成这些机器计算能力强弱的原因是能量释放效率的研究（等同于0~2形式文法的规约），而这些都不是编译器的范畴，假如人体中化学能释放够快的话，没准也不需要飞机火车。我理解的编译器在这个例子中角色应该是，假如飞机是解决目前行程问题的最强自动机，那么在这个前提下，编译器就是那些飞机场，航空公司，机票代理商，飞机上的座椅，杂志，视频，难吃的飞机餐等等，都是为了做飞机更舒服，没有这些呢，半个世纪前的飞机同样也能到达广州，没准比现代更快。另外还想到一点，高维空间，黑洞什么的代表着计算复杂度的问题，三维世界里就只能做飞机了。 : 暖神，语义分析是在语法树建立之后，我理解的，语义是种对语法的进一步约束，在语法分析对应于乔氏文法的条件下，语义分析后的语言就递归可枚举语言的一个更小子集，语义/特性加入的越多，约束越多，那么这个语言能表达/计算的能力越弱。 : 有个问题是各种语义的约束是怎么去形式化的呢？这些语义特性都是正交的么，语义/特性的加入会影响到图灵完备性吗？ : ...................

难得一见的plt帖子，赞

暖神是干啥的啊，感觉对计算机系统结构各个方面都很了解。

学习！