work.h?1?#include<iostream>
?2?#include<stdlib.h>
?3?#include<stdio.h>
?4?#include<string.h>
?5?
?6?/*************STRUCT*************/
?7?#ifndef?keyword
?8?#define?keyword
?9?/*
10??*?關鍵字結構，用于work2.cpp
11??*/
12?struct?KEYWORD_NODE{
13?????char?val[100];
14?};
15?
16?/*
17??*?非終結符結構，用于work3.cpp
18??*/
19?struct?N_NODE{//非終結符
20?????char?val;//值
21?????int?cnt;//產生式數目
22?????char?ARR[30][30];
23?};
24?#endif
25?
26?/************FUNCTION************/
27?void?init();
28?bool?isLetter(char?ch);
29?void?dealSourceCode();
30?void?morphologyAnalysis();
31?void?dealOperatorPrecedenceGrammar();
32?using?namespace?std;

?

init.cpp?1?/***************************************************************\
?2??*Author:Hu?Wenbiao
?3??*Created?Time:?Mon?15?Nov?2010?09:12:44?PM?CST
?4??*File?Name:?init.cpp
?5??*Description:執行各文件所需的初始化操作
?6?\***************************************************************/
?7?//*========================*Head?File*========================*\\
?8?
?9?#include"work.h"
10?/*----------------------*Global?Variable*----------------------*/
11?//work2.cpp
12?extern?KEYWORD_NODE?KEYWORD[30];
13?//work3.cpp
14?extern?bool?F[30][30],L[30][30];
15?extern?N_NODE?N_ARRAY[30];
16?extern?char?T_ARRAY[30];
17?extern?char?PRECEDENCETABLE[30][30];
18?//*=======================*Main?Program*=======================*//
19?
20?/*
21??*?設置關鍵字，用于work2.cpp的初始化
22??*/
23?void?setKeyword(int?pos,string?str){
24?????int?p=0;
25?????while(str[p]){
26?????????KEYWORD[pos].val[p]=str[p];
27?????????p++;
28?????}
29?}
30?
31?/*
32??*?各文件的初始化
33??*/
34?void?init(){
35?
36?????/*
37??????*?work2.cpp
38??????*/
39?????memset(KEYWORD,0,sizeof(KEYWORD));
40?????setKeyword(1,"const");
41?????setKeyword(2,"var");
42?????setKeyword(3,"procedure");
43?????setKeyword(4,"call");
44?????setKeyword(5,"begin");
45?????setKeyword(6,"end");
46?????setKeyword(7,"if");
47?????setKeyword(8,"then");
48?????setKeyword(9,"while");
49?????setKeyword(10,"do");
50?????setKeyword(11,"odd");
51?????setKeyword(12,"+");
52?????setKeyword(13,"-");
53?????setKeyword(14,"*");
54?????setKeyword(15,"/");
55?????setKeyword(16,">");
56?????setKeyword(17,">=");
57?????setKeyword(18,"<");
58?????setKeyword(19,"<=");
59?????setKeyword(20,"=");
60?????setKeyword(21,"<>");
61?????setKeyword(22,".");
62?????setKeyword(23,"(");
63?????setKeyword(24,")");
64?????setKeyword(25,",");
65?????setKeyword(26,";");
66?????setKeyword(27,":=");
67?
68?????/*
69??????*?work3.cpp
70??????*/
71?????memset(N_ARRAY,0,sizeof(N_ARRAY));
72?????memset(T_ARRAY,0,sizeof(T_ARRAY));
73?????memset(F,0,sizeof(F));
74?????memset(L,0,sizeof(F));
75?????memset(PRECEDENCETABLE,0,sizeof(PRECEDENCETABLE));
76?} work1.cpp??1?/***************************************************************\?*?Author:?Hu?Wenbiao
??2??*?Created?Time:?Wed?06?Oct?2010?09:29:56?AM?CST
??3??*?File?Name:?work1.cpp
??4??*?Description:?處理源代碼格式，將多余空格去掉，換行，跳格改成空格
??5??*?去掉注釋。
??6?\***************************************************************/
??7?//*========================*Head?File*========================*\\
??8?
??9?#include?"work.h"
?10?/*----------------------*Global?Variable*----------------------*/
?11?
?12?//*=======================*Main?Program*=======================*//
?13?
?14?/*
?15??*?處理空格和注釋
?16??*/
?17?void?dealSourceCode(){
?18?????bool?space=false,multiply=false,slash=false,quote=false;
?19?????char?ch;
?20?????int?slash_multiply=0;
?21?????while(scanf("%c",&ch)!=EOF){
?22?
?23?????????if(ch=='\\'){//轉義符
?24?????????????printf("\\");
?25?????????????scanf("%c",&ch);
?26?????????????printf("%c",ch);
?27?????????????continue;
?28?????????}
?29?
?30?????????if(quote){//有引號
?31?????????????//有printf("\"")這種情況
?32?????????????//有printf("\\")這種情況
?33?????????????//有printf("")這種情況
?34?
?35?????????????if(ch=='\"'){//第三種情況
?36?????????????????printf("\"");
?37?????????????????quote=false;
?38?????????????????continue;
?39?????????????}
?40?
?41??????????????/*?處理前兩種情況*/
?42?????????????char?buf[10000];
?43?????????????int?p=0;
?44?????????????buf[p++]=ch;
?45?????????????while(scanf("%c",&buf[p])!=EOF&&(buf[p]!='\"'||(buf[p-1]=='\\'&&(p==1||buf[p-2]!='\\'))))p++;
?46?????????????buf[p+1]='\0';
?47?????????????printf("%s",buf);
?48?????????????quote=false;
?49?????????????continue;
?50?????????}
?51?
?52?????????if(ch=='?'||ch=='\n'||ch=='\t'){//空格處理
?53?????????????if(!space){
?54?????????????????printf("?");
?55?????????????????space=true;
?56?????????????}
?57?????????????while(scanf("%c",&ch)!=EOF&&(ch=='?'||ch=='\n'||ch=='\t'));
?58?????????}
?59?
?60?????????if(ch=='/'){//有可能是注釋，注釋處理
?61?????????????scanf("%c",&ch);
?62?
?63?????????????if(ch=='/'){//單行注釋
?64?????????????????while(scanf("%c",&ch)!=EOF&&ch!='\n');
?65?????????????}
?66?????????????else?if(ch=='*'){//多行注釋
?67?????????????????slash_multiply=1;
?68?????????????????slash=multiply=false;
?69?????????????????while(slash_multiply){
?70?????????????????????if(scanf("%c",&ch)==EOF)break;//輸入源文件語法錯誤
?71?????????????????????if(ch=='/'){
?72?????????????????????????if(multiply){
?73?????????????????????????????slash_multiply--;
?74?????????????????????????????multiply=slash=false;
?75?????????????????????????}
?76?????????????????????????else
?77???????????????????????????slash=true;
?78?????????????????????}
?79?????????????????????else?if(ch=='*'){
?80?????????????????????????if(slash){
?81?????????????????????????????slash_multiply++;
?82?????????????????????????????multiply=slash=false;
?83?????????????????????????}
?84?????????????????????????else
?85???????????????????????????multiply=true;
?86?????????????????????}
?87?????????????????}
?88?????????????}
?89?????????????else{//不是注釋
?90?????????????????printf("/");
?91?????????????????if(ch=='?'||ch=='\n'||ch=='\t')
?92???????????????????space=true;
?93?????????????????printf("%c",ch);
?94?????????????}
?95?????????}
?96?????????else?if(ch=='\"'){//發現第一個引號"\""
?97?????????????printf("\"");
?98?????????????quote=true;
?99?????????}
100?????????else{//普通字符
101?????????????printf("%c",ch);
102?????????????space=false;
103?????????}
104?????}
105?}
106?/*
107?int?main(){
108?????freopen("input.txt","r",stdin);
109?????freopen("output.txt","w",stdout);
110?????dealSourceCode();
111?????return?0;
112?}
113?*/ work2.cpp/***************************************************************\
?*Author:Hu?Wenbiao
?*Created?Time:?Mon?15?Nov?2010?07:09:54?PM?CST
?*File?Name:?work2.cpp
?*Description:詞法分析器
\***************************************************************/
//*========================*Head?File*========================*\\

