編譯原理英語句子畫圖分析

❶ 編譯原理

4、文法G為：
A->aABe/Ba
B->dB/ε
構造LL(1)分析表並判斷adae是否是該文法的句子。
5、文法G為：
A->i:=E；
E->E+E
E->E*E
E->i
構造SLR分析表，並判斷i:=i*i是否是該文法的句子。
6、文法G為：
S->E
E->aB/bB
A->cA/d
B->Cb/d
構造該文法的LR(0)和SLR（1）分析表，並模擬分析句子bcd時分析棧和輸入串的變化。
7、文法G為：
E->E+T/T
T->T*F/F
F->P^F/P
P->(E)/i
判斷該文法是否為算符優先文法，若是，構造優先表。

❷ 編譯原理，如何判斷一個FA是DFA還是NFA

DFA或NFA是對計算機程序的行為的抽象模型.你編寫的程序其實就對應了一個自動機.簡單舉例來說,如果a,b可以取值0或1; 程序：if(a==1) b=1; 這個程序對應了一個自動機.
對應的自動機就有狀態 (0,0),(0,1),(1,1),(1,0)
比如你自動機的初始狀態是 (1,0)即a=1,b=0時,運行程序的下一個狀態就是(1,1).
畫圖出來就是 這4個狀態作為頂點,並且有下面幾條邊
(0,0) --> (0,0)（自環）,(1,0)-->(1,1),(1,1)-->(1,1)（自環）,(0,1)-->(0,1)自環
存在的意義就是一種理論模型,也可以認為是一種編程思想.詞法分析系也離不開 if else,這一系列的if else和條件也就組成自動機.
最經典體現自動機思想的演算法就是KMP演算法,你肯定學過,字元串子串匹配的演算法.回憶這個演算法的過程：演算法第一步構造的next表（數據結構教材的說法）其實就是根據子串的內容構造了一個自動機!演算法第二步將原串作為自動機輸入,自動機的輸出就是匹配到的子串位置或者無匹配.

❸ ！！編譯原理DFA和NFA

DFA或NFA是對計算機程序的行為的抽象模型。你編寫的程序其實就對應了一個自動機。簡單舉例來說，如果a,b可以取值0或1; 程序： if(a==1) b=1; 這個程序對應了一個自動機。
對應的自動機就有狀態 (0,0), (0,1), (1,1), (1, 0)
比如你自動機的初始狀態是 (1,0)即a=1,b=0時，運行程序的下一個狀態就是(1,1)。

畫圖出來就是 這4個狀態作為頂點，並且有下面幾條邊
(0,0) --> (0,0)（自環）, (1,0)-->(1,1), (1,1)-->(1,1)（自環）, (0,1)-->(0,1)自環

存在的意義就是一種理論模型，也可以認為是一種編程思想。 詞法分析系也離不開 if else， 這一系列的if else和條件也就組成自動機。。。

最經典體現自動機思想的演算法就是KMP演算法，你肯定學過，字元串子串匹配的演算法。 回憶這個演算法的過程：演算法第一步構造的next表（數據結構教材的說法）其實就是根據子串的內容構造了一個自動機！ 演算法第二步將原串作為自動機輸入，自動機的輸出就是匹配到的子串位置或者無匹配。

❹ 編譯原理中的lookhead描述的是什麼意思

lookahead 就是向前看。在語法分析過程中，分析器根據當前已經掃描過的標記流，再加上尚未掃描的標記，確定怎樣分析這個句子。如果只看一個尚未處理的標記就能確定怎麼進行下一步分析，就叫做Lookahead 1，如果需要看兩個才能確定，就叫做Lookahead 2，依此類推。

❺ 正在學習編譯原理，語法圖應該用什麼軟體畫會比較簡單一點

一般用YACC畫，不過建議用GOLD PARSER。畫起來最快，不要編程。
步驟：
1）寫出正確的文法。
2）在測試窗口中輸入要分析的字元串。

❻ 編譯原理-LL1文法詳細講解

我們知道2型文法( CFG )，它的每個產生式類型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。

例如, 一個表達式的文法:

最終推導出 id + (id + id) 的句子，那麼它的推導過程就會構成一顆樹，即 CFG 分析樹：

從分析樹可以看出，我們從文法開始符號起，不斷地利用產生式的右部替換產生式左部的非終結符，最終推導出我們想要的句子。這種方式我們稱為自頂向下分析法。

