- Article -

编译原理粗浅学习笔记1预备知识

分类于 编译原理 标签 编译原理 笔记 发表于2020-06-03 20:50

背景

对于计算机的任何一个领域来说，水都可以深得超出外行的想象，编译原理也是，因此我悄悄在标题上添加了粗浅两个字，当然，我们也不要妄自菲薄，潜意识里给自己划定范围，没有尝试就不应该觉得自己不行。即使最后只学习了一部分知识点，我觉得也能解决我长期以来的大部分疑惑和对原理了解的强烈愿望。希望从中学习词法分析dfa/nfa，Parsing方面的BNF，知道AST，会写简单的递归下降parser，会用antlr之类的parser generator等。

在开发博客的过程中，因为当初想着学习 GO ,因此坚决不想使用第三方库，尽量自己实现和学习，到后面需要解析 MD 文档，本来开始我是想着自己用正则来做的，但是正则性能不是很好，也不好维护，我想着除了正则还要其他方式吗？能根据各种规则生成自己需要的东西， 于是了解到了编译原理，然后发现将一系列字符串根据文法规则解析然后翻译成自己想要的东西这种技术太酷了。虽然后面博客的 md解析 使用的是 JS 的第三方库，但是这件事却给我学习编译原理的强烈愿望。后面也发现，只有学习了编译原理，才能在本质上去了解编程语言而不被各种眼花缭乱的编程语言所吸引。希望自己能坚持下来，然后自己实现一个简单可用的 MD引擎。

编译原理的一般步骤

编译器的前端和后端

编译器一般分为前端和后端，他们分别是：

前端

后端

这里我也主要是学习前端，因为后端大部分都是和机器相关，也比较底层，如果有一天真的用到了在学也不迟。

编译原理可以做什么？

各种编程语言语法高亮，less,scss转换为css等 从各种格式的数据中提取信息：XML/JSON/CSV/Excel；... 各种格式文本的转换：word/markdown... 生成到pdf/html/.. 写爬虫从HTML中抓感兴趣的内容，实现/修改模板引擎，ORM..自定义描述测试用例规范的脚本， 然后自动生成测试用例...心理学实验，按一个简单规范（语法）写描述性句子，就能生成相关的场景图； 用yacc解析法律文本等等。

其他理解的相关概念

对于计算机基础不扎实的我来说，要学习和理解编译原理，可能想要一些额外的知识储备，理解一些其他相关的知识点。 这些知识点都是看视频和在网上收集整理而来。

上下文无关文法 & 上下文有关文法

知乎 Towser 的例子

上下文无关文法就是说这个文法中所有的产生式左边只有一个非终结符,即

//产生式：
Sent -> S V O
S -> 人 | 天
V -> 吃 | 下
O -> 雨 | 雪 | 饭 | 肉

Sent、 S、 V、 O 是非终结符，汉字是终结符，上面的文法一共可以组合22种，｛人吃饭，天下雨，人吃肉，天下雪，人下雪，天下饭，天吃肉，……｝ 因此有的组合是不通顺的，我们添加一些文法约束。

Sent -> S V O
S -> 人 | 天
人V -> 人吃
天V -> 天下
下O -> 下雨 | 下雪
吃O -> 吃饭 | 吃肉

这里对 V 的推导过程施加了约束：虽然 V 还是能推出”吃“和”下“两个词，但是仅仅当 V 左边是”人“时，才允许它推导出”吃“；而当 V 左边是”天“时，允许它推导出”下“。这样通过上下文的约束，就保证了主谓搭配的一致性,这样一来，这个语言包含的句子就只有｛人吃饭，天下雨，人吃肉，天下雪｝这四条，都是语义上合理的。因此这种就是上下文有关文法。

Token

Token是编程语言中最小的具有独立含义的词法单元。

词法分析是计算机科学中将字符序列转换为标记（token）序列的过程。从输入字符流中生成标记的过程叫作标记化（tokenization），在这个过程中，词法分析器还会对标记进行分类。

二元运算其他表示

sum = (10 + 20) * ( num + square )

编译器自展(跌代) & 语言的自举

以前简单的了解过这部分，我一直百思不得其解，语言的自举简直就是鸡生蛋和蛋生鸡的问题。