#include"work.h"
/*----------------------*Global?Variable*----------------------*/

KEYWORD_NODE?KEYWORD[30];
//*=======================*Main?Program*=======================*//

bool?isLetter(char?ch){//判斷是否是字母
????return?(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9');
}

bool?isNumber(char?ch){//判斷是否是數字
????return?ch>='0'&&ch<='9';
}

/*
?*判斷是否是關鍵字，是則返回編碼，否則返回28(標識符)
?*/
int?getKeywordId(char*?str,int?s,int?t){
????int?i,p;
????for(i=0;i<12;i++){
????????p=0;
????????while?(KEYWORD[i].val[p]?&&?s+p<=t?&&?
????????????????????KEYWORD[i].val[p]==str[s+p]){
????????????p++;
????????}

????????if(KEYWORD[i].val[p]=='\0'?&&?s+p>t)
??????????return?i;
????}
????return?28;//id
}

/*
?*判斷是否是分隔符或操作符，是則返回編碼，否則返回0(Error)
?*/
int?getSepOrOprId(char*?str,int?s,int?t){
????int?i,p;
????for(i=12;i<28;i++){
????????p=0;
????????while?(KEYWORD[i].val[p]?&&?s<=t?&&?
????????????????????KEYWORD[i].val[p]==str[s]){
????????????p++,s++;
????????}

????????if(KEYWORD[i].val[p]=='\0'?&&?s>t)
??????????return?i;
????}
????return?0;//Error
}

/*
?*?按要求的格式輸出
?*/
void?printOut(int?id,char*?str,int?s,int?t){
????printf("%d:?",id);
????for(;s<=t;s++)
??????printf("%c",str[s]);
????printf("\n");
}

/*
?*?是否是分隔符或操作符組成元素
?*/
bool?isSepOrOpr(char?ch){
????return?ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='>'||ch=='<'||ch=='='
????????||ch=='.'||ch=='('||ch==')'||ch==','||ch==';'||ch==':';
}

/*
?*?對字符串str進行分析
?*/
void?dealMorphology(char*?str){
????int?p=0,s,t;
????while(str[p]){
????????s=t=p;
????????if(isNumber(str[p])){//整型
????????????while(str[p]&&isNumber(str[p]))?p++;
????????????t=p-1;
????????????if(isLetter(str[p])){//整型中有字母，錯誤
????????????????printOut(0,str,s,t);
????????????}
????????????else{//整型
????????????????printOut(29,str,s,t);
????????????}
????????}
????????else?if(isLetter(str[p])){//標識符
????????????while(str[p]&&(isLetter(str[p])||isNumber(str[p])))?p++;
????????????t=p-1;
????????????printOut(getKeywordId(str,s,t),str,s,t);
????????}
????????else?if(isSepOrOpr(str[p])){//分隔符或操作符
????????????while(str[p]?&&?isSepOrOpr(str[p]))?p++;
????????????t=p-1;
????????????printOut(getSepOrOprId(str,s,t),str,s,t);
????????}
????????else?if(s==t&&str[s]=='\n'){
????????????p++;
????????????continue;
????????}
????????else{
????????????printf("ERROR:\n");
????????????p++;
????????}
????}
}

/*
?*?將dealSourceCode()處理后代碼按空格進行分成若干字符串進行分別處理
?*/
void?morphologyAnalysis(){
????char?str[1000];?int?p;?bool?flag=true;
????while(flag){
????????p=0;
????????while((flag=(scanf("%c",&str[p])!=EOF))&&str[p]!='?')?p++;
????????str[p]=0;
????????dealMorphology(str);
????}
} work3.cpp??1?/***************************************************************\
??2??*Author:Hu?Wenbiao
??3??*Created?Time:?Tue?16?Nov?2010?05:11:20?PM?CST
??4??*File?Name:?work3.cpp
??5??*Description:算符優先文法
??6??*?1.非終結符和終結符的編號（id）都是它們在數組中的下標
??7??*?2.算法只能處理單字符的非終結符和終結符（大寫字母為非終結符，
??8??*?其他為終結符）
??9??*?3.處理的表達式必須含有:=且其左邊不能含有運算符，否則會被作為
?10??*?標識符的一部分處理
?11??*?4.表達式的標識符可以是字符串如：aa=bb+cc+dd*eef
?12??*?5.處理表達式時先將標識符轉化為i（因為文法中只用i表示標識符），
?13??*?標識符的名稱在NAME中記錄，另外產生的中間標識符（如T1、E2）
?14??*?的名稱也在NAME中記錄，名稱的id為其下標，NAME[0]記錄等號“:=”
?15??*?左邊的那個標識符，對于其他的標識符若id為0表示出錯
?16?\***************************************************************/
?17?//*========================*Head?File*========================*\\
?18?
?19?#include<stack>
?20?#include"work.h"
?21?
?22?/*----------------------*Global?Variable*----------------------*/
?23?
?24?N_NODE?N_ARRAY[30];//非終端符數組（下標從1開始）
?25?char?T_ARRAY[30];//終端符數組（下標從1開始）
?26?bool?F[30][30],L[30][30];//F[i][j]表示id為j的終結符是否屬于
?27?????????????????????????//id為i的非終結符的FIRSTVT，L相同。
?28?stack<pair<int,int>?>?S;//用于求FIRSTVT和LASTVT
?29?char?PRECEDENCETABLE[30][30];//算符優先關系表
?30?char?NAME[100][10];//用來存放標識符名稱，NAME[i]表示id為i的標識符
?31?int?name_foot[100];//分配中間標識符的下標，如T1中的1
?32?//*=======================*Main?Program*=======================*//
?33?
?34?int?getTnodeId(char?ch){//返回終端符編碼（下標），不存在返回0
?35?????int?p=1;
?36?????while(T_ARRAY[p]&&T_ARRAY[p]!=ch)?p++;
?37?????if(T_ARRAY[p])
?38?????????return?p;
?39?????else
?40?????????return?0;
?41?}
?42?
?43?int?getNnodeId(char?ch){//返回非終端符編碼（下標），不存在返回0
?44?????int?pos=1;
?45?????while(N_ARRAY[pos].val?&&?N_ARRAY[pos].val!=ch)?pos++;
?46?????if(N_ARRAY[pos].val)
?47???????return?pos;
?48?????else
?49???????return?0;
?50?}
?51?
?52?int?getNameId(char*?str,int?s,int?t){//給str[s]~str[t]分配位置，并返回id
?53?????int?ptr=0;
?54?????while(NAME[ptr][0])ptr++;
?55?
?56?????for(int?i=0;s+i<=t;i++)
?57???????NAME[ptr][i]=str[s+i];
?58?
?59?????return?ptr;
?60?}
?61?
?62?int?getNameId(char?ch){//同上，重載
?63?????name_foot[ch]++;
?64?????int?ptr=0;
?65?????while(NAME[ptr][0])ptr++;
?66?
?67?????NAME[ptr][0]=ch;
?68?????NAME[ptr][1]=char(name_foot[ch]+'0');
?69?
?70?????return?ptr;
?71?}
?72?
?73?void?insertN_ARRAY(char?val,char*?str,int?s,int?t){//增加非終結符
?74?????int?pos=1;
?75?????while(N_ARRAY[pos].val&&N_ARRAY[pos].val!=val)?pos++;
?76?????N_ARRAY[pos].val=val;
?77?????int?cnt=N_ARRAY[pos].cnt,p=0;
?78?????for(;s<=t;p++,s++){
?79?????????N_ARRAY[pos].ARR[cnt][p]=str[s];
?80?????}
?81?????N_ARRAY[pos].cnt++;
?82?}
?83?
?84?void?insertT_ARRAY(char?ch){//增加終結符
?85?????int?p=1;
?86?????while(T_ARRAY[p])?p++;
?87?????T_ARRAY[p]=ch;
?88?}
?89?
?90?bool?isNnode(char?ch){//判斷是否是非終結符
?91?????return?ch>='A'&&ch<='Z';
?92?}
?93?
?94?/*
?95??*?求解所有非終結符的FIRSTVT
?96??*/
?97?
?98?void?getFIRSTVT(){
?99?????pair<int,int>?cur;//cur.first是非終結符的id，cur.second是終結符的id
100?????int?nr_Nnode=1;
101?????while(N_ARRAY[nr_Nnode].val)?nr_Nnode++;//其實nr_Nnode=(nr?of?Nnode)+1
102?????for(int?i=1;i<nr_Nnode;i++){//每個非終結符
103?????????for(int?j=0;j<N_ARRAY[i].cnt;j++){//每個產生式
104?????????????if(!isNnode(N_ARRAY[i].ARR[j][0])){//N_ARRAY[i].ARR[j][0]是終結符
105?????????????????int?id_Tnode=getTnodeId(N_ARRAY[i].ARR[j][0]);
106?????????????????if(F[i][id_Tnode])continue;
107?????????????????F[i][id_Tnode]=true;
108?????????????????S.push(pair<int,int>(i,id_Tnode));
109?????????????}
110?????????????//N_ARRAY[i].ARR[j][1]是終結符
111?????????????else?if(N_ARRAY[i].ARR[j][1]?&&?!isNnode(N_ARRAY[i].ARR[j][1])){
112?????????????????int?id_Tnode=getTnodeId(N_ARRAY[i].ARR[j][1]);
113?????????????????if(F[i][id_Tnode])continue;
114?????????????????F[i][id_Tnode]=true;
115?????????????????S.push(pair<int,int>(i,id_Tnode));
116?????????????}
117?????????}
118?????}
119?????while(!S.empty()){
120?????????cur=S.top(),S.pop();
121?????????char?curNnodeVal=N_ARRAY[cur.first].val;
122?
123?????????for(int?i=1;i<nr_Nnode;i++){
124?????????????if(F[i][cur.second])continue;//cur.second已經屬于FIRSTVT(i)
125?????????????for(int?j=0;j<N_ARRAY[i].cnt;j++){//查找哪個產生式右邊以curNnodeVal為首
126?????????????????if(N_ARRAY[i].ARR[j][0]==curNnodeVal){
127?????????????????????F[i][cur.second]=true;
128?????????????????????S.push(pair<int,int>(i,cur.second));
129?????????????????????break;
130?????????????????}
131?????????????}
132?????????}
133?????}
134?????/*輸出FIRSTVT*/
135?????for(int?i=1;i<nr_Nnode;i++){
136?????????for(int?j=1;j<30;j++){
137?????????????if(F[i][j]){
138?????????????????printf("FIRSTVT(%c):?{",N_ARRAY[i].val);
139?????????????????while(j<30){
140?????????????????????if(F[i][j])
141???????????????????????printf("%c?",T_ARRAY[j]);
142?????????????????????j++;
143?????????????????}
144?????????????????printf("}\n");
145?????????????}
146?????????}
147?????}
148?????printf("\n");
149?????/**/
150?}
151?
152?/*
153??*?求解所有非終結符的LASTVT
154??*/
155?
156?void?getLASTVT(){
157?????pair<int,int>?cur;
158?????int?nr_Nnode=1;
159?????while(N_ARRAY[nr_Nnode].val)?nr_Nnode++;
160?????for(int?i=1;i<nr_Nnode;i++){
161?????????for(int?j=0;j<N_ARRAY[i].cnt;j++){
162?????????????int?ptr=0;
163?????????????while(N_ARRAY[i].ARR[j][ptr])?ptr++;
164?????????????ptr--;
165?????????????if(!isNnode(N_ARRAY[i].ARR[j][ptr])){
166?????????????????int?id_Tnode=getTnodeId(N_ARRAY[i].ARR[j][ptr]);
167?????????????????if(L[i][id_Tnode])continue;
168?????????????????L[i][id_Tnode]=true;
169?????????????????S.push(pair<int,int>(i,id_Tnode));
170?????????????}
171?????????????else?if(ptr>0&&!isNnode(N_ARRAY[i].ARR[j][ptr-1])){
172?????????????????int?id_Tnode=getTnodeId(N_ARRAY[i].ARR[j][ptr-1]);
173?????????????????if(L[i][id_Tnode])continue;
174?????????????????L[i][id_Tnode]=true;
175?????????????????S.push(pair<int,int>(i,id_Tnode));
176?????????????}
177?????????}
178?????}
179?????while(!S.empty()){
180?????????cur=S.top(),S.pop();
181?????????char?curNnodeVal=N_ARRAY[cur.first].val;
182?
183?????????for(int?i=1;i<nr_Nnode;i++){
184?????????????for(int?j=0;j<N_ARRAY[i].cnt;j++){
185?????????????????int?ptr=0;
186?????????????????while(N_ARRAY[i].ARR[j][ptr])?ptr++;
187?????????????????ptr--;
188?????????????????if(N_ARRAY[i].ARR[j][ptr]==curNnodeVal?&&
189?????????????????????????!L[i][cur.second]){
190?????????????????????L[i][cur.second]=true;
191?????????????????????S.push(pair<int,int>(i,cur.second));
192?????????????????????break;
193?????????????????}
194?????????????}
195?????????}
196?????}
197?????/*輸出LASTVT*/
198?????for(int?i=1;i<nr_Nnode;i++){
199?????????for(int?j=1;j<30;j++){
200?????????????if(L[i][j]){
201?????????????????printf("LASTVT(%c):?{",N_ARRAY[i].val);
202?????????????????while(j<30){
203?????????????????????if(L[i][j])
204???????????????????????printf("%c?",T_ARRAY[j]);
205?????????????????????j++;
206?????????????????}
207?????????????????printf("}\n");
208?????????????}
209?????????}
210?????}
211?????printf("\n");
212?????/**/
213?}
214?
215?/*
216??*?求算符優先表
217??*/
218?
219?void?getPrecedenceTable(){
220?????int?nr_Nnode=1,nr_Tnode=1;
221?????while(N_ARRAY[nr_Nnode].val)?nr_Nnode++;
222?????while(T_ARRAY[nr_Tnode])?nr_Tnode++;
223?
224?????/**關于#的比較**/
225?????int?id_sharp=getTnodeId('#');
226?????for(int?j=1;j<nr_Tnode;j++){
227?????????if(F[1][j]){
228?????????????PRECEDENCETABLE[id_sharp][j]='<';
229?????????}
230?????????if(L[1][j]){
231?????????????PRECEDENCETABLE[j][id_sharp]='>';
232?????????}
233?????}
234?
235?????/***************/
236?
237?????for(int?i=1;i<nr_Nnode;i++){//每個非終結符
238?????????for(int?j=0;j<N_ARRAY[i].cnt;j++){//每個產生式
239?????????????int?tail=0;
240?????????????while(N_ARRAY[i].ARR[j][tail])?tail++;
241?????????????tail--;//最后一位（非零）
242?????????????for(int?p=0;p<tail;p++){
243?????????????????//tt
244?????????????????if(!isNnode(N_ARRAY[i].ARR[j][p])?&&?
245?????????????????????????????!isNnode(N_ARRAY[i].ARR[j][p+1])){
246?????????????????????int?id1=getTnodeId(N_ARRAY[i].ARR[j][p]);
247?????????????????????int?id2=getTnodeId(N_ARRAY[i].ARR[j][p+1]);
248?????????????????????if(PRECEDENCETABLE[id1][id2]){
249?????????????????????????printf("ERROR:不是算符優先文法!");
250?????????????????????????exit(EXIT_FAILURE);
251?????????????????????}
252?????????????????????PRECEDENCETABLE[id1][id2]='=';
253?????????????????}
254?????????????????//tNt
255?????????????????if(p<=tail-2&&!isNnode(N_ARRAY[i].ARR[j][p])&&
256?????????????????????????????isNnode(N_ARRAY[i].ARR[j][p+1])&&
257?????????????????????????????!isNnode(N_ARRAY[i].ARR[j][p+2])){
258?????????????????????int?id1=getTnodeId(N_ARRAY[i].ARR[j][p]);
259?????????????????????int?id2=getTnodeId(N_ARRAY[i].ARR[j][p+2]);
260?????????????????????if(PRECEDENCETABLE[id1][id2]){
261?????????????????????????printf("ERROR:不是算符優先文法!");
262?????????????????????????exit(EXIT_FAILURE);
263?????????????????????}
264?????????????????????PRECEDENCETABLE[id1][id2]='=';
265?????????????????}
266?????????????????//tN
267?????????????????if(!isNnode(N_ARRAY[i].ARR[j][p])?&&
268?????????????????????????????isNnode(N_ARRAY[i].ARR[j][p+1])){
269?????????????????????int?id1=getTnodeId(N_ARRAY[i].ARR[j][p]);
270?????????????????????int?id_Nnode=getNnodeId(N_ARRAY[i].ARR[j][p+1]);
271?????????????????????int?id2=1;
272?????????????????????while(T_ARRAY[id2]){
273?????????????????????????if(F[id_Nnode][id2]){
274?????????????????????????????if(PRECEDENCETABLE[id1][id2]){
275?????????????????????????????????printf("ERROR:不是算符優先文法!");
276?????????????????????????????????exit(EXIT_FAILURE);
277?????????????????????????????}
278?????????????????????????????PRECEDENCETABLE[id1][id2]='<';
279?????????????????????????}
280?????????????????????????id2?++;
281?????????????????????}
282?????????????????}
283?????????????????//Nt
284?????????????????if(isNnode(N_ARRAY[i].ARR[j][p])?&&
285?????????????????????????????????!isNnode(N_ARRAY[i].ARR[j][p+1])){
286?????????????????????int?id_Nnode=getNnodeId(N_ARRAY[i].ARR[j][p]);
287?????????????????????int?id2=getTnodeId(N_ARRAY[i].ARR[j][p+1]);
288?????????????????????int?id1=1;
289?????????????????????while(T_ARRAY[id1]){
290?????????????????????????if(L[id_Nnode][id1]){
291?????????????????????????????if(PRECEDENCETABLE[id1][id2]){
292?????????????????????????????????printf("ERROR:不是算符優先方法!");
293?????????????????????????????????exit(EXIT_FAILURE);
294?????????????????????????????}
295?????????????????????????????PRECEDENCETABLE[id1][id2]='>';
296?????????????????????????}
297?????????????????????????id1++;
298?????????????????????}
299?????????????????}
300?????????????}
301?????????}
302?????}
303?????//輸出優先表////
304?????cout<<"??";
305?????for(int?i=1;i<nr_Tnode;i++){
306?????????cout<<T_ARRAY[i]<<"?";
307?????}
308?????cout<<endl;
309?????for(int?i=1;i<nr_Tnode;i++){
310?????????cout<<T_ARRAY[i]<<"?";
311?????????for(int?j=1;j<nr_Tnode;j++){
312?????????????if(PRECEDENCETABLE[i][j])
313???????????????cout<<PRECEDENCETABLE[i][j]<<"?";
314?????????????else
315???????????????cout<<"??";
316?????????}
317?????????cout<<endl;
318?????}
319?????cout<<endl;
320?????//
321?}
322?
323?/*
324??*?比較ARR[s]~ARR[t]中的id和str中的符號是否匹配
325??*?其中非終結符的id是取負值的，比較時也不比較非
326??*?終結符是否相同，只要求終結符相同，非終結符相
327??*?對應就返回true
328??*/
329?
330?bool?cmpIdNodeVal(pair<int,int>*?ARR,int?s,int?t,char*?str){
331?????int?ptr=0,id;
332?????while(s<=t?&&?str[ptr]){
333?????????if(isNnode(str[ptr])){//非終結符
334?????????????if(ARR[s].first>0)
335???????????????return?false;
336?????????}
337?????????else?if(ARR[s].first!=getTnodeId(str[ptr]))
338???????????return?false;
339?????????ptr++;
340?????????s++;
341?????}
342?????if(s<=t?||?str[ptr])
343???????return?false;
344?????return?true;
345?}
346?
347?/*
348??*?將STACK[s]~STACK[t]歸約，返回歸約后的非終結符的值，
349??*?分配并由name返回非終結符的名稱id
350??*/
351?
352?char?reduction(pair<int,int>*?STACK,int?s,int?t,int&?name){
353?????int?i=1;
354?????while(N_ARRAY[i].val){
355?????????for(int?j=0;j<N_ARRAY[i].cnt;j++){
356?????????????if(cmpIdNodeVal(STACK,s,t,N_ARRAY[i].ARR[j])){//查找成功
357?
358?
359?????????????????///輸出///
360?
361?????????????????if(s==t&&STACK[s].first>0){//?1
362?????????????????????name=STACK[s].second;
363?????????????????}
364?
365?????????????????if(s+1==t){//?2
366?????????????????????????name=getNameId(N_ARRAY[i].val);
367?????????????????????if(STACK[s].first>0){
368?????????????????????????printf("(%c,_,%s,%s)\n",
369?????????????????????????????????????T_ARRAY[STACK[s].first],NAME[STACK[t].second],NAME[name]);
370?????????????????????}
371?????????????????????else{
372?????????????????????????printf("(%c,%s,_,%s)\n",
373?????????????????????????????????????T_ARRAY[STACK[t].first],NAME[STACK[s].second],NAME[name]);
374?????????????????????}
375?????????????????}
376?????????????????if(s+2==t){//?3
377?????????????????????if(STACK[s].first>0&&STACK[t].first>0){//(T)這種情況
378?????????????????????????name=STACK[s+1].second;
379?????????????????????}
380?????????????????????else{
381?????????????????????????name=getNameId(N_ARRAY[i].val);
382?????????????????????????printf("(%c,%s,%s,%s)\n",T_ARRAY[STACK[s+1].first],
383?????????????????????????????????NAME[STACK[s].second],NAME[STACK[t].second],NAME[name]);
384?????????????????????}
385?????????????????}
386?
387?????????????????//
388?
389?????????????????return?N_ARRAY[i].val;
390?????????????}
391?????????}
392?????????i++;
393?????}
394?????return?0;
395?}
396?
397?/*
398??*?核心函數，處理傳入的單句表達式，要求表達式必須為
399??*?abc:=x*y+zuv?的形式，即必須有:=號且其左邊不能有運
400??*?算符，否則會被當作標識符的一部分處理
401??*/
402?
403?void?operatorPrecedenceParser(char*?str0){
404?????///將空格去掉///
405?????int?s=0,t=0,p;
406?????while(str0[t]){
407?????????if(str0[t]!='?'){
408?????????????str0[s]=str0[t];
409?????????????s++;
410?????????}
411?????????t++;
412?????}
413?????str0[s]=0;
414?
415?????///將str0轉換成str，由文法符號表示///
416?????char?str[1000];
417?????int?str_name[1000];//str_name[i]是str[i]的名稱，當str[i]為操作符時無意義
418?
419?????memset(NAME,0,sizeof(NAME));
420?????memset(name_foot,0,sizeof(name_foot));
421?
422?????s=0;
423?????while(str0[s]&&str0[s]!=':')s++;
424?????if(str0[s]==0){
425?????????printf("ERROR:表達式不合法\n");
426?????????return;
427?????}
428?????getNameId(str0,0,s-1);//放在NAME[0]，在下面進行歸約時標識符id為0時表示出錯
429?????s+=2;//?:=右邊首字符
430?????p=0;
431?????while(str0[s]){
432?????????if(isLetter(str0[s])){//標識符
433?????????????t=s;
434?????????????while(str0[t]&&isLetter(str0[t]))t++;
435?????????????str[p]='i';
436?????????????str_name[p]=getNameId(str0,s,t-1);
437?????????????s=t,p++;
438?????????}
439?????????else{//操作符
440?????????????str[p]=str0[s];
441?????????????s++,p++;
442?????????}
443?????}
444?????str[p]='#';//結束符
445?????str[p+1]=0;
446?????//
447?????
448?????pair<int,int>?STACK[1000];//STACK[i].first保存id，正數是Tnode，負數是Nnode
449???????????????????????????????//STACK[i].second保存標識符id?
450?????int?k=0,j;STACK[k].first=getTnodeId('#');//STACK[k]棧頂
451?????p=0;//str[p]當前字符
452?????int?q,cid;
453?
454?????while(str[p]){
455?????????cid=getTnodeId(str[p]);//當前字符id
456?
457?????????if(STACK[k].first>0)?j=k;
458?????????else?j=k-1;
459?
460?????????while(PRECEDENCETABLE[STACK[j].first][cid]=='>'){
461?????????????do{
462?????????????????q=STACK[j].first;
463?????????????????j=STACK[j-1].first>0?j-1:j-2;
464?????????????}while(PRECEDENCETABLE[STACK[j].first][q]=='=');
465?
466?????????????int?tmp_name=0;
467?????????????char?tmp=reduction(STACK,j+1,k,tmp_name);//歸約
468?????????????k=j+1;
469?????????????STACK[k].first=-getNnodeId(tmp);
470?????????????if(tmp_name)
471???????????????STACK[k].second=tmp_name;
472?????????????else?//?name為0表示錯誤
473???????????????printf("ERROR:tmp_name,when?reduction");
474?????????}
475?????????if(PRECEDENCETABLE[STACK[j].first][cid]=='<'?||
476?????????????????????PRECEDENCETABLE[STACK[j].first][cid]=='='){
477?????????????k++;
478?????????????STACK[k].first=cid,STACK[k].second=str_name[p];
479?????????????p++;
480?????????}
481?????????else{
482?????????????if(str[p]=='#'&&j==0){
483?
484?????????????????//給:=左邊的符號賦值
485?????????????????printf("(:=,%s,_,%s)\n",NAME[STACK[1].second],NAME[0]);
486?
487?????????????????printf("Done!\n");
488?????????????????return;
489?????????????}
490?????????????else{
491?????????????????printf("ERROR:歸約時出錯！");
492?????????????????exit(-1);
493?????????????}
494?????????}
495?????}
496?????
497?}
498?
499?/*
500??*?讀入文法
501??*/
502?
503?void?readGrammar(){
504?????char?str[30];
505?????
506?????while(scanf("%[^\n]%*c",str)!=EOF){
507?????????///將空格去掉///
508?????????int?s=0,t=0;
509?????????while(str[t]){
510?????????????if(str[t]!='?'){
511?????????????????str[s]=str[t];
512?????????????????s++;
513?????????????}
514?????????????t++;
515?????????}
516?????????str[s]=0;
517?????????//
518?
519?????????if(str[0]<'A'||str[0]>'Z'){//檢查首字母是否大寫
520?????????????printf("ERROR:首字母不是非終結符\n");
521?????????????continue;
522?????????}
523?????????int?p=0;
524?????????while(str[p]&&(str[p]!='-'||str[p+1]!='>'))?p++;//檢查是否有符號"->"
525?????????if(!str[p]){
526?????????????printf("ERROR:不是產生式\n");
527?????????????continue;
528?????????}
529?????????p+=2;
530?????????///找終結符///
531?????????t=p;
532?????????while(str[t]){
533?????????????if(!isNnode(str[t])&&str[t]!='|')
534???????????????insertT_ARRAY(str[t]);
535?????????????t++;
536?????????}
537?????????//
538?
539?????????///找產生式///
540?????????while(str[p]){
541?????????????s=t=p;?
542?????????????while(str[p]&&str[p]!='|')?p++;
543?????????????if(str[p]){
544?????????????????t=p-1,p++;
545?????????????}
546?????????????else
547?????????????????t=p;
548?
549?????????????insertN_ARRAY(str[0],str,s,t);
550?????????}
551?????????//
552?????}
553?????insertT_ARRAY('#');//加入終結符'#'
554?}
555?
556?/*
557??*?算符優先文法主函數
558??*/
559?
560?void?dealOperatorPrecedenceGrammar(){
561?????freopen("input31","r",stdin);
562?????freopen("output3","w",stdout);
563?????readGrammar();
564?????getFIRSTVT();
565?????getLASTVT();
566?????getPrecedenceTable();
567?
568?????freopen("input32","r",stdin);
569?????char?str[100];
570?????while(scanf("%[^\n]%*c",str)!=EOF){
571?????????operatorPrecedenceParser(str);
572?????}
573?}

?

?

work.cpp?1?/***************************************************************\
?2??*Author:Hu?Wenbiao
?3??*Created?Time:?Mon?15?Nov?2010?09:58:46?PM?CST
?4??*File?Name:?work.cpp
?5??*Description:主函數
?6?\***************************************************************/
?7?//*========================*Head?File*========================*\\
?8?
?9?#include"work.h"
10?/*----------------------*Global?Variable*----------------------*/
11?
12?//*=======================*Main?Program*=======================*//
13?
14?int?main(){
15?????init();
16?????freopen("input1","r",stdin);
17?????freopen("output1","w",stdout);
18?????dealSourceCode();
19?????freopen("output1","r",stdin);
20?????freopen("output2","w",stdout);
21?????morphologyAnalysis();
22?
23?????dealOperatorPrecedenceGrammar();//輸入的設置在該函數中
24?}

?

?

?

?

轉載于:https://www.cnblogs.com/Open_Source/archive/2011/01/01/1923797.html

總結

以上是生活随笔為你收集整理的编译原理实验（算符优先文法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。