top-down和bottom-up解析的關鍵區別在於,top-down解析執行從起始符號到輸入字符串的解析,而bottom-down解析執行從輸入字符串到起始符號的解析。此外,自頂向下和自底向上解析的另一個重要區別是,自頂向下的解析使用最左邊的派生,而自下而上的解析使用最右邊的派生。
高級語言有助於編寫計算機程序。程序員更容易理解它們,但計算機不容易理解。因此,將程序轉換為高級程序。編譯器的任務是將人類可讀的源代碼轉換為機器可讀的機器代碼。一個程序要經過幾個步驟才能轉換成機器碼。整個過程稱為語言處理系統。其中之一是彙編。語法分析器或解析器在編譯器中,它執行解析任務。
目錄
1. 概述和主要區別
2. 什麼是自頂向下的解析
3. 什麼是自下而上的解析
4. 並排比較-表格形式的自頂向下與自下而上分析
5. 摘要
什麼是自頂向下分析(top down parsing)?
每種編程語言都有一組表示語言的規則。語法分析器或語法分析器獲取輸入字符串,並根據語法結果檢查它是否正確。換句話說,語法應該使用解析樹生成該字符串。
在自頂向下的解析中,解析從起始符號開始,並將到達給定的輸入字符串。考慮以下語法產生式規則。輸入字符串(w)為cad。
S->cAd
A->ab/A
執行自頂向下解析後的解析樹如下所示。
S產生c A d,A產生b。弦是cabd。它不是必需的字符串。因此,有必要進行回溯,即使用其他替代方法。
類似地,S產生c A d。對A應用另一個選項將得到A。現在它給出了所需的字符串。因此,解析器接受這個輸入字符串。執行自頂向下解析後的解析樹如下所示。
當輸入字符串(w)為abcde時
考慮以下語法產生式規則。
S->aABe公司
A->Abc/b
B->d
在自頂向下的分析中,
S->aABe(代替A->Abc)
S->aAbcBe(替換A->b)
S->Abcbe(代替B->d)
聖母院
替換首先從最左邊的變量開始,然後到下一個右邊的位置,依此類推。因此,它遵循最左邊的求導方法。此外,當存在變量時,決定選擇什麼樣的產生式規則是很重要的。
什麼是自下而上分析(bottom up parsing)?
在自下而上中,解析是以另一種方式進行的。解析從輸入字符串到起始符號。考慮以下語法產生式規則,並讓輸入字符串為wɛcad
S->cAd
A->ab/A
執行自底向上解析後的解析樹如下所示。
給定的字符串是cad。a由a生成。c、a和d組合得到起始符號S。
當輸入字符串(w)為abcde時
考慮以下語法產生式規則。
S->aABe公司
A->Abc/b
B->d
在自下而上的分析中,
S->aABe(代替B->d)
S->aAde(替換A->Abc)
S->aAbcde(子例程A->b)
聖母院
替換首先從最右邊的變量開始,然後移到下一個左邊的位置,依此類推。因此,它遵循左mot求導方法。
自上而下(top down)和自下而上分析(bottom up parsing)的區別
自頂向下解析是一種解析策略,它首先查看解析樹的最高級別,然後使用形式語法的規則沿著解析樹向下展開。自底向上解析是一種解析策略,它首先查看解析樹的最低層,然後使用形式語法的規則向上搜索解析樹。在自頂向下的解析中,解析從起始符號到輸入字符串。另一方面,在自下而上的解析中,解析從輸入字符串到起始符號。
此外,自頂向下分析的主要決策是選擇使用什麼產生式規則來構造字符串,而自下而上分析的主要決策是選擇何時使用產生式規則來減少字符串以獲得起始符號。此外,自頂向下的解析使用最左邊的派生,而自下而上的解析使用最右邊的派生。
總結 - 自上而下(top down) vs. 自下而上分析(bottom up parsing)
top-down和bottom-up解析的區別在於,top-down解析執行從起始符號到輸入字符串的解析,而bottom-down解析執行從輸入字符串到起始符號的解析。