編譯原理i2j

⑴ C語言編譯原理是什麼

編譯共分為四個階段：預處理階段、編譯階段、匯編階段、鏈接階段。

1、預處理階段：

主要工作是將頭文件插入到所寫的代碼中，生成擴展名為「.i」的文件替換原來的擴展名為「.c」的文件，但是原來的文件仍然保留，只是執行過程中的實際文件發生了改變。（這里所說的替換並不是指原來的文件被刪除）

2、匯編階段：

插入匯編語言程序，將代碼翻譯成匯編語言。編譯器首先要檢查代碼的規范性、是否有語法錯誤等，以確定代碼的實際要做的工作，在檢查無誤後，編譯器把代碼翻譯成匯編語言，同時將擴展名為「.i」的文件翻譯成擴展名為「.s」的文件。

3、編譯階段：

將匯編語言翻譯成機器語言指令，並將指令打包封存成可重定位目標程序的格式,將擴展名為「.s」的文件翻譯成擴展名為「.o」的二進制文件。

4、鏈接階段：

在示例代碼中，改代碼文件調用了標准庫中printf函數。而printf函數的實際存儲位置是一個單獨編譯的目標文件（編譯的結果也是擴展名為「.o」的文件），所以此時主函數調用的時候，需要將該文件（即printf函數所在的編譯文件）與hello world文件整合到一起，此時鏈接器就可以大顯神通了，將兩個文件合並後生成一個可執行目標文件。

⑵ 編譯原理詞法分析

