亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        編譯程序語法分析句柄問題分析與探討

        2017-03-21 20:44:41朱朝霞
        電腦知識與技術(shù) 2016年33期
        關(guān)鍵詞:句柄編譯器

        朱朝霞

        摘要:語法分析是編譯程序的核心部分,其任務(wù)是檢查詞法分析器輸出的單詞序列是否是源語言中的句子。該文以編譯程序自底向上語法分析為主線,探討自底向上語法分析歸約中的句柄求解問題,希望對編譯原理的課程教學(xué)有啟發(fā)作用。

        關(guān)鍵詞:編譯器; 自底向上語法分析;句柄;棧;歸約

        中圖分類號:TP314.51 文獻標識碼:A 文章編號:1009-3044(2016)33-0110-02

        語法分析是編譯程序的核心部分,其任務(wù)是檢查詞法分析器輸出的單詞序列是否是源語言中的句子,亦即是否符合源語言的語法規(guī)則。完成句型的分析,主要有兩種方式:一種是使用推導(dǎo)方式推導(dǎo)出句子,即自頂向下的語法分析方法;另一種是利用歸約方式識別句子,即自底向上的語法分析方法。本文以編譯程序自底向上語法分析為主線,探討自底向上語法分析歸約中的句柄求解問題,希望對編譯原理的課程教學(xué)有啟發(fā)作用。

        1 自底向上語法分析

        自底向上語法分析,也稱移進-歸約分析,指從給定的輸入符號串w出發(fā),試圖將其歸約為文法的開始符號。其實現(xiàn)思想是對輸入符號串自左向右進行掃描,并將輸入符逐個移入一個后進先出棧中,邊移入邊分析,一旦棧頂符號串形成某個句型的句柄或可歸約串時,就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號串,重復(fù)這一過程直到歸約到棧中只剩下文法的開始符號時為分析成功。

        在自底向上的分析過程中,最關(guān)鍵的問題是句柄的識別問題,即每次規(guī)約時按當(dāng)前句型的句柄進行規(guī)約。自底向上語法分析方法主要有優(yōu)先分析法和LR分析法。下面以兩種分析法為例求解句型的句柄及可歸約串問題。

        2 優(yōu)先分析法

        優(yōu)先分析法可分為簡單優(yōu)先分析法和算符優(yōu)先分析法。簡單優(yōu)先分析法的基本思想是對一個文法按一定原則求出該文法所有符號即包括終結(jié)符和非終結(jié)符之間的優(yōu)先關(guān)系,按照這種優(yōu)先關(guān)系確定歸約過程的句柄,其歸約過程是一種規(guī)范歸約。

        算符優(yōu)先分析的基本思想是只規(guī)定算符之間的優(yōu)先關(guān)系,不考慮非終結(jié)符之間的優(yōu)先關(guān)系,在歸約過程中只要找到可歸約串就歸約,并不考慮歸約到哪個非終結(jié)符名,其歸約過程不是歸范歸約。

        2.1 簡單優(yōu)先分析法中的句柄

        簡單優(yōu)先分析法的分析算法:

        先根據(jù)已知優(yōu)先文法構(gòu)造相應(yīng)優(yōu)先關(guān)系矩陣,并將文法的產(chǎn)生式保存,設(shè)置符號棧S:

        1)將輸入符號串a(chǎn)1 a2 an #依次逐個存入符號棧S中,直到遇到棧頂符號ai的優(yōu)先性大于下一個待輸入符號aj時,停止進棧;

        2)以棧頂當(dāng)前符號ai為句柄尾,由此向左在棧中找句柄的頭符號ak,即找到ak-1的優(yōu)先性小于ak為止;

        3)由句柄ak ai在文法的產(chǎn)生式中查找右部為ak ai的產(chǎn)生式,若找到則用相應(yīng)左部代替句柄,若找不到則為出錯,此時可斷定輸入串不是該文法的句子;

        4)重復(fù)上述三步直到歸約完輸入符號串,棧中只剩文法的開始符號為止。

        對符號串#b(aa)b#的移進-歸約分析過程中,根據(jù)算法及優(yōu)先關(guān)系表求得歸約的句柄依次分別為:a、Aa)、(B、bAb。

        簡單優(yōu)先分析法中句柄的求解過程是每次察看句型中相鄰的兩個符號,通過兩個符號的優(yōu)先關(guān)系判定出前一個符號是句柄的尾。然后,再反向找出句柄的頭。如下圖所示:

        圖中U即為移進-歸約分析過程中當(dāng)前句型的句柄。

        2.2 算符優(yōu)先分析法中的句柄

        自底向上的算符優(yōu)先分析法,也稱自左向右歸約。由于算符優(yōu)先分析法不考慮非終結(jié)符之間的優(yōu)先關(guān)系,在歸約過程中只要找到可歸約串就歸約,并不考慮歸約到哪個非終結(jié)符名,因此算符優(yōu)先分析過程中的句柄是一個最左素短語的求解過程。對一文法來說,需先求得句型的所有素短語,處于句型最左邊的素短語即算符優(yōu)先分析的句柄。一個算符優(yōu)先文法的最左素短語形式為NiaiNi+1ai+1…ajNj+1,符號的優(yōu)先關(guān)系應(yīng)滿足:ai-1aj+1。

        使用算符優(yōu)先分析法的規(guī)約過程與規(guī)范歸約是不同的,以文法G[E]為例,

        (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→PF|P (6) P→(E) (7) P→i

        如果對輸入串#i+i#進行規(guī)范歸約分析過程需要12步,然而使用算符優(yōu)先歸約時只需要7步,分析過程中形成的歸約串只有三個:i、i、E+E。原因是算符優(yōu)先分析中去掉了單非終結(jié)符歸約,其歸約過程是一種快速歸約過程。

        3 LR分析法

        LR分析法是一種能根據(jù)當(dāng)前分析棧中的符號串和向右順序查看輸入串的k個(k≥0)符號就可以唯一地確定分析器的動作是移進還是歸約和用哪個產(chǎn)生式歸約,因而也就能唯一地確定句柄。LR分析法是規(guī)范推導(dǎo)的逆過程,是一種規(guī)范歸約。

        LR分析過程:將文法的終結(jié)符和非終結(jié)符都看成有窮自動機的輸入符號,每次把一個符號進棧看成已識別過了該符號,同時狀態(tài)進行轉(zhuǎn)換,當(dāng)識別到可歸前綴時,相當(dāng)于在棧中形成句柄,認為達到了識別句柄的終態(tài)。

        LR分析器的關(guān)鍵部分是分析表的構(gòu)造。LR分析表是LR分析器的核心部分,是總控程序的依據(jù)。一張LR分析表包括兩部分:一部分是“動作”(ACTION)表,表示當(dāng)前狀態(tài)下所面臨輸入符應(yīng)做的動作是移進、歸約、接受或出錯。另一部分是“狀態(tài)轉(zhuǎn)換”(GOTO)表,表示在當(dāng)前狀態(tài)下面臨文法的輸入符號時應(yīng)轉(zhuǎn)向的下一個狀態(tài)。

        對一個文法構(gòu)造了它的LR分析表后就可以在LR分析器的總控程序控制下對輸入串進行分析,即根據(jù)輸入串的當(dāng)前符號和分析棧的棧頂狀態(tài)查找分析表應(yīng)采取的動作,對狀態(tài)棧和符號棧進行相應(yīng)的操作即移進、歸約、接受或報錯。

        LR分析法中的歸約過程:

        當(dāng)在棧頂形成句柄為β時,則用β歸約為相應(yīng)的非終結(jié)符A,即當(dāng)文法中有A→β的產(chǎn)生式,而β的長度為γ,則從狀態(tài)棧和文法符號棧中自頂向下去掉γ個符號。并把A移入文法符號棧內(nèi),再把滿足Sj=GOTO[Sm-γ,A]的狀態(tài)移進狀態(tài)棧,當(dāng)歸約到文法符號棧中只剩文法的開始符號S時,并且輸入符號串已結(jié)束即當(dāng)前輸入符是‘#,則為分析成功。

        對符號串#baab#分析過程中,歸約過程中求得的句柄依次為:ε、ε、aBa、bAb、AB。

        4 結(jié)束語

        在編譯程序自底向上的語法分析過程中,最關(guān)鍵的問題是句柄的識別問題。簡單優(yōu)先分析法其歸約過程是一種規(guī)范歸約,準確、歸范、但分析效率較低,實際使用價值不大。算符優(yōu)先分析法其歸約過程不是歸范歸約,但分析速度快、簡單、直觀,特別適于用手工方式來實現(xiàn),很多編譯程序都使用算符優(yōu)先法分析表達式。LR分析法分析速度快,能準確、及時地指出輸入串的語法錯誤及出錯位置,比自底向上優(yōu)先分析法對文法的限制要少得多,對大多數(shù)用無二義性的上下文無關(guān)文法描述的語言都可以用LR分析器予以識別。

        參考文獻:

        [1] 蔣宗禮,姜守旭. 編譯原理[M]. 北京:高等教育出版社, 2010.

        [2] 張素琴, 呂映芝. 編譯原理[M]. 北京:清華大學(xué)出版社, 2005.

        [3] 張昱,陳意云. 編譯原理與技術(shù)[M]. 北京:高等教育出版社, 2010.

        [4] 陳火旺, 蔣偉進. 編譯原理[M]. 長沙:中南大學(xué)出版社, 2005.

        [5] 黃賢英,王柯柯. 編譯原理及實踐教程[M]. 北京:清華大學(xué)出版社, 2008.

        猜你喜歡
        句柄編譯器
        基于相異編譯器的安全計算機平臺交叉編譯環(huán)境設(shè)計
        運行速度大突破華為《方舟編譯器》詳解
        編譯技術(shù)綜述
        高校圖書館持久標識符應(yīng)用研究
        Microchip為MPLAB XC系列專業(yè)版編譯器推出低成本可續(xù)訂包月許可證
        MFC應(yīng)用程序多線程混合顯示界面方法研究
        通用NC代碼編譯器的設(shè)計與實現(xiàn)
        基于SPY++的軟件功能擴展的研究
        編譯器無關(guān)性編碼在微控制器中的優(yōu)勢
        基于ARM嵌入式平臺的x86譯碼SOC架構(gòu)設(shè)計
        女人的精水喷出来视频| 国产v精品成人免费视频400条| 国产一区二区三区亚洲天堂| 国产成人美涵人妖视频在线观看| 亚洲av色图一区二区三区| 免费无码又爽又刺激网站直播| 亚洲国产精品va在线播放| 日韩a∨精品日韩在线观看| 青榴社区国产精品| 视频一区二区三区国产| 91久久精品色伊人6882| 久久青青草原亚洲av无码麻豆| 欧美大香线蕉线伊人久久| 麻豆国产成人AV网| 精品国产一区二区三区av新片| 国产精品成人亚洲一区| 夜夜添夜夜添夜夜摸夜夜摸 | 最近中文字幕在线mv视频在线 | 国产亚洲一区二区三区成人| 极品夫妻一区二区三区| 欧美丰满少妇xxxx性| 日韩少妇内射免费播放| 久久久久国产亚洲AV麻豆| 亚洲av毛片一区二区久久| 国产精品一区二区av不卡 | 狠狠色噜噜狠狠狠狠7777米奇| 亚洲成人观看| 国产精品三级1区2区3区| 日韩人妻系列在线观看| 在线看片免费人成视频电影 | 公与淑婷厨房猛烈进出| 一本加勒比hezyo无码人妻| 亚洲一区二区在线视频播放| 青青草视频在线观看视频免费 | 亚洲无码夜夜操| 美女把内衣内裤脱了给男人舔| 日本道免费一区二区三区日韩精品| 国产尤物av尤物在线观看| Y111111国产精品久久久| 在线精品亚洲一区二区三区| 亚洲高清三区二区一区 |