編譯原理-自下而上的語(yǔ)法分析(編輯修改稿)
2025-06-18 04:33 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ? i| E+E|EE|E*E|E/E|(E) ? 它的句子有幾種 不同的規(guī)范歸約 。 ? 歸約即計(jì)算表達(dá)式的值。歸約順序不同，則計(jì)算的順序也不同，結(jié)果也不一樣。 ? 起決定作用的是 相鄰的兩個(gè)算符之間的優(yōu)先關(guān)系 。如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進(jìn)行歸約，則歸約過(guò)程是 唯一 的。 ? 所謂 算符優(yōu)先分析法 就是定義算符之間的某種優(yōu)先關(guān)系，借助于這種關(guān)系尋找 “ 可歸約串 ” 和進(jìn)行歸約 。 算符優(yōu)先分析 ? 定義任何兩個(gè)可能相繼出現(xiàn)的終結(jié)符 a與 b的優(yōu)先關(guān)系 ： 三種關(guān)系 a ≮ b a的優(yōu)先級(jí)低于 b a ≒ b a的優(yōu)先級(jí)等于 b a ≯ b a的優(yōu)先級(jí)高于 b ? 注意 ：與數(shù)學(xué)上的 、 、 =不同， a ≮ b并不意味著 b ≯ a ? 算符優(yōu)先文法及優(yōu)先表構(gòu)造 ? 一個(gè)文法，如果它的任一 產(chǎn)生式的右部都不含兩個(gè)相繼 (并列 )的非終結(jié)符 ，即不含如下形式的產(chǎn)生式右部： … QR… 則我們稱(chēng)該文法為 算符文法 。 ? 約定： ? a、 b代表任意終結(jié)符； ? P、 Q、 R代表任意非終結(jié)符； ? ‘ …’ 代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空字。 ? 假定 G是一個(gè)不含 ?產(chǎn)生式的算符文法。對(duì)于任何一對(duì)終結(jié)符 a、 b，我們說(shuō)： 1. a≒ b 當(dāng)且僅當(dāng)文法 G中含有形如P→… ab… 或 P→… aQb… 的產(chǎn)生式； ? 如果一個(gè)算符文法 G中的任何終結(jié)符對(duì) (a，b)至多只滿(mǎn)足下述三關(guān)系之一： a ≒ b， a ≮ b， a ≯ b 則稱(chēng) G是一個(gè) 算符優(yōu)先文法 。 2. a≮ b 當(dāng)且僅當(dāng) G中含有形如 P→… aR… 的產(chǎn)生式，而 R b… 或 R Qb… ； ????3. a≯ b 當(dāng)且僅當(dāng) G中含有形如 P→… Rb… 的產(chǎn)生式，而 R … a或 R … aQ。 ???? 算符優(yōu)先文法及優(yōu)先表構(gòu)造 ? 例 :考慮下面的文法 G[E]： (1) E→E+T | T (2) T→T*F | F (3) F→P ? F | P (4) P→(E) | i ?由第 (4)條規(guī)則，有 ‘ (’ ≒ ‘)’； ?由規(guī)則 E→E＋ T和 T?T*F， 有 ＋ ≮ *； ?由 (2)和 (3)，可得 * ≮ ↑； ?由 (1)E→E＋ T和 E ? E+T，可得 + ≯ +； ?由 (3)F→P?F和 F ? P?F，可得 ↑ ≮ ↑。 ?由 (4)P→(E)和 E?E+T?T+T?T*F+T?F*F+T ?P↑F*F+T?i↑F*F+T 有 (≮ +、 (≮ *、 (≮ ↑和 (≮ i。 算符優(yōu)先文法及優(yōu)先表構(gòu)造 ? 優(yōu)先關(guān)系表 （ 為終結(jié)符） + * ↑ i ( ) + * ? i ( ) ≯ ≯ ≯ ≯ ≮ ≯≮ ≮ ≯ ≯ ≯ ≮ ≯ ≮ ≮ ≮ ≮ ≯ ≮ ≯ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≯ ≯ ≯ ≯ ≒ ≯ ≯ ≯ ≯ ≯ ≯ ≒ ? 從算符優(yōu)先文法 G構(gòu)造優(yōu)先關(guān)系表的算法 ： ? 通過(guò)檢查 G的每個(gè)產(chǎn)生式的每個(gè)候選式，可找出所有滿(mǎn)足 a≒ b的終結(jié)符對(duì)。 ? 確定滿(mǎn)足關(guān)系 ≮ 和 ≯ 的所有終結(jié)符對(duì)： 首先需要對(duì) G的每個(gè)非終結(jié)符 P構(gòu)造兩個(gè)集合FIRSTVT(P)和 LASTVT(P)： 算符優(yōu)先文法及優(yōu)先表構(gòu)造 F I R S T V T P a P a P Qa a V Q VT N( ) { | , , }? ? ? ? ?? ?? ?或 而},|{)( NT VQVaaQPaPaPL A S T V T ????? ?? 而或 ?? 算符優(yōu)先文法及優(yōu)先表構(gòu)造 ? 有了這兩個(gè)集合之后，就可以通過(guò)檢查每個(gè)產(chǎn)生式的候選式確定滿(mǎn)足關(guān)系 ≮ 和 ≯ 的所有終結(jié)符對(duì)。 ? 如：假定有個(gè)產(chǎn)生式的一個(gè)候選形為 …aP… 那么，對(duì)任何 b?FIRSTVT(P)，有 a ≮ b。 ? 假定有個(gè)產(chǎn)生式的一個(gè)候選形為 …Pb… 那么，對(duì)任何 a?LASTVT(P)，有 a ≯ b。 FIRSTVT(P)的算法 ? 構(gòu)造集合 FIRSTVT(P)的算法 ： 按其定義，可用下面兩條規(guī)則來(lái)構(gòu)造集合FIRSTVT(P)： ?1. 若有產(chǎn)生式 P→a… 或 P→Qa… ，則a?FIRSTVT(P)； ?2. 若 a?FIRSTVT(Q)，且有產(chǎn)生式 P→Q… ，則 a?FIRSTVT(P)。 FIRSTVT(P)的算法 ? 數(shù)據(jù)結(jié)構(gòu)： ? 布爾數(shù)組 F[P， a]，使得 F[P， a]為真的條件是，當(dāng)且僅當(dāng) a?FIRSTVT(P)。開(kāi)始時(shí)，按上述的規(guī)則 (1)對(duì)每個(gè)數(shù)組元素 F[P， a]賦初值。 ? 棧 STACK，把所有初值為真的數(shù)組元素 F[P， a]的符號(hào)對(duì) (P， a)全都放在 STACK之中。 ? 運(yùn)算： ? 如果棧 STACK不空，就將頂項(xiàng)逐出，記此項(xiàng)為 (Q， a)。對(duì)于每個(gè)形如 P→Q… 的產(chǎn)生式，若 F[P， a]為假，則變其值為真且將 (P， a)推進(jìn) STACK棧。 ? 上述過(guò)程必須一直重復(fù)，直至棧 STACK拆空為止。 FIRSTVT(P)的算法 ? 如果把這個(gè)算法稍為形式化一點(diǎn)，我們可得如下所示的一個(gè)程序 (包括一個(gè)過(guò)程和主程序 )： ?過(guò)程 PROCEDURE INSERT(P， a)； IF NOT F[P， a] THEN BEGIN F[P， a]:=TRUE； 把 (P， a)下推進(jìn) STACK棧 END； FIRSTVT(P)的算法 ?主程序： BEGIN FOR 每個(gè)非終結(jié)符 P和終結(jié)符 a DO F[P， a]:=FALSE； FOR
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1