『壹』 如何通俗易懂地解釋編譯原理中語法分析的過程
分成詞法分析，語法分析（LL演算法，遞歸下降演算法，LR演算法），語義分析，運行時環境，中間代碼，代碼生成，代碼優化這些部分。其實現在很多編譯原理的教材都是按照85,86出版的那本龍書來安排教學內容的，所以那本龍書的內容格式幾乎成了現在編譯原理教材的定式，包括國內的教材也是如此。一般來說，大學裡面的本科教學是不可能把上面的所有部分都認真講完的，而是比較偏重於前面幾個部分。像代碼優化那部分東西，就像個無底洞一樣，如果要認真講，就是單獨開一個學期的課也不可能講得清楚。所以，一般對於本科生，對詞法分析和語法分析掌握要求就相對要高一點了。
詞法分析相對來說比較簡單。可能是詞法分析程序本身實現起來很簡單吧，很多沒有學過編譯原理的人也同樣可以寫出各種各樣的詞法分析程序。不過編譯原理在講解詞法分析的時候，重點把正則表達式和自動機原理加了進來，然後以一種十分標準的方式來講解詞法分析程序的產生。這樣的做法道理很明顯，就是要讓詞法分析從程序上升到理論的地步。
語法分析部分就比較麻煩一點了。現在一般有兩種語法分析演算法，LL自頂向下演算法和LR自底向上演算法。LL演算法還好說，到了LR演算法的時候，困難就來了。很多自學編譯原理的都是遇到LR演算法的理解成問題後就放棄了自學。其實這些東西都是只要大家理解就可以了，又不是像詞法分析那樣非得自己寫出來才算真正的會。像LR演算法的語法分析器，一般都是用工具Yacc來生成，實踐中完全沒有比較自己來實現。對於LL演算法中特殊的遞歸下降演算法，因為其實踐十分簡單，那麼就應該要求每個學生都能自己寫。當然，現在也有不少好的LL演算法的語法分析器，不過要是換在非C平台，比如Java,Delphi,你不能運用YACC工具了，那麼你就只有自己來寫語法分析器。
『貳』 編譯原理筆記9：語法分析樹、語法樹、二義性的消除
語法分析樹和語法樹不是一種東西 。習慣上，我們把前者叫做「具體語法樹」，其能夠體現推導的過程；後者叫做「抽象語法樹」，其不體現過程，只關心最後的結果。
語法分析樹是語言推導過程的圖形化表示方法。這種表示方法反映了語言的實質以及語言的推導過程。
定義：對於 CFG G 的句型，分析樹被定義為具有下述性質的一棵樹：
推導，有最左推導和最右推導，這兩種推導方式在推導過程中的分析樹可能不同，但因最終得到的句子是相同的，所以最終的分析樹是一樣的。
分析樹能反映句型的推導過程，也能反映句型的結構。然而實際上，我們往往不關心推導的過程，而只關心推導的結果。因此，我們要對 分析樹 進行改造，得到 語法樹 。語法樹中全是終結符，沒有非終結符。而且語法樹中沒有括弧
定義：
說白了，語法樹這玩意，就一句話： 葉子全是操作數，內部全是操作符 ，樹里沒有非終結符也不能有括弧。
語法樹要表達的東西，是操作符（運算）作用於操作數（運算對象）
舉倆例子吧：
【例】： -(id+id) 的語法樹：
【例】：-id+id 的語法樹：
顯然，我們從上面這兩個語法樹中，直接就能觀察出來它們的運算順序。
【例】：句型 if C then s1 else s2
二義性問題：一個句子可能對應多於一棵語法樹。
【例】： 設文法 G： E → E+E | E*E | (E) | -E | id
則，句子 id+id*id、id+id+id 可能的分析樹有：
在該例中，雖然 id+id+id 的 「+」 的結合性無論左右都不會影響結果。但萬一，萬一「+」的含義變成了「減法」，那麼左結合和右結合就會引起很大的問題了。
我們在這里講的「二義性」的「義」並非語義——我們現在在學習的內容是「語法分析器」，尚未到需要研究語言背後含義的階段。
我們現在講的「二義性」指的是一個句子對應多種分析樹。
二義性的體現，是文法對同一句子有不止一棵分析樹。這種問題由【句子產生過程中的某些推導有多於一種選擇】引起。懸空 else 問題就可以很好地體現這種【超過一種選擇】帶來的二義性問題，示例如下。
看下面這么個例子。。
（其實，我感覺這個其實比較像是「說話大喘氣」帶來的理解歧義問題。。。）上面的產生式中並沒體現出來該咋算分一塊，所以兩種完全不同的句子結構都是合法的。
二義性問題是有救的，大概有以下這三種辦法：
這些辦法的核心，其實都是將優先順序和結合性說明白。
核心：把優先順序和結合性說明白
既然要說明白，那就不能讓一個非終結符可以直接在當次推導中能推出會帶來優先順序和結合性歧義的東西。（對分析樹的一個內部節點，不會有出現在其下面的分支是相同的非終結符的情況。如果有得選，那就有得歧義了。沒得選才能確定地一路走到黑）
改寫為非二義文法的二義文法大概有下面這幾個特點：
改寫的關鍵步驟：
【例】改寫下面的二義文法為非二義文法。圖右側是要達成的優先順序和結合性
改寫的核心其實就兩句話：
所以能夠得到非終結符與運算的對應關系（因為不同的運算有不同的優先順序，我們想要引入多個優先順序就要引入多個新的非終結符。這樣每個非終結符就可以負責一個優先順序的運算符號，也就是說新的非終結符是與運算有關系的了。因此這里搞出來了「對應關系」四個字）如下：
優先順序由低到高分別是 +、 、-，而距離開始符號越近，優先順序越低。因此在這里的排序也可以+ -順序。每個符號對應一層的非終結符。根據所需要的結合性，則可確定是左遞歸還是右遞歸，以確定新的產生式長什麼樣子
【例】：規定優先順序和結合性，寫出改寫的非二義文法
我們已經掌握了一種叫做【改寫】的工具，能讓我們消除二義性。接下來我們就要用這個工具來嘗試搞搞懸空 else 問題！
懸空 else 問題出現的原因是 then 數量多於 else，讓 else 有多個可以結合的 then。在二義文法中，由於選哪兩個 then、else 配對都可以，故會引起出現二義的情況。在這里，我們規定 else 右結合，即與左邊最靠近的 then 結合。
為改寫此文法，可以將 S 分為完全匹配（MS）和不完全匹配（UMS）兩類。在 MS 中體現 then、else 個數相等即匹配且右結合；在UMS 中 then、else 不匹配，體現 else 右結合。
【例】：用改寫後的文法寫一個條件語句
經過檢查，無法再根據文法寫出其他分析樹，故已經消除了二義性
雖然二義文法會導致二義性，但是其並非一無是處。其有兩個顯著的優點：
在 Yacc 中，我們可以直接指定優先順序、結合性而無需自己重寫文法。
left 表示左結合，right 表示右結合。越往下的算符優先順序越高。
嗯就這么簡單。。。
我們其實可以把語言本身定義成沒有優先順序和結合性的。。然後所有的優先、結合都交由括弧進行控制，哪個先算就加括弧。把一個過程的結束用明確的標志標記出來。
比如在 Ada 中：
在 Pascal 中，給表達式加括弧：
『叄』 編譯原理, 寫一個簡單文法的詞法/語法分析器有簡單的方法嗎
那就用 lex 和 yacc 寫
不過實驗課程就是讓你手算一次
如果你用工具直接生成了意義不大
『肆』 編譯的語法分析
編譯程序的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語法規則的語法單位，如表達式、賦值、循環等，最後看是否構成一個符合要求的程序，按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構，程序是最終的一個語法單位。編譯程序的語法規則可用上下文無關文法來刻畫。
語法分析的方法分為兩種：自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發，向下推導，推出句子。而自下而上分析法採用的是移進歸約法，基本思想是：用一個寄存符號的先進後出棧，把輸入符號一個一個地移進棧里，當棧頂形成某個產生式的一個候選式時，即把棧頂的這一部分歸約成該產生式的左鄰符號。
『伍』 編譯原理題，在建立LL(1)語法分析器時，提左因子和消除左遞歸的目的是什麼
消除左遞歸是因為LL文法不能處理含有左遞歸的文法。
提左因子只是推後產生式的選擇決定，等到獲取足夠多的輸入再作選擇。
『陸』 編譯原理語法分析器程序設計，用C語言或C++，哪裡有這個程序
1.文法簡略，沒有實現的部分，可以在此文法的基礎上進行擴充，本程序的採用自頂向下的LL(1)文法。
2.可以自動實現求First
集和
Follow
集。
3.處終結符外（有些硬編碼的成分），終結符的文法可以自定義，也就是說讀者可以自定義文法。
4.為方便理解，C語言的文法描述寫成中文。
5.程序將詞法分析和語法分析結合起來，詞法分析的結果作為語法分析的輸入。
6.最終結果在控制台顯示的有：詞法分析、First集、Follow集、Select集，在preciateResult.txt
中寫入了語法分析結果，在preciateTable.txt
中寫入了預測分析表。
7.文法的詞素之間必須有空格分開。
『柒』 一般設計編譯器要將詞法分析和語法分析分開的原因是什麼
簡單性——詞法分析技術不如語法分析技術技術復雜，分開之後詞法分析過程更簡單。(這里還有一些意思差不多的話)
效率——詞法分析佔用的時間是整個編譯時間的一大部分，所以將它們分開有利於優化詞法分析，而提高編譯效率
可移植性——詞法分析通常平台相關，語法分析器可以是平台無關的。分開了對移植有利。
（引自《程序設計語言概念》(第9版) Sebesta著）
『捌』 運用編譯系統的設計原理，設計並實現編譯系統的前端詞法分析器和語法分析器
#include <stdio.h>
#include <ctype.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define NULL 0
#define MAX_KEY_NUM 10
#define MAX_BORDER_NUM 6
#define MAX_ARITH_NUM 4
#define MAX_RELATION_NUM 6
#define MAX_CONSTS_NUM 20
#define MAX_LABEL_NUM 20
FILE *fp;
char cbuffer;
char *key[MAX_KEY_NUM]={"if","else","for","while","do","return","break","continue","main","int"};
char *border[MAX_BORDER_NUM]={",",";","{","}","(",")"};
char *arithmetic[MAX_ARITH_NUM]={"+","-","*","/"};
char *relation[MAX_RELATION_NUM]={"<","<=","==",">=",">","="};
char *consts[MAX_CONSTS_NUM];
char *label[MAX_LABEL_NUM];
int constnum=0,labelnum=0;
//===============================================
int search(char searchchar[],int wordtype)
{
int i=0;
switch (wordtype) {
case 1:
for (i=0;i<MAX_KEY_NUM;i++)
{
if (strcmp(key[i],searchchar)==0)
return(i+1);
}
case 2:
{for (i=0;i<MAX_BORDER_NUM;i++)
{
if (strcmp(border[i],searchchar)==0)
return(i+1);
}
return(0);
}
case 3:
{for (i=0;i<MAX_ARITH_NUM;i++)
{
if (strcmp(arithmetic[i],searchchar)==0)
{
return(i+1);
}
}
return(0);
}
case 4:
{for (i=0;i<MAX_RELATION_NUM;i++)
{
if (strcmp(relation[i],searchchar)==0)
{
return(i+1);
}
}
return(0);
}
case 5:
{
for (i=0;i<constnum;i++)
{
if(constnum>0)
if (strcmp(consts[i],searchchar)==0)
{
return(i+1);
}
}
consts[i]=(char *)malloc(sizeof(searchchar));
strcpy(consts[i],searchchar);
constnum++;
return(i);
}
case 6:
{
for (i=0;i<labelnum;i++)
{
if (strcmp(label[i],searchchar)==0)
{
return(i+1);
}
}
label[i]=(char *)malloc(sizeof(searchchar));
strcpy(label[i],searchchar);
labelnum++;
return(i);
}
} // end of switch
}
//===============================================
char alphaprocess(char buffer)
{
int atype;
int i=-1;
char alphatp[20];
while ((isalpha(buffer))||(isdigit(buffer)))
{
alphatp[++i]=buffer;
buffer=fgetc(fp);
}
alphatp[i+1]='\0';
if (atype=search(alphatp,1))
printf("%s (1,%d)\n",alphatp,atype);
else
{
atype=search(alphatp,6);
printf("%s (6,%d)\n",alphatp,atype);
}
return(buffer);
}
//===============================================
char digitprocess(char buffer)
{
int i=-1;
char digittp[20];
int dtype;
while ((isdigit(buffer)))
{
digittp[++i]=buffer;
buffer=fgetc(fp);
}
digittp[i+1]='\0';
dtype=search(digittp,5);
printf("%s (5,%d)\n",digittp,dtype);
return(buffer);
}
//===============================================
char otherprocess(char buffer)
{
int i=-1;
char othertp[20];
int otype,otypetp;
othertp[0]=buffer;
othertp[1]='\0';
if (otype=search(othertp,3))
{
printf("%s (3,%d)\n",othertp,otype-1);
buffer=fgetc(fp);
goto out;
}
if (otype=search(othertp,4))
{
buffer=fgetc(fp);
othertp[1]=buffer;
othertp[2]='\0';
if (otypetp=search(othertp,4))
{
printf("%s (4,%d)\n",othertp,otypetp-1);
goto out;
}
else
othertp[1]='\0';
printf("%s (4,%d)\n",othertp,otype-1);
goto out;
}
if (buffer==':')
{
buffer=fgetc(fp);
if (buffer=='=')
printf(":= (2,2)\n");
buffer=fgetc(fp);
goto out;
}
else
{
if (otype=search(othertp,2))
{
printf("%s (2,%d)\n",othertp,otype-1);
buffer=fgetc(fp);
goto out;
}
}
if ((buffer!='\n')&&(buffer!=' '))
printf("%c error,not a word\n",buffer);
buffer=fgetc(fp);
out: return(buffer);
}
//===============================================
void main()
{
int i;
for (i=0;i<=20;i++)
{
label[i]=NULL;
consts[i]=NULL;
};
if ((fp=fopen("c:\example.c","r"))==NULL)
printf("error");
else
{
cbuffer = fgetc(fp);
while (cbuffer!=EOF)
{
if (isalpha(cbuffer))
cbuffer=alphaprocess(cbuffer);
else if (isdigit(cbuffer))
cbuffer=digitprocess(cbuffer);
else cbuffer=otherprocess(cbuffer);
}
printf("over\n");
getchar();
}
}
『玖』 簡述將源程序編譯成可執行程序的過程
一個源程序到一個可執行程序的過程：預編譯、編譯、匯編、鏈接。其中，編譯是主要部分，其中又分為六個部分：詞法分析、語法分析、語義分析、中間代碼生成、目標代碼生成和優化。
預編譯：主要處理源代碼文件中的以「#」開頭的預編譯指令。處理規則如下：
1、刪除所有的#define，展開所有的宏定義。
2、處理所有的條件預編譯指令，如「#if」、「#endif」、「#ifdef」、「#elif」和「#else」。
3、處理「#include」預編譯指令，將文件內容替換到它的位置，這個過程是遞歸進行的，文件中包含其他文件。
4、刪除所有的注釋，「//」和「/**/」。
5、保留所有的#pragma 編譯器指令，編譯器需要用到他們，如：#pragma once 是為了防止有文件被重復引用。
6、添加行號和文件標識，便於編譯時編譯器產生調試用的行號信息，和編譯時產生編譯錯誤或警告是能夠顯示行號。
(9)編譯時語法分析器擴展閱讀：
編譯過程中語法分析器只是完成了對表達式語法層面的分析，語義分析器則對表達式是否有意義進行判斷，其分析的語義是靜態語義——在編譯期能分期的語義，相對應的動態語義是在運行期才能確定的語義。
其中，靜態語義通常包括：聲明和類型的匹配，類型的轉換，那麼語義分析就會對這些方面進行檢查，例如將一個int型賦值給int*型時，語義分析程序會發現這個類型不匹配，編譯器就會報錯。
『拾』 求一個盡量完整的編譯器：詞法分析器+語法分析器
在一個模式被匹配之前，詞法分析器往往需要超前掃描該詞素後面的若干個字元，使用將字元退回輸入流的方法，需要移動大量字元的時間，由於 詞法分析器是編譯期間唯一需要逐一掃描源程序字元的過程，因此它的效率將極大的影響編譯器的性能，因此人們發明了雙緩沖區的技術。
雙緩沖區技術原理如下：
把一個緩沖區分成前後兩個部分，每部分能夠容納N(1024/4096)個字元，每次系統讀命令讀入N個字元到前半部分或者後半部分，如果剩餘的不足N個字元，則在最後增加一個不同於其他任何字元的字元，如eof/#，用於標識源文件的結束。緩沖區包括兩個指針beginning和forward，在兩個指針之間的字元串就是當前的詞素。一開始兩個指針都指向第一個字元，然後forward向後掃描，直至發現一個匹配的詞素為止。如果forward跨過中間標記，則往後半部分讀入N個字元。如果forward指針移過最後位置，則向前半部分讀入N個字元，且forward指針重新指向開始繼續處理過程。為了處理方便在兩個部分的最後都增加一個文件結束標識eof。示意圖如下：
______________________________________________________________________
|............for......while.... ........................................ |....int i .................................................. ...................| |_______________________________eof|_______________eof________________eof|
| |
beginning forward
下面是雙緩沖區的一個c實現：
#include <stdio.h>
#include <string.h>
#define MAXWORD 1000
struct bibuffer
{
char* buffer[2048]; //緩沖區空間
char* beginning,forward; //前向和後向指針
int count; //前向指針記數
} bbuf;
void parse(char c)
{
if(c=' ')
{
memcpy(word[i],beginning,(size_t)(forward-beginning));
i++;
}
else forward++;
}
int main(int argc,char* argv)
{
File* fp;
char* word[MAXWORD];
int i=0;
buffer=new char[2048];
fp=open("test.c","r");
read(fp,buffer,1023);
buffer[1023]='#';
read(fp,buffer+1024,1023);
buffer[2047]='#';
bbuf->buffer=buffer;
bbuf->beginning=bbuf->forward=bbuf->buffer;
bbuf->count=0;
while(1)
{
forward=forward+1;
if(count==1023)
{
read(fp,buffer+1024,1023);
forward++;
//這個函數的具體代碼就要和具體的詞法分析規則而定,這里假設只識別空格分割的單詞
parse(*forward);
}
else if(count>=2048)
{
read(fp,buffer,1023);
forward=bbuf->buffer;
//這個函數的具體代碼就要和具體的詞法分析規則而定,這里假設只識別空格分割的單詞
parse(*forward);
}
else if(count!=1023&&count<2048&&(*forward)='#')
{
break; //詞法分析結束
}
}
}
