編譯原理 第六章 算符優(yōu)先分析法

本文格式為Word版，下載可任意編輯——編譯原理第六章算符優(yōu)先分析法第6章自底向上優(yōu)先分析

第六章算符優(yōu)先分析法

課前索引

什么是自下而上語(yǔ)法分析的策略？

什么是移進(jìn)-歸約分析？

移進(jìn)-歸約過(guò)程和自頂向下最右推導(dǎo)有何關(guān)系？

自下而上語(yǔ)法分析成功的標(biāo)志是什么？

什么是可歸約串？

移進(jìn)-歸約過(guò)程的關(guān)鍵問(wèn)題是什么？

如何確定可歸約串？

如何決定什么時(shí)候移進(jìn)，什么時(shí)候歸約？

什么是算符文法？什么是算符優(yōu)先文法？

算符優(yōu)先分析是如何識(shí)別可歸約串的？

算符優(yōu)先分析法的優(yōu)缺點(diǎn)和局限性有哪些？

算符優(yōu)先分析法是自下而上（自底向上）語(yǔ)法分析的一種，特別適應(yīng)于表達(dá)式的語(yǔ)法分析，由于它的算法簡(jiǎn)單直觀易于理解，因此，也是學(xué)習(xí)其它自下而上語(yǔ)法分析的基礎(chǔ)。通過(guò)本章學(xué)習(xí)學(xué)員應(yīng)把握：

對(duì)給定的文法能夠判斷該文法是否是算符文法

對(duì)給定的算符文法能夠判斷該文法是否是算符優(yōu)先文法

對(duì)給定的算符文法能構(gòu)造算符優(yōu)先關(guān)系表，并能利用算符優(yōu)先關(guān)系表判斷該文法是否是算符優(yōu)先文法。

能應(yīng)用算符優(yōu)先分析算法對(duì)給定的輸入串進(jìn)行移進(jìn)-歸約分析，在分析的每一步能確定當(dāng)前應(yīng)移進(jìn)還是歸約，并能判斷所給的輸入串是否是該文法的句子。

了解算符優(yōu)先分析法的優(yōu)缺點(diǎn)和實(shí)際應(yīng)用中的局限性。

算符優(yōu)先分析法是自下而上語(yǔ)法分析的一種，它的算法簡(jiǎn)單、直觀、易于理解，所以尋常作為學(xué)習(xí)其它自下而上語(yǔ)法分析的基礎(chǔ)。為學(xué)好本章內(nèi)容，學(xué)員應(yīng)復(fù)習(xí)有關(guān)語(yǔ)法分析的知識(shí)，如：什么是語(yǔ)言、文法、句子、句型、短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄、最右推導(dǎo)、規(guī)范歸約基本概念。

通過(guò)本章學(xué)習(xí)后，學(xué)員應(yīng)當(dāng)能知道算符文法的形式。

對(duì)一個(gè)給定的算符文法能構(gòu)造算符優(yōu)先關(guān)系分析表，并能判別所給文法是否為算符優(yōu)先文法。

分清規(guī)范句型的句柄和最左素短語(yǔ)的區(qū)別，進(jìn)而分清算符優(yōu)先歸約和規(guī)范歸約的區(qū)別。

算符優(yōu)先分析的可歸約串是句型的最左素短語(yǔ)，在分析過(guò)程中如何尋覓可歸約串是算符優(yōu)先分析的關(guān)鍵問(wèn)題。對(duì)一個(gè)給定的輸入串能應(yīng)用算符優(yōu)先關(guān)系分析表給出分析（歸約）步驟，并最終判斷所給輸入串是否為該文法的句子。

深入理解算符優(yōu)先分析法的優(yōu)缺點(diǎn)和實(shí)際應(yīng)用中的局限性。

第6章自底向上優(yōu)先分析

第6章自底向上優(yōu)先分析

短語(yǔ)、直接短語(yǔ)、句柄的定義：文法G[S]，

SαAδ且Aβ則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)。若有Aβ則稱β是句型αβδ相對(duì)于A或規(guī)則A→β的直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。

算符優(yōu)先分析法是一種自底向上分析方法，也稱移進(jìn)-歸約分析法，粗略地說(shuō)它的實(shí)現(xiàn)思想是對(duì)輸入符號(hào)串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄時(shí)，(該句柄對(duì)應(yīng)某產(chǎn)生式的右部)，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這稱為一步歸約。重復(fù)這一過(guò)程直到歸約到棧中只剩文法的開(kāi)始符號(hào)時(shí)則為分析成功，也就確認(rèn)輸入串是文法的句子。本章將在介紹自底向上分析思想基礎(chǔ)上，著重介紹算符優(yōu)先分析法。

