LLVM - 编译器前端 - 理解BNF（巴科斯-诺尔范式）

一：概述

        BNF（Backus-Naur Form，巴科斯-诺尔范式）是一种用于描述上下文无关文法的形式语言，广泛应用于定义编程语言、协议和文件格式的语法规则。

        下面是一小段类Pascal编程语言，这个编程语言就可以用BNF描述。用BNF描述编程语言的语法规则之后，就可以根据这个规则生成抽象语法树，这是编译器前端的一个重要数据结构。是编译器的基础。

MODULE Gcd;
PROCEDURE GCD(a, b: INTEGER) : INTEGER;
VAR t: INTEGER;
BEGINIF b = 0 THENRETURN a;END;WHILE b # 0 DOt := a MOD b;a := b;b := t;END;RETURN a;
END GCD;
END Gcd.

二：BNF 的基本语法结构

        上面那段编程代码，就可以用BNF描述，其规则如下：

compilationUnit: "MODULE" identifier ";" ( import )* block identifier "." ;
Import : ( "FROM" identifier )? "I