• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    遞歸對(duì)自頂向下語法分析的影響

    2018-03-19 17:00:44朱朝霞
    電腦知識(shí)與技術(shù) 2018年4期
    關(guān)鍵詞:編譯器

    摘要:在編譯程序的語法分析中,含有左遞歸的文法,無法采用自頂向下的方法來進(jìn)行語法分析,該文從遞歸的角度出發(fā),討論遞歸對(duì)自頂向下語法分析的影響。

    關(guān)鍵詞:編譯器 ;語法分析;遞歸;左遞歸;右遞歸

    中圖分類號(hào):TP314.51 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2018)04-0231-02

    語法分析是編譯程序的核心部分,語法分析方法有多種,每一種語法分析方法只能處理某一種形式的文法,為了適應(yīng)所選擇的語法分析方法,常常需要對(duì)原始文法進(jìn)行改造。比如含有左遞歸文法或二義性文法將無法采用自頂向下的方法來進(jìn)行語法分析,本文從遞歸的角度出發(fā),討論遞歸對(duì)自頂向下語法分析的影響。

    1 遞歸的定義

    遞歸作為一種算法在程序設(shè)計(jì)語言中廣泛應(yīng)用,程序調(diào)用自身的編程技巧稱為遞歸,遞歸可把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原始問題相似的規(guī)模較小的問題來求解,只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算,大大地減少了程序的代碼量。遞歸的主要優(yōu)勢(shì)在于用有限的語句來定義對(duì)象的無限集合。其缺點(diǎn)是遞歸算法相對(duì)于非遞歸算法效率低,在遞歸調(diào)用的過程中系統(tǒng)需要為每一層的返回點(diǎn)、局部變量等開辟棧來存儲(chǔ),如果遞歸次數(shù)過多容易造成棧溢出。

    2 文法中的遞歸

    若文法中存在一個(gè)(或多個(gè))非終結(jié)符號(hào),它可以推導(dǎo)出含有其自身的符號(hào)串,則稱該非終結(jié)符號(hào)是遞歸的。一個(gè)文法中如果含有遞歸的非終結(jié)符號(hào),則此該文法稱為遞歸文法。

    文法中遞歸的分類:

    假設(shè)A是文法G的某個(gè)語法變量,如果存在推導(dǎo)AαAβ,則稱文法是遞歸的;

    1) 當(dāng)α=ε時(shí),稱之為左遞歸;當(dāng)β=ε時(shí),稱之為右遞歸;

    2) 如果AαAβ需要兩步以上推導(dǎo),則稱文法G是間接遞歸;并且當(dāng)α=ε時(shí),稱之為間接左遞歸;當(dāng)β=ε時(shí),稱之為間接右遞歸;

    3) 如果文法G中存在形如A→αAβ的產(chǎn)生式,則稱文法G是直接遞歸;當(dāng)α=ε時(shí),稱之為直接左遞歸,當(dāng)β=ε時(shí),稱之為直接右遞歸。

    3 遞歸對(duì)自頂向下語法分析的影響

    3.1 消除左遞歸引起的無窮推導(dǎo)問題

    使用自頂向下語法分析法進(jìn)行語法分析時(shí),假設(shè)文法中存在非終結(jié)符A,并且有AAa左遞歸,此文法是不能使用自頂向下的方法進(jìn)行語法分析的。因?yàn)楫?dāng)試圖用A去匹配輸入串時(shí),有可能使分析過程陷入無限循環(huán),因?yàn)榭赡茉跊]有“匹配”任何輸入符號(hào)的情況下,又要求用下一層A去進(jìn)行新的匹配,即使當(dāng)某個(gè)非終結(jié)符用某個(gè)選擇匹配成功時(shí),這種成功可能是暫時(shí)的,由于存在這種虛假現(xiàn)象,需要使用復(fù)雜的回溯技術(shù),而試探與回溯效率低、代價(jià)高,只有理論意義,在實(shí)踐中價(jià)值不大。因此,要想使用自頂向下的語法分析,必須消除文法中的左遞歸。

    1) 消除直接左遞歸

    采用直接改寫法:即把文法中直接左遞歸改寫為一個(gè)等價(jià)的非直接左遞歸形式。

    假定關(guān)于A的全部產(chǎn)生式為:

    A→Aα1|Aα2|…|Aαm|β1|β2|…|βn (αi非空,βj不以A開頭,1≤i≤m,1≤j≤n)

    消除直接左遞歸后改寫為:

    A→β1A | β2A| …|βnA

    A→α1A|ɑ2A|…|ɑmA|ε

    此方法改寫后可刪除文法中直接左遞歸,但不能消除兩步或多步推導(dǎo)形成的間接左遞歸。

    2) 消除文法中所有多重間接左遞歸的方法:

    當(dāng)文法中含有多重間接左遞歸時(shí),需先將產(chǎn)生式非終結(jié)符進(jìn)行置換,將間接左遞歸轉(zhuǎn)變?yōu)橹苯幼筮f歸,再按直接改寫法來消除直接左遞歸。

    輸入:不含循環(huán)推導(dǎo)和A→ε產(chǎn)生式的文法G

    輸出:與G等價(jià)的不含左遞歸的文法

    步驟:1.將文法的非終結(jié)符按某一順序排序,例如:P1,P2,…,Pn

    2. for i:=1 to n

    3. { for j:=1 to i-1

    4. { 若Pj的所有產(chǎn)生式為Pj→δ1|δ2|…|δk

    5. 將其替換形如Pi→Pjr的產(chǎn)生式得到Pi→δ1r|δ2r|…|δkr;}

    6. 消除Pi中的一切直接左遞歸

    7. 化簡(jiǎn)上述所得文法,去除無用產(chǎn)生式

    3.2 遞歸下降語法分析法中的遞歸

    遞歸下降分析法,是一種確定的自頂向下語法分析方法,它根據(jù)各個(gè)產(chǎn)生式的結(jié)構(gòu),為文法的每個(gè)語法變量編寫一個(gè)處理子程序,用來識(shí)別該語法變量所代表的語法成分。由于產(chǎn)生式中的語法變量可能是遞歸調(diào)用的,所以這種實(shí)現(xiàn)方法要求子程序可以遞歸調(diào)用,另外,這種分析方法也是尋求輸入串的一個(gè)最左推導(dǎo)過程,所以稱為遞歸下降分析法。它要求文法必須滿足LL(1)文法。

    采用遞歸下降分析法的文法中不能含有直接左遞歸的產(chǎn)生式,因?yàn)樽筮f歸會(huì)使遞歸下降語法分析器進(jìn)入一個(gè)無限循環(huán)。

    遞歸下降分析法遞歸調(diào)用多,所以速度慢,占用空間較多。

    4 文法中同時(shí)含有左遞歸和右遞歸的危害

    如果一文法中既含有左遞歸又含有右遞歸,即有AAvA或AA 或 A Aα及A βA (v∈V*)三者之一情況,則稱此文法是二義性的。

    對(duì)于編譯程序而言,二義性文法是有害的。由于語法結(jié)構(gòu)分析上的不確定性,必然會(huì)導(dǎo)致語義處理上的不確定性,最終生成的目標(biāo)代碼具有不確定性。并且對(duì)于二義性文法來說,不存在一種確切的方法進(jìn)行語法分析,此時(shí)可通過引入新的語法變量,來消除文法的二義性。

    例:文法G[E]: E→id E→E+E E→E*E E→(E) 同時(shí)含有左遞歸和右遞歸,是二義性文法。

    但在規(guī)定了優(yōu)先順序和結(jié)合律后可將文法改寫為:

    G[E]:E → T| E+T

    T → H| T*H

    H →(E)| id

    此時(shí)文法中只含有左遞歸而無右遞歸,改寫后的文法是個(gè)無二義性文法。

    5 結(jié)束語

    含有左遞歸文法或二義性文法將無法采用自頂向下的方法來進(jìn)行語法分析,此時(shí)我們可以將含有左遞歸的文法轉(zhuǎn)換為改寫為一個(gè)等價(jià)的非直接左遞歸形式,將二義性文法通過規(guī)定優(yōu)先順序和結(jié)合律將文法改寫為無二義性文法。如果改寫后的文法是滿足LL(1)文法,就可以采用確定的自頂向下分析法進(jìn)行語法分析。

    參考文獻(xiàn):

    [1] 朱朝霞,周云才. 二義性文法的語法分析方法探討[J] 長(zhǎng)江大學(xué)學(xué)報(bào),2008,5(6).

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

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

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

    [5] 陳火旺, 蔣偉進(jìn),等. 編譯原理[M] 長(zhǎng)沙:中南大學(xué)出版社,2005.

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

    猜你喜歡
    編譯器
    代碼生成器形式化驗(yàn)證技術(shù)研究
    面向理想性能空間的跨架構(gòu)編譯分析方法
    基于相異編譯器的安全計(jì)算機(jī)平臺(tái)交叉編譯環(huán)境設(shè)計(jì)
    運(yùn)行速度大突破華為《方舟編譯器》詳解
    Microchip為MPLAB XC系列專業(yè)版編譯器推出低成本可續(xù)訂包月許可證
    Identification and quantitative mRNA analysis of a novel splice variant of GPIHBP1 in dairy cattle
    Altium發(fā)布新一代BOSCH GTM—IP MCS TASKING C 編譯器
    彈載計(jì)算機(jī)程序優(yōu)化研究
    航空兵器(2014年5期)2015-02-10 02:43:52
    通用NC代碼編譯器的設(shè)計(jì)與實(shí)現(xiàn)
    優(yōu)化編譯器的設(shè)計(jì)
    群文天地(2011年14期)2011-04-20 02:50:36
    馆陶县| 潼南县| 南部县| 南昌县| 象山县| 东城区| 南投县| 清镇市| 石河子市| 正安县| 哈巴河县| 太仓市| 松江区| 云和县| 郸城县| 彩票| 乐平市| 黄梅县| 阿坝县| 湖南省| 海阳市| 富阳市| 含山县| 华安县| 五河县| 阿克陶县| 东宁县| 榆树市| 临安市| 曲靖市| 佛学| 桑植县| 仙游县| 巴林左旗| 栖霞市| 玛多县| 天等县| 秦皇岛市| 咸丰县| 昂仁县| 隆昌县|