從文法開始符號起，不斷用非終結符的候選式(即產生式)替換當前句型中的非終結符，最終得到相應的句子。
在每一步推導過程中，我們需要做兩個選擇:

因為一個句型中，可能存在多個非終結符，我們就不確定選擇那一個非終結符進行替換。
對於這種情況，我們就需要做強制規定，每次都選擇句型中第一個非終結符進行替換(或者每次都選擇句型中最後一個非終結符進行替換)。

自頂向下的語法分析採用最左推導方式，即總是選擇每個句型的最左非終結符進行替換。

最終的結果是要推導出一個特定句子(例如 id + (id + id) )。
我們將特定句子看成一個輸入字元串，而每一個非終結符對應一個處理方法，這個處理方法用來匹配輸入字元串的部分，演算法如下:

方法解析:

這種方式稱為遞歸下降分析( Recursive-Descent Parsing )：

當選擇的候選式不正確，就需要回溯( backtracking )，重新選擇候選式，進行下一次嘗試匹配。因為要不斷的回溯，導致分析效率比較低。

這種方式叫做預測分析( Predictive Parsing )：

要實現預測分析，我們必須保證從文法開始符號起，每一個推導過程中，當前句型最左非終結符 A 對於當前輸入字元 a ,只能得到唯一的 A 候選式。

根據上面的解決方法，我們首先想到，如果非終結符 A 的候選式只有一個以終結符 a 開頭候選式不就行了么。
進而我們可以得出，如果一個非終結符 A ，它的候選式都是以終結符開頭，並且這些終結符都各不相同，那麼本身就符合預測分析了。

這就是S_文法，滿足下面兩個條件:

例子:

這就是一個典型的S_文法，它的每一個非終結符遇到任一終結符得到候選式是確定的。如 S -> aA | bAB , 只有遇到終結符 a 和 b 的時候，才能返回 S 的候選式，遇到其他終結符時，直接報錯，匹配不成功。

雖然S_文法可以實現預測分析，但是從它的定義上看，S_文法不支持空產生式(ε產生式)，極大地限制了它的應用。

什麼是空產生式(ε產生式)？

例子

這里 A 有了空產生式，那麼 S 的產生式組 S -> aA | bAB ，就可以是 a | bB ,這樣 a , bb , bc 就變成這個文法 G 的新句子了。

根據預測分析的定義，非終結符對於任一終結符得到的產生式是確定的，要麼能獲取唯一的產生式，要麼不匹配直接報錯。

那麼空產生式何時被選擇呢？

由此可以引入非終結符 A 的後繼符號集的概念:
定義: 由文法 G 推導出來的所有句型，可以出現在非終結符 A 後邊的終結符 a 的集合，就是這個非終結符 A 的後繼符號集，記為 FOLLOW(A) 。

因此對於 A -> ε 空產生式，只要遇到非終結符 A 的後繼符號集中的字元，可以選擇這個空產生式。
那麼對於 A -> a 這樣的產生式，只要遇到終結符 a 就可以選擇了。

由此我們引入的產生式可選集概念:
定義: 在進行推導時，選用非終結符 A 一個產生式 A→β 對應的輸入符號的集合，記為 SELECT(A→β)

因為預測分析要求非終結符 A 對於輸入字元 a ,只能得到唯一的 A 候選式。
那麼對於一個文法 G 的所有產生式組，要求有相同左部的產生式，它們的可選集不相交。

在 S_文法基礎上，我們允許有空產生式，但是要做限制:

將上面例子中的文法改造:

但是q_文法的產生式不能是非終結符打頭，這就限制了其應用，因此引入LL(1)文法。

LL(1)文法允許產生式的右部首字元是非終結符，那麼怎麼得到這個產生式可選集。
我們知道對於產生式:

定義: 給定一個文法符號串 α ， α 的 串首終結符集 FIRST(α) 被定義為可以從 α 推導出的所有串首終結符構成的集合。

定義已經了解清楚了，那麼該如何求呢？
例如一個文法符號串 BCDe , 其中 B C D 都是非終結符， e 是終結符。

因此對於一個文法符號串 X1X2 … Xn ，求解 串首終結符集 FIRST(X1X2 … Xn) 演算法:

但是這里有一個關鍵點，如何求非終結符的串首終結符集？