那何为自举呢？我们知道一门编程语言写好了原代码，需要用编译器去编译代码，生成二进制可执行的机器码。而自举就是使用当前的编程语言来写一个自己的编译器来编译自己的代码，是不是有点不可思议？？

例如，发明了Go语言之后，刚开始是没有编译器的，他的编译器是 C 写的。这个编译器可以将 go 源代码翻译成 二进制机器码，然后，在用go写一个 go 的编译器，然后用之前C写的编译器编译这个编译器，那么我们就得到了一个新的编译器，这个新的编译器是 GO 自己写的 Go 编译器，自此 GO 就完成了自举，一个语言的自举代表语言的成熟。

那么问题来了，C的编译器如 gcc 又是从哪里来的呢？而gcc本身又是c语言程序，那gcc是怎么被编译出来的?

如果说C的编译器是汇编写的，那汇编器又是那里来的呢？很显然汇编的编译器是机器码写的，用机器码写一个完整的汇编编译器也是不可能的，因为机器码都是二进制0和1.那第一个汇编编译器怎么来的呢？？这其实就是编译器的自展了，比如，刚开始我们可以用机器码实现一些简单的汇编指令，比如循环，得到一个最小的汇编器，再用这个汇编器完善其他汇编指令，以此不停的跌代自展，直到完成一个汇编器

目前一共有三种类型的编程语言：编译型、解释型、虚拟机型。 其中，编译型和虚拟机型语言是可以自举的，而解释型语言是不能自举的。其中，编译型语言可以完整自举。不过虚拟机型语言的自举是不完整的——它不能自己实现自己的虚拟机。跌代

二义性

如果文法G中的某个句子存在不只一棵语法树，则称该句子是二义性的。如果文法含有二义性的句子，则称该文法是二义性的，设计一个完善的语言应该避免这种二义性。

自然语言处理（NLP）和 编程语言翻译

NLP (Natural Language Processing) 是人工智能（AI）的一个子领域。简单说就是对人类语言的分析处理研究。

自然语言与编程语言翻译基本都是经过相同的步骤流程：词法分词，语法分析，语义分析，token翻译，重组，优化结构，到最后的结果。 但是编程语言与自然语言相比：

  1. 词汇量：编程语言的关键字等标识有限，自然语言的词汇量巨量无限
  2. 结构化：编程语言是结构化的，自然语言是非结构化
  3. 歧义性：编程语言都有确定的语义表达，自然语言不同语境不同的意思
  4. 容错性：程序必须保证拼写绝对正确，自然语言更随意，也容许有错误表达
  5. 易变性：编程语言的变化缓慢又小，自然语言的变化随着社会发展
  6. 简略性：编程语言要求准确细致满足所有运行条件，自然语言简略干练形式不限

逻辑语

在中文或英文等自然语言中，同一句话往往可以根据不同的文化环境，不同的地域，不同的时间表达的意思也不一样，相对于人造语来说，学习成本一般会高得多。 逻辑语是一门精确的人造语，除此之外，还有道本语、国际辅助语、简语等，而简语被作者介绍为世界上最简易的实用语言，对语言感兴趣可以 关注知乎上一位作者 路易·罗莎 是一个造语者(Conlanger)，同时也是语言相关话题的优秀回答者。

逻辑语（lojban）基于形式逻辑，可以像计算机语言一样被parse。

DSL（领域专用语言）

领域专用语言（domain specific language / DSL），其基本思想是“求专不求全”，不像通用目的语言那样目标范围涵盖一切软件问题，而是专门针对某一特定问题的计算机语言。 领域专用语言是一种针对特定类问题优化，包含更高级抽象的编程语言。 DSL 使用来自专业或领域的概念和规则。

Yacc & Lex

Lex 代表 Lexical Analyzar。Yacc 代表 Yet Another Compiler Compiler。 Lex是由美国Bell实验室M.Lesk等人用C语言开发的一种词法分析器自动生成工具 Yacc 是一个经典的生成语法分析器的工具。

最后，其他的知识点在后面的实践中学习吧。应该编译原理的每一个步骤都会有一篇总结。

参考的学习资料

黔ICP备15004120号 | © 2018 - 2019 XuSenLin Powered By ForestBlog