语言和计算机编程语言

https://blog.csdn.net/xfxyy_sxfancy/article/details/44854197 编程语言的诞生，源于对计算机控制的难题。人和人交谈用自然语言即可，但计算机只认识指令，例如，我们个人电脑上用的intel的CPU，常用的指令集就有x86,x86-64,MMX,SSE,SSE2,SSE3等。

指令就是按照规则编排的数字信号，由CPU硬件电路直接识别，那么我们如何希望直接控制，就要用机器码对其进行操作，但我们希望简单的方式来描述，计算机发明的最初，人们便使用助记符也就是常说的汇编指令来帮助人们编写这些指令。

如下，是dos下的汇编helloworld：

;;;;;;;;;;;;;;;;;;;;;hello.asm;;;;;;;;;;;;;;;;;;;;;;;;;;;;

assume cs:code,ds:data

data segment
  db "hello world" 
data ends

code segment
  start:
  mov ax,data
  mov ds,ax
  mov bx,0b800h
  mov es,bx
  mov cx,11 
  mov si,0
  mov bx,0
  mov ah,01000010b
  s:mov al,ds:[si]
      mov es:[bx],ax
      mov es:[bx+1],ah
      inc si
      add bx,2
      loop s

      mov ax,4c00h
      int 21h

code ends
end start

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

这种方法，可以将程序代码保存在电脑中，修改和编辑都很简便。但要人理解还很困难，编译器就在帮助我们，将高级语言转换成为这种低级的机器码或汇编指令，说白了，编译器就是一个字符串处理程序，将一种格式编写的字符串数据转换成另一种。输入是源代码的文本文件，输出是低级语言或机器码。

那么，我们为了让计算机识别我们定义的一种编程语言，都要做哪些工作呢？

语言的描述——BNF范式

首先我们需要定义我语言的规范，为什么不用自然语言？因为太难了，现在自然语言处理，仍然是世界性的难题，目前还没有哪种程序能够将自然语言处理的很好，所以我们不得已，只能放弃。

乔姆斯基(Chomsky)于1956年建立形式语言的描述以来，形式语言的理论发展很快。他将文法分成四种类型，即0型、1型、2型和3型，0型即自然语言文法，1型称为上下文相关文法，2型称为上下文无关文法，3型称为正则文法。

2型文法和3型文法在计算机中应用较为广泛，主要是因为其限制较多，处理较为容易。

为了描述一个文法，我们常常使用巴斯克范式（BNF范式）来描述一个文法的结构：

<句子> ::= <主语> <谓语> <宾语>
<谓语> ::= <动词> | <动词短语>
<主语> ::= 你 | 我 | 他

这里的BNF范式实际上应该叫做扩展巴斯克范式（EBNF），而且并没有定义完整，只是一个演示，每一行范式的左边的部分，称为非终结符，而主语那一行，右边的每个词，都称为终结符，如果定义完整时，应该每一个非终结符都有定义，都要能从终结符和非终结符推倒而来。这个BNF范式表示了每一个语法成分是应该由怎样的结构组成的。

注：

一般是使用上下文无关文法来写的，主要的用途是将词法分析生成的token转化为语法树

抽象语法树（AST）

有了BNF范式定义我们的文法规则，那么我们在识别一个文法的时候，就能对其构建一棵抽象语法树（AST），这个语法树就是帮助我们进行代码编译工作的核心数据结构。

例如，12*(24-5)/(17+6)的抽象语法树:

文法的识别

如果我们定义了一个文法，那么我们用什么样的方法识别它呢？这里我们介绍两种最常见的方法，自顶向下分析法和自底向上分析法。

这是两种解决问题的思路，一种是从整体上看，不断的推倒当前语法树下面应该构建的部分是什么，一种是从局部入手，不断归约可能的语法树，然后将它们组合起来。

详细

https://www.jianshu.com/p/15efcb0c06c8 https://blog.csdn.net/yudianxia/article/details/79668289

由于经常研究东西，所以经常涉及语法的定义；以前我都是按照我自己定义的一套语法格式描述规则来进行严谨地描述语法格式，但是我自己设计的这套语法格式描述规则并不通用，所以决定改为通用的语法格式描述规则--ABNF(扩展的巴科斯范式BNF);

内容

一. 巴科斯范式BNF

巴科斯范式的英文缩写为BNF，它是以美国人巴科斯(Backus)和丹麦人诺尔(Naur)的名字命名的一种形式化的语法表示方法，用来描述语法的一种形式体系，是一种典型的元语言。又称巴科斯-诺尔形式(Backus-Naur form)。它不仅能严格地表示语法规则，而且所描述的语法是与上下文无关的。它具有语法简单，表示明确，便于语法分析和编译的特点。 BNF表示语法规则的方式为：

非终结符用尖括号括起。
每条规则的左部是一个非终结符，右部是由非终结符和终结符组成的一个符号串，中间一般以::=分开。
具有相同左部的规则可以共用一个左部，各右部之间以直竖“|”隔开。

BNF中常用的元字符及其表示的意义如下：

在双引号中的字 "word" 代表着这些字符本身。而double_quote用来代表双引号；
在双引号外的字（有可能有下划线）代表着语法部分；
尖括号 < > 内包含的为必选项；
方括号 [ ] 内包含的为可选项；
大括号 { } 内包含的为可重复0至无数次的项；
圆括号 ( ) 内包含的所有项为一组，用来控制表达式的优先级；
竖线 | 表示在其左右两边任选一项，相当于"OR"的意思；
::= 是“被定义为”的意思；
...  表示术语符号；
斜体字: 参数，在其它地方有解释；

