语法分析.txt

用于编译原理的语法分析实验

说明：本次代码需要上次此法分析代码生成的文件如a.txt作为输入，然后根据给定文法bnf.txt和LR1分析表lr1.lr1判断是否语法是否正确。

三个文件如下：

a.txt

1,1
0,*
1,2
0,+
0,(
2,xy
0,+
1,44
0,)


bnf.txt

A;E;E;E+T;E;E-T;E;T;T;T*F;T;T\F;T;F;F;(E);F;i;


lr1.lr1

0;(;S4;0;i;S5;0;E;1;0;T;2;0;F;3;1;+;S6;1;-;S7;1;#;acc;2;+;r3;2;-;r3;2;*;S8;2;\;S9;2;#;r3;3;+;r6;3;-;r6;3;*;r6;3;\;r6;3;#;r6;4;(;S13;4;i;S14;4;E;10;4;T;11;4;F;12;5;+;r8;5;-;r8;5;*;r8;5;\;r8;5;#;r8;6;(;S4;6;i;S5;6;T;15;6;F;3;7;(;S4;7;i;S5;7;T;16;7;F;3;8;(;S4;8;i;S5;8;F;17;9;(;S4;9;i;S5;9;F;18;10;+;S20;10;-;S21;10;);S19;11;+;r3;11;-;r3;11;*;S22;11;\;S23;11;);r3;12;+;r6;12;-;r6;12;*;r6;12;\;r6;12;);r6;13;(;S13;13;i;S14;13;E;24;13;T;11;13;F;12;14;+;r8;14;-;r8;14;*;r8;14;\;r8;14;);r8;15;+;r1;15;-;r1;15;*;S8;15;\;S9;15;#;r1;16;+;r2;16;-;r2;16;*;S8;16;\;S9;16;#;r2;17;+;r4;17;-;r4;17;*;r4;17;\;r4;17;#;r4;18;+;r5;18;-;r5;18;*;r5;18;\;r5;18;#;r5;19;+;r7;19;-;r7;19;*;r7;19;\;r7;19;#;r7;20;(;S13;20;i;S14;20;T;25;20;F;12;21;(;S13;21;i;S14;21;T;26;21;F;12;22;(;S13;22;i;S14;22;F;27;23;(;S13;23;i;S14;23;F;28;24;+;S20;24;-;S21;24;);S29;25;+;r1;25;-;r1;25;*;S22;25;\;S23;25;);r1;26;+;r2;26;-;r2;26;*;S22;26;\;S23;26;);r2;27;+;r4;27;-;r4;27;*;r4;27;\;r4;27;);r4;28;+;r5;28;-;r5;28;*;r5;28;\;r5;28;);r5;29;+;r7;29;-;r7;29;*;r7;29;\;r7;29;);r7;


代码部分如下：



Stdfax.cpp

// stdafx.cpp : source file that includes just the standard includes
// LR1.pch will be the pre-compiled header
// stdafx.obj will contain the pre-compiled type information

#include "stdafx.h"

// TODO: reference any additional headers you need in STDAFX.H
// and not in this file


stdafx.h

// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
//      are changed infrequently
//

#if !defined(AFX_STDAFX_H__F2CCDD4E_3367_4AF0_9C7E_7548030D5D43__INCLUDED_)
#define AFX_STDAFX_H__F2CCDD4E_3367_4AF0_9C7E_7548030D5D43__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#define WIN32_LEAN_AND_MEAN   // Exclude rarely-used stuff from Windows headers

#include <stdio.h>

// TODO: reference additional headers your program requires here

//{{AFX_INSERT_LOCATION}}
// Microsoft Visual C++ will insert additional declarations immediately before the previous line.

#endif // !defined(AFX_STDAFX_H__F2CCDD4E_3367_4AF0_9C7E_7548030D5D43__INCLUDED_)


CharStack.h

// File Name: CharStack.h

#define MAX_DATA_LEN 256 // 数据缓冲区长度

// word type
#define WT_OPERATOR   0 // 操作符
#define WT_UINT    1 // 非负整数
#define WT_VARIABLE   2 // 变量

struct WORDNODE    // 单词序列节点
{
unsigned short byType;   // 类别
char Value[MAX_DATA_LEN]; // 值
WORDNODE *pNext;    // 下一结点
};

struct CHARNODE
{
char   cCur;   // 当前符号
WORDNODE *pWord;   // 单词节点
};

CHARNODE m_CharStack[1024];
int m_nCharTop = -1;

void InitCharStack()
{
m_nCharTop = -1;
}

void PushChar(char c, WORDNODE *pWord)
{
++m_nCharTop;
m_CharStack[m_nCharTop].cCur = c;
m_CharStack[m_nCharTop].pWord = pWord;
}

CHARNODE* PopChar()
{
return &m_CharStack[m_nCharTop--];
}

CHARNODE* TopChar()
{
return &m_CharStack[m_nCharTop];
}

void PrintCharStack()
{
int i;
for (i = 0; i <= m_nCharTop; i++)
   printf("%c", m_CharStack[i].cCur);
for (; i < 15; i++)
   printf(" ");
}


IntStack.h

// File Name: IntStack.h

int m_IntStack[1024];
int m_nIntTop = -1;

void InitIntStack()
{
m_nIntTop = -1;
}

void PushInt(int c)
{
m_IntStack[++m_nIntTop] = c;
}

int PopInt()
{
return m_IntStack[m_nIntTop--];
}

int TopInt()
{
if (m_nIntTop < 0)
   return '\0';
return m_IntStack[m_nIntTop];
}

void PrintIntStack()
{
int i;
for (i = 0; i <= m_nIntTop; i++)
   printf("%3d", m_IntStack[i]);
for (; i < 15; i++)
   printf("   ");
}



LR1.cpp

/ / LR1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "CharStack.h"
#include "IntStack.h"
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

struct BNFNODE // 产生式节点
{
char Left;      // 产生式左部
char Right[MAX_DATA_LEN]; // 产生式右部
int   RLen;      // 产生式右边长度
} m_Bnf[MAX_DATA_LEN];
int m_nBnfLen;

enum ACTIONTYPE // 动作类别
{
Push,   // 移进
Sumup,   // 规约
Accept,   // 接受
Error   // 出错
};

struct LR1TABLE
{
int   nStatus;   // 状态
char CurChar;   // 当前符号
ACTIONTYPE ActionType; // 动作类别
int   nNextStatus; // 下一状态
} m_Lr1[MAX_DATA_LEN];
int   m_nLr1Len;

/*****************************************************
* 以下是词法分析文件操作
******************************************************/
// 清空链表
void ClearWords(WORDNODE *pHeader)
{
WORDNODE *pNode;

while (pHeader != NULL)
{
   pNode = pHeader->pNext;
   free(pHeader);
   pHeader = pNode;
}
}

// 增加结点
WORDNODE* AddNode(char c[], WORDNODE *pTail)
{
// c第0个字节为单词类别，第1个为逗号，第2个以后是值

WORDNODE *pNode = (WORDNODE *)malloc(sizeof(WORDNODE));
pNode->byType = c[0] - '0';
pNode->pNext = NULL;

int nChars = MAX_DATA_LEN - 2;
memcpy(pNode->Value, &c[2], nChars);

pTail->pNext = pNode;
return pNode;
}

bool ReadWords(char FileName[], WORDNODE *pHeader)
{
// 打开文件 
FILE *f = fopen(FileName, "r");
if (f == NULL)
{
   ClearWords(pHeader);
   return false;
}

WORDNODE *pTail = pHeader;
char c[MAX_DATA_LEN];

// 读取数据
while (!feof(f))
{
   fscanf(f, "%s\n", c);
   pTail = AddNode(c, pTail);
   printf("%s\n", c);
}

// 关闭文件
fclose(f);

// 增加一个结束符
c[0] = WT_OPERATOR + '0';
c[1] = ',';
c[2] = '#';
c[3] = '\0';
AddNode(c, pTail);

return true;
}

/*****************************************************
* 以下是文法文件操作
******************************************************/
char *ReadFile(char FileName[], int *nLen)
{
// 打开文件
FILE *f = fopen(FileName, "r");
if (f == NULL)
   return NULL;

// 读取文件
char *pChar = (char *)malloc(sizeof(char) * MAX_DATA_LEN);

// 读取数据
int nRead;
*nLen = 0;
while (!feof(f))
{
   nRead = fread(pChar + *nLen, sizeof(char), MAX_DATA_LEN, f);
   *nLen += nRead;
   if (nRead < MAX_DATA_LEN) // 文件结尾
    break;

   pChar = (char *)realloc(pChar, *nLen + sizeof(char) * MAX_DATA_LEN);
}

// 关闭文件
fclose(f);

return pChar;
}

bool ReadBnfs()
{
// 读取文件
int nLen;
char *pChar = ReadFile("Bnf.txt", &nLen);
if (pChar == NULL)
   return false;

// 解析出文法产生式
int nBegin, nCur, nIndex = 0;
for (nBegin = 0, nCur = 0; nCur < nLen; nCur++)
{
   // 左部
   m_Bnf[nIndex].Left = pChar[nCur];

   // 右部
   nCur += 2;
   nBegin = nCur;
   for (; pChar[nCur] != ';'; nCur++);
   m_Bnf[nIndex].RLen = nCur - nBegin;
   memcpy(m_Bnf[nIndex].Right, pChar + nBegin, m_Bnf[nIndex].RLen);
   m_Bnf[nIndex].Right[m_Bnf[nIndex].RLen] = '\0';

   nIndex++;
}
m_nBnfLen = nIndex;

return true;
}

/*****************************************************
* 以下是LR(1)分析表文件操作
******************************************************/
ACTIONTYPE GetActionType(char c)
{
if (c >= '0' && c <= '9')
   return Push;

switch (c)
{
case 'S':
   return Push;
case 'r':
   return Sumup;
case 'a':
   return Accept;
}

return Error;
}

bool ReadLR1()
{
// 读取文件
int nLen;
char *pChar = ReadFile("Lr1.Lr1", &nLen);
if (pChar == NULL)
   return false;

// 解析出分析表
int nBegin, nCur, nIndex = 0;
for (nBegin = 0, nCur = 0; nCur < nLen; nCur++)
{
   // 状态
   m_Lr1[nIndex].nStatus = atoi(&pChar[nCur]);
   for (; pChar[nCur] != ';'; nCur++);
   nCur++;

   // 符号
   m_Lr1[nIndex].CurChar = pChar[nCur];
   nCur += 2;

   // 动作类别
   m_Lr1[nIndex].ActionType = GetActionType(pChar[nCur]);
   if (pChar[nCur] == 'a')
   {
    nCur += 3;
    m_Lr1[nIndex].nNextStatus = 0;
   }
   else
   {
    if (pChar[nCur] == 'S' || pChar[nCur] == 'r')
     nCur++;
    // 状态转换
    m_Lr1[nIndex].nNextStatus = atoi(&pChar[nCur]);
    for (; pChar[nCur] != ';'; nCur++);
   }

   nIndex++;
}
m_nLr1Len = nIndex;

return true;
}

/********************************************************
* 以下是语法分析部分
*********************************************************/
/************************************************
* 获取当前单词符号：
* 如果是整数或标识符，返回'i'
* 如果是算法，返回算法
*************************************************/
char GetCurChar(WORDNODE *pNode)
{
switch (pNode->byType)
{
case WT_OPERATOR: // 操作符
   return pNode->Value[0];
case WT_UINT:   // 整数
case WT_VARIABLE: // 变量
   return 'i';
}

return '\0';
}

int GetLR1Index(int nStatus, char a)
{
for (int i = 0; i < m_nLr1Len; i++)
{
   if (m_Lr1[i].nStatus == nStatus && m_Lr1[i].CurChar == a)
    return i;
}
return -1;
}

// 打印状态
void PrintState(WORDNODE *pNode, int nBnfIndex)
{
PrintIntStack();
PrintCharStack();

WORDNODE *pPrint = pNode;
int nCount = 0;
while (pPrint != NULL)
{
   printf("%c", GetCurChar(pPrint));
   pPrint = pPrint->pNext;
   nCount++;
}
for (; nCount < 12; nCount++)
   printf(" ");

if (nBnfIndex == -1)
{
   if (GetCurChar(pNode) == 'i')
    printf("i=%s", pNode->Value);
}
else
   printf("%c-->%s", m_Bnf[nBnfIndex].Left, m_Bnf[nBnfIndex].Right);

printf("\n");
}

bool LR1Analysis(WORDNODE *pHeader)
{
InitIntStack();
PushInt(0);//初始化状态栈

InitCharStack();
PushChar('#',NULL);//压入初始符号#

WORDNODE *T;
T=pHeader->pNext;// 指向第一个单词
    
PrintState(T,-1);//打印当前状态

while(true)
{
   int a=TopInt();
   char c=GetCurChar(T);
   int t=GetLR1Index(a,c);//根据状态栈栈顶符号和单词对应的文法符号查询分析表

     ACTIONTYPE A;
   A=m_Lr1[t].ActionType;
   if(A==Push)
   {
    PushInt(m_Lr1[t].nNextStatus); //压入分析表中的状态
    PushChar(m_Lr1[t].CurChar,T);//压入对应的文法符号
    T=T->pNext;//指向下一个单词
    PrintState(T,-1);//打印当前状态
   }
   else if(A==Sumup)
   {
    int nlen=m_Bnf[m_Lr1[t].nNextStatus].RLen;//根据产生式索引取得产生式右部长度nLen；
    for(int i=1;i<=nlen;i++)
    {
     PopInt();
     PopChar();
   
    }// 弹出nLen个状态和nLen个符号；

    PushChar(m_Bnf[m_Lr1[t].nNextStatus].Left,NULL);//将产生式左部压入符号栈；
    PrintState(T,m_Lr1[t].nNextStatus);

    int m=TopInt();

     
    int s=GetLR1Index(m,TopChar()->cCur);//根据状态栈栈顶状态和符号栈栈顶符号查询分析表，
                          //确定转移状态；
    if(s>=0)
  
     PushInt(m_Lr1[s].nNextStatus);
    
   
    else 
     return false;// 若转移状态存在，则压入状态栈；若不存在则返回false
   }//if(A==Sumup)
   else 
    if(A==Accept)
      return true; //若动作类别为接受（Accept）：返回true
    else
     return false;//若查询不成功（返回-1），返回false
}//while

}//LR1Analysis

int main(int argc, char* argv[])
{
// 输入文件名
char FileName[MAX_DATA_LEN];
printf("请输入词法分析的文件名：\n");
scanf("%s", FileName);

// 读取文件
printf("单词序列：\n");
WORDNODE *pHeader = (WORDNODE *)malloc(sizeof(WORDNODE));
if (!ReadWords(FileName, pHeader))
{
   printf("读取词法分析文件失败！\n");
   ClearWords(pHeader);
   return 0;
}

// 读取文法
if (!ReadBnfs())
{
   printf("读取产生式失败！\n");
   ClearWords(pHeader);
   return 0;
}

// 读取LR(1)分析表
if (!ReadLR1())
{
   printf("读取LR(1)分析表失败！\n");
   ClearWords(pHeader);
   return 0;
}

// 语法分析
printf("语法分析过程：\n");
printf("状态栈                                       归约串         输入串      产生式\n");
if (LR1Analysis(pHeader))
   printf("语法分析成功！\n");
else
   printf("语法分析失败！\n");

// 清空链表
ClearWords(pHeader);

getchar();
getchar();

return 0;
}