棧頂符號(hào)串是指該符號(hào)串包含棧頂符號(hào)在內(nèi)，并由棧中某個(gè)符號(hào)為該符號(hào)串的頭，棧頂符號(hào)為該符號(hào)串的尾，也可以只有一個(gè)棧頂符號(hào)。

6.1自底向上分析概述

自底向上分析法，也稱移進(jìn)-歸約分析法，或自下而上分析。現(xiàn)舉例說(shuō)明。

例6.1

設(shè)文法G[S]為：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d

對(duì)輸入串a(chǎn)bbcde#進(jìn)行分析，檢查該符號(hào)串是否是G[S]的句子。由于自底向上分析的移進(jìn)-歸約過(guò)程是自頂向下最右推導(dǎo)的逆過(guò)程，而最右推導(dǎo)為規(guī)范推導(dǎo)，自左向右的歸約過(guò)程也稱規(guī)范歸約。簡(jiǎn)單看出對(duì)輸入串a(chǎn)bbcde的最右推導(dǎo)是：

SaAcBeaAcdeaAbcdeabbcde

由此我們可以構(gòu)造它的逆過(guò)程即歸約過(guò)程。

先設(shè)一個(gè)先進(jìn)后出的符號(hào)棧，并把句子左括號(hào)\號(hào)放入棧底，其分析過(guò)程如表6.1。

表6.1用移進(jìn)-歸約對(duì)輸入串a(chǎn)bbcde#的分析過(guò)程f6-1-1.swf

圖6.1自底向上構(gòu)造語(yǔ)法樹(shù)的過(guò)程

第6章自底向上優(yōu)先分析

推倒的逆過(guò)程為：SaAcBeaAcdeaAbcdeabbcde

對(duì)上述分析過(guò)程也可看成自底向上構(gòu)造語(yǔ)法樹(shù)的過(guò)程，每步歸約都是構(gòu)造一棵子樹(shù)，最終當(dāng)輸入串終止時(shí)剛好構(gòu)造出整個(gè)語(yǔ)法樹(shù)，圖6.1(a)(b)(c)(d)給出構(gòu)造過(guò)程，可與表中相應(yīng)分析步驟對(duì)照。

在上述移進(jìn)-歸約或自底向上構(gòu)造語(yǔ)法樹(shù)的過(guò)程中，我們?cè)趺粗篮螘r(shí)移進(jìn)，何時(shí)歸約，不能只簡(jiǎn)單地看成棧頂出現(xiàn)某一產(chǎn)生式的右部就可用相應(yīng)產(chǎn)生式歸約，例如在表6.1分析到第5)步時(shí)棧中的符號(hào)串是#aAb，棧頂符號(hào)串b和Ab分別是產(chǎn)生式(2)，(3)的右部，這時(shí)終究用(2)歸約還是用(3)歸約是自底向上分析要解決的關(guān)鍵問(wèn)題。

由于移進(jìn)-歸約是規(guī)范推導(dǎo)(最右推導(dǎo))的逆過(guò)程，即規(guī)范歸約(最左歸約)。當(dāng)一個(gè)文法無(wú)二義性時(shí)，那么它對(duì)一個(gè)句子的規(guī)范推導(dǎo)是唯一的，規(guī)范歸約也必然是唯一的。因而每次歸約時(shí)一定要按當(dāng)前句型的句柄，也就是說(shuō)，任何時(shí)候棧中的符號(hào)串和剩余的輸入串組成一個(gè)句型，當(dāng)句柄出現(xiàn)在棧頂符號(hào)串中時(shí)，則可用句柄歸約，這樣一直歸約到輸入串只剩終止符，文法符號(hào)棧中只剩開(kāi)始符號(hào)。這時(shí)才能認(rèn)為輸入符號(hào)串是文法的句子。否則為出錯(cuò)。

由此可見(jiàn)自底向上分析的關(guān)鍵問(wèn)題是在分析過(guò)程中如何確定句柄，也就是說(shuō)如何知道何時(shí)在棧頂符號(hào)串中已形成某句型的句柄，那么就可以確定何時(shí)可以進(jìn)行歸約。自底向上的分析算法好多，我們僅在本章和第7章介紹目前常