语言按语法分类

• 非形式语言
  • 中文、英文
• 形式语言（乔姆斯基谱系）追溯19世纪50年代
  • 0型 无限制文法
  • 1型 上下文相关文法
  • 2型 上下文无关文法
    • 大部分计算机语言主体上都是上下文无关文法
    • 比如Javascript就是上下文无关文法，会在某些点，违反上下文无关文法原则（get）
  • 3型 正则文法

理解形式语言

产生式（BNF – Backus-Naur Form）

• 用尖括号括起来的名称来表示语法结构名
• 语法结构分成基础结构和需要用其他语法结构定义的复合结构
  • 基础结构称终结符
  • 复合结构称非终结符
• 引号和中间的字符表示终结符
• 可以有括号
• • 表示重复多次
• | 表示或
• • 表示至少一次

BNF 表示 四则运算

• 加法，允许连加

  • <Number>::= “0” | “1” | “2” | “3” | … | “9”
  • <DecimalNumber>::= “0” | ((“1” | “2” | “3” | … “9”) <Number>*)
  • <AddtiveExpression>::= <DecimalNumber> “+” <DecimalNumber>
  • 支持多个连加，采用递归：
    • <AddtiveExpression>::= <AddtiveExpression> “+” <DecimalNumber>
  • 最终：
    • <AddtiveExpression>::= <DecimalNumber> | <AddtiveExpression> “+” <DecimalNumber>

• 乘法

  • <MultiplecativeExpression>::= <DecimalNumber> | < MultiplecativeExpression> “*” <DecimalNumber>

  • 1 + 2 * 3

    • 加法表达式，是由两个乘法表达式加起来的

    • 1 * 1 + 2 * 3

    • 因此加法表示成

      <AddtiveExpression>::= < MultiplecativeExpression> | < AddtiveExpression> “+” <DecimalNumber>

• LogicExpression

  <LogicExpression>::= <AddtiveExpression> |

  <LogicExpression> "||" <AddtiveExpression> |
  <LogicExpression> "&&" <AddtiveExpression>

• 除法

  <MultiplecativeExpression>::= <DecimalNumber> | < MultiplecativeExpression> “/“ <DecimalNumber>

• 减法

  <AddtiveExpression>::= <MultiplecativeExpression> | < AddtiveExpression> “-“ <MultiplecativeExpression>

• 带括号的四则运算

  • 括号

    <PrimaryExpression<::= <DecimalNumber< | “(“ | <LogicExpression< | “)”

  • 乘法表达式便可以变成

    <MultiplecativeExpression>::= <PrimaryExpression> | < MultiplecativeExpression> “*” < PrimaryExpression>

  • 除法，同理乘法，换符号

    <MultiplecativeExpression>::= <PrimaryExpression> | < MultiplecativeExpression> “/“ < PrimaryExpression>

  • 加减

    <AddtiveExpression>::= <MultiplecativeExpression> | < AddtiveExpression> “+” <MultiplecativeExpression> | < AddtiveExpression> “-“ <MultiplecativeExpression>

通过 BNF 理解形式语言（乔姆斯基谱系）

• 0型 无限制文法
  • ?::=?
• 1型 上下文相关文法
  • ?<A>?::=?<B>?

    
1
2
3
4
{
  get a { return 1},
  get: 1
}

- 1）类似关键字， 2）get: 属性

• 2型 上下文无关文法

  • <A>::=?
  • 2 ** 1 ** 2

• 3型 正则文法，只允许左递归（Javascript在**出现前，一直遵循着左递归）

  • <A>::=<A>?

  • <A>::=?<A>x

  • Javascript 表达式大部分在3型

  • ** 右结合

    1 2	2 ** 2 --> 4 2 ** (2 ** 3) --> 256

    • **

      <ExpExpression> = <MulticativeExpression> | <MulticativeExpression> “**” <ExpExpression>

optional 正则表达式+ BNF 表示四则运算

其他产生式

• EBNF ABNF Customized
  • 

现代语言语言的特例

• C++，* 可能表示乘号或者指针，具体是哪个，取决于星号前面的标识符是否被声明为类型
  • 非形式话语言，语法与语义相关，* 可以在很早之前出现
• VB中， < 可能是小于号，也可能是 XML 直接量的开始，取决于当前位置是否可以接受 XML 直接量
  • 1型 上下文无关文法
• Python，行首的 tab 符和空格会根据上一行的行首空白以一定规则被处理成虚拟终结符 indent 或者 dedent
• Javascript，/ 可能是除号，也可能是正则表达式开头，处理方式类似于VB，字符串模板中也需要特殊处理},还有自动插入分号规则
  • 同 VB / JSX

语言的分类

图灵完备性

• 图灵机（凡是可计算的，都能计算出来）
• 图灵完备性
  • 命令式 – 图灵机
    • goto
    • if 和 while
  • 声明式 – lambda
    • 递归

动态与静态

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

类型系统 In 静态语言

• 动态类型系统和静态类型系统
  • 不是说 Typescript 才有类型系统，而是它才有静态类型系统
• 强类型和弱类型
  • String + Number
    • 产生了隐式的类型转换
  • String == Boolean
  • C++ 有隐式转换，弱类型
• 复合类型
  • 结构体
  • 函数签名
    • 参数列表 + 返回值类型
• 子类型
  • 逆变/协变
    • 协变 –> 凡是能用到Array<Parent>的地方，都能用Array<Child>
    • 逆变 –> 凡是能用到Array<Child>的地方，都能用Array<Parent>

一般命令式编程语言

Atom

Expression

Statement 语句

Structure

Program