知识点

编译原理学习-基础(第一章)

1. BNF 与 EBNF

牙医教你 450 行代码自制编程语言 - 1, 从 EBNF 开始

1.1 wiki

  • BNF(Backus–Naur Form)，巴科斯-诺尔范式，一种用于描述计算机编程语言等正式语言的与上下文无关语法的元语法(metasyntax)符号表示法。它不仅能严格地表示语法规则，而且所描述的语法是与上下文无关的。它具有语法简单，表示明确，便于语法分析和编译的特点。简而言之，它是一种描述语言的语言。
  • EBNF(Extended Backus–Naur Form)，扩展巴科斯-诺尔范式，是基本巴科斯范式(BNF)元语法符号表示法的一种扩展。

1.2. 基本语法

左式(LeftHandSide) ::= 右式(RightHandSide).

这个形式也被叫做 production。左式被叫做“非终端符号(non-terminal symbol)”，而右式则描述了其的组成，由非终结符和终结符组成的一个符号串。

1.3. 终端符号与非终端符号

  • 终端符号(Terminal symbols)：形成所描述的语言的最基本符号。所描述语言的标点符号(不是EBNF自己的)会被左右加引号(它们也是终端符号)，而其他终端符号会用粗体打印。
  • 非终端符号(non-terminal symbol)：是用于描述语法的变量，它必须被定义在一个 production 中，或者说，它们必须出现在某个地方的 production 的左式中。
记号 意义
"" 终端符号，代表着这些字符本身
'' 终端符号，代表着这些字符本身
, 连接符
= 定义
; 结束符
` `
<> 必选
[] 可选
{} 包含的为可重复0至无数次的项
(*...*) 注释
?...? 特殊序列

1.4. 实战

自定义一个语言的EBNF 定义，代码如下

1
2
3
4
5
6
7
8
9
SourceCharacter ::=  #x0009 | #x000A | #x000D | [#x0020-#xFFFF] 
Name            ::= [_A-Za-z][_0-9A-Za-z]*
StringCharacter ::= SourceCharacter - '"'
String          ::= '"' '"' Ignored | '"' StringCharacter '"' Ignored
Variable        ::= "$" Name Ignored
Assignment      ::= Variable Ignored "=" Ignored String Ignored
Print           ::= "print" "(" Ignored Variable Ignored ")" Ignored
Statement       ::= Print | Assignment
SourceCode      ::= Statement+

  • SourceCharacter ::= #x0009 | #x000A | #x000D | [#x0020-#xFFFF]
    指 SourceCharacter 这个表达式，可以是 Unicode #x0009 、 #x000A 、 #x000D 或者 #x0020-#xFFFF 这个范围。

  • Name ::= [_A-Za-z][_0-9A-Za-z]*
    指 Name 这个表达式，开头由下划线、大小写字母构成，即名称不能以数字为开头， 一部分原因其实是为了规避词法解析中与数字冲突的问题，因为数字是用数字开头的， 如果不是数字的类型也用数字开头，那么解析器的实现就会变得相当复杂

  • StringCharacter ::= SourceCharacter - '"'
    这里的 - '"' 代表不包含双引号，即 StringCharacter 是 SourceCharacter 但不包含双引号。

  • String ::= '"' '"' Ignored | '"' StringCharacter '"' Ignored
    代表 String 表达式，由空字符串 "" Ignored (双引号里面是空的) 或包含双引号的字符串 "StringCharacter" Ignored 构成。Ignored 代表可忽略的字符，比如空格、tab、换行、注释等。

  • Variable ::= "$" Name Ignored
    指 Variable 由一个美元符号 $ 和 Name 表达式构成

  • Assignment ::= Variable Ignored "=" Ignored String Ignored
    指 Assignment 组成

  • Print、Statement、SourceCode
    指 Print 语句由 print、左圆括号、Variable、右圆括号组成。

    Statement 代表语法中的所有语句，我们只有 Print 和 Assignment 是合法语句。

    最后用 SourceCode 来封装 Statement，+ 代表 SourceCode 里面可以有多个语句。