編譯原理第六章答案.doc

《編譯原理第六章答案.doc》由會員分享，可在線閱讀，更多相關《編譯原理第六章答案.doc（9頁珍藏版）》請在裝配圖網上搜索。

第6 章 自底向上優(yōu)先分析 第1 題 已知文法G[S]為： S→a|∧|(T) T→T,S|S (1) 計算G[S]的FIRSTVT 和LASTVT。 (2) 構造G[S]的算符優(yōu)先關系表并說明G[S]是否為算符優(yōu)先文法。 (3) 計算G[S]的優(yōu)先函數。 (4) 給出輸入串(a,a)#和(a,(a,a))#的算符優(yōu)先分析過程。 答案： 文法展開為： S→a S→∧ S→(T) T→T,S T→S (1) FIRSTVT - LASTVT 表： 表中無多重人口所以是算符優(yōu)先（OPG）文法。 友情提示：記得增加拓廣文法 S`→#S#，所以# FIRSTVT(S)，LASTVT(S) #。 (3)對應的算符優(yōu)先函數為： Success! 對輸入串（a,(a,a)）# 的算符優(yōu)先分析過程為： Success! 第2 題 已知文法G[S]為： S→a|∧|(T) T→T,S|S (1) 給出(a,(a,a))和(a,a)的最右推導，和規(guī)范歸約過程。 (2) 將(1)和題1 中的(4)進行比較給出算符優(yōu)先歸約和規(guī)范歸約的區(qū)別。 答案： (2)算符優(yōu)先文法在歸約過程中只考慮終結符之間的優(yōu)先關系從而確定可歸約串，而與 非終結符無關，只需知道把當前可歸約串歸約為某一個非終結符，不必知道該非終結符的名 字是什么，因此去掉了單非終結符的歸約。 規(guī)范歸約的可歸約串是句柄，并且必須準確寫出可歸約串歸約為哪個非終結符。 第３題： 有文法G[S]： S??V V??T|ViT T??F|T+F F??)V*|( (1) 給出(+(i(的規(guī)范推導。 (2) 指出句型 F+Fi(的短語，句柄，素短語。 (3) G[S]是否為OPG？若是，給出(1)中句子的分析過程。 因為該文法是OP，同時任意兩個終結符的優(yōu)先關系唯一，所以該文法為OPG。 (+(i(的分析過程 第４題 文法G［S］為： S→S;G｜G G→G(T)｜H H→a｜(S) T→T+S｜S （１） 構造G［S］的算符優(yōu)先關系表，并判斷G［S］是否為算符優(yōu)先文法。 （２） 給出句型a(T+S);H;(S)的短語、句柄、素短語和最左素短語。 （３） 給出a;(a+a)和(a+a)的分析過程，說明它們是否為G［S］的句子。 （４） 給出（３）中輸入串的最右推導，分別說明兩輸入串是否為G[S]的句子。 （５） 由（３）和（４）說明了算符優(yōu)先分析的哪些缺點。 （６） 算符優(yōu)先分析過程和規(guī)范歸約過程都是最右推導的逆過程嗎？ 答案： （1）構造文法G［S］的算符優(yōu)先關系矩陣：