编程语言通识

形式语言（乔姆斯基谱系）

• 0型 无限制文发
• 1型 上下文相关文法
• 2型 上下文无关文法
• 3型 正则文法

BNF（巴科斯范式）

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

语法规则

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

常用元字符

• ::= ：是“被定义为”的意思；示例：字符串 ::= 用引号包围的字符序列，表示 字符串 就是 用引号包围的字符序列
• "..." ：终结符，即引号中的字符序列本身，并非指代其它字。而终结符双引号 " 用 double_quote 用来表示；示例：函数调用 ::= 名字 "()" 表示 函数的调用 是由 名字 加上左右括号字符 () 组成；
• double_quote ：代表终结符双引号 "； 示例：字符串 ::= double_quote ... double_quote，表示 字符串 是由被字符 " 包围的字符序列组成；
• 在双引号外的字代表着语法部分；示例：基本类型 ::= 字符串 | 数字 | 布尔，表示 字符串 或 数字 或 布尔 都是 基本类型，但 字符串、数字、布尔 具体是什么，由其它规则定义；
• <...>：必选项；示例：名字 ::= [姓] <名> 表示 名字 中的 名 是必须要有的，但 姓 是可有可无的，即：姓 名 是 名字，名 也是 名字；
• [...]：可选，可有可无；示例：名字 ::= [姓] <名> 表示 名字 中的 名 是必须要有的，但 姓 是可有可无的，即：姓 名 是 名字，名 也是 名字；
• {...}：重复，0 或 任意次重复；示例：AB ::= "a" {"b"}，表示 AB 是由 一个 a 后面跟上任意数量（包括0个）个 b 组成，如 a、a b、a bb、a bbb
• (...)：分组，用来控制表达式的优先级；示例：AX ::= "a" ("m"|"n")，表示 AX 是由 一个 a 后面跟上 m 或 n 组成；
• |：替换，即 或 的意思；示例：布尔 ::= "true" | "false"，表示 true 或 false 都是 布尔；
• ...：表示各种列举或省略的代码片断；示例：a...z 表示从 a 到 z 的字符，"..." 表示由双引号 " 包围起来的任意字符；
• 斜体字: 参数，在其它地方有解释

参考：语法格式描述规范BNF、EBNF、ABNF

带括号的四则运算产生式

<!-- 数字 -->
<Number> ::= "0" | "1" | "2" | ... | "9"
<!-- 十进制数 -->
<DecimalNumber> ::= "0" | (("1" | "2" | ... | "9") <Number>*)
<!-- 表达式 -->
<PrimaryExpression> ::= <DecimalNumber> | "(" <LogicalExpression> ")"
<!-- 乘法/除法表达式 -->
<MultiplicativeExpression> ::= <PrimaryExpression> | 
  <MultiplicativeExpression> "*" <PrimaryExpression> | 
  <MultiplicativeExpression> "/" <PrimaryExpression>
<!-- 加法/减法表达式 -->
<AdditiveExpression> ::= <MultiplicativeExpression> | 
  <AdditiveExpression> "+" <MultiplicativeExpression> |
  <AdditiveExpression> "-" <MultiplicativeExpression> |
<!-- 逻辑表达式 -->
<LogicalExpression> ::= <AdditiveExpression> | 
  <LogicalExpression> "||" <AdditiveExpression> |
  <LogicalExpression> "&&" <AdditiveExpression>

通过产生式理解乔姆斯基谱系

• 0型 无限制文发： ?::=?
• 1型 上下文相关文法： ?<A>?::=?<B>?
• 2型 上下文无关文法： <A>::=?
• 3型 正则文法: <A>::=<A>?、<A>::=?<A>x

图灵完备性

• 命令式 —— 图灵机
  • goto
  • if 和 while
• 声明式 —— lambda
  • 递归

动态与静态

• 动态语言
  • 在用户的设备/在线服务器上
  • 产品实际运行时
  • Runtime（运行时）
• 静态语言
  • 在程序员的设备上
  • 产品开发时
  • Compiletime（编译时）

类型系统

• 动态类型系统与静态类型系统
• 强类型与弱类型
• 复合类型：结构体、函数签名
• 子类型：协变/逆变
  • 协变：凡是能用 Array<Parent> 的地方，都能用 Array<Child>
  • 逆变：凡是能用 Array<Child> 的地方，都能用 Array<Parent>

一般命令式编程语言

Atom

• Identifier
• Literal

Expression

• Atom
• Operator
• Punctuator

Statement

• Expression
• Keyword
• Punctuator

Structure

• Function
• Class
• Process
• Namespace
• ...

Program

• Program
• Module
• Package
• Library