终结符 & 生产式 & 文法

在整个软件生态中，编译原理无处不在，作为一个Web前端工程师，比较接近的有JSX Compiler，Vue SFC Compiler，又或者是Babel将现代Javascript转成兼容性语法的转译器，而日常用的浏览器中，又涉及到负责解析 HTML/CSS 的HTML Compiler，CSS Compiler，负责将GLSL转成GPU指令用于渲染计算的Shader Compiler。可以看出，编译原理对于软件知识的深入探索具有积极意义，本文章简单介绍编译原理中的终结符、生产式和文法。


终结符

终结符我们可以理解是语法最小的不可分割语法单元

if (var1 > 0) {
  let var1 = 1; 
}

在当前例子中，“if” | “var1” | ”(” | ”)” | ”>” | “0” | ”{” | ”}” | “let” | ”=” | “1” | ”;” 是该程序的终结符


生产式 & 非终结符

一个产生式通常是这么表达：

A→a

上一节的程序可以用下面生产式表示，其中IfStatement、BinaryExpression和BlockStatement都是非终符，因为它们都可以继续推导

IfStatement -> BinaryExpression # var1 > 0
               | BlockStatement # let var1 = 1;

继续推导后，LeftLiteral、Operator和Operator是不可分解的语法单位，都是终结符

BinaryExpression -> LeftLiteral # 对应 var1
                    | RightLiteral # 对应 0
                    | Operator # 对应 >

常见文法

文法的作用是用于描述语言的规律。

巴科斯范式

使用产生式来定义语言的语法规则，其中每个产生式由非终结符和终结符组成。非终结符表示可由其他符号推导出的符号，而终结符表示语言中的基本符号，可以说该范式最是最简单的文法规范。

扩展巴科斯范式

是对巴科斯范式的扩展，提供更多的便利性和表达能力。该范式引入了特殊符号和规则，如重复、可选项和分组等，使文法的表示更加简洁和易读

上下文无关文法

形式化的文法，其中产生式的左侧只包含一个非终结符。很多通用编程语言都是该文法 赋值表达式生成式的推导过程：

const a = 1 + 2 + 3
declaration -> const id = expr
expr -> expr + term
      -> expr + term + term
      -> term + factor + factor
      -> factor + 2 + 3
      -> 1 + 2 + 3

上下文无关文法，只依靠关注本身的信息，去进行推导 例如

expr -> BinaryExpressionAdd # 加法
        | BinaryExpressionMinus # 减法
        | BinaryExpressionMulti # 乘法
        | BinaryExpressionDivi # 除法

根据expr表达式里面本身的符号，是+，-，*，/就可以进行右侧的表达式推导。

上下文相关文法

形式化的文法，其中产生式的左侧可以包含多个符号，而右侧则是对应的推导规则。在通用编程语言的编译中使用比较少，在IR中间语言，人工智能，自然语言等处理上用得比较多。

例如在自然语言处理中：

"小明说他很喜欢这本书"

对于代词”他”的解析，需要依赖上下文：

小明 他 -> 小明 小明   # 当"他"前面提到了"小明"，"他"就指代"小明"

其生产式

Name Pronoun -> Name Name

再比如在某些编程语言的类型推导中，虽然不算严格的上下文相关语法，但可以用于简单意会

// C语言
int array[5];
array[n] = 10;  // n 必须是整数类型

这里变量 n 的类型检查就需要依赖数组下标的上下文：

array[expr] -> array[int]    # 数组下标表达式必须是整数类型

这就是典型的上下文相关文法，生成规则需要考虑周围的上下文信息才能确定是否可以应用。

无限制文法

对产生式的形式没有任何限制，复杂自然语言。


总结

本文章更多是从工程角度简单阐述了终结符、生产式 和 文法三者作用和关系，更少地去使用数学表达式，想了解更深入的内容在《编译原理》。