覽器語法解析算法的并行化研究 覽器語法解析算法的并行化研究 摘要 網(wǎng)絡(luò)瀏覽器作為一個 算密集型的應(yīng)用程序，已經(jīng)成為掌上移動設(shè)備上的重要應(yīng)用之一，但同時又受到掌上移動設(shè)備較弱的 算能力的制約。由于散熱能耗等限制，在掌上移動設(shè)備單個計算單元運算能力很難顯著提升的條件下，網(wǎng)絡(luò)瀏覽器并行化成為提高瀏覽器性能的可行途徑之一。 語法解析器是網(wǎng)絡(luò)瀏覽器的重要組成部分，負責(zé)將詞法解析器從文本解析得到的符號序列解析成為符合某種語法 (通常是 法 )的語法解析樹，以便之后布局引擎等使用。據(jù)調(diào)查，語法解析器的解析工作在許多主流瀏 覽器的整個網(wǎng)頁處理過程中，占據(jù)了非?？捎^的運行時間，因此對語法解析算法的并行化是網(wǎng)絡(luò)瀏覽器并行化非常重要的部分。 語法解析問題是針對上下文無關(guān)語法及其語言的解析問題，目前比較常用的是 法解析技術(shù)和 法解析技術(shù)，這兩種技術(shù)在編譯器方面得到廣泛應(yīng)用并且經(jīng)過多種優(yōu)化，已經(jīng)趨于成熟。相比之下，很早被提出的通用解析算法 法和 法在這方面的應(yīng)用并不多，主要是由于雖然這兩種算法是通用的解析方法，但相比上面提到的技術(shù)，在效率上要相差很多，不過著這個僅僅是在串行化解析的角度下而言的。 法和 并行化方面更具有潛力。 法作為通用的解析算法，可以處理所有上下文無關(guān)語法，但前提條件是需要將語法轉(zhuǎn)化為符合喬姆斯基范式定義的形式。喬姆斯基范式對于語法形式的要求很嚴格，一般定義的語法很難符合，轉(zhuǎn)化過程也較為繁瑣。設(shè)計中，通過使用 寫工具完成了一般語法向喬姆斯基范式轉(zhuǎn)化的功能，工具使用了管道模型，通過不同的語法過濾器將遠語法中違反喬姆斯基范式定義的規(guī)則刪除，以此成功地將裁剪后的 法轉(zhuǎn)化為符合喬姆斯基范式的形式。需要指出的是，語法在轉(zhuǎn)化之后在規(guī)模上 擴大了許多，尤其是非終結(jié)符數(shù)量和規(guī)則數(shù)量，經(jīng)過試驗發(fā)現(xiàn)主要是由于刪除單元規(guī)則時大量的規(guī)則復(fù)制造成的。 語法的轉(zhuǎn)換引入了解析后語法樹與原語法存在差異的問題。通過分析原語法與轉(zhuǎn)化后語法的不一致性以及語法樹中不一致結(jié)點出現(xiàn)的原因，參考語法轉(zhuǎn)化的逆過程，我們提出了一套語法樹還原的方案，保證了解析前后語法與語法樹的一致，使得 法的使用對外界透明。 之后在 ，使用 C+完成了利用 法并行解析符合喬姆斯基范式語法的工具。通過對 法中子問題依賴關(guān)系的梳理，找出算法中能夠進行并行計算的部分，利用 持的 能最終實現(xiàn)算法的并行化。 在虛擬機下的測試表明，使用并行化算法的同步開銷會使得單核以及雙核情況下，并行算法的效率反而要低于串行算法。而當運算符單元的數(shù)量上升之后，并行算法的優(yōu)勢才得以體現(xiàn)。 法與 法相似，也是通用的上下文無關(guān)語法解析算法。本次設(shè)計中沒能夠進行實現(xiàn)，僅僅是對其進行了考察。 法是將語法解析問題轉(zhuǎn)化為對 合中的 的計算。 法相比 法，不需要對語法進行轉(zhuǎn)化，可以直接作用于任何上下文無關(guān)文法，包括具有二義 性的文法，這樣就避免了 法中繁瑣的語法轉(zhuǎn) 覽器語法解析算法的并行化研究 化和語法樹還原工作。并且 法中的 具有較直觀的含義，可以利用計算過程中的中間項目提高語法解析部分的響應(yīng)速度，雖然不一定是最終正確的結(jié)果，缺可以提高用戶體驗。另一方面， 法中的子問題劃分要比 法中困難的多，而且為了能夠使得 法并行化，在每個分段輸入的開始進行了預(yù)測，這樣導(dǎo)致的結(jié)果是并行算法要比串行算法計算更多的可能性，增加了問題的規(guī)模。 關(guān)鍵詞： 網(wǎng)絡(luò)瀏覽器，上下文無關(guān)語法，語法解析，并行化 覽器語法解析算法的并行化研究 of in eb as a of in its by of of a by t be in a its to by is an of It by a be by to we to is to of is its At LL R in to in To we YK a as a of as a we to be is Its a in a to In 覽器語法解析算法的并行化研究 In we a to is in of We to of in in to we of of We its by in of By of of in to we a of to to YK of + to YK by of of In of is of s YK is to is be is a of in YK on 覽器語法解析算法的并行化研究 YK to of in a of be in of to n On is in YK in to be to of is a is to of 覽器語法解析算法的并行化研究 目 錄 第一章 緒論 絡(luò)瀏覽器的架構(gòu) 下文無關(guān)語法的解析 上下文無關(guān)語法 法解析技術(shù) 法解析技術(shù) 二章 符合喬姆斯基范式語法的轉(zhuǎn)化 姆斯基范式 化方法 消除開始符號規(guī)則 消除空串規(guī)則 消除單元規(guī)則 消除混合規(guī)則 消除長規(guī)則 用 寫的語法轉(zhuǎn)換工具 用工具轉(zhuǎn)化 法 三章 利用 法進行語法解析 法介紹 法的并行化實現(xiàn) 體實現(xiàn) 法樹的還原 問題的產(chǎn)生 問題的解決方案 四章 考察 法 法介紹 法的并行化 章小結(jié) 考文獻 辭 覽器語法解析算法的并行化研究 第 1 頁 共 19 頁 第一章 緒論 隨著網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)瀏覽器已經(jīng)成為移動掌上設(shè)備不可缺少的應(yīng)用之一。它在運行過程中，同時扮演著 譯器，網(wǎng)頁布局引擎以及 釋器的角色，是較為典型的 制應(yīng)用，對 計算能力有很 高的要求。但由于移動掌上設(shè)備相對較弱的運算能力，很大程度上限制了網(wǎng)絡(luò)瀏覽器的功能。對于這個問題，考慮到電耗散熱等因素，掌上設(shè)備上單個計算單元的運算能力很難在短期內(nèi)有較大提升，因此使用多個計算單元來提高設(shè)備整體的運算能力成為了相對可行的方案。這時，網(wǎng)絡(luò)瀏覽器本身的并行化成為了迫切需要解決的問題。 在網(wǎng)絡(luò)瀏覽器對網(wǎng)頁的解析工程中，第一步是將 本解析成為語法樹。這項工作又分為詞法解析和語法解析兩步。 析在整個網(wǎng)頁處理過程中占據(jù)了可觀的份額。在“ s in 提到解析工 作在 整個處理過程中占據(jù) 3%到 10%的時間。而據(jù)“ 的測試， 是將 40%的時間用于解析 1。由此可見，對于語法解析算法的改進能夠在很大程度上提升網(wǎng)絡(luò)瀏覽器的性能。 絡(luò)瀏覽器的架構(gòu) 這一節(jié)簡要介紹一下目前網(wǎng)絡(luò)瀏覽器的大體架構(gòu)，可能與具體某個網(wǎng)絡(luò)瀏覽器的架構(gòu)有所出入。如圖 1示，網(wǎng)絡(luò)瀏覽器主要包括八個部分：用戶接口、瀏覽引擎、渲染引擎、網(wǎng)絡(luò)模塊、 釋器、 析器、顯示后端和數(shù)據(jù)持久模塊 2。 圖中箭頭表示各個部分之間的依賴關(guān)系。 圖 1絡(luò)瀏覽器架構(gòu)示意圖 (1)用戶接口是位于用戶和瀏覽引擎之間的模塊。他為用戶提供了諸如工具欄，下載，打印等功能接口。有時候，他可能會與用戶的桌面環(huán)境相集成以此與其他應(yīng)用進行通信。 (2)瀏覽引擎作為一個可嵌入組件，提供訪問渲染引擎的高層次接口。它能夠載入一個給定的 且提供諸如前進、后退、重載等操作。同時，外部模塊能夠利用瀏覽引擎提供的鉤子查看當前瀏覽會話的各種狀態(tài)，比如目前頁面的載入進程以及 警告。它還為渲染引擎設(shè)置選項的查詢 和修改提供了入口。 覽器語法解析算法的并行化研究 第 2 頁 共 19 頁 (3)渲染引擎可以說是網(wǎng)絡(luò)瀏覽器最重要的部分，它為一個 供可視化顯示。通常，它可以顯示 者 檔，這些文檔中可能還包括諸如圖片等嵌入對象，也有可能被 行修飾。這一模塊需要對整個顯示頁面進行布局，決定每個元素在頁面中的具體位置。 析器作為這個模塊的一部分，把 者 本文檔轉(zhuǎn)化成結(jié)構(gòu)化的數(shù)據(jù)結(jié)構(gòu)。 (4)網(wǎng)絡(luò)模塊的職責(zé)是實現(xiàn)如 網(wǎng)絡(luò)協(xié)議。同時還要再不同的字符集之間進行轉(zhuǎn)化，解決 體類型文件類型的問題，他可能會為最近使用的資源 實現(xiàn)一個緩存。 (5)如它的名字，用于解釋嵌入在網(wǎng)頁中的 發(fā)的一個面向?qū)ο蟮哪_本語言。某些 能，比如彈出窗口等，有時會被瀏覽引擎或者渲染引擎處于安全性考慮而屏蔽。 (6)析器用于將 檔解析為 。這個模塊可能是整個網(wǎng)絡(luò)瀏覽器中被重用的最多的模塊。事實上，幾乎所有瀏覽器都是使用現(xiàn)有的析器而不是從頭創(chuàng)建一個自己的 析器。 (7)顯示后端為最終的顯示提供用戶界面組件，字體等一些通常與操作系統(tǒng)密切綁定的元素。 (8)數(shù)據(jù)持久模塊將一些與瀏覽會話相關(guān)的數(shù)據(jù)存儲在磁盤上。這些數(shù)據(jù)可能是如書簽、工具欄設(shè)置此類的高層次數(shù)據(jù)，也有可能是如 存等底層數(shù)據(jù)。 下文無關(guān)語法的解析 語法可以用上下文無關(guān)語法（ 表示。對 語法解析也可以認為是對特定上下文無關(guān)語法的解析工作。由于語法解析工作中對文本解釋需要依賴于之前的文本，因此這項工作通常是順序完成的。 下文無關(guān) 語法 一個上下文無關(guān)語法 G，可以被表示為形如 四元組。其中， N 表示非終結(jié)符的集合； 表示終結(jié)符的集合，同時需要保證 N 與 總不含共有元素，即 N=； P 表示N 到 ( N)*1的關(guān)系的集合； S 表示開始符。 通常情況下，為了方便表示，我們使用 V 表示 N， 使用英文大寫字母（如 A， B，C）來表示非終結(jié)符集合 N 中的元素，使用小寫英文字母（如 a， b， c）表示終結(jié)符集合 中的元素，使用希臘字母（如 ， ）表示任意終結(jié)符和非終結(jié)符的序列 。 L(G)表示語法 G=的語言集合，有 L(G)=w *： S*w 。 一個特定上下文無關(guān)語法 G 的識別器能夠判斷一個任意的字符串是否是 L(G)中的元素。在此基礎(chǔ)上，語法 G 的解析器能夠為識別的字符串生成語法解析樹。盡管生成語法樹的工作要比僅僅識別字符串困難一些，但是通常我們在設(shè)計實現(xiàn)解析器時僅僅把識別問題納入考慮范疇，因為這兩者聯(lián)系緊密，在識別問題被解決時，往往只需要修改一些數(shù)據(jù)結(jié)構(gòu)，記錄識別過程中的一些信息，就可以構(gòu)造一個解析器 3。 用的上下文無關(guān)語法解析方法 法分析技術(shù) 4 法分析技術(shù)中的第一個 L 表示對輸入進 行從左到有的掃描，第二個 L 表示構(gòu)造最1 *表示 號運算，之后若無特殊說明，均為此意 覽器語法解析算法的并行化研究 第 3 頁 共 19 頁 左推導(dǎo)序列。 LL(k)語法分析技術(shù)中最常用的是 )語法分析，這里 1 表示從輸入序列中向前看一個輸入符號來確定用于展開的產(chǎn)生式。 一個語法是 )的，當且僅當語法 G 中任意兩個形如 A | 規(guī)則滿足以下條件時： 1)不存在終結(jié)符 a 使得 和 都能推倒出以 a 開始的串。 2) 和 中最多只能有一個推導(dǎo)出空串。 3)如果 可以推導(dǎo)出空串，那么 不能推導(dǎo)出任何以 )2中某個終結(jié)符開始的串。同理，當 可以推導(dǎo)出空串時，這條規(guī)則對 也適用。 可以說 )對于語法的要求還是相對 較嚴格的，很多直觀的語法定義并不能滿足 )的語法要求，而使用 LL(k2)的方法解析，效率又很難令人滿意。所以 )語法分析有時會與 LL(k2)語法分析混合使用，在大多數(shù)情況下使用 )而在局部不滿足 )語法要求的地方多向前看幾個輸入符號，使用 LL(k2)完成工作。比較典型的一個例子是 法分析技術(shù) 4 法分析技術(shù)中的 L 表示對輸入進行從左到右的掃描， R 表示反向的構(gòu)造出一個最右推導(dǎo)序列。目前最流行的自底向上的語法分析器都是基于 LR(k)語法分析的概念。這里 常取 k=0 和 k=1，具備較強的實踐意義。 法分析器是表格驅(qū)動的，這一點與非遞歸的 法分析器很相似。 法分析器主要具有以下的優(yōu)點： 1)對于大多數(shù)程序設(shè)計語言，只要能夠?qū)懗錾舷挛臒o關(guān)語法，就能夠構(gòu)造出對應(yīng)的 然確實存在非 上下文無關(guān)語法，但通常情況下，特別是對于程序設(shè)計語言，在設(shè)計構(gòu)造是都可以避免使用這樣的語法。 2)法分析方法是已知的最通用的無回溯移入 且他的實現(xiàn)能夠和其他更加原始的移入 3)一個 法分析器能夠在對輸入進行從左到右的掃描時盡早地發(fā)現(xiàn)錯誤。 4)能夠使用預(yù)測方法或者 法進行語法分析的語法都可以使用 語法分析器分析。一個語法是 LR(k)語法的條件是黨我們在一個最右句型看到某個產(chǎn)生式的右部時，如果我們向前再看 k 個字符，就能夠決定是否使用這個產(chǎn)生式進行規(guī)約。而這個條件要比 LL(k)語法寬松很多。相應(yīng)的，在面對 LL(k)語法時，我們在決定是否要使用某個產(chǎn)生式展開，需要向前看改產(chǎn)生式右邊推導(dǎo)出的串的 k 個字符。因此 法能夠比 法描述更多的語言。 當然， 法也存在缺點。當為一個具體的語 言語法手動構(gòu)造一個 法分析器的工作量是非常巨大的，需要特殊的工具進行輔助。 2 )表示在某些句型中可以緊跟在 A 后面的終結(jié)符的集合 覽器語法解析算法的并行化研究 第 4 頁 共 19 頁 第二章 符合喬姆斯基范式語法的轉(zhuǎn)化 姆斯基范式 (下簡稱 喬姆斯基范式是上下文無關(guān)語法的一個自己，我們說一個語法是喬姆斯基范式的當且僅當一個文法的規(guī)則 P 中所有元素屬于以下情況中的一種： AAa S 在這里 A， B， C 是非終結(jié)符， a 是終結(jié)符， S 是開始符號， 是空串。需要指出的是，B 和 C 都不能夠是開始符號。 喬姆斯基范式的一個重要特點是，所有上下文無關(guān)語 法都可以通過一定變換轉(zhuǎn)化為符合喬姆斯基范式的形式。 化方法 需要將一個語法 么該語法的規(guī)則集合 先要做的就是將這些違反定義的規(guī)則歸類，再為每類規(guī)則尋找轉(zhuǎn)化為符合定義形式的方法 5。 我們將違反 義的規(guī)則分為五類，具體如下： (1)開始符號規(guī)則（ 即在規(guī)則右邊出現(xiàn)了開始符號，而 義中明確指出規(guī)則右邊是不能出現(xiàn)開始符號的。形如 A其中 S 是開始符號 ， u,v V*。 (2)空串規(guī)則（ 即非開始符推出空串， 定義中只有開始符號允許推出空串。形如 A ，其中 A 為除了開始符號的非終結(jié)符， 為空串。 (3)單元規(guī)則（ 即由一個非終結(jié)符推出另一個非終結(jié)符， 義中當規(guī)則右邊為非終結(jié)符時，數(shù)量必須為兩個。形如 AB ，其中 A， B 都是非終結(jié)符。 (4)混合規(guī)則 （ ， 即規(guī)則右邊存在至少一個終結(jié)符和非終結(jié)符， 義中終結(jié)符必須單獨出現(xiàn)在規(guī)則右邊。形如 Aw ，其中 w V*并且 w 中包含終結(jié)符和非終結(jié)符至 少各一個。 (5)長規(guī)則（ 即規(guī)則右邊符號數(shù)量大于兩個， 義中當規(guī)則為非終結(jié)符時，數(shù)量必須為兩個。形如 Aw ，其中 w V*并且 |w|2。 在對違反 義的規(guī)則進行分類后，我們就可以根據(jù)這些規(guī)則的特點，在保證變換等價的情況下，逐一消除這些規(guī)則，達到將原有語法轉(zhuǎn)化為等價的 法。下面將介紹具體方法。 假設(shè)原有語法為 G，變換后的語法為 除開始符號規(guī)則 消除開始符號規(guī)則的做法十分簡單。 為了使得在 開始符號不再出現(xiàn)在規(guī)則右邊，我們引入新的符號 為 開始 符號，同時添加規(guī)則 。由于 新添加的符號，它不可能出現(xiàn)在其他規(guī)則中，那么自然地，它也不可能出現(xiàn)在其他規(guī)則的右邊。而 S 已經(jīng)不再是 開始符號了，所以經(jīng)過轉(zhuǎn)化后，新的語法 將沒有開始符號規(guī)則。 驗證變換后 L(= L(G)。如果 w L(G)，那么必然有 S*w ，由于在 有 ，則有 w ，所以 w L(；相反的，有 w L(由于 一能夠推出的就是 S，則 覽器語法解析算法的并行化研究 第 5 頁 共 19 頁 顯然的，對于每一個 w 必然是以 *w 的形式出現(xiàn)，也就有 S*w ，即 w L(由此可見， L(= L(G)。 除空串規(guī)則 消除空串規(guī)則的做法相對復(fù)雜。首先我們需要定義哪些非終結(jié)符是可為空的，修改這些可為空的符號出現(xiàn)的規(guī)則。 第一步：可為空定義：如果存在規(guī)則 A ，那么稱 A 是可為空的；如果存在規(guī)則AB 1中 部可為空，那么 A 是可為空的。我們將所有可為空符號組成的集合記為 E。 第二步：對于 G 中的規(guī)則，我們將它們分成三類，進行不同的處理，構(gòu)建新的語法 如 A 的規(guī)則，我們簡單將其刪除，不加入新語法 于 A 已經(jīng)被記錄到 E 中，之后 會進行處理保證變換的等價。形如 Aw ，其中 w N*，如果 w 中的符號都不可為空，那么，我們在新語法中保留這個規(guī)則。之后是最關(guān)鍵的一步，如果規(guī)則不屬于上述兩種情況，則規(guī)則具有 Aw ，其中 w N*，并且 w 中包含可為空的符號，那么 w 可以表示為形式中 示可為空的符號， 不包含可為空的符號。對于 們枚舉所有 在與不存在的組合，在 生成對應(yīng)的 2n 條規(guī)則。例如A其中 B， C 可為空，那么生成規(guī)則 A A A AD 。 第三步：如果開始符號 S 也出現(xiàn)在 E 中，那么向 的規(guī)則中添加 S 。 除單元規(guī)則 與消除空串規(guī)則相似的，我們首先定義二元組 (A,B)，稱為單元對。一個單元對 (A,B)代表的含義是 A*B 。為了之后操作的方便，我們將所有 (A,A)也定義為單元對，其中 A N。可以通過如下操作找出語法 G 中的所有單元對： 1)簡單地定義所有 (A,A)為單元對，其中 A N。 2)如果 (A,B)是一個單元對，并且存在規(guī)則 BC 那么我們認為 (A,C)也是一個單元對。 之后我們構(gòu)造新的語法 于單元對 (A,B)，如 果在 G 中存在規(guī)則 Bw ， w V*，那么我們將規(guī)則 Aw 加入 們注意到，由于之前我們將 (A,A)也作為單元對，在剔除AB 形式的規(guī)則的同時，原有符合定義的規(guī)則將會被復(fù)制到 去。 除混合規(guī)則 相比之前兩個規(guī)則的消除，混合規(guī)則的消除相比要簡單的多。這里我們的目的是要去除混合規(guī)則中的終結(jié)符，使之成為一個長規(guī)則，待由下一步消除長規(guī)則時徹底除去。對于一個混合規(guī)則 Aw ， w V*，我們可將 w 寫成形式 里 表終結(jié)符號，對于每個出現(xiàn)的終結(jié)符，我 們添加新的非終結(jié)符 造新規(guī)則 i，利用替代原有規(guī)則中的 得原來的規(guī)則成為 A 樣以后，所有混合規(guī)則都被轉(zhuǎn)化為符合 義的規(guī)則或者長規(guī)則。 除長規(guī)則 由于經(jīng)過上一步的變化，這里處理的長規(guī)則的右部全部為非終結(jié)符。即具有形式AB 1中 非終結(jié)符。這里，我們通過引入新的幫助非終結(jié)符，將一個長規(guī)則切割成許多符合 義的短規(guī)則，具體做法如下： 我們加入幫助非終結(jié)符 2,.,原有規(guī)則變?yōu)?AB 1 2 過這部變換后，原有語法中所有不符合 義的規(guī)則都被消除了，轉(zhuǎn)化得到的新語法即符合 定義。 用 寫的語法轉(zhuǎn)換工具 由于將一般語法轉(zhuǎn)化為符合 義的形式需要大量工作，而且設(shè)計中使用的是裁剪的 法，規(guī)模也比較大，使用手工轉(zhuǎn)化工作量巨大而且容易出錯，于是決定使用 覽器語法解析算法的并行化研究 第 6 頁 共 19 頁 寫工具完成轉(zhuǎn)化工作。 工具按照上一節(jié)中的方法對語法進行轉(zhuǎn)換。工具使用了管道模型，針對上一節(jié)中的每一種規(guī)則的消除 ，編寫一個語法過濾器，這些語法過濾器共同繼承接口 個接口有一個方法 個方法接受一個 代表一個上下文無關(guān)語法的數(shù)據(jù)結(jié)構(gòu)，并是些了對于語法操作的一些基本方法，比如添加規(guī)則，復(fù)制語法等 )并返回一個經(jīng)過修改的語法。我們從文件中讀入原始語法，將其構(gòu)造成為構(gòu)，再將五個語法過濾器串聯(lián)，使得原始語法依次通過這些語法過濾器，我們就可以得到一個符合 義的語法。 圖 1法轉(zhuǎn)化工具示意圖 這里五個語法過濾器 分別為 應(yīng)五種規(guī)則的移除工作。 用工具轉(zhuǎn)化 法 作為只有 法解析的輸入語法，我們需要對裁剪過的 除了標簽的屬性）進行轉(zhuǎn)化，使其符合 義的形式。這里我們使用工具對其進行處理并記錄下各個階段中各種規(guī)則的數(shù)量，語法規(guī)模的變化等數(shù)據(jù)。 從表 2我們可以看到，原有語法的非終結(jié)符號會在消除空串規(guī)則的時候被刪除，這是不能接受 的，因為以后的模塊可能需要用到這些符號，而這些符號所代表的含義也丟失了，在之后的章節(jié)中我們會詳細描寫如何找回這些丟失的結(jié)點。同時我們看到規(guī)則的數(shù)量在去除單元規(guī)則的時候數(shù)量發(fā)生了爆炸，擴大了五倍之多。引起這個現(xiàn)象的主要原因是 們看到在初始語法中就包含了 123 條單元規(guī)則，而消除單元規(guī)則我們采取的是復(fù)制規(guī)則的方式使得前后語法能夠保持等價，如果單元規(guī)則右邊的非終結(jié)符擁有大量導(dǎo)出規(guī)則，那么他們將會全部被復(fù)制給左邊的非終結(jié)符號，因此會導(dǎo)致規(guī)則數(shù)目的急劇增加。而且我們可以觀察到， 每個轉(zhuǎn)化規(guī)則并不是完全將對應(yīng)需要去除的規(guī)則直接轉(zhuǎn)化為符合 義的形式，有時會先轉(zhuǎn)化為尚未被處理的不符合范式定義的規(guī)則，交由之后的語法過濾器處理，這就解釋了為什么單元規(guī)則，混合規(guī)則以及長規(guī)則在轉(zhuǎn)化過程中有增加的情況，同時也說明了各個語法過濾器的使用是有先后次序的。 覽器語法解析算法的并行化研究 第 7 頁 共 19 頁 表 2化過程中的語法各項數(shù)據(jù)的變化 原語法 去除開始規(guī)則 去除空串規(guī)則 去除單元規(guī)則 去除混合規(guī)則 去除長規(guī)則 終結(jié)符 172 172 172 172 172 172 非終結(jié)符 293 293 291 291 294 373 規(guī)則 396 396 466 2026 2029 2108 開始規(guī)則 0 0 0 0 0 0 空串規(guī)則 20 20 0 0 0 0 單元規(guī)則 123 123 131 0 0 0 混合規(guī)則 10 10 10 65 0 0 長規(guī)則 73 73 79 912 912 0 第三章 利用 法進行語法解析 法介紹 法是 由 人提出的算法 6，用于判斷一個字符串是否屬于某個上下文無關(guān)語法。這個算法采用了自底向上和動態(tài)規(guī)劃的方法。對于輸入長度 為n 的字符串， 法可以在多項式時間內(nèi) O(決解析問題。同時 法可以解決任意上下文無關(guān)語法的解析問題，但需要首先將語法轉(zhuǎn)化為符合 義的形式。 下面給出的是這個算法的偽代碼。 我們注意到在偽代碼 3，主要解決的問題就是 Pn,n,m數(shù)組的取值問題。這里說明下 Pn,n,m的值所代表的含義，如果 Pi,j,k的值為 么表示 .以被解釋為 .法以終結(jié)符規(guī)則作為起始，由于 義 中的非終結(jié)符規(guī)則的右邊僅僅有兩個非終結(jié)符，我們很容易就能夠?qū)嵭凶缘紫蛏系臍w并。如下圖 3果 以被解釋為 B，而 以被解釋為 C，同時又有 A那么 。 覽器語法解析算法的并行化研究 第 8 頁 共 19 頁 圖 3法偽代碼 圖 3法規(guī)約示意圖 為了說明這個算法，我們首先 定義算法的輸入： 輸入長度為 n 的字符串 入 符合 義的 語法 G，其中包含 m 個非終結(jié)符 2,.,了方便表述，將 形如 A 其中 A,B,C 為非終結(jié)符）稱為非終結(jié)符規(guī)則；形如 Aa （ 其中 A 為非終結(jié)符， a 為終結(jié)符）稱為終結(jié)符規(guī)則；形如 S （ 其中S 為開始符號， 為空串 ）稱為空串規(guī)則。 Pn,n,m i = 1 to n j = 1 to n k = i to m Pi,j,ki = 1 to n 對于所有終結(jié)符規(guī)則 Njs i，執(zhí)行 Pi,1,ji = 2 to n j = 1 to k = 1 to 于所有的非終結(jié)符規(guī)則 果有 Pj,k,b和 Pj+k,c的值同時為 么執(zhí)行 Pj,i