Can you summarize the following document?
        
  文法主要由一組變換字串的規則組成。(如果它只包含這些規則,那麼它就是一個半圖厄系統。)要在該語言中生成字串,首先需要一個只包含一個開始符號的字串。然後按任意順序應用產生式規則,直到生成既不包含起始符號也不包含指定非終結符號的字串。產生式規則是通過把字串中第一次出現產生式規則左邊的地方,替換成產生式規則的右邊,來作用於這個字串的(參見理論圖靈機的運算)。由文法產生的語言包含能用這種方式產生的所有不同的字串。開始符號上的任何特定產生式規則序列都會在語言中產生一個不同的字串。如果產生同一個字串有多種不同的方式,那這個文法就是具有二義性的文法了。  例如,假設字母表由 "a" 和 "b" 組成,開始符號是 "S",我們有以下產生式規則:  那麼我們從 "S" 開始,選擇一個規則。如果我們選擇規則1,我們將獲得字串 "aSb"。如果我們再次選擇規則1,我們用 "aSb" 替換 "S",得到字串 "aaSbb"。如果我們現在選擇規則2,我們將 "S" 替換為 "ba" 並獲得字串 "aababb",然後就完成了。我們可以用符號將這一系列選擇寫得更簡短:formula_3。這種文法的語言就是無限集 formula_4,其中 formula_5 是 formula_6 重複 formula_7 次(formula_8 表示使用規則1的次數)。

  

  20世紀50年代,諾姆·喬姆斯基首次提出了生成語法的經典形式化理論, 其中文法 "G" 由以下部分組成: 文法的形式定義為四元組 formula_16。這種形式語法在文獻中常被稱為重寫系統或短語結構文法。

  文法的運算可以用字串的關係來定義:  注意文法 formula_17 實際上是半圖厄系統 formula_32,以完全相同的方式重寫字串;唯一的區別在於我們區分了特定的非終結符號,這些符號必須在重寫規則中重寫,並且只對從指定的開始符號 formula_23 到沒有非終結符號的字串的重寫感興趣。

  "在這些例子中,形式語言使用集合建構式符號描述。"  考慮文法 formula_27,其中 formula_35,formula_36,formula_23 是開始符號,formula_38 由以下產生式規則組成:  這個文法定義了語言 formula_43,這裡 formula_44 表示 "n" 個 formula_6 串連所得的字串。因此,該語言是由1個或更多的 formula_6,後面跟著相同數量的 formula_47,接著是相同數量的 formula_48 組成的字串集合。  formula_49 內字串的推導例子如下:

  1956年諾姆·喬姆斯基首次將生成文法形式化時, 他將它們分為現在稱為喬姆斯基譜系的四種型別。其中兩種重要的文法型別分別是上下文無關文法(2型)和正則文法(3型)。可以用這兩種文法描述的語言分別稱為上下文無關語言和正則語言。儘管比無限制文法(0型,實際上無限制文法可以表示任何圖靈機可以接受的語言)要弱得多,但這兩種受限制的語法最常用,因為它們的解析器可以高效地實現。 例如,所有正規語言都可以被有限狀態機識別,對於上下文無關文法的有用子集,有一些著名的演算法可以生成高效的LL剖析器LR剖析器,以識別文法生成的相應語言。

  上下文無關文法要求產生式左側只能包含一個符號,並且該符號為非終結符號。這個限制是非常重要的;不是所有的語言都可以由上下文無關的語法生成。那些可以被稱為上下文無關語言。  上例定義的語言 formula_43 並不是一個上下文無關語言,並且這個可以用上下文無關語言的泵引理嚴格證明,但 formula_52(1個及以上 formula_6 後面跟同樣數量的 formula_47)是一個上下文無關語言。因為它可以由文法 formula_55(formula_56,formula_57,formula_23 為開始符號)定義,用下列產生式規則:  通過Earley演算法可以在 formula_61 時間(參見大O符號)內識別上下文無關語言。也就是說,對於每一種上下文無關的語言,都可以構建一臺以字串為輸入並及時確定字串是否為該語言成員的機器,其中 formula_8 是字串的長度。 確定性上下文無關語言是可線上性時間內識別的上下文無關語言的子集。 由多種演算法針對這類語言或它的子集。

  在正則文法中,左側仍然只是一個非終結符號,但右側也受到限制。右側可以是空字串,也可以是單個終結符號,或者是後跟非終結符號的單個終結符號,但不能是其他符號。(有時會使用更寬泛的定義:可以允許更長的終結字串或單個非終結字串,而不能有其他任何東西,從而使語言更易於表示,同時仍然定義同一類語言。)  上面定義的語言 formula_52 不是一個正則語言,但下面這個語言是:formula_64(一個或多個 formula_6 後面跟著一個或多個 formula_47,這兩個的數量可以不一樣)。它之所以是正則語言,是因為可以通過文法 formula_67 定義,其中 formula_68,formula_57,formula_23 為開始符號,還有如下產生式規則:  由正則文法生成的所有語言都可以被有限狀態機在 formula_76 時間內識別出來。雖然在實際應用中,正則文法通常使用正規表示式來表示,但是實際應用中使用的一些正規表示式並沒有嚴格地生成正則語言,也因此沒有表現出線性識別效能。

  語言學家和電腦科學家對喬姆斯基的形式語法的原始層次結構進行了許多擴充套件和變化,通常是為了增強表達能力,或者是為了使分析或解析更加容易。一些形式的文法包括:

  遞迴文法是包含遞迴產生式規則的語法。例如,如果存在一個非終結符 "A",可以通過產生式規則生成一個以 "A" 為最左邊符號的字串,那麼上下文無關語言的文法就是左遞迴的。

  儘管有大量關於語法分析演算法的文獻,但這些演算法大多假設要被分析的語言最初是通過生成式文法來描述的,並且目標是將生成式文法轉換成一個有效的語法分析器。嚴格地說,生成文法不以任何方式對應用於解析語言的演算法,而且各種演算法對被認為是格式良好的產生式規則的形式有不同的限制。嚴格地說,生成文法不能在任何方面都與解析語言的演算法對應上,而且各種演算法對產生式規則的形式有不同的限制,這些產生式規則被認為是形式良好的。  另一種方法是首先根據分析型文法將語言形式化,分析型文法能更直接地對應於語言分析器的結構和語義。分析型文法體系的例子包括:
在形式語言理論中,文法(為了避免歧義,常稱作“形式文法”)是形式語言中字串的一套產生式規則。這些規則描述瞭如何用語言的字母表生成符合語法 (程式語言)的有效的字串。文法不描述字串的含義,也不描述在任何上下文中可以用它們做什麼——只描述它們的形式。