以生成規則定義文法

接下來，我們來學習程式語言的語法記法。程式語言的語法大部份是以「生成規則」（production rule）定義出來的。生成規則的規則是以遞迴方式來定義文法。

我們先用自然語言思考一下：（日文的）文法的巢狀結構。（譯註：這段用別的自然語言也通用，如中文。）舉例來說，「花很漂亮」這個句子中「花」這個名詞可以換成「紅色的花」也是正確的句子。把「紅色的」再延伸變成「淡紅色的」也還是正確的句子。這個句子也可以放進別的句子，像「我認為淡紅色的花很漂亮」。

這類文法，可以想成是根據「『句子』由『主語』和『述語』構成」或「『名詞詞組』是在『名詞』或『形容詞』後接上『名詞詞組』構成」這類規則定義出來的。所以，從「句子」出發，根據規則延伸，就可以造出無數符合定義的文法的句子。

或是我們反過來說，對於已經存在的句子，考慮符合該句子的延伸步驟，就可以考慮其文字列背後的結構。

原本上述的概念是為了自然語言而建立的，但是非常適合電腦處理的資料，所以生成規則以程式語言為首，也應用在電腦的各個領域中。

小知識：杭士基的生成文法

建立生成文法這個概念的，是諾姆﹒杭士基（全名：艾弗拉姆﹒諾姆﹒杭士基，英：Avram Noam Chomsky）這位語言學者。他的概念對語言學、電腦科學有非常大的影響。

根據杭士基的假說，人類說語言的理由，是因為人與生俱來的專門處理生成規則的腦部結構。因為人類有辦法得出遞迴的語言規則，才有辦法說出語言。人類以外的動物之所以沒有語言能力，他認為是是因為動物的腦並不具有得出生成規則的結構。杭士基的主張，雖在假說提出後近60年的今日仍未被證明或反證，但時至今日仍被認為非常有說服力。