因此對於一個非終結符 A , 求解 串首終結符集 FIRST(A) 演算法:

這里大家可能有個疑惑，怎麼能將 FIRST(Bβ) 添加到 FIRST(A) 中，如果問文法符號串 Bβ 中包含非終結符 A ，就產生了循環調用的情況，該怎麼辦?

對於 串首終結符集 ，我想大家疑惑的點就是，串首終結符集到底是針對 文法符號串 的，還是針對 非終結符 的，這個容易弄混。
其實我們應該知道， 非終結符 本身就屬於一個特殊的 文法符號串 。
而求解 文法符號串 的串首終結符集，其實就是要知道文法符號串中每個字元的串首終結符集:

上面章節我們知道了，對於非終結符 A 的 後繼符號集 :
就是由文法 G 推導出來的所有句型，可以出現在非終結符 A 後邊的終結符的集合，記為 FOLLOW(A) 。

仔細想一下，什麼樣的終結符可以出現在非終結符 A 後面，應該是在產生式中就位於 A 後面的終結符。例如 S -> Aa ，那麼終結符 a 肯定屬於 FOLLOW(A) 。

因此求非終結符 A 的 後繼符號集 演算法：

如果非終結符 A 是產生式結尾，那麼說明這個產生式左部非終結符後面能出現的終結符，也都可以出現在非終結符 A 後面。

我們可以求出 LL(1) 文法中每個產生式可選集:

根據產生式可選集，我們可以構建一個預測分析表，表中的每一行都是一個非終結符，表中的每一列都是一個終結符，包括結束符號 $ ，而表中的值就是產生式。
這樣進行語法推導的時候，非終結符遇到當前輸入字元，就可以從預測分析表中獲取對應的產生式了。

有了預測分析表，我們就可以進行預測分析了，具體流程:

可以這么理解：

我們知道要實現預測分析，要求相同左部的產生式，它們的可選集是不相交。
但是有的文法結構不符合這個要求，要進行改造。

如果相同左部的多個產生式有共同前綴，那麼它們的可選集必然相交。
例如:

那麼如何進行改造呢？
其實很簡單，進行如下轉換:

如此文法的相同左部的產生式，它們的可選集是不相交，符合現預測分析。

這種改造方法稱為 提取公因子演算法 。

當我們自頂向下的語法分析時，就需要採用最左推導方式。
而這個時候，如果產生式左部和產生式右部首字元一樣(即A→Aα)，那麼推導就可能陷入無限循環。
例如:

因此對於:

文法中不能包含這兩種形式，不然最左推導就沒辦法進行。

例如:

它能夠推導出如下:

你會驚奇的發現，它能推導出 b 和 (a)* (即由 0 個 a 或者無數個 a 生成的文法符號串)。其實就可以改造成:

因此消除 直接左遞歸 演算法的一般形式：

例如:

消除間接左遞歸的方法就是直接帶入消除，即

消除間接左遞歸演算法：

這個演算法看起來描述很多，其實理解起來很簡單：

思考 : 我們通過 Ai -> Ajβ 來判斷是不是間接左遞歸，那如果有產生式 Ai -> BAjβ 且 B -> ε ,那麼它是不是間接左遞歸呢？
間接地我們可以推出如果一個產生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那麼這個產生式是不是間接左遞歸。

❼ 編譯原理中 「句子」的概念 LR（1）分析法中「L」 「 R」的含義分別是

字母表上符合某種規則構成的串稱作句子。
L：自左至右掃描，R：最右推倒的逆過程。

❽ 編譯原理LL1語法分析的例子誰有

這個句子要分成兩大部分看：1.He said that....2.All things considered, he thought it was a bad idea.
2是1的賓語從句，但復雜的是在2這個賓語從句中包含了一個獨立主格結構（All things considered），其實2的核心主語和謂語應該是he和thought，此時all things是獨立於這個核心主語的，我們叫它獨立主格，此時considered不是謂語動詞，而是非謂語，在這里表示被動，所以all things considered不是一句完整的話（完整的應該是all things are considered）這里all things 是獨立主格considered是它的非謂語，一起構成一個獨立主格結構，和後面句子放在一起構成主句的賓語從句，是符合語法的。

❾ 編譯原理LR分析法中的SLR(1)分析表和LR分析過程、語法樹怎麼求

