MLIR：EBNF，扩展巴科斯范式

文章来自微信公众号“科文路”，欢迎关注、互动。转发须注明出处。

Multi-Level Intermediate Representation（MLIR）是创建可重用、可扩展编译器基础设施的新途径。本文为第 3 期，介绍编译器基础概念 EBNF。

参考 Wiki：Extended Backus–Naur form

出发点

在计算机科学中，扩展巴科斯范式（Extended Backus–Naur Form，EBNF）是 BNF 的扩展，它是一簇元语法（metasyntax）符号，可以用来表达上下文无关的语法。

基于 EBNF 可以更精确的设计或描述编程语言规则，减少歧义。在 MLIR 的文档中，EBNF 被用来描述 MLIR 语法规则。

终结符是组成串的基本符号，例如字母、数字字符，标点符号和空格符。

基础

EBNF 由终结符（terminal symbols） 与 非终结符的产生规则（non-terminal production rules）组成，这些规则控制如何将终结符组合成合法序列。

也就是说 EBNF 定义了非终结符匹配一个符号序列的规则。基础结构为，

<non-terminal> ::= <replacement>

常见用法（语法）如下，其中特殊符号的含义参照下面的符号表。

alternation ::= expr0 | expr1 | expr2  // Either expr0 or expr1 or expr2.
sequence    ::= expr0 expr1 expr2      // Sequence of expr0 expr1 expr2.
repetition0 ::= expr*  // 0 or more occurrences.
repetition1 ::= expr+  // 1 or more occurrences.
optionality ::= expr?  // 0 or 1 occurrence.
grouping    ::= (expr) // Everything inside parens is grouped together.
literal     ::= `abcd` // Matches the literal `abcd`.

digit     ::= [0-9]
hex_digit ::= [0-9a-fA-F]
letter    ::= [a-zA-Z]
id-punct  ::= [$._-]

integer-literal ::= decimal-literal | hexadecimal-literal
decimal-literal ::= digit+
hexadecimal-literal ::= `0x` hex_digit+
float-literal ::= [-+]?[0-9]+[.][0-9]*([eE][-+]?[0-9]+)?
string-literal  ::= `"` [^"\n\f\v\r]* `"`   TODO: define escaping rules

符号表

ISO/IEC 14977 standard, by R. S. Scowen, page 7, table 1.

单引、双引号优先级不同。

Usage	Notation
定义	=
序列连接	,
终止	;
或	|
0次或1次	[ … ]
0次或多次	{ … }
分组	( … )
单引终止符串	“ … “
双引终止符串	‘ … ‘
注释	(* … *)
特殊序列	? … ?
例外	-

例子

下面这个例子可以匹配的序列包括 ba，bana，boma，banana，banoma，bomana，…

example ::= `b` (`an` | `om`)* `a`

当然了，既然使用 EBNF 能定义编程语言的语法规则，那用法自然不胜枚举。介于篇幅，就介绍到这里了。

都看到这儿了，不如关注每日推送的“科文路”、互动起来~

至少点个赞再走吧~