嵌套：計算思維的另一個核心思想#
遞歸的特點其實是層層嵌套，就像俄羅斯套娃。嵌套是計算思維的另一個核心思想，可以視為遞歸思想的拓展——遞歸是嵌套的特例，它嵌套的永遠是自己。
對嵌套的理解深度直接影響程序設計的水平，因為今天面向對象的程序設計，其內部的過程或函數彼此之間的關係本身就是嵌套的。
計算機的思維方式 vs 常人的思維方式#
- 常人思維（如早期 Fortran 程序）：按照步驟順序執行的流程，步驟 1 → 步驟 2 → 步驟 3 → ……
- 計算機思維：遵循自頂向下遞歸的原則，整個程序被分解為一個個封裝好的獨立模塊，模塊之間相互嵌套調用
模塊化設計的特點#
- 每個模塊只完成一個功能
- 如果需要其他功能，就調用其他模塊
- 程序的結構就是嵌套的
- 模塊之間可以相互嵌套（遞歸則是一種特殊的相互嵌套，每一層嵌套的都是自己）
用計算機分析自然語言#
分析自然語言的語法，就是要把一句話一級一級地分析出語法結構。
語法規則（重寫規則）示例#
- 句子 = 主語部分 + 謂語部分
- 主語部分 = 定語 + 名詞短語
- 定語 = 名詞短語 | 形容詞短語
- 名詞短語 = 形容詞 + 名詞
- 謂語部分 = 謂語 + 賓語 / 謂語 + 狀語
- 賓語 = 句子 | 名詞短語
- 狀語 = 副詞 + 動詞
語法分析的嵌套特性#
- 這些規則是從上往下嵌套的：句子包含主語和謂語，主語又包含定語和名詞短語……
- 規則之間可能相互嵌套：例如一個句子的賓語可能包括另一個句子
- 這正是自頂向下遞歸算法的應用場景
語法分析的例子#
以「今年北京頤和園的遊客人數比往年減少了一成」為例：
- 語法分析器首先在「人數」和「比」之間畫一道線，分為主語和謂語部分
- 在「遊客」和「人數」之間再畫一道線，把主語分成定語和名詞短語
- 一直分析到每一個詞
上下文無關文法與上下文相關文法#
上下文無關文法（Context-Free Grammar）#
- 規則左邊的句子成分可以無條件地被右邊的一組句子成分代替，與上下文無關
- 分析自然語言語句的複雜度是 O(N^3)，其中 N 是句子的長度
- 今天使用的計算機程序語言，其文法都是上下文無關的
上下文相關文法（Context-Sensitive Grammar）#
- 一個句子成分是否能被重寫，取決於它的上下文
- 例如「改革」一詞，既可以作名詞也可以作動詞，取決於上下文
- 分析複雜度本身是 NP 困難（NP-hard）問題，通常情況可簡化到 O(N^6)，遠高於上下文無關文法的 O(N^3)
實際做法#
- 以上下文無關文法為基礎，在某些情況下考慮引入少量的上下文相關文法規則
- 20 世紀 80 年代後，引入概率的機率式上下文無關文法（PCFG）大大提高了語法分析的準確性
- 從機器學習的角度來看，PCFG 和馬爾可夫模型基本上等價
學習語法分析的兩個好處#
- 加深對計算思維的理解：特別是對遞歸、嵌套和模塊化的理解。遞歸思想的關鍵是把大問題不斷拆成小問題，在自然語言理解中，文法規則就是告訴計算機該怎麼拆的指令
- 親身感受計算量的龐大：分析一個長度為 20 個單詞的句子，讓大學生來做不過一兩分鐘的事情，但讓計算機做（在沒有算法優化的情況下）也需要一分鐘左右、萬億次計算
在計算機工程上，有時對算法效率看似微小的提升，都能極大地縮短運算時間。採用有效算法的產品可能通吃市場，而算法未經優化的競品可能毫無競爭力。每一級工程師水平的差異，反映到產品上，可能就會有數量級的差別。
要點回顧#
- 自然語言的文法分析，就是把線性的句子變成一棵語法樹
- 分析一個語句需要很多文法規則，過去是人編寫的，今天是通過機器學習得到的
- 文法規則可以是上下文無關的，也可以是上下文相關的