JSON 和 Context-free Grammar 的關係

Copy from JSON.org

object
  {}
  { members }
members
  pair
  pair , members
pair
  string : value
array
  []
  [ elements ]
elements
  value
  value , elements
value
  string
  number
  object
  array
  true
  false
  null

JSON 可以由 Context-free Grammar 所做成。當中的 rule 都是 non-ambiguous，內裡的 leftmost derivation…

前言

在很久很久以前，數學家門研究怎樣產生電腦，和研究怎樣令電腦運作, 這門的學問叫 Theory of computation (真的是 theory, 因為都是抽象的電腦), 當中有兩個分支:

• Automata theory 研究機械怎樣計算
• Formal language 研究 language, language 是給 automata 計算的東西
…