第二題和第三題拿去，剛做的：

由B->cAa|c就可知該文法不是LR(0)文法了

❿ 學了編譯原理這門課，要求編一個：詞法分析的程序，要求對詞法分析至少選擇三種不同類型的句子進行單詞識

給你一個toyl語言的
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<windows.h>
#define is_end_of_input(ch) ((ch)=='#')
#define is_letter(ch) ('A'<=(ch)&&(ch)<='Z'||'a'<=(ch)&&(ch)<='z')
#define is_digit(ch) ('0'<=(ch)&&(ch)<='9')
#define is_digit_or_letter(ch) (is_letter(ch)||is_digit(ch))
#define is_operator(ch) ((ch)=='+'||(ch)='-'||(ch)='*')
#define is_layout(ch) (!is_end_of_input(ch)&&(ch)<=' ')
#define Step 10 //字元串每次增長的長度.

typedef struct
{
char * Class;
char seman[];
int len;
int value;
}mytoken;

typedef struct node
{
char words[20];
int length;
int time;
struct node *next;
}mynode;
//全局變數
char ch;
char *fp;
mytoken token;
int TYPE=-1;
int num=1;
int j=0;
int Length=0;
void error()//報錯
{
printf("錯誤\n");
}

char * getstr() //從鍵盤獲取任意長度的輸入函數實現
{
char *temp, *str=(char *)malloc(10);
int c=0, len=0, times=1, number=0;
if(!str)
{
printf("內存不足!");
return (char *)NULL;
}
number+=times*Step;

do //遇到#則輸入結束。
{
c=getchar();
if(len==number)
{
times++;
number=times*Step;
temp=str;
str=(char *)realloc(str,number);
if(str==NULL)
{
printf("內存不足!");
str=temp;
break;
}
}
*(str+len)=c;
len++;
}while(c!='#');
str=(char *)realloc(str,len+1); //字元串的最終長度調整.
*(str+len)='\0';
return str;
}

void next_char(void)//獲取下一個字元
{
ch=*fp;
fp=fp+1;

}

void next_valchar(void)//獲取第一個有效的字元，過濾空格等。
{
next_char();
if(ch=='#')exit(0);//當文件只有空格和#號時
while(is_layout(ch))
{
next_char();
//if(ch=='#')exit(0);
}
}

void back()//指針回走
{
fp=fp-1;
}

void recongnize_name(char chr)//識別字元串
{
char name[10];
int i=0;
name[i++]=ch;
next_char();
while(is_digit_or_letter(ch))
{
name[i++]=ch;
next_char();

}

if((ch!=' ')&&(ch!='\t')&&(ch!='\n')&&(ch!='#')&&(ch!=':')&&(ch!='(')&&(ch!=')')&&(ch!=';'))//轉非法字元串處理
{

do
{
name[i++]=ch;
next_char();

}while((ch!=' ')&&(ch!='\t')&&(ch!='\n')&&(ch!='#'));
if((name[i-1]=='#')||(name[i-1]=='\n'))//去掉結束符#或回車
{
name[i-1]='\0';
}
back();//指針回走
name[i]='\0';
printf("非法字元串\t%s\n",name);

}
else{
name[i]='\0';
if (name== "begin")
{
token.Class="BEGIN";
}
else if (name== "end")
{
token.Class="END";
}
else if (name=="read")
{
token.Class=="READ";
}
else if (name=="write")
{
token.Class="WRITE";
}
else
{
token.Class="IDEN";
int n=0;
Length=0;
while(name[n]!='\0')
{

token.seman[n]=name[n];
n++;
}
Length=n;
token.seman[n]=name[n];

}
back();
}
}

void recongnize_number(char cha)//識別數字
{
int N=0;
int m;
char name[10];//存非法字元串
int i=0;
while((m=is_digit(ch)))
{
N=N*10+(ch-'0');

name[i++]=ch;
next_char();
}
if(ch==' '||ch=='\t'||ch=='\n'||ch=='#'||(ch==';'))
{
token.Class="NUMB";
token.value=N;
back();
}
else//轉非法字元串處理
{

do
{
name[i++]=ch;
next_char();

}while((ch!=' ')&&(ch!='\t')&&(ch!='\n')&&(ch!='#'));
if((name[i-1]=='#')||(name[i-1]=='\n'))//去掉結束符#或回車
{
name[i-1]='\0';
}
back();//指針回走
name[i]='\0';
printf("非法字元串\t%s\n",name);
TYPE=-1;

}

}

