构建简易网页浏览器

这篇文章是对观看Programming Languages -Building a Web Browser视频课程的总结。课程介绍了编程语言的基础知识。关键概念包括如何指定和处理有效的字符串，句子和程序结构。课程中使用python来演示相关概念的示例代码。

概述

1. 字符串模式

有效的Javascript程序的集合，只是一组非常大的字符串。我们需要使用一些工具来处理它。

2. 词法分析

将很大的字符串（例如网页）分解为令牌列表(tokens)，词法分析器使用有限状态机实现。词法分析所定义的type，定义了一连串的值或者相关的操作，像number，string, + - / *， length和list等。

• Regular Expression

  来指定一些字符集的简明表示法。(Regular Language)，用来做词法分析。

  使用诸如r+, r*, r1|r2, [a-z], r?，来指定token。

• Finite State Machines

  绘制正则表达式，讨论了正则表达式如何转化成FSM，讨论了DSA(deterministic finite automaton)与NFA(nondeterministic finite automaton)的区别。没有具体讨论实现的算法和DFA和NFA状态机的基本定义。

3. 语法分析

• Context Free Grammers

  也是用来指定一些字符串集的简明表示法，预先定义一些加法，减法的定义，函数的定义等，用来做语法分析。

  拥有记忆部分，也可以称之为动态规划。

  例如

  # 声明语句:
  stmt => identifier = exp
  exp => exp + exp
  exp => exp - exp
  exp => number
  
  # 表达式语句：
  stmt => identifier = exp
  stmt => return exp
  
  # 控制流
  stmt => if exp compoundstmt
  stmt => if exp compoundstmt else compoundstmt
  compoundstmt => { stmts }
  
  # 递归
  stmts => stmt stmts
  stmt => some expression
  
  # functions, JS 程序就是语句和函数定义列表
  element => function identifier (optparams) compoundstmt
  compoundstmt => { stmts }

  枚举所有的有效字符串是十分慢的，课程中介绍了记忆图表解析技术的方式，将上下文无关语法和可能记忆组合到一起。其他GLR(广义LR解析)，LALRCD，LLLRLALR等顺带提了一下。

4. 解析

如果词法分析获得的tokens列表在预先定义的上下文无关语法(CFG)中，则生成解析树。

解析树的时候，需要带入scope作用域。我们称之为environment变量。

环境变量主要有两个作用： 1. 将变量映射到值。 2. 指向父环境。

解释解析树的时候，需要带上environment去解释。

继而介绍了图灵机的停机问题，解释了为什么程序部分运行中产生的错误，无法优化，例如while死循环。

5. 解释

解释前需要做的工作

解析前需要做的操作有sematics(语义)和optimization(优化)。

语义: 程序可能有类型错误，例如你用字符串除以整数。或者有一些其他的情况，一般情况下会返回一个值，意味着我们已经计算了一下东西。

优化：将具有相同语义化但是需要更少资源的程序替换另一端程序。举例x + 1 => x，使用x替换x + 1计算后的值，优化的关键是不能更改程序的含义，x/x不能替换城1。这一部分，V8引擎会去做。

解释过程

在优化的分析树上进行递归遍历，程序的含义通过子表达式的含义计算而得。

图形展示：

web浏览器

对HTML使用词法解析和语法解析，将JavaScript视为特殊的令牌，HTML解释器接收JS解释器返回的字符串，HTML解释器调用图形库来展示返回的字符串。

学习总结

课程也不是很长，不过在学习的过程中，学习到了很多之前学前端应用知识没有的知识点。涉及了自动机，上下文无关等编译方面的知识。对计算的浏览器的整体运行也有了一个概括，很多知识知识代入性的，它告诉我了有这么个知识点。后期的学习中，可以慢慢挖掘这些知识点，去深入拓展自己的知识深度。