華閱文章網解釋最左素短語的含義
算符優先分析 [上一節] [下一節] 5.2.1 算符優先文法及其優先表構造 一個文法，如果它的任一產生式的右部都不含兩個相繼（并列）的非終結符，即不含如下形式的產生式右部：…QR…則我們稱該文法為算符文法.在后面的定義中，a、b代表任意終結符；P、Q、R代表任意非終結符；‘…’代表由終結符和非終結符組成的任意序列，包括空字.假定G是一個不含e-產生式的算符文法.對于任何一對終結符a、b，我們說：1. a?b當且僅當文法G中含有形如P→…ab…或P→…aQb…的產生式；2. a?b當且僅當G中含有形如P→…aR…的產生式，而Rb…或RQb…；3. a?b當且僅當G中含有形如P→…Rb…的產生式，而R…a或R…aQ.如果一個算符文法G中的任何終結符對（a,b）至多只滿足下述三關系之一：a?b,a?b, a?b則稱G是一個算符優先文法.現在來研究從算符優先文法G構造優先關系表的算法.通過檢查G的每個產生式的每個候選式，可找出所有滿足a?b的終結符對.為了找出所有滿足關系?和?的終結符對，我們首先需要對G的每個非終結符P構造兩個集合FIRSTVT(P)和LASTVT(P): FIRSTVT(P)={a | Pa…或PQa…，a?VT而Q?VN} LASTVT(P)={a | P…a或P…aQ,a?VT而Q?VN} 5.2.2 算符優先分析算法 所謂素短語是指這樣的一個短語，它至少含有一個終結符，并且，除它自身之外不再含任何更小的素短語.所謂最左素短語是指處于句型最左邊的那個素短語.如上例，P*P和i是句型P*P+i的素短語，而P*P是它的最左素短語.現在考慮算符優先文法，我們把句型（括在兩個#之間）的一般形式寫成： #N1a1N2a2…NnanNn+1# (5.4)其中，每個ai都是終結符，Ni是可有可無的非終結符.換言之，句型中含有n個終結符，任何兩個終結符之間頂多只有一個非終結符.必須記住，任何算符文法的句型都具有這種形式.我們可以證明如下定理（證明留給有興趣的讀者作練習）：一個算符優先文法G的任何句型（5.4）的最左素短語是滿足如下條件的最左子串Njaj…NiaiNi+1, aj-1?aj aj? aj+1，…，ai-1?ai ai?ai+1根據這個定理，下面我們討論算符優先分析算法.為了和定理的敘述相適應，我們現在僅使用一個符號棧S，既用它寄存終結符，也用它寄存非終結符.下面的分析算法是直接根據這個定理構造出來的，其中k代表符號棧S的使用深度. 5.2.3 優先函數 在實際實現算符優先分析算法時，一般不用表5.1這樣的優先表，而是用兩個優先函數f和g.我們把每個終結符q與兩個自然數f(q)和g(q)相對應，使得 若q1?q2 則 f(q1)g(q2)函數f稱為入棧優先函數，g稱為比較優先函數.使用優先函數有兩方面的優點：便于作比較運算，并且節省存儲空間，因為優先關系表占用的存儲量比較大.其缺點是，原先不存在優先關系的兩個終結符，由于與自然數相對應，變成可比較的了.因而，可能會掩蓋輸入串的某些錯誤.但是，我們可以通過檢查棧頂符號q和輸入符號a的具體內容來發現那些原先不可比較的情形.如果優先函數存在，那么，從優先表構造優先函數的一個簡單方法是：1. 對于每個終結符a（包括#）令其對應兩個符號fa和ga，畫一張以所有符號fa和ga為結點的方向圖，如果a ??b，那么，就從fa畫一箭弧至gb；如果a??b，就畫一條從gb到fa的箭弧.2. 對每個結點都賦予一個數，此數等于從該結點出發所能到達結點（包括出發結點自身在內）的個數.賦給fa的數作為f(a)，賦給gb的數作為g(b).3. 檢查所構造出來的函數f和g，看它們同原來的關系表是否有矛盾.如果沒有矛盾，則f和g就是所要的優先函數.如果有矛盾，那么，就不存在優先函數.現在必須證明：若a?b，則f(a)=g(b)；若a?b，則f(a) g(b).第一個關系可從函數的構造直接獲得.因為，若a?b，則既有從fa到gb的弧，又有從gb到fa的弧.所以，fa和gb所能到達的結是全同的.至于a?b和a?b的情形，只須證明其一.如果a?b，則有從fa到gb的弧.也就是，gb能到達的任何結fa也能到達.因此，f(a)3 g(b).我們所需證明的是，在這種情況下，f(a)=g(b)不應成立.我們將指出，如果f(a)=g(b)，則根本不存在優先函數.假若f(a)=g(b)，那么必有 a?b, a1??b, a1??b1，…am??bm, a??bm因為對任何優先函數都必須滿足（5.5） 所規定的條件，而上面的關系恰恰表明，對任何優先函數f和g來說，必定有f(a)> g(b)3 f(a1)3 g(b1)3 … 3 f(am)3 g(bm)3 f(a)從而導致f(a)> f(a)，產生矛盾.因此，不存在優先函數f和g. 5.2.4 算符優先分析中的出錯處理 5.2.4 算符優先分析中的出錯處理使用算符優先分析法時，可在兩種情況下，發現語法錯誤：1. 若在棧頂終結符號與下一輸入符號之間不存在任何優先關系；2. 若找到某一“句柄”（此處“句柄”指素短語），但不存在任一產生式，其右部為此“句柄”.針對上述情況，處理錯誤的子程序也可分成幾類.首先，我們考慮處理類似第2種情況錯誤的子程序.當發現這種情況時，就應該打印錯誤信息.子程序要確定該“句柄”與哪個產生式的右部最相似.例如，假定從棧中確定的“句柄”是abc，可是，沒有一個產生式，其右部包含a,b,c在一起.此時，可考慮是否刪除a,b,c中的一個.例如，假若有一產生式，其右部為aAcB，則可給出錯誤信息：“非法b”；若另有。
關于編譯原理
答案是b。
首先，素短語必須是短語，這棵語法樹相對于根節點E有3個短語：P,P+T,P+T+i。句柄就是最左直接短語，就是P。
素短語只能在這三個短語中選了。 1. P不包括終結符，顯然不是素短語； 2. 注意，P+T是3個字符，那個"+"是終結符，所以不要認為它沒有終結符！！！它是一個素短語，因為它的任意一個真子串都不是素短語。
3. P+T+i不是素短語，因為其真子串"P+T"是一個素短語。 所以"P+T"是素短語，也是最左素短語。
編譯原理的2道題
短語分別是G,SdG,(SdG), a,(SdG)<a
直接短語為G 和a
句柄為G
應該是最左素短語 本體中應為（SdG）;a也是素短語
第二題就更加簡單了
這里只給出一個NFA：確定化算法機械套用一下即可
