【正文】 是源程序中的字面值。符號類別符號值表41 詞法Token字這五類單詞將用不同的方法處理。一種是用手工方式構(gòu)造，另一種是所謂詞法分析程序的自動生成。特殊符號共有12種：分別是4種基本的整數(shù)運算符號，5種比較符號（等號、小于號、小于等于、大于、大于等于），以及左括號、右括號、分號、賦值符號。 其它數(shù)(1個或更多的數(shù)字序列)標識符(1個或更多的字母序列)表42C語言的記號除了上表的記號之外，C語言的源程序還要遵循以下的詞法規(guī)則：代碼應是自由書寫格式；空白符由空格、制表位和新行組成。開 始輸入C源文件 是否文件結(jié)尾巴尾Y N 進入主控模塊選擇識別的單詞形成Token字Y停 止 圖41 單獨成趟的詞法分析控制流程圖，其核心函數(shù)是scan( )，它每次從第一個非空格或換行符開始識別，直到遇到空格或者換行符，遇到單行注釋就跳過本行從“//”開始的以后字符識別，遇到多行注釋就跳過直到遇到“*/”為止（不支持注釋嵌套）。 Token是本實驗的所有類的基類，有2個成員變量：Tag，Value。 string s。 while (true) { if ((c)==NULL) //到文件結(jié)尾 return (Token())。 //行數(shù)+1 else if (c==39。) //遇到空格或者制表符 continue。 amp。 || ()==39。 else //其他 { switch(c) //對字符進行分析 { case 39。: {...} case 39。: {...} case 39。: {...} case 39。: {...} case 39。|39。(39。: return (Token(get_int()), )))。 case 39。{39。: return (Token(get_int(}), }))。 case 39。))。 case 39。:39。39。 c \39。\039。目前語法分析方法有多種多樣，大致分為自頂而下和自底而上兩大類。自底向上分析法，也稱移進歸約分析法。LR（K）。由于LR（K）分析方法對文法限制很少，因而大多數(shù)能用上下文無關(guān)文法描述的程序設(shè)計語言都可用LR分析法進行有效分析，而且LR分析效率不亞于自頂向下分析法好、算法優(yōu)先分析法，及其他“移進規(guī)約”分析法。 C語言抽象出來的文法規(guī)則文法是為了深入研究語言的內(nèi)在性質(zhì)，而構(gòu)造語言的方法。2. 一個中間字母集，稱為非終結(jié)符，記為nontermanal，一般出現(xiàn)在規(guī)則左部的符號都是非終結(jié)符。4. 文法的開始符號S0。 25 expression_statement expression 。 54 jump_statement break 。這些編碼都是由程序自動算出，如表43所示。10expression_statement4111external_declaration42=12function_definition43=13function_name44==14iteration_statement4515jump_statement46=16logical_or_expression47break17logical_and_expression48continue18multiplicative_expression49double19parameter50double_num20primary_expression51e21relational_expression52id22selection_statement53if23statement54int24statement_list55int_num25translation_unit56return26type_specifier57void27　while28{29||30}31表43 C的終結(jié)符和非終結(jié)符我們可以從表42中閱讀出本實驗C的語法規(guī)則：C程序只是一個語句序列，它共有5種語句：if語句、while語句、賦值語句。比較運算符的優(yōu)先權(quán)都低于算術(shù)運算符。另外，變量只有全局作用域。分析表由來Grammer類來表示。 //文法結(jié)點數(shù)組 vectorint table_head。 //存放非終結(jié)符數(shù)值形式的集合文法結(jié)點結(jié)構(gòu)體：struct cfg_node{ string left。 //文法右部的鍵值放入對應的vector}。由于分析表非常大（171行，57列），故采用機械算法構(gòu)造。閉包利用集合的唯一性，故使用C++標準STL庫中的set模板。 //可能出現(xiàn)輸入符號的Tag}。項目集閉包具體實現(xiàn)：vectoritem_nodeamp。pos++) //對于closure的每一個項目依次求 { size_t cfg_no = closure[pos].cfg_no。 if (is_nonterminal(non_tml)) //加點位置下一個字符是非終結(jié)符，繼續(xù)擴展 { ... } //end if } //end for return closure。 static const int dollar = get_int($)。 size_t dot_pos = closure_item[i][k].dot_pos。 cfg[cfg_no].right_int[dot_pos]==x amp。 p_itemcfg_no = cfg_no。 } } return get_closure(j)。 vectoritem_node item_tmp。 tmpcfg_no = 0。 //cerr \nInit items begin...\n。 i()。 j++) //由I0狀態(tài)擴展，直到項目集不再增大為止 { vectoritem_node goto_tmp。 int str_nxdot = cfg[cfg_no].right_int[dot_pos]。 goto_tmp = get_goto(i, str_nxdot)。 //填規(guī)約時分析表 } else { cout Reduction conflict state: i endl。amp。 } if (()0) //移進動作，填分析表 { ... } //end if } //end for } //end for delete tmp。LR（1）分析器分析方法：LR（1）分析方法的基本思想是從左至右掃描程序，進行自底向上的語法分析，且在分析的每一步既要記住當前移進和規(guī)約的全部文法符號，又要向前看1個輸入符號，由此確定棧頂?shù)姆柎欠駱?gòu)成相對某一產(chǎn)生式的句柄，從而確定當前縮影采取的分析動作（移進或規(guī)約）。對于不同的文法，分析表各不相同，而總控程序都是一樣的（）。4． LR（1）分析器的工作過程就是在總控程序的控制下，從左到右掃描輸入符號串，根據(jù)分析棧中的文法符號和狀態(tài)及當前的輸入符號，按分析表的指示完成相應的分析動作。語義分析部分以語法分析部分的輸出作為輸入，輸出則是中間代碼甚至目標代碼。在一個典型的靜態(tài)類型的語言（如C語言）中，語義分析的工作通常包括構(gòu)造符號表、記錄聲明中建立的名字的含義、在表達式和語句中進行類型推斷和類型檢查、在程序的不同作用域范圍內(nèi)判斷變量的合法性。其他的語言介于這兩種極端情況之間（例如Pascal語言，不像Ada和C對靜態(tài)語義分析的要求那樣嚴格，也不像LISP那樣完全沒有要求）。在C中的類型檢查也比較簡單。 C的符號表在C語義分析程序的符號表的設(shè)計中，首先要確定哪些信息需要在符號表中保存。 //地址}。 C語義分析程序的實現(xiàn)將語言結(jié)構(gòu)的語義以屬性(attribute)的形式賦予代表此結(jié)構(gòu)的文法符號，而屬性的計算以語義規(guī)則(semantic rules)的形式賦予由文法符號組成的產(chǎn)生式；在語法分析推導或歸約的每一步驟中，通過語義規(guī)則實現(xiàn)對屬性的計算，以達到對語義的處理。 {= 。 28 assignment_expression logical_or_expression { assignment_exp。 {=null} 25 expression_statement expression 。其中直接向上傳遞的信息直接封裝在節(jié)點U_node中，包括存儲四元式的code域等，在語法指導定義中則只給出向上傳遞的即為U_node域。 //存放符號表利用map中key的唯一性，存放符號表。需要保存一個記錄表來記錄每一個變量的在內(nèi)存中的位置（符號表），每一個符號的結(jié)點定義如下：struct idenfierNode{ int type。僅有的布爾型值是兩個整數(shù)值進行比較的結(jié)果。這一類分析通常包括對“最優(yōu)化”或代碼改進技術(shù)的實現(xiàn)。對于不同的語言來說，語義分析的差異很大。由于它包括了計算上下文無關(guān)文法和標準語法分析算法以外的信息（即語義信息），因此，它不能被視為語法。以上的每一個步驟都用程序完整實現(xiàn)。（Lr:: analyse()函數(shù)中定義stackstack_nodestk。其邏輯結(jié)構(gòu)如下圖所示：…aiai+1…總控程序 Snxn…S1X1S0X0 圖42 LR（1）分析具體步驟一個LR（1）分析器由三部分組成：1． 一個有待分析的輸入符號串（c源程序）。}5) 生成LR(1)分析表，由于分析表的龐大，故將之生成后存于文件中。 else { cerr Accept conflict\n。amp。amp。amp。 size_t cfg_no = closure_item[i][j].cfg_no。 for (size_t j=0。 //計算初始項目集I0 static size_t count = 0。 (*tmp)。 const int dollar = get_int($)。項目集的個數(shù)即為有窮狀態(tài)自動機的狀態(tài)個數(shù)，根據(jù)以上57個產(chǎn)生式，本編譯器產(chǎn)生的狀態(tài)為171個。 //加點位置后移1位 (*p_item)。 x!=dollar) { item_node* p_item = new item_node。 //對于項目集中的每個項目，只要加點位置下一個字符Tag為x，把加點后的項目加入到新項目集 if (cfg[cfg_no].()dot_pos amp。 kclosure_item[i].size()。即是一個項目集遇到輸入代碼流中的一個符號后轉(zhuǎn)向的另一個狀態(tài)時候的項目集，并將之返回。 //加點 int prefix = closure[pos].possible_prefix。closure){ for (size_t pos=0。例如 {S ，}假設(shè)是第n個產(chǎn)生式，cfg_no = n， dot_pos=2，possible_prefix=””的編號。 //產(chǎn)生式編號 size_t dot_pos。為方便以后訪問，求完所有非終結(jié)符的first集后將它放在一個以非終結(jié)符為鍵的hash表中。 LR（1）語法分析關(guān)鍵的步驟是構(gòu)造LR（1）分析表。 //左部多對應的鍵值 vectorstring right。 //string符號集 setint terminal。Grammer類的構(gòu)造函數(shù)用來初始化ReadCfg類的成員變量，成員變量定義為protected型，方便Grammer類直接取到。 C語法分析程序的實現(xiàn)在實現(xiàn)C的語法分析器時，采用的核心算法是自底而上的LR（1）分析方法。C中的標識符指的是簡單整型變量，它沒有類似數(shù)組或記錄等類型的變量。布爾表達式使用比較運算符“=”和“”，通常用在if語句和while語句中作為測試條件；算術(shù)表達式使用整型運算符“+”、“”、“*”、“/”，它們具有左結(jié)合和常規(guī)的優(yōu)先關(guān)系。amp。 56 jump_statement return expression 。amp。下面是總結(jié)出來的c語言的文法，總共有57條規(guī)則：1 S0 translation_unit 2 translation_unit external_declaration 3 external_declaration function_definition 4 external_declaration declaration 5 declaration type_specifier id 。規(guī)則形如type_specifier void。一