基本介紹
- 中文名：文法檢查程式
- 外文名：grammar checker
- 學科：計算機
- 定義：檢查符合某種文法規則的程式
- 有關術語：形式語言
- 領域：編譯
簡介,形式語言,喬姆斯基體系,文法規則描述,詞法分析,語法分析,
簡介
形式語言是：某個字母表上，一些有限長字串的集合，而形式文法是描述這個集合的一種方法，也可以稱做文法。文法之所以這樣命名，是因為它與人類自然語言中的文法相似的緣故。
文法檢查程式是用於檢查形式語言是否符合某種文法規則的程式。在計算機科學中，形式語言是程式語言及其語法的基礎，因此文法檢查程式也可以認為是對程式的語法分析和詞法分析進行檢查程式，這一過程發生在程式編譯過程中。根據喬姆斯基體系將文法分為四個層次，不同層次對應的文法檢查程式是有所差別的。文法檢查程式主要目的是檢查可能出現的語法和詞法錯誤。
形式語言
形式語言的字母是從該語言的字元串可以形成的一組符號，字母，或標記，通常它的要求是有限的。
字元串由這個稱為字的字母形成，這些詞屬於一個特定的形式語言有時被稱為形式公式。一個正式的語言，往往是通過一個正式的語法，如正則文法或上下文無關文法定義，稱作形成規律。
形式語言理論主要研究的是內部結構模式這類語言的純粹的語法領域。形式語言理論是從語言學衍生而來，作為一種理解自然語言的句法規律。在計算機科學中，形式語言通常作為定義程式語言和語法的基礎，是正式版本的自然語言的子集。在計算複雜性理論中，決策問題通常定義為形式語言，複雜類被定義為形式語言的集合，它能被具有有限計算能力的機器所解析。在邏輯和數學基礎中，形式語言是用來表示公理系統的語法。
喬姆斯基體系
0-型文法（無限制文法或短語結構文法）包括所有的文法。該類型的文法能夠產生所有可被圖靈機識別的語言。可被圖靈機識別的語言是指能夠使圖靈機停機的字串，這類語言又被稱為遞歸可枚舉語言。注意遞歸可枚舉語言與遞歸語言的區別，後者是前者的一個真子集，是能夠被一個總停機的圖靈機判定的語言。
1-型文法（上下文相關文法）生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這裡的A是非終結符號，而 α, β 和 γ 是包含非終結符號與終結符號的字串；α, β 可以是空串，但 γ 必須不能是空串；這種文法也可以包含規則 S->ε ，但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。
文法規則描述
程式設計語言中的幾類單詞可用下述規則描述：
〈標識符〉→l|l〈字母數字〉
〈字母數字〉→l|d|l〈字母數字〉|d〈字母數字〉
〈無符號整數〉→d|d〈無符號整數〉
〈運算符〉→+|-|*|/|=|〈〈等號〉|〉〈等號〉……
〈等號〉→=
〈界符〉→，|；|(|)|……
其中l表示a～z中的任何一英文字母，d表示0～9中的任一數字。
關鍵字（保留字）也是一種單詞，一般關鍵字（保留字）都是由字母構成，它的描述也極容易，實際上，關鍵字（保留字）集合是標識符集合的子集。
最複雜的一類單詞要屬無符號實數了，比如25.55e+5和2.1，它們可以由如下規則描述。
例
〈無符號數〉→d〈餘留無符號數〉|.〈十進小數〉|e〈指數部分〉
〈餘留無符號數〉→d〈餘留無符號數〉|.〈十進小數〉|e〈指數部分〉|ε
〈十進小數〉→d〈餘留十進小數〉
〈餘留十進小數〉→e〈指數部分〉|d〈餘留十進小數〉|ε
〈指數部分〉→d〈餘留整指數〉|s〈整指數〉
〈整指數〉→d〈餘留整指數〉
〈餘留整指數〉→d〈餘留整指數〉|ε
其中s表示正或負號(+，-)，d表示0～9中的任一數字。
詞法分析
源程式中的單詞符號經掃描器分析，一般產生二元式：單詞種別；單詞自身的值。單詞種別通常用整數編碼，如果一個種別只含一個單詞符號，那么對這個單詞符號，種別編碼就完全代表它自身的值了。若一個種別含有許多個單詞符號，那么，對於它的每個單詞符號，除了給出種別編碼以外，還應給出自身的值。