int next_token(void)//讀下一個單詞
{
next_valchar();
char name[10];//存首字母非法的字元串
int fg=0;
int i=0;
if('0'<=(ch)&&(ch)<='9')
{
TYPE=0;
}
else if('A'<=(ch)&&(ch)<='Z'||'a'<=(ch)&&(ch)<='z')
{
TYPE=1;
}
else
{
TYPE=2;
}

switch(TYPE)
{
case 0:
recongnize_number(ch);break;
case 1:
recongnize_name(ch);break;
case 2:
switch(ch)
{
case '+' :
token.Class="ADD";
token.seman[0]='+';
token.seman[1]='\0';
TYPE=2;
break;
case '*' :
token.Class="MULT";
token.seman[0]='*';
token.seman[1]='\0';
TYPE=2;
break;
case ':' :
next_char();
if(ch!='=')
{
error();
TYPE=-1;
break;
}
token.Class="ASS";
token.seman[0]=':';
token.seman[1]='=';
token.seman[2]='\0';
TYPE=2;
break;
case ';' :
token.Class="SEMI";
token.seman[0]=';';
token.seman[1]='\0';
TYPE=2;
break;
case '(' :
token.Class="OPEN";
token.seman[0]='(';
token.seman[1]='\0';
TYPE=2;
break;
case ')' :
token.Class="CLOSE";
token.seman[0]=')';
token.seman[1]='\0';
TYPE=2;
break;
default :
fg=1;
break;

}
}
if(fg==1)//非法字元串處理
{
name[i++]=ch;
while((ch!=' ')&&(ch!='\t')&&(ch!='\n')&&(ch!='#'))
{
next_char();
name[i++]=ch;
}
if((name[i-1]=='#')||(name[i-1]=='\n'))//去掉結束符#或回車

{
name[i-1]='\0';
}
back();//指針回走
name[i]='\0';
printf("非法字元串\t%s\n",name);
TYPE=-1;//置TYPE為-1
}

}

int compare(node *head,char words[],int Length)//單詞的比較
{
node *p;
p=head;
if(head==NULL)
{
return 0;
}
else
{

int fg=1;

do
{
int i,j,succ;
i=0;
succ=0;
while((i<=p->length-Length)&&(!succ))
{
j=0;
succ=1;
while((j<Length)&&succ)
{
if(words[j]==(p->words[i+j]))
{
j++;
}
else
{
succ=0;
}

}
i++;
}
if(succ&&(j>=p->length))
{
(p->time)++;
fg=0;

}
if(p->next!=NULL)
{
p=p->next;
}

}while((p->next!=NULL)&&fg);

if(fg==0)
{
return 1;
}
else
{
return 0;
}

}
}

node *insert(node *head) //將讀到的新單詞加入鏈表
{
node *p;
p=(mynode*)malloc(sizeof(mynode));/*分配空間*/
strcpy(p->words,token.seman);
int n=0;
p->length=0;
p->time=1;
while(p->words[n]!='\0')
{
p->length++;
n++;
}
p->next=NULL;
if(head==NULL)
{
head=p;
}
else
{
p->next=head->next;
head->next=p;
}

return head;
}

void display(node *head)//列印鏈表的內容
{
node *p;
p=head;
if(!p) printf("\n無標識符！");
else
{
printf("\n各標識符或保留字及其出現的次數為：\n");
printf("標識符\t出現次數\n");
while(p) { printf("%s\t%d\n",p->words,p->time);p=p->next;}

}
}

int main(int argc, char *argv[])
{
char *str1=NULL;
printf("請輸入程序代碼：\n");
str1=getstr();//獲取用戶程序段的輸入
fp=str1;
mynode *head=NULL;
do{
next_token();

switch(TYPE)
{
case 0:
printf("[%d]\t(%s,\t\"%d\")\n",num++,token.Class,token.value);
break;
case 1:
case 2:
printf("[%d]\t(%s,\t\"%s\")\n",num++,token.Class,token.seman);
int f;
f=0;
f=compare(head,token.seman,Length);
if((TYPE==1)&&(f==0))
{

head=insert(head);
}
break;
default:
break;
}

}while(*fp!='#');

display(head);
return 0;
}