編譯的詞法分析，一般是先畫一個狀態轉換圖，一般是有多少分支，就有多少if語句，分支裡面再分（可能有循環語句）。注意記住詞的類別和詞的字元串，請以以下代碼為例，理會一下詞法分析的大致過程。
while(s[i]!='#')
{
while(s[i]==' '||s[i]=='\t'||s[i]=='\n')
{
if(s[i]=='\n')
line++;
i++;
}
if(s[i]=='#')
break;
j=i;
if(s[i]>='a'&&s[i]<='z'||s[i]>='A'&&s[i]<='Z')
{
i++;
while(s[i]>='a'&&s[i]<='z'||s[i]>='A'&&s[i]<='Z'||s[i]>='0'&&s[i]<='9')
i++;
if((i-j)==2&&s[j]=='i'&&s[j+1]=='f')
{
strcpy(dancishuzu[dancigeshu].name,"if");
dancishuzu[dancigeshu].bianhao=4;
dancigeshu++;
}
else if((i-j)==3&&s[j]=='i'&&s[j+1]=='n'&&s[j+2]=='t')
{
strcpy(dancishuzu[dancigeshu].name,"int");
dancishuzu[dancigeshu].bianhao=2;
dancigeshu++;
}
else if((i-j)==3&&s[j]=='f'&&s[j+1]=='o'&&s[j+2]=='r')
{
strcpy(dancishuzu[dancigeshu].name,"for");
dancishuzu[dancigeshu].bianhao=6;
dancigeshu++;
}
else if((i-j)==4&&s[j]=='m'&&s[j+1]=='a'&&s[j+2]=='i'&&s[j+3]=='n')
{
strcpy(dancishuzu[dancigeshu].name,"main");
dancishuzu[dancigeshu].bianhao=1;
dancigeshu++;
}
else if ((i-j)==4&&s[j]=='c'&&s[j+1]=='h'&&s[j+2]=='a'&&s[j+3]=='r')
{
strcpy(dancishuzu[dancigeshu].name,"char");
dancishuzu[dancigeshu].bianhao=3;
dancigeshu++;
}
else if ((i-j)==4&&s[j]=='e'&&s[j+1]=='l'&&s[j+2]=='s'&&s[j+3]=='e')
{
strcpy(dancishuzu[dancigeshu].name,"else");
dancishuzu[dancigeshu].bianhao=5;
dancigeshu++;
}
else if ((i-j)==5&&s[j]=='w'&&s[j+1]=='h'&&s[j+2]=='i'&&s[j+3]=='l'&&s[j+4]=='e')
{
strcpy(dancishuzu[dancigeshu].name,"while");
dancishuzu[dancigeshu].bianhao=7;
dancigeshu++;
}
else{
dancishuzu[dancigeshu].bianhao=10;
count=0;
while(j<i)
{
dancishuzu[dancigeshu].name[count++]=s[j];
j++;
}
dancishuzu[dancigeshu].name[count]='\0';
dancigeshu++;
}
}
else if(s[i]>='0'&&s[i]<='9')
{
while(s[i]>='0'&&s[i]<='9')
i++;
dancishuzu[dancigeshu].bianhao=11;
count=0;
while(j<i)
{
dancishuzu[dancigeshu].name[count++]=s[j];
j++;
}
dancishuzu[dancigeshu].name[count]='\0';
dancigeshu++;
}

else if(s[i]=='=')
{
if(s[i+1]=='=')
{
dancishuzu[dancigeshu].bianhao=30;
strcpy(dancishuzu[dancigeshu].name,"==");
dancigeshu++;
i+=2;
}
else
{
dancishuzu[dancigeshu].bianhao=12;
strcpy(dancishuzu[dancigeshu].name,"=");
dancigeshu++;
i++;
}
}
else if(s[i]=='+')
{
dancishuzu[dancigeshu].bianhao=13;
strcpy(dancishuzu[dancigeshu].name,"+");
dancigeshu++;
i++;
}
else if(s[i]=='-')
{
dancishuzu[dancigeshu].bianhao=14;
strcpy(dancishuzu[dancigeshu].name,"-");
dancigeshu++;
i++;
}
else if(s[i]=='*')
{
dancishuzu[dancigeshu].bianhao=15;
strcpy(dancishuzu[dancigeshu].name,"*");
dancigeshu++;
i++;
}
else if(s[i]=='/')
{
dancishuzu[dancigeshu].bianhao=16;
strcpy(dancishuzu[dancigeshu].name,"/");
dancigeshu++;
i++;
}
else if(s[i]=='(')
{
i++;
dancishuzu[dancigeshu].bianhao=17;
strcpy(dancishuzu[dancigeshu].name,"(");
dancigeshu++;
}
else if(s[i]==')')
{
i++;
dancishuzu[dancigeshu].bianhao=18;
strcpy(dancishuzu[dancigeshu].name,")");
dancigeshu++;
}
else if(s[i]=='[')
{
i++;
dancishuzu[dancigeshu].bianhao=19;
strcpy(dancishuzu[dancigeshu].name,"[");
dancigeshu++;
}
else if(s[i]==']')
{
i++;
dancishuzu[dancigeshu].bianhao=20;
strcpy(dancishuzu[dancigeshu].name,"]");
dancigeshu++;
}
else if(s[i]=='{')
{
i++;
dancishuzu[dancigeshu].bianhao=21;
strcpy(dancishuzu[dancigeshu].name,"{");
dancigeshu++;
}
else if(s[i]=='}')
{
i++;
dancishuzu[dancigeshu].bianhao=22;
strcpy(dancishuzu[dancigeshu].name,"}");
dancigeshu++;
}
else if(s[i]==',')
{
i++;
dancishuzu[dancigeshu].bianhao=23;
strcpy(dancishuzu[dancigeshu].name,",");
dancigeshu++;
}
else if(s[i]==':')
{
i++;
dancishuzu[dancigeshu].bianhao=24;
strcpy(dancishuzu[dancigeshu].name,":");
dancigeshu++;
}
else if(s[i]==';')
{
i++;
dancishuzu[dancigeshu].bianhao=25;
strcpy(dancishuzu[dancigeshu].name,";");
dancigeshu++;
}
else if(s[i]=='>')
{
if(s[i+1]=='=')
{
dancishuzu[dancigeshu].bianhao=28;
strcpy(dancishuzu[dancigeshu].name,">=");
dancigeshu++;
i+=2;
}
else
{
i++;
dancishuzu[dancigeshu].bianhao=26;
strcpy(dancishuzu[dancigeshu].name,">");
dancigeshu++;
}
}
else if(s[i]=='<')
{
if(s[i+1]=='=')
{
dancishuzu[dancigeshu].bianhao=29;
strcpy(dancishuzu[dancigeshu].name,"<=");
dancigeshu++;
i+=2;
}
else
{
i++;
dancishuzu[dancigeshu].bianhao=27;
strcpy(dancishuzu[dancigeshu].name,"<");
dancigeshu++;
}
}
else if(s[i]=='!'&&s[i+1]=='=')
{
dancishuzu[dancigeshu].bianhao=31;
strcpy(dancishuzu[dancigeshu].name,"!=");
dancigeshu++;
i+=2;
}
else
{
printf("\nline:%derror!",line);
i++;
return;
}
}

⑶ 求 編譯原理 語法分析程序

可以參考我的空間，我在三年前寫過類似代碼。
http://hi..com/逄韶華/ihome/myblog

⑷ 編譯原理詞法分析器

#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<process.h> /*頭文件*/

void init();
char *DchangeB(char *buf);
int search(char *buf,int type,int command);
void intdeal(char *buffer);
void chardeal(char *buffer);
void errordeal(char error,int lineno);
void scanner();

