形式文法
維基百科,自由的 encyclopedia
在形式語言理論中,文法(為了避免歧義,常稱作「形式文法」)是形式語言中字串的一套產生式規則(英語:Production (computer science))。這些規則描述了如何用語言的字母表生成符合語法(英語:syntax (programming languages))的有效的字串。文法不描述字串的含義,也不描述在任何上下文中可以用它們做什麼——只描述它們的形式。
形式語言理論是應用數學的一個分支,是研究形式文法和語言的學科。它在理論電腦科學、理論語言學、形式語意學、數理邏輯等領域有着廣泛的應用。
形式文法是從一個「開始符號」出發的一套重寫字串的規則。因此,文法通常被認為是語言生成器。然而,它有時也可以用作「辨識器」(電腦學中的一種函數,用於確定給定字串是否屬於該語言,是否為語法錯誤)的基礎。形式語言理論使用另一個理論來描述辨識器,也就是自動機理論。自動機理論有一個有趣的結果,某些形式語言是無法設計出辨識器的。[1] 語法分析是通過將一段話語(自然語言中的一個字串)分解成一組符號,並根據語言的語法分析每一個符號的過程。大多數語言的話語含義都是根據其句法結構來確定的——這種做法被稱為組合語意學。因此,在語言中描述話語含義的第一步就是把它分解成若干部分,然後觀察它經過分析後的形式(在電腦科學中被稱為分析樹,在生成文法中被稱為深層結構)。