編譯原理自底向上優(yōu)先分析法

編譯原理自底向上優(yōu)先分析法編譯原理是計(jì)算機(jī)科學(xué)中的重要課程，了解優(yōu)先分析法是學(xué)好該課程的必備條件。本講座將介紹優(yōu)先分析法的各個(gè)組成部分。輸入文法在編譯器中，文法描述了一種語言的結(jié)構(gòu)。輸入文法是創(chuàng)建由該語言構(gòu)成的分析樹的第一步。我們將學(xué)習(xí)如何定義和推導(dǎo)文法。文法的基本組成文法有兩部分：終結(jié)符和非終結(jié)符。終結(jié)符是語言中的實(shí)際字符，非終結(jié)符是由終結(jié)符組成的語言元素。文法的表示方法我們可以使用巴科斯-諾爾范式（BNF）或擴(kuò)展的巴科斯-諾爾范式（EBNF）來表示文法。文法推導(dǎo)通過使用產(chǎn)生式規(guī)則，我們可以推導(dǎo)出該語言中的所有有效字符串。First&Follow在編譯器中，F(xiàn)irst和Follow是從輸入文法中確定非終結(jié)符的關(guān)鍵步驟。它們是用于生成預(yù)測分析表的必要信息。1First集的構(gòu)成First集是終結(jié)符號(hào)的集合，可以由一個(gè)非終結(jié)符號(hào)派生出來的所有可能的終結(jié)符號(hào)序列的第一個(gè)終結(jié)符號(hào)的集合。2如何計(jì)算First集對(duì)于每個(gè)非終結(jié)符號(hào)，從左到右考慮所有產(chǎn)生式規(guī)則.W,W'...Wk.合併每個(gè)產(chǎn)生式規(guī)則的First集，如果某個(gè)W'可以經(jīng)過一連串產(chǎn)生式規(guī)則推導(dǎo)出空集，那么我們將其后一維的First集并入當(dāng)前集合中。3Follow集的構(gòu)成Follow集是包含終結(jié)符的集合，可以出現(xiàn)在非終結(jié)符號(hào)后面的所有例子字符串的集合。這到依據(jù)在預(yù)測分析表的構(gòu)造中。預(yù)測分析表預(yù)測分析表包含了編譯器在分析輸入時(shí)如何選擇正確的產(chǎn)生式。它是基于First和Follow集的。我們將學(xué)習(xí)如何構(gòu)造和使用預(yù)測分析表。構(gòu)造方法為每個(gè)非終結(jié)符和每個(gè)終結(jié)符創(chuàng)建一個(gè)表。每個(gè)單元格包含一個(gè)產(chǎn)生式。單元格在表中按照它們對(duì)應(yīng)的產(chǎn)生式規(guī)則排序。使用方法在分析和匹配每個(gè)終結(jié)符的同時(shí)，在預(yù)測分析表中匹配最左列為輸入元素的非終結(jié)符。從單元格中取出產(chǎn)生式并執(zhí)行規(guī)則。優(yōu)點(diǎn)與其他分析技術(shù)相比，在通用語法上表現(xiàn)更強(qiáng)，能處理繼承沖突，并且有廣泛的應(yīng)用領(lǐng)域。自底向上的Shift-Reduce分析方法Shift-Reduce分析的思想是在分析的過程中使用棧。在Shift狀態(tài)，輸入文本符號(hào)被讀入并入棧。在Reduct狀態(tài)下，根據(jù)產(chǎn)生式規(guī)則，將棧中的符號(hào)刪除并替換為非終結(jié)符號(hào)。1Shift-Reduce過程應(yīng)用Shift過程，移動(dòng)輸入符號(hào)并將該符號(hào)推入棧頂。然后應(yīng)用Reduce過程，在Stack頂點(diǎn)找到規(guī)模相符的右部符號(hào)組合。2表與自底向上分析通過視圖，在表格中按照Stack的層數(shù)和當(dāng)前輸入符號(hào)查找適當(dāng)?shù)牟僮?，并決定應(yīng)用Shift還是Reduce。這通常被稱為自底向上分析。SLR分析法SLR分析算法是LR文法的一種，它構(gòu)建了LR自動(dòng)雙向有限狀態(tài)器。我們將了解如何使用SLR分析法進(jìn)行語法分析。LR文法概述LR分析是自底向上移進(jìn)-規(guī)約（Shift-Reduce）分析技術(shù)。使用大量出現(xiàn)在可用于選擇處理方式的語言構(gòu)造句子中的定向符號(hào)來構(gòu)建LR表。SLR文法SLR文法是一個(gè)可以完成LR分析的一個(gè)子集，它特別適用于編寫簡單的編譯器，并且能夠在小型計(jì)算機(jī)上運(yùn)行的場景。LR分析法LR分析是自底向上移進(jìn)-規(guī)約（Shift-Reduce）分析技術(shù)的一種。它被廣泛認(rèn)為是最強(qiáng)大的語法分析器。我們將了解其構(gòu)造過程和LD文法。1LR分析LR分析是使用雙向有限狀態(tài)自動(dòng)機(jī)實(shí)現(xiàn)的語法分析方式,在LR語法計(jì)算中，Seeker不會(huì)登記已處理的符號(hào)，也無法回溯來檢測文法的錯(cuò)誤。2LR(0)項(xiàng)和LR(0)狀態(tài)LR(0)項(xiàng)是LR分析過程中的狀態(tài)，指出所有其右側(cè)可規(guī)約的字符串，并且包含指向在此狀態(tài)處理過的第一次出現(xiàn)的符號(hào)的指針。3LALR語法LALR文法是一種LR分析器，它通過標(biāo)準(zhǔn)LR分析中不遵守的狀態(tài)合并技術(shù)，解決了可預(yù)測語法的所有點(diǎn)。LALR分析法具有“Look-aheadLR”的轉(zhuǎn)寫。LALR語法是LR語法兩級(jí)壓縮技術(shù)的產(chǎn)物。我們將學(xué)習(xí)LALR分析法，它更加通用，具有與LR分析相媲美的強(qiáng)大功能。LALR分析法的原理在文法的句法單元集合先被退役,因?yàn)長ALR強(qiáng)制剪枝~LR~通用性的缺點(diǎn)。在分析階段，我們再次組成LR分析樹、類似于SLR出口。如果LALR分析法使用錯(cuò)誤輸入正常的句法，LALR分析器可以正常工作。但是，一部分LAL