プログラミング言語 — 知識ノート

人間が書いたテキストが、どうやって意味を持つのか。

3 つの層#

層	問い	担当
字句	どこが単語の切れ目か	字句解析
構文	どういう構造か	構文解析
意味	何を表しているか	意味解析、型システム

自然言語の音韻論・統語論・意味論に対応する。

x = 1 + 2 * 3
   ↓ 字句解析
[x] [=] [1] [+] [2] [*] [3]
   ↓ 構文解析
     =
    /    x    +
       /       1   *
         /         2   3
   ↓ 意味解析
型は？ 変数 x は宣言されている？

形式言語との対応#

文法	認識する機械	用途
正規文法	有限オートマトン	字句解析
文脈自由文法	プッシュダウンオートマトン	構文解析
文脈依存	—	型検査などは通常の手続きで行う

括弧の対応は正規言語では表現できない（反復補題）ので、字句と構文を分ける必要がある。この階層は理論的な必然であって、便宜ではない。

参考文献#

Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed. Pearson, 2006.
Robert Nystrom. Crafting Interpreters. Genever Benning, 2021.（全文公開） https://craftinginterpreters.com/
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd ed. Pearson, 2006.