?? scpascal.cpp
字號:
firstTable[expression][0]=id;//expression
firstTable[expression][1]=num;
firstTable[expression][2]=lpare;
firstTable[expression][3]=rw_not;
firstTable[expression][4]=rw_true;
firstTable[expression][5]=rw_false;
firstTable[expression][6]=op_add;
firstTable[expression][7]=op_sub;
firstTable[procedure_statement][0]=id;//procedure_statement
firstTable[expression_list][0]=id;//expression_list
firstTable[expression_list][1]=num;
firstTable[expression_list][2]=lpare;
firstTable[expression_list][3]=rw_not;
firstTable[expression_list][4]=rw_true;
firstTable[expression_list][5]=rw_false;
firstTable[expression_list][6]=op_add;
firstTable[expression_list][7]=op_sub;
firstTable[simple_expression][0]=id;//simple_expression
firstTable[simple_expression][1]=num;
firstTable[simple_expression][2]=lpare;
firstTable[simple_expression][3]=rw_not;
firstTable[simple_expression][4]=rw_true;
firstTable[simple_expression][5]=rw_false;
firstTable[simple_expression][6]=op_add;
firstTable[simple_expression][7]=op_sub;
firstTable[term][0]=id;//term
firstTable[term][1]=num;
firstTable[term][2]=lpare;
firstTable[term][3]=rw_not;
firstTable[term][4]=rw_true;
firstTable[term][5]=rw_false;
firstTable[sign][0]=op_add;//sign
firstTable[sign][1]=op_sub;
firstTable[factor][0]=id;//factor
firstTable[factor][1]=num;
firstTable[factor][2]=lpare;
firstTable[factor][3]=rw_not;
firstTable[factor][4]=rw_true;
firstTable[factor][5]=rw_false;
firstTable[start][0]=rw_program;
}
struct transnode{
int formula;//公式號
int dot; //點位置
int forward; //向前搜索符號串
transnode * next;//指向本結構的指針
};
//#define struct transnode* transnodePtr
static int Firstback[30];//Firstback[0]是指返回的值的個數初始化為0，后面的是返回的First值初始化為－1。
void First(struct transnode *ptr) //求任意字符串First集合
{
int PN;
int flag=0;
if (productions[ptr->formula].length < (ptr->dot))
return;
if (productions[ptr->formula].length == (ptr->dot)){
Firstback[1+Firstback[0]]=ptr->forward;
Firstback[0]=Firstback[0]+1;
return;
}
PN = productions[ptr->formula].product[ptr->dot+1];//PN是點后的字符代碼。
if (PN == empty ) {//PN點后是空
return;
}
if (!IsNT(PN)) { //如果PN是終結符
Firstback[1+Firstback[0]]=PN;//返回的是該終結符
Firstback[0]=Firstback[0]+1;
return;
}
if (IsNT(PN)){ //如果PN是非終結符
for(int i = 0;firstTable[PN][i] != -1;i++){//檢查First表是否該非終結符的First中可以為空
if (firstTable[PN][i]==empty){//若有空置標志位
flag=1;
}
}
if (flag==0){//先前檢查沒有空
int j;
for(j = 0;firstTable[PN][j] != -1;j++){
Firstback[j+1+Firstback[0]] = firstTable[PN][j];
}
Firstback[0]=Firstback[0]+j;
}
if (flag==1){//先前檢查有空
struct transnode * tempptr = new struct transnode;
//printf("%d ",tempptr);
tempptr->formula = ptr->formula;
tempptr->forward = ptr->forward;
tempptr->dot = ptr->dot+1;
First(tempptr);//先遞歸求得為空以后的First
int j;
for(j = 0;firstTable[PN][j] != -1;j++){
if (firstTable[PN][j] != empty){
Firstback[j+1+Firstback[0]] = firstTable[PN][j];
}
}
Firstback[0]=Firstback[0]+j-1;
}
}
}
typedef struct transnode* transnodePtr;
int PinPtr(transnodePtr p,transnodePtr ptr){ //查看節點p是否在ptr指示的鏈表中存在
while(ptr != NULL){
if ((p->formula == ptr->formula)&&
(p->dot == ptr->dot)&&(p->forward == ptr->forward)){
return 1;
}else{
ptr = ptr->next;
}
}
return 0;
}
void Insert(struct transnode *ptr,struct transnode * newnode){ //在ptr指示的鏈表中插入一個新的結點
struct transnode *fnode ;
fnode = ptr;
if (!PinPtr(newnode,ptr)){
while (fnode->next != 0) {//一直搜索至最后的節點
fnode=fnode->next;
}
fnode->next=newnode;
newnode->next=0;
}
}
int lengthof(struct transnode* p){ //計算結點數目
int x = 0;
while(p != NULL){
x++;
p = p->next;
}
return x;
}
struct transnode * closure(struct transnode *ptr){ //求ptr所指生成式的閉包
int PN;
struct transnode *aptr;
aptr=ptr;
while (aptr != 0){
PN = productions[aptr->formula].product[aptr->dot+1];//PN是點后的字符代碼。
{//該程序塊執行對First返回值初始化的任務
int i;
Firstback[0]=0;
for(i = 1;i < 30;i++)
Firstback[i] = -1;
}
//if (productions[ptr->formula].length <= (ptr->dot)); //若點在最后，PN沒有,不作動作
//if ((PN < 8)&&(PN>3)) ; //如果PN是終結符,不作動作
if (IsNT(PN)){
struct transnode * tempptr = new struct transnode;
//printf("%d ",tempptr);
tempptr->formula = aptr->formula;
tempptr->forward = aptr->forward;
tempptr->dot = aptr->dot+1;
First(tempptr);
int i,j;
for(i = 0;i < LENOFPRODUCTIONS; i++){
if (productions[i].product[0]==PN)
for(j = 0;j < Firstback[0];j++){
struct transnode * newnode = new struct transnode;
//printf("%d ",newnode);
newnode->formula = i;//新建的節點公式號是從productions[i].product[1]搜索來
newnode->dot = 0;//新建的節點點位置在0處
newnode->forward = Firstback[j+1];//新建的向前搜索符號串是算得得First
Insert(ptr,newnode);//在ptr指向的鏈表中插入新的一項newnode
}
}
}
int cc = lengthof(ptr);
aptr=aptr->next;
}
return ptr;
}
//以上是closure（）部分的定義，下面開始初始化分析表
#define MAX 1000
//狀態棧的定義
int stateStack[MAX];
int point = 0;
int push(int x){ //進棧函數
if (point == MAX){
return 0;
}else{
stateStack[point] = x;
point++;
return 1;
}
}
int pop(int x){ //出棧函數
point = point-x;
if (point<0){
point = point+x;
return 0;
}else{
return 1;
}
}
int top(int x){ //找棧頂
int i = point-x;
if (i<0){
printf("Not so many element in the stack");
return -1;
}else{
return i;
}
}
void printStack(){ //打印棧
int i;
for (i=0;i<point;i++){
printf("%d",stateStack[i]);
}
printf("\n");
}
void printTop(int x){ //打印棧頂
int i;
for (i = top(x);i<point;i++){
printf("%d",stateStack[i]);
}
printf("\n");
}
//actionTable和gotoTable分析表的結構定義
#define shift 0
#define reduce 1
#define acc 2
//#define error 3
#define ok 4
#define MAXSTATES 1000
struct reduceInfo{
int formula;
int length;
int leftsym;
}; //歸約信息的結構
union actioninfo{
int state;
struct reduceInfo ri;
void (*p)();
}; //action表的信息
struct actionItem{
int typ;
union actioninfo ai;
}; //action表結點
struct actionItem actionTable[MAXSTATES][NUMOFSYMBOLS];
int numofstates = 0;
union gotoinfo{
int state;
void (*p)();
}; //goto表的信息
struct gotoItem{
int typ;
union gotoinfo gi;
}; //goto表的結點
struct gotoItem gotoTable[MAXSTATES][NUMOFSYMBOLS];
struct LR1node{
int length;
transnodePtr tp;
}; //LR1項目狀態集的頭結點.
struct LR1node LR1[MAX];
int numofLR1 = 0;
//輸出為增加項目集規范族和對goTable的設置
int compare(transnodePtr p1,transnodePtr p2){ //判斷p1,p2所指鏈表是否完全相同
transnodePtr p;
p = p1;
while(p != NULL){
if (!(PinPtr(p,p2))){
return 0;
}
p = p->next;
}
p = p2;
while(p != NULL){
if (!(PinPtr(p,p1))){
return 0;
}
p = p->next;
}
return 1;
}
int findinLR1(transnodePtr ptr,int b){ //找新生LR1項目規范族是否已經存在
int i;
for (i = 0; i<numofLR1; i++){
if (LR1[i].length == b){
if (i == 335){
printf("");
}
if (compare(ptr,LR1[i].tp)){
return i;
}
}
}
return numofLR1;
}
void gofrom(int I){ //從LR1狀態分析中狀態遷移函數
int flag[MAX];
int i,ax,bx,cx;
transnodePtr p,newPtr;
transnodePtr ptr = NULL;
if (I == 11){
printf("");
}
for (i=0; i<MAX; i++){
flag[i] = 0;
}
while(1){
i = 0;
p = LR1[I].tp;
while ((flag[i] != 0) && (p->next != NULL)){
p = p->next;
i++;
}
if (flag[i] == 0){
flag[i] = 1;
//判斷是否可做closure
if (p->dot < productions[p->formula].length){
//newPtr = (transnodePtr)malloc(sizeof(struct transnode));
newPtr = new struct transnode;
//printf("%d ",newPtr);
newPtr->formula = p->formula;
newPtr->dot = p->dot+1;
newPtr->forward = p->forward;
newPtr->next = NULL;
ptr = newPtr;
ax = productions[p->formula].product[(p->dot)+1];
while (p->next != NULL) {
p = p->next;
++i;
if (flag[i] == 0){
if (p->dot<productions[p->formula].length){
if (ax == productions[p->formula].product[(p->dot)+1]){
//newPtr = (transnodePtr)malloc(sizeof(struct transnode));
newPtr = new struct transnode;
//printf("%d ",newPtr);
newPtr->formula = p->formula;
newPtr->dot = p->dot+1;
newPtr->forward = p->forward;
newPtr->next = ptr;
ptr = newPtr;
flag[i] = 1;
}
}
}
}
ptr = closure(ptr);
bx = lengthof(ptr);
cx = findinLR1(ptr,bx);
if (cx == numofLR1){
if (numofLR1 == 405){
printf("");
}
//printf("%d come from %d\n",numofLR1,I);
if (numofLR1 == 11){
printf("from %d",I);
}
numofLR1++;
LR1[cx].length = bx;
LR1[cx].tp = ptr;
}
//goTable[I,a] = c;
if (IsNT(ax)){
gotoTable[I][ax].typ = ok;
gotoTable[I][ax].gi.state = cx;
}else{
actionTable[I][ax].typ = shift;
actionTable[I][ax].ai.state = cx;
}
}
else{
if ((p->formula == 0) && (p->forward == DOLLAR)){
actionTable[I][DOLLAR].typ = acc;
}else{
actionTable[I][p->forward].typ = reduce;
actionTable[I][p->forward].ai.ri.formula = p->formula;
actionTable[I][p->forward].ai.ri.length = productions[p->formula].length;
actionTable[I][p->forward].ai.ri.leftsym = productions[p->formula].product[0];
}
continue;
}
}else{
break;
}
}
}
void InitLR1(){ //初始化LR1項目規范集
int i;
for (i=0;i<MAX;i++){
LR1[i].length = 0;
LR1[i].tp = NULL;
}
transnodePtr ptr;
ptr = new struct transnode;
ptr->formula = 0;
ptr->dot = 0;
ptr->forward = DOLLAR;
ptr->next = NULL;
ptr = closure(ptr);
LR1[0].length = lengthof(ptr);
LR1[0].tp = ptr;
numofLR1 = 1;
i = 0;
while(i<numofLR1){
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -