形式语言

什么是符号？

符号本身是抽象的，只有大家一起约定了它的功能和意义，它才变得有意义。

比如我们约定$表示美元，￥表示人民币，如果张三非要坚持用@表示人民币，显然大家都不会鸟他。

符号的形式是多样的，例如常见的字母、数字、标点符号、运算符号等，语言中的词汇、图像甚至手势，只要能表达信息，都可以看做是符号。

符号表达的信息，来自于大家共同认可的约定。

什么是符号系统？

单个符号传递的信息是有限的，我们可以将符号进行组合传递更加丰富的信息。

组成符号的方式就是规则，符号和规则组成了符号系统。

这种组合规则可以是自然形成的，例如自然语言中的语法和语义规则；

也可以是人为约定的，例如编程语言中的语法。

什么是语言？

语言是人类用来传递信息的工具，一般包含词汇、语法和语义。

词汇可以看成符号，语法和语义可以看成规则，所以语言实际上就是一个符号系统。

语言系统中的符号不仅仅包含词汇，像音节、音调等都是一种符号。

语法规定了词汇等符号怎么组成句子（但是句子不一定有实际含义）。

语义确定了符号和各种表达的含义，使得人们可以理解复杂的表达。

自然语言 & 形式语言

自然语言（Natural Language）就是自然形成的语言，例如汉语、英语等。

形式语言（Formal Language）是科学家人为创造的符号系统，用来表示逻辑、算法或者数学概念。

自然语言与人们生活息息相关，它的词汇、语法随时都在变化，活力满满，用于日常交流。

而形式语言一般追求严谨统一，语法什么的都很死板，主要用于科学研究。

自然语言一般是有限的（符号、语法等），而形式语言一般是通过有限的手段描述无限的语言。

例如，所有由 n 个 a 构成的词汇组成的语言 La={a,aa,aaa,...} 就是一个无限符号的形式语言。

常见的形式语言

编程语言：描述算法、逻辑和计算过程
数学符号系统：表示数学概念和运算，例如加减乘除、方程符号、集合符号等
逻辑符号系统：描述逻辑推理和论证的符号系统
数据库查询语言：描述数据库的数据和操作，实现数据的检索和管理，例如 SQL
正则表达式：描述字符串的模式、匹配规则和替换等操作
绘图语言：用于图形绘制和排版，例如 SVG
……

形式语法

简单点理解就是，语法描述了词汇怎么组成句子。

形式语法用于描述形式语言的语法结构和规则，即描述语言符号系统的规则部分。

自然语言中的语法一般叫做文法。在自然语言中，最简单的语法估计就是主谓宾了。

通过语法造出来的句子不一定有意义，因为语法只描述结构，能否真正传达信息还需要语义验证。

形式语法包含五个要素：终结符（Terminal Symbol）、非终结符（Nonterminal Symbol）、语法规则、语法推导、语法树。

终结符 vs 非终结符

终结符就是最基本的符号，不能再继续拆分的符号，例如算术表达式语言中的数字（0~9）和运算符（+-*/）。

语言系统中的符号不仅仅包含最基本的符号，例如算术表达式语言中的123也是一个符号，但是它可以拆分成1和23两部分，23还可以继续拆分成2和3。

注意在上述拆分过程中，123实际上是作为字符串处理的，这也是形式语法定义中的一个重要特点：万物皆字符串。

类似到自然语言中，26个字母组成的单词，单词组成的短语，句子都是符号的一部分，只是它们属于非终结符。

所以我们可以看到，非终结符是很宽泛的，但究其根本，它们都是由终结符经过一定的规则推导而来的。

另一个角度，非终结符的范围实际上包含了终结符。

产生式表示法

产生式（Production Rule）是描述语法规则的一种形式，指导语言的生成和解析过程。

产生式通常由一个左部和一个右部组成，形如：左部 -> 右部。

左部表示要替换的符号，通常是一个非终结符；

右部表示替换后的符号序列，可以是终结符和非终结符的组合。

例如我们定义一个形式语言的字母表是{a,b}，开始符号是S，产生式规则有两个：

S -> aSb
S -> ba

从S开始，假设我们选择规则1，我们将获取字符串aSb。

如果我们再次选择规则1，aSb中的S会被再次替换，于是我们得到a(aSb)b，即aaSbb。

然后我们选择规则2可以得到aa(ba)bb，即aababb。

于是我们得到这样一个构造路径：S => aSb => aaSbb => aababb。

在上面的例子中，右部往往会出现终结符，目的是在原来字符串的基础上引入新的子串，这样字符串才能一直扩充，形成句子。

我们使用 n 次规则1，然后再使用1次规则2，就可以得到一个仅有ab组成的字符串，所有的n的计算结果形成的集合就是我们定义的形式语言的符号集合。

n=0: ba
n=1: abab
n=2: aababb
...

通过有限的手段表达，类似于通项公式：
$$
{a^nbabn|n\ge0}={ba,abab,aababb,...}
$$

语法规则

语法规则描述了如何使用终结符和非终结符来构造语言中的合法字符串。

语法规则一般使用产生式的形式表示。

常见的语法规则：

上下文无关文法规则（Context-Freee Grammar Rules）：A -> a 表示将非终结符 A 替换为符号序列 a（终结符和非终结符的组合）
正则表达式规则（Regular Expression Rules）：A -> aB 表示将非终结符 A 替换为终结符 a 后紧跟着非终结符 B
正则文法规则（Regular Grammar Rules）：A -> a 表示将非终结符替换为终结符；A -> ε 表示将非终结符替换为空串
上下文敏感文法规则（Context-Sensitive Grammar Rules）：αAβ -> αγβ 表示在符号序列 αAβ 中，如果满足某些上下文条件，可以将非终结符 A 替换为符号序列 γ
……

语法推导

参考上文的产生式表示法，形式语法的语法推导就是根据语法规则，通过逐步替换符号来生成语言中的合法字符串的过程。

推导过程从一个起始符号开始，按照规则不断进行符号替换，直到生成一个符合语法规则的合法字符串。

形式语法的语法推导的一般步骤是：

确定起始符号：推导的起点
选择一个语法规则进行替换：将左部的非终结符替换为右侧的符号序列
重复应用规则：如果替换后的符号序列中仍然存在非终结符，则继续应用规则，选择一个非终结符进行替换，直到所有的非终结符都被替换成终结符
结束推导：所有的非终结符都被替换成终结符，且生成的符号序列符合语法规则时，推导结束

语法树

自然语言通过主语、动词、宾语、标点符号等概念来描述客观世界的事件。

计算机编程语言通过类型、运算符、流程语句、函数、对象等概念来描述基于二进制的运算过程。

基本上所有的编程语言都是从源代码出发，将其抽象成描述计算过程的树状结构，树上的每一个节点都表示一种结构。

编程语言依靠语法分析器将源代码字符串转换成抽象语法树（AST, Abstract Syntax Tree）。

表达式和语法树

我们习惯于使用中缀表达式来描述这个表达式：

(1 + 2 ) * 3

将双目运算符放在运算对象中间是符合自然直觉的。

除此之外，还可以写成前缀表达式和后缀表达式的形式：

前缀表达式：* ( + 1 2 ) 3
后缀表达式：( 1 2 + ) 3 *

不论哪种表达式，它们描述的计算过程是一致的，即它们对应的语法树是一致的。

三种表达式的写法很容易可以和二叉树的前序遍历、中序遍历和后序遍历联系起来。

类似的，1 + 2 * 3 对应的树为

Python ast 库

ast 是 Python 中的标准库，用于将源代码转换成抽象语法树。

import ast
ast.dump(ast.parse("(1+2)*3"))

'Module(
  body=[
    Expr(
      value=BinOp(
        left=BinOp(
          left=Constant(value=1), 
          op=Add(), 
          right=Constant(value=2)
        ), 
        op=Mult(), 
        right=Constant(value=3)
      )
    )
  ], 
  type_ignores=[]
)'

我们可以利用语法树做些什么？

源代码本身只是一个字符串，例如我们需要写一个插件高亮源代码中的所有 if 条件，首先肯定需要找到源代码中的所有条件表达式。

最简单的方式肯定是直接字符串匹配，但这样显然不是一个优雅的解决方案，例如代码被注释了怎么排除？

最好的方式还是将源代码转换成抽象语法树，通过语法树找到所有的节点，修改后还原为字符串即可。

形式语言和抽象语法树