二. 扩展的巴科斯范式ABNF

RFC2234 定义了扩展的巴科斯范式(ABNF)。近年来在Internet的定义中 ABNF 被广泛使用。ABNF 做了更多的改进。扩充巴科斯-瑙尔范式(ABNF)基于了巴科斯-瑙尔范式(BNF)，但由它自己的语法和推导规则构成。这种元语言的发起原则是描述作为通信协议(双向规范)的语言的形式系统。它建档于 RFC 4234 中通常充当 IETF 通信协议的定义语言。 推导规则 ABNF 规定是一组推导规则，写为：

规则 = 定义 ; 注释 CR LF

说明：

这里的规则是大小写敏感的非终止符，定义是由定义这个规则的符号序列、一个文档注释组成，并结束于回车换行。
规则名字是大小写不敏感的: , , 和都提及同一个规则。规则名字由开始于一个字母的字母、数字和连字符组成。不要求用尖括号(“<”, “>”) (如 BNF 那样)包围规则名字。但是它们可以用来界定规则名字，比如在冗文中识别出规则名字的时候。ABNF 使用 7-位 ASCII 编码，在 8-位域中把高位置零。
终结符由一个或多个数值字符指定。数值字符可以指定为跟随着基数(b = 二进制, d = 十进制, x = 十六进制)的一个百分号“%”，随后是这个数值，或数值的串联(用“.” 来指示)。例如回车可以指定为十进制的 %d13 或十六进制的 %x0D。回车换行可以指定为 %d13.10。
文字正文通过使用包围在引号(")中字符串来指定。这些字符串是大小写不敏感的，使用的字符集是 US-ASCII。所以字符串“abc”将匹配“abc”, “Abc”, “aBc”, “abC”, “ABc”, “AbC”, “aBC” 和 “ABC”。对于大小写敏感匹配，必须定义明确的字符: 要匹配 “aBc” 定义将是 %d97 %d66 %d99。

操作符 空白被用来分隔定义的各个元素: 要使空格被识别为分割符则必须明确的包含它。串联

规则1 规则2

规则可以通过列出一序列的规则名字来定义。 示例： 要匹配字符串“aba”可以使用下列规则:

fu = %x61; a
bar = %x62; b
mumble = fu bar fu

选择

规则1 / 规则2

规则可以通过用反斜杠(“/”)分隔的多选一规则来定义。 示例： 要接受规则或规则可构造如下规则： fubar = fu / bar

递增选择规则1 =/ 规则2

可以通过使用在规则名字和定义之间的“=/”来向一个规则增加补充选择。示例：规则 ruleset = alt1 / alt2 / alt3 / alt4 / alt5

等价于 ruleset = alt1 / alt2 ruleset =/ alt3 ruleset =/ alt4 / alt5

值范围 %c##-##

数值范围可以通过使用连字符(“-”)来指定。示例：规则 OCTAL = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7"

等价于 OCTAL = %x30-37

序列分组 (规则1 规则2)

元素可以放置在圆括号中来组合定义中的规则。示例：要匹配“elem fubar snafu”或“elem tarfu snafu”可以构造下列规则： group = elem (fubar / tarfu) snafu

要匹配“elem fubar”或“tarfu snafu”可以构造下列规则： group = elem fubar / tarfu snafu group = (elem fubar) / (tarfu snafu)

可变重复 n*n规则

要指示一个元素的重复可以使用形式 元素。可选的 给出要包括的元素的最小数目，缺省为 0。可选的 给出要包括的元素的最大数目，缺省为无穷。对零或多个元素使用 元素，对一或多个元素使用 1元素，对二或三个元素使用 23元素。特定重复 n规则

要指示明确数目的元素可使用形式元素，它等价于 *元素。使用 2DIGIT 得到两个数字，使用 3DIGIT 得到三个数字。(DIGIT 在下面的核心规则中定义)。可选序列 [规则]

示例：要指示可选元素下列构造是等价的： [fubar snafu] 1(fubar snafu) 01(fubar snafu)

注释 ; 注释

分号(“;”)开始一个注释并持续到此行的结束。操作符优先级上述操作符有从最紧绑定(binding)到最松绑定的给定优先级:

字符串，名字形成(formation) 注释值范围重复分组，可选串联选择

与串联一起使用选择操作符可以造成混淆，建议使用分组来做明确串联分组。核心规则核心规则定义于 ABNF 标准中；

核心规则.png

三. 郭斌勇版巴科斯范式ABNF-GBY

对于会正则表达工式的人来说，可能不喜欢喜欢ABNF的重复规则，而更喜欢正则表达工的重复规则（正如我的喜好一样），为了实现类正则的巴科斯范式，我便定义了郭斌勇版巴科斯范式ABNF-GBY；

郭斌勇版巴科斯范式ABNF-GBY是基本ABNF修改和扩展的，相对于ABNF，有如下区别：

修改弃用 ABNF中的重复规则和 BNF中的可重复项表示{ }，改用如下正则表达式的重复规则，如下：规则{min,max}

表示规则重复次数大于或等于min次，小于或等于max次； min表示最小的重复次数，默认值为0； max表示最大的重复次数，默认值为无穷大；当min或者max被省略时，min或者max取相应默认值；规则{n}

等价于：规则{n,n}

表示规则重复n次；

增加相对ABNF，增加以下元字符： ? : 表示前面的规则重复零次或一次；等价于{0,1}；

: 表示前面的规则重复一次或多次(大于等于1次）；等价于{1,};

: 表示前面的规则重复任意次；等价于{0,}；

cisen / blog

语言的描述——BNF范式 #232