void init()
{ char *key[]={"","auto","break","case","char","const","continue","default","do","double",
"else","enum","extern","float","for","goto","if","int","long","register",
"return","short","signed","sizeof","static","struct","switch","typedef",
"union","unsigned","void","volatile","while"}; /*C語言所有關鍵字/
char *limit[]={" ","(",")","[","]","->",".","!","++","--","&","~",
"*","/","%","+","-","<<",">>","<","<=",">",">=","==","!=","&&","||",
"=","+=","-=","*=","/=",",",";","{","}","#","_","'"};/*運算、限界符*/
fstream outfile;
int i,j;
char *c;
outfile.open("key.txt",ios::out);
for(i=0;i<32;i++)
outfile<<key[i]<<endl;
outfile.close();
outfile.open("Limit.txt",ios::out);
for(j=0;j<38;j++)
outfile<<limit[j]<<endl;
c="";
outfile<<c;
outfile.close();
outfile.open("bsf.txt",ios::out);
outfile.close();
outfile.open("cs.txt",ios::out);
outfile.close();
outfile.open("output.txt",ios::out);
outfile.close();
}

char *DchangeB(char *buf)
{

int temp[20];
char *binary;
int value=0,i=0,j;
for(i=0;buf[i]!='\0';i++)
value=value*10+(buf[i]-48); /*將字元轉化為十進制數*/
if(value==0)
{
binary=new char[2];
binary[0]='0';
binary[1]='\0';
return(binary);
}
i=0;
while(value!=0)
{
temp[i++]=value%2;
value/=2;
}
temp[i]='\0';
binary=new char[i+1];
for(j=0;j<=i-1;j++)
binary[j]=(char)(temp[i-j-1]+48);
binary[i]='\0';
return(binary); /*十進制轉化為二進制*/

}

int search(char *buf,int type,int command)
{ int number=0;
fstream outfile;
char ch;
char temp[30];
int i=0;
switch(type)
{
case 1: outfile.open("key.txt",ios::in);break;
case 2: outfile.open("bsf.txt",ios::in);break;
case 3: outfile.open("cs.txt",ios::in);break;
case 4: outfile.open("limit.txt",ios::in);break;
}
outfile.get(ch);
while(ch!=EOF){
while(ch!='\n')
{
temp[i++]=ch;
outfile.get(ch);
}
temp[i]='\0';
i=0;
number++;
if(strcmp(temp,buf)==0)
{
outfile.close();
return number; /*若找到，返回在相應表中的序號*/
}
else
outfile.get(ch);
} //結束外層while循環
if(command==1)
{
outfile.close( );
return 0; /*找不到，當只需查表，返回0，否則還需造表*/

}
switch(type)
{
case 1: outfile.open("key.txt",ios::in);break;
case 2: outfile.open("bsf.txt",ios::in);break;
case 3: outfile.open("cs.txt",ios::in);break;
case 4: outfile.open("limit.txt",ios::in);break;
}
outfile<<buf;
outfile.close();
return number+1;
}

void intdeal(char *buffer){

fstream outfile;
int result;
result=search(buffer,1,1); /*先查關鍵字表*/
outfile.open("output.txt",ios::app);
if(result!=0)
outfile<<buffer<<result<<endl; /*若找到，寫入輸出文件*/
else
{
result=search(buffer,2,2); /*若找不到，則非關鍵字，查標識符表，還找不到則造入標識符表*/
outfile<<buffer<<result<<endl;
} /*寫入輸出文件*/
outfile.close();
}

void chardeal(char *buffer)
{ fstream outfile;
int result;
result=search(buffer,1,1); /*先查關鍵字表*/
outfile.open("output.txt",ios::app);
if(result!=0)
outfile<<buffer<<result<<endl; /*若找到，寫入輸出文件*/
else
{
result=search(buffer,2,2); /*若找不到，則非關鍵字，查標識符表，還找不到則造入標識符表*/
outfile<<buffer<<result<<endl;
} /*寫入輸出文件*/
outfile.close();
}

void errordeal(char error,int lineno)
{ cout<<"\nerror: "<<error<<" ,line"<<lineno;
}

void scanner()
{ fstream infile,outfile;
char filename[20];
char ch;
int err=0;
int i=0,line=1;
int count,result,errorno=0;
char array[30];
char *word;
printf("\n please input the file scanner name:");
scanf("%s",filename);
err=1;
infile.open(filename,ios::nocreate|ios::in);
while(! infile)
{
cout<<"cannot open file"<<endl;
printf("please input the file name again:\n");
scanf("%s",filename);
infile.open(filename,ios::nocreate|ios::in);
err++;
if(err==3)
{cout<<"SORROY YOU CAN'T VUEW THE PRGARME\n";
cout<<"TANKE YOU VIEW"<<endl;
exit(0);}
}
infile.get(ch);
while(ch!=EOF)
{ /*按字元依次掃描源程序，直至結束*/
i=0;
if(((ch>='A')&&(ch<='Z'))||((ch>='a')&&(ch<='z'))||(ch=='_'))
{ /*以字母開頭*/
while(((ch>='A')&&(ch<='Z'))||((ch>='a')&&(ch<='z'))||(ch=='_')||((ch>='0')&&(ch<='9')))
{
array[i++]=ch;
infile.get(ch);
}
word=new char[i+1];
memcpy(word,array,i);
word[i]='\0';
intdeal(word);
if(ch!=EOF)
infile.seekg(-1,ios::cur);
}
else if(ch>='0'&&ch<='9')
{ /*以數字開頭*/
while(ch>='0'&&ch<='9')
{
array[i++]=ch;
infile.get(ch);
}
word=new char[i+1];
memcpy(word,array,i);
word[i]='\0';
intdeal(word);
if(ch!=EOF)
infile.seekg(-1,ios::cur);
}
else if((ch==' ')||(ch=='\t'))
; /*消除空格符和水平製表符*/
else if(ch=='\n')
line++; /*消除回車並記錄行數*/
else if(ch=='/')
{ /*消除注釋*/
infile.get(ch);
if(ch=='=')
{ /*判斷是否為『/=』符號*/
outfile.open("output.txt",ios::noreplace|ios::app);
outfile<<"/=\t\t\t4\t\t\t32\n";
outfile.close();
}
else if(ch!='*')
{ /*若為除號，寫入輸出文件*/
outfile.open("output.txt",ios::noreplace|ios::app);
outfile<<"/\t\t\t4\t\t\t13\n";
outfile.close();
outfile.seekg(-1,ios::cur);
}
else if(ch=='*')
{ /*若為注釋的開始，消除包含在裡面的所有字元*/
count=0;
infile.get(ch);
while(count!=2)
{ /*當掃描到『*』且緊接著下一個字元為『/』才是注釋的結束*/
count=0;
while(ch!='*')
infile.get(ch);
count++;
infile.get(ch);
if(ch=='/')
count++;
else
infile.get(ch);
}
}
}
else if(ch=='"')
{ /*消除包含在雙引號中的字元串常量*/
outfile.open("output.txt",ios::noreplace|ios::app);
outfile<<ch<<"\t\t\t4\t\t\t37\n";
outfile.close();
while(ch!='"')
infile.get(ch);
infile<<ch<<"\t\t\t4\t\t\t37\n";
infile.close();
}
else
{ /*首字元為其它字元,即運算限界符或非法字元*/
array[0]=ch;
infile.get(ch); /*再讀入下一個字元，判斷是否為雙字元運算、限界符*/
if(ch!=EOF)
{ /*若該字元非文件結束符*/
array[1]=ch;
word=new char[3];
memcpy(word,array,2);
word[2]='\0';
result=search(word,4,1); /*先檢索是否為雙字元運算、限界符*/
if(result==0)
{ /*若不是*/
word=new char[2];
memcpy(word,array,1);
word[1]='\0';
result=search(word,4,1); /*檢索是否為單字元運算、限界符*/
if(result==0)
{ /*若還不是，則為非法字元*/
errordeal(array[0],line);
errorno++;
infile.seekg(-1,ios::cur);
}
else
{ /*若為單字元運算、限界符，寫入輸出文件並將掃描文件指針回退一個字元*/
outfile.open("output.txt",ios::noreplace|ios::app);
outfile<<word<<"\t\t\t4\t\t\t"<<result<<"\t"<<endl;
outfile.close();
infile.seekg(-1,ios::cur);
}
}
else
{ /*若為雙字元運算、限界符，寫入輸出文件*/
outfile.open("output.txt",ios::noreplace|ios::app);
outfile<<word<<"\t\t\t4\t\t\t"<<result<<endl;;
outfile.close( );
}
}
else
{ /*若讀入的下一個字元為文件結束符*/
word=new char[2];
memcpy(word,array,1);
word[1]='\0';
result=search(word,4,1); /*只考慮是否為單字元運算、限界符*/
if(result==0) /*若不是，轉出錯處理*/
errordeal(array[0],line);
else
{ /*若是，寫輸出文件*/
outfile.open("output.txt",ios::noreplace|ios::app);
outfile<<word<<"\t\t\t4\t\t\t"<<result<<"\t"<<endl;
outfile.close();
}
}
}
infile.get(ch);
}
infile.close();
cout<<"\nThere are "<<errorno<<" error(s).\n"; /*報告錯誤字元個數*/
}
void main()
{ char yn;

do{
init(); /*初始化*/
scanner();/*掃描源程序*/

printf("Are You continue(y/n)\n"); //判斷是否繼續？
yn=getch();
}while(yn=='y'||yn=='Y');
}

⑸ 編譯原理中，LR(0)文法的項目集規范族的I0,I1,I2,I3…………是怎麼求的～

先舉個例子：

}

將其命名為I1。

其他可類似推出。

⑹ 編譯原理中的一概念：什麼是左線性正規文法

正規文法是左線性文法和右線性文法的統稱.它們都是Chomsky分類下的3型文法.由正規文法產生的語言稱為正規集.下面我們將會看到,這里之所以用「正規」二字為一種語言命名,是因為這種語言的結構可以用所謂正規式來描述.
1．右線性文法
設G[S]=(VN,VT,P,S)為CFG,若P中的產生或均有如下的形式：
A→aB或A→a（A∈VN,a∈VT）
則稱G為右線性文法.例如,文法
G1[S]=({S,A,B},{a,b},P1,S)
其中
P1={S→aA,A→aA,A→bB,A→b,B→bB,B→b}
為一右線性文法,G1所產生的正規集為
L(G1)={aibj |i,j≥1}
2．左線性文法
若一個文法G[S]=(VN,VT,P,S)中的產生式均有如下的形式：
A→Ba或A→a（A,B∈VN,a∈VT）
則稱G為左線性文法.例如,文法
G2[S]=({S,A},{a,b},P2,S)
其中
P2={S→Sb,S→Ab,A→Aa,A→a}
為一左線性文法,且有
L(G2)=L(G1)={aibj |i,j≥1}
請注意,雖然文法
G3[S]=({S,A,B},{a,b},P3,S)
其中
P3={S→aA,A→aA,A→Bb,A→b,B→Bb,B→b}
也同樣產生語言{aibj |i,j≥1},但由於G3中同時含有左線性產生式和右線性產生式,故G3不是正規文法.
另外
P4={S-->aA,A-->ab},
也不是正規文法

⑺ 編譯原理的終結符和非終結符如何理解

一、非終結符：

1、非終結符可以再分成更細的東西。

2、不是終結符的都是非終結符。非終結符可理解為一個可拆分元素，而終結符是不可拆分的最小元素。終結符號就是語言中用到的基本元素，名詞、動詞、形容詞、助詞等等基本語言單位。

二、終結符：

1、終結符直接就代表一個意思，比如關鍵字if就不能再分成i和f了。

2、通俗的說就是不能單獨出現在推導式左邊的符號，也就是說終結符不能再進行推導。非終結符則是"語法"中用到的元素，除非談論"語法"，一般交談語言中並不會用到非終結符。比如：主語、短語、片語、句子。

(7)編譯原理i2j擴展閱讀：

終結符和非終結符在計算機科學和語言學的領域是用來指定推導規則的元素。在某個形式語法之中，終結符和非終結符是兩個不交的集合。

從形式語言中定義看，終結符(T)就是不可再分的字元或串。而非終結符(N)是一個遞歸形式的定義:由終結符和至少一個非終結符號組成的串。

如果編譯過程中發現源程序有錯誤，編譯程序應報告錯誤的性質和錯誤的發生的地點，並且將錯誤所造成的影響限制在盡可能小的范圍內，使得源程序的其餘部分能繼續被編譯下去，有些編譯程序還能自動糾正錯誤，這些工作由錯誤處理程序完成。

需要注意的是，一般上編譯器只做語法檢查和最簡單的語義檢查，而不檢查程序的邏輯。

網路-終結符

網路-編譯

⑻ 編譯原理語法分析編程

#include <iostream>
#include <string>
#include <fstream>
#include <queue>
#include <string.h>
#include <stdio.h>

using namespace std;

enum Datatype { RESERVE_WORD=1,IDENTIFIER=2,DIGIT=3,OPERATOR=4,SEPRATOR=5 };

struct OutputStruct
{
public:
Datatype type;
string value;
};

string operate[]={"sin","cos","pow"};
string KeyWord[]={"main","int","if","char","cout"};
const int MAX_SIZE=255;
char BUFF[MAX_SIZE]; //buffer to contain a char line.
ifstream inFile;
ofstream outFileStream;
queue<OutputStruct> tt;

bool IsKeyWord(string& cs)
{
for(int i=0;i<5;++i)
if(cs==KeyWord[i])
return true; //Exist
return false;
}

void ReadLineAndAnalyze()
{
int strSize=0;
int i;
int errFlag=0;
char ch;
string outStructStr,str;
struct OutputStruct outStruct;
{
i=0;
inFile.getline(BUFF,MAX_SIZE,'\n');
strSize=inFile.gcount();
cout<<BUFF;
do{
str="";
do{
ch=BUFF[i];
i++;
}while(ch==' '||ch==' '||ch=='\n');
switch(ch)
{

case '+':
case '-':
case '*':
case '/':
outStruct.type=OPERATOR;
outStruct.value=ch;
break;
case '=':
case '>':
case '<':
outStructStr=ch;
if(BUFF[i]=='=')
{
outStruct.type=OPERATOR;
outStructStr+=BUFF[i];
outStruct.value=outStructStr;
i++;
}
else
{
outStruct.type=OPERATOR;
outStruct.value=ch;
};
break;

case ',':
case ';':
case '{':
case '}':
case '(':
case ')':
case '[':
case ']':
case '\"':
outStruct.type=SEPRATOR;
outStruct.value=ch;
break;

case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
outStructStr+=ch;
while(BUFF[i]>='0'&&BUFF[i]<='9'||BUFF[i]=='.')
{
outStructStr+=BUFF[i];
i++;
}//while
outStruct.type=DIGIT;
outStruct.value=outStructStr;
break;

default:
if(ch>='a'&&ch<='z'||ch>='A'&&ch<='Z')
{
outStructStr+=ch;
while(BUFF[i]>='a'&&BUFF[i]<='z'||BUFF[i]>='A'&&BUFF[i]<='Z')
{
outStructStr+=BUFF[i];
i++;
}//while
if(IsKeyWord(outStructStr))
{
outStruct.type=RESERVE_WORD;
outStruct.value=outStructStr;
}
else
{
outStruct.type=IDENTIFIER;
outStruct.value=outStructStr;
}
break;
}
else
errFlag=1;
}//switch;
if(!errFlag)
tt.push(outStruct);
errFlag=0;
outStructStr="";
}while(i<strSize-1);

}//while(i<MAX_SIZE&&!inFile.eof());//do_while
return;
}

float F();
float T();
float E();
float S();

float F()
{
float ret;
if((tt.front().type==IDENTIFIER)||(tt.front().type==DIGIT))
{
ret=atof(tt.front().value.c_str());
if(tt.empty())
{
cout<<"END"<<endl;exit(0);
}
tt.pop();
return ret;
}
if(tt.front().value=="(")
{
if(tt.empty())
{
cout<<"END"<<endl;exit(0);
}
tt.pop();
ret=E();
if(tt.front().value==")")
{
if(tt.empty())
{
cout<<"END"<<endl;exit(0);
}
tt.pop();
return ret;
}
else
{
cout<<"\b ----ERROR! "<<tt.front().value<<" 缺少右括弧"<<endl;
cout<<"Press \"enter\" to modify the data file!";
getchar();
system("notepad data.txt");
exit(0);
}
}
else
{
cout<<"\b ----ERROR! "<<tt.front().value<<" 缺少因子"<<endl;
cout<<"Press \"enter\" to modify the data file!";
getchar();
system("notepad data.txt");
exit(0);
}
}
float T()
{
float i,j;
i=F();
if(tt.front().value=="*")
{
if(tt.empty())
{
cout<<"END"<<endl;exit(0);
}
tt.pop();
j=T();
return i*j;
}
else if(tt.front().value=="/")
{
if(tt.empty())
{
cout<<"END"<<endl;exit(0);
}
tt.pop();
j=T();
if(abs(j)<0.0000001)
{
cout<<"\b ----ERROR! 除數為零!"<<endl;
cout<<"Press \"enter\" to modify the data file!";
getchar();
system("notepad data.txt");
exit(0);
}
return i/j;
}
return i;
}

float E()
{
float i,j;
i=T();
if(tt.front().value=="+")
{
if(tt.empty())
{
cout<<"END"<<endl;exit(0);
}
tt.pop();
j=E();
i=i+j;
}
else if(tt.front().value=="-")
{
if(tt.empty())
{
cout<<"END"<<endl;exit(0);
}
tt.pop();
j=E();
i=i-j;
}
if(tt.front().value==";"||tt.front().type==OPERATOR||tt.front().value==")")
return i;
else
{
cout<<"\b ----ERROR! "<<tt.front().value<<" 缺少運算符"<<endl;
cout<<"Press \"enter\" to modify the data file!";
getchar();
system("notepad data.txt");
exit (0);
}
}

float S()
{
float i;
i=E();
if(tt.front().value==";")
{
if(tt.empty())
{
cout<<"END"<<endl;exit(0);
}
tt.pop();
return i;
}
cout<<"\b ----ERROR! "<<tt.front().value<<" 缺少左括弧"<<endl;
cout<<"Press \"enter\" to modify the data file!";
getchar();
system("notepad data.txt");
exit(0);
}

void GrammaAnalize()
{
float i;
if(tt.empty())
{
cout<<"END"<<endl;exit(0);
}
i=S();
cout<<"\b="<<i<<endl;
}

int main()
{
inFile.open("data.txt");
if(!inFile)
{
cout<<"打開源文件失敗!";
return 1;
}
while(!inFile.eof())
{
ReadLineAndAnalyze();
GrammaAnalize();
}
inFile.close();
return 0;
}

⑼ 計算機編譯原理 圖 裡面的 圓圈 表示什麼意思

先打個比方：
用程序接受從鍵盤輸入的單詞，並對照詞典判斷是不是拼寫正確，步驟是：
一個一個地接收字母，每接受一個字母，識別狀態往前推進一步。
假如只考慮識別3個單詞：it, if, is

狀態1：剛開始，一個字母還沒收到。
狀態2：接收到一個字母 i
狀態3：又接收到一個字母 s
1，2，3用圓圈圈起來，1和2之間畫個箭頭連起來，箭頭上標上字母 i。2和3也畫個箭頭，標上字母 s 。
這樣的一張圖，表示的是單詞 is 的識別過程。

這個過程，就是你照片中第一個圖，1，2，3串成一直線的圖。
圖中V1對應 i , 圖中 V2 對應 s

你書上的圖，描述的是「自動機」。自動機反映的是讀取到一連串字母後的狀態變化過程。
它包含若干個狀態，即畫有圓圈的數字。
當讀入一個字母時，自動機從一個狀態運行到另一個狀態，對應圖上的一個帶箭頭線條。線上標注的符號，代表讀到的字元。

⑽ 編譯原理問題，高手進。

回答下列問題：(30分)
(6分)對於下面程序段
program test (input, output)
var i, j: integer;
procere CAL(x, y: integer);
begin
y:=y*y; x:=x-y; y:=y-x
end;
begin
i:=2; j:=3; CAL(i, j)
writeln(j)
end.
若參數傳遞的方法分別為(1)傳值、(2)傳地址，(3)傳名，請寫出程序執行的輸出結果。
答： (1) 3 (2) 16 (3) 16 (每個值2分)

(6分)計算文法G(M)的每個非終結符的FIRST和FOLLOW集合，並判斷該文法是否是LL(1)的，請說明理由。
G(M)：
M → TB
T → Ba |
B → Db | eT |
D → d |

解答：
計算文法的FIRST和FOLLOW集合：(4分)
FIRST(M) = { a，b，e，d， } FIRST(T) = { a，b，e，d， }
FIRST(B) = {b，e，d， } FIRST(D) = {d，}
FOLLOW (M) = {#} FOLLOW (T) = { a，b，e，d，#}
FOLLOW (B) = {a，# } FOLLOW (D) = { b}

檢查文法的所有產生式，我們可以得到：
1. 該文法不含左遞歸，
2. 該文法中每一個非終結符M，T，B，D的各個產生式的候選首符集兩兩不相交。
3. 該文法的非終結符T、B和D，它們都有候選式，而且
FIRST(T)∩FOLLOW(T)={ a，b，e，d }≠
所以該文法不是LL(1)文法。(2分)

(4分)考慮下面的屬性文法
產 生 式 語 義 規 則
S→ABC

A→a
B→b
C→c B.u := S.u
A.u := B.v + C.v
S.v := A.v
A.v :=3*A.u
B.v := B.u
C.v := 1
畫出字元串abc的語法樹;
對於該語法樹，假設S.u的初始值為5，屬性計算完成後，S.v的值為多少。
答：(1) (2分)

(2) S.v的值為18 (2分)

(4分)運行時的DISPLAY表的內容是什麼？它的作用是什麼？
答：DISPLAY表是嵌套層次顯示表。每當進入一個過程後，在建立它的活動記錄區的同時建立一張嵌套層次顯示表diaplay.假定現在進入的過程層次為i，則它的diaplay表含有i+1個單元，自頂向下每個單元依次存放著現行層、直接外層、…、直至最外層(主程序，0層)等每層過程的最新活動記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變數。

(5分)對下列四元式序列生成目標代碼：
A:=B*C
D:=E+A
G:=B+C
H:=G*D
其中，H在基本塊出口之後是活躍變數， R0和R1是可用寄存器。
答: 目標代碼序列
LD R0 B
MUL R0 C
LD R1 E
ADD R1 R0
LD R0 B
ADD R0 C
MUL R0 R1
ST R0 H

(5分)寫出表達式a+b*(c-d)對應的逆波蘭式、三元式序列和抽象語法樹。
答：
逆波蘭式：(abcd-*+) (1分)
三元式序列: (2分)
OP ARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
抽象語法樹：(2分)

(8分)構造一個DFA，它接受={a，b}上所有包含ab的字元串。
答：
(2分)構造相應的正規式：(a|b)*ab(a|b)*

(3分)
a a

a b
b b

(3分)確定化：
I
{0,1,2} {1,2,3} {1,2}
{1,2,3} {1,2,3} {1,2,4,5,6}
{1,2} {1,2,3} {1,2}
{1,2,4,5,6} {1,2,3,5,6} {1,2,5,6}
{1,2,3,5,6} {1,2,3,5,6} {1,2,4,5,6}
{1,2,5,6} {1,2,3,5,6} {1,2,5,6}
b b
b a
a a a a

a b b
b

最小化：
{0，1，2} {3，4，5}
{0， 2}，1， {3，4，5}

(6分)寫一個文法使其語言為L(G)={anbncm| m,n≥1，n為奇數，m為偶數}。
答：
文法G(S):

(8分)對於文法G(S):

1. 寫出句型b(Ma)b的最右推導並畫出語法樹。
2. 寫出上述句型的短語，直接短語和句柄。
答：
1. (4分)

2. (4分)
短語: Ma)， (Ma)， b(Ma)b
直接短語: Ma)
句柄: Ma)

(12分)對文法G(S)：
S → a | ^ | (T)
T → T，S | S
(1) 構造各非終結符的FIRSTVT和LASTVT集合;
(2) 構造算符優先表;
(3) 是算符優先文法嗎?
(4) 構造優先函數。
答：
(1) (4分)

(2) (4分)
a ^ ( ) ,
a > >
^ > >
( < < < = <
) > >
, < < < > >

(3) 是算符優先文法，因為任何兩個終結符之間至多隻有一種優先關系。 (1分)

(4) 優先函數(3分)
a ^ ( ) ,
F 4 4 2 4 4
G 5 5 5 2 3

(8分)設某語言的do-while語句的語法形式為
S do S(1) While E
其語義解釋為：

針對自下而上的語法分析器，按如下要求構造該語句的翻譯模式，將該語句翻譯成四元式：
(1) 寫出適合語法制導翻譯的產生式；
(2) 寫出每個產生式對應的語義動作。
答：(1). 適合語法制導翻譯的文法(4分)
G(S):
R do
UR S(1) While
SU E
(2). (4分)
R do
{ R.QUAD:=NXQ }

UR S(1) While
{ U.QUAD:=R.QUAD;
BACKPATCH(S.CHAIN, NXQ) }

SU E
{ BACKPATCH(E.TC, U.QUAD);
S.CHAIN:=E.FC }

答案二：
(1) S do M1 S(1) While M2 E
M ε (4分)
(2) M ε { M.QUAD := NXQ } (4分)
S do M1 S(1) While M2 E
{
BACKPATCH(S(1).CHAIN, M2.QUAD);
BACKPATCH(E.TC, M1.QUAD);
S.CHAIN:=E. FC
}

(10分)將語句
while C>0 do if A B=0 then C:=C+D else C:=C*D
翻譯成四元式。
答：
100 (j>， C， 0， 102)
101 (j， -， -， 112)
102 (jnz， A， -， 106)
103 (j， -， -， 104)
104 (j=， B， 0， 106)
105 (j， -， -， 109)
106 (+， C， D， T1)
107 (:=， T1， -， C)
108 (j， -， -， 100)
109 (*， C， D， T2)
110 (:=， T2， -， C)
111 (j， -， -， 100)
112

(10分)設有基本塊如下：
T1:=3
T2:=A*B
T3:=9+T1
M:=A*B
T4:=C-D
L:=T3*T4
T2:=C+D
N:=T2
畫出DAG圖；
設L，M，N 是出基本塊後的活躍變數，請給出優化後的四元式序列。
答：

1. (6分)
L

*
T2,M T4 T2,N

* - +

T1 T3
3 A B 12 C D

2. (4分)
M:=A*B
S1:=C-D
L:=12*S1
N:=C+D

(8分)文法G(S)及其LR分析表如下，請給出串baba#的分析過程。
(1) S → DbB (2) D → d (3) D → ε
(4) B → a (5) B → Bba (6) B → ε
LR分析表
ACTION GOTO
b D a # S B D
0 r3 s3 1 2
1 acc
2 s4
3 r2
4 r6 S5 r6 6
5 r4 r4
6 s7 r1
7 S8
8 r5 r5
解答：
步驟 狀態 符號 輸入串
0 0 # baba#
1 02 #D baba#
2 024 #Db aba#
3 0245 #Dba ba#
4 0246 #DbB ba#
5 02467 #DbBb a#
6 024678 #DbBba #
7 0246 #DbB #
8 01 #S # acc
哈哈，估計認識！！