bianyi .txt

一些编译原理词法分析和语法分析的源程序,比较深,因为编译本身比较难,所以适合学习编译有一定时间的人学习

这学期的编译原理课语法分析已经快讲完了。整个编译器的前端主要就包括了词法分析和语法分析两个部分。现在自己开始着手用C语言写编译器的前端。以下是程序的说明。
1）该程序是词法分析部分Lexical Analyse。
2）只支持无符号整数类型。不支持数组和指针等高级特性。
3）不支持函数。注释为C++式的“//”。
4）使用VC++.NET编译。
//////////////////////////////Lexical.h////////////////////////////////////
#ifndef _LEXICAL_H_
#define _LEXICAL_H_

//状态机状态枚举
typedef enum {START=0,UNKNOWN=0,COMMENT,NUMBER,IDENTI,IF,ELSE,END,REPEAT,UNTIL,ASSIGN,EQUAL,PLUS,MINUS,MULTI,DIVIDE,LESS,GREATER,LPAREN,RPAREN,SEMI,EXPRESSION} LexTokenType;
//状态转换结构
typedef struct {LexTokenType beg; char Domainbeg; char Domainend; LexTokenType end;} TransState;
//关键字描述结构
typedef struct {char strExp[10]; LexTokenType type;} TokenDes;
//记号结构
typedef struct {char *strName; LexTokenType type;} LexToken;

LexToken* GetNextToken(char *pSource);

#endif//_LEXICAL_H_
//////////////////////////////Lexical.c////////////////////////////////////
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "lexical.h"

//有限状态机状态转换描述
TransState trans[] ={
    {NUMBER,'0','9',NUMBER},
    {IDENTI,'A','Z',IDENTI},
    {IDENTI,'a','z',IDENTI},
    {IDENTI,'0','9',IDENTI},
    {START,' ',' ',START},
    {START,'\t','\t',START},
    {START,'\n','\n',START},
    {START,'\r','\r',START},
    {START,'0','9',NUMBER},
    {START,'A','Z',IDENTI},
    {START,'a','z',IDENTI},
    {START,'+','+',PLUS},
    {START,'-','-',MINUS},
    {START,'*','*',MULTI},
    {START,'/','/',DIVIDE},
    {START,'<','<',LESS},
    {START,'>','>',GREATER},
    {START,'(','(',LPAREN},
    {START,')',')',RPAREN},
    {START,';',';',SEMI},
    {START,'=','=',ASSIGN},
    {DIVIDE,'/','/',COMMENT},
    {COMMENT,'\n','\n',START},
    {COMMENT,'\n'+1,127,COMMENT},
    {COMMENT,1,'\n'-1,COMMENT},
    {COMMENT,-128,-1,COMMENT},
    {ASSIGN,'=','=',EQUAL},
};

//关键字(保留字)描述
TokenDes reserve[] ={
    {"if",IF},
    {"else",ELSE},
    {"end",END},
    {"repeat",REPEAT},
    {"until",UNTIL},
};

LexToken* GetNextToken(char *pSource)
{//考虑速度，不检测file合法性
    static int LineNO = 0;
    static int PosNow = 0;
    static int SizeStateTrans = sizeof(trans)/sizeof(TransState);
    static int SizeReserve = sizeof(reserve)/sizeof(TokenDes);
    static int SizeToken = sizeof(LexToken);
    LexToken *ptoken = NULL;
    LexTokenType CurState = START;
    int PosStart = PosNow;
    int i,j,tokenlen=0;
    char ch;
    ptoken = (LexToken*)malloc(SizeToken);//省略错误检查
    while (1)
    {
        ch = pSource[PosNow];
        if (ch == '\n')//如果碰到回车字符,行号加1
            LineNO++;
        for (i=0; i<SizeStateTrans; i++)
        {
            if ((CurState==trans[i].beg) && (ch>=trans[i].Domainbeg) && (ch<=trans[i].Domainend))//满足该状态转换
            {
                CurState = trans[i].end;//转换到该状态
                break;//跳出for循环，准备察看下一个字符
            }
        }
        if (i == SizeStateTrans)//未找到合适的状态转换
        {
            if (CurState == START)//如果开始于START状态
            {
                if (ch == '\0')//遇到文件尾
                {
                    free(ptoken);
                    return NULL;
                }
                ptoken->type = UNKNOWN;//认定为：遇到未知字符
                ptoken->strName = NULL;
                return ptoken;
            }
            else//找到一个新的记号
            {
                if (CurState == COMMENT)//这种情况出现在代码以注释结束时
                {
                    free(ptoken);
                    return NULL;
                }
                tokenlen = PosNow - PosStart;
                ptoken->strName = (char*)malloc(tokenlen+1);
                strncpy(ptoken->strName, pSource+PosStart, tokenlen);
                ptoken->strName[tokenlen] = '\0';
                ptoken->type = CurState;
                if (ptoken->type == IDENTI)//如果该记号被认为是标识符
                {
                    for (j=0; j<SizeReserve; j++)
                    {
                        if (!strcmp(ptoken->strName, reserve[j].strExp))//如果在关键字中找到该标识符
                        {
                            ptoken->type = reserve[j].type;
                            break;
                        }
                    }
                }
                return ptoken;
            }
        }
        else//转换了状态
        {
            PosNow++;//消耗掉该字符
            if (CurState == START)//如果又转换到了START状态
                PosStart = PosNow;
        }
    }
}
///////////////////////////////////main.c////////////////////////////////////////
#include <windows.h>
#include <stdio.h>
#include "Lexical.h"

int main ()
{
    HANDLE file = CreateFile("source.txt",GENERIC_READ,0,NULL,OPEN_EXISTING,0,NULL);
    long size = GetFileSize(file,NULL);
    char *pBuffer = (char*)malloc(size+1);
    long sizenow;
    LexToken* ptoken;
    ReadFile(file,pBuffer,size,&sizenow,NULL);
    pBuffer[size] = '\0';
    while (ptoken=GetNextToken(pBuffer))
    {
        printf("%10s,  %d\n",ptoken->strName,ptoken->type);
    }
    return 0;
}
//////////////以下是测试文本(ANSI格式)///////////////////
//用来测试程序，这里是注释
if today is monday
and 1+1=23
2123/4==6
///////////////////以下是输出(节点名称和节点类型编号)/////////////////////////
        if,  4
     today,  3
        is,  3
    monday,  3
       and,  3
         1,  2
         +,  11
         1,  2
         =,  9
        23,  2
      2123,  2
         /,  14
         4,  2
        ==,  10
         6,  2

-----------------------------------

关于Basic程序解释器及编译原理的简单化(2)---C++封装好的Basic解释器 
 
 
 
分类导航 
 
 
   关于Basic程序解释器及编译原理的简单化(2)---C++封装好的Basic解释器 
这是CMake的源代码.主要负责词汇的提取
你可以调用它的CMake::get_token(),返回个CToken的类.

/////////////////////////////////////////////////////
// Make.h
///////////////////////////////////////////////////

enum token_types{DELIMITER,VARIABLE,NUMBER,COMMAND,
             STRING,QUOTE,FINISHED,NONE,ENTER};         // 标记类型集合


#define TOKEN_MAX 80
#define STRDELIMITER "+-*^/=;(),><" // 符号集合
#define DIM     11 // Dim
#define AS      12 // As
#define INTEGER 13 // Integer
#define PRINT   14 // Print

class CToken 
{
public:
 char token[TOKEN_MAX];
 int token_type;
 int tok;
};

class CMake  
{
public:
 CMake(char *Prog,int Proglength);
 virtual ~CMake();
public:
    char *prog;
 int proglength;
 int isdelim(char c);     // 如果是运算符号返回1,不是则返回0
 int iswhite(char c);     // 是空格返回1,不是则返回0
 int look_up(char *c);    // 返回COMMAND类型,c是COMMAND字符串的指针
 CToken get_token(void);   // 得到标记
 int findchar(char *str,char ch); // 从str里找到ch,返回其在str里的引索;如果str里没有ch,则返回-1
};

/////////////////////////////////////////////////////////////////////

 

 

// Make.cpp: implementation of the CMake class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Make.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CMake::CMake(char *Prog,int Proglength)
{
  proglength=Proglength;
  prog=new char[Proglength+1];
  strcpy(prog,Prog);
}

CMake::~CMake()
{
 
}


CToken CMake::get_token(void) 
{
 register char *temp;
 CToken m_token;
    m_token.token_type=0;
 m_token.tok=0;
 temp=m_token.token;
 if(*prog=='')
 {
  *m_token.token='';
  m_token.tok=0;
  m_token.token_type=FINISHED;
  return m_token;
 }
 while(iswhite(*prog)) ++prog;
    
 if(*prog==' ') // 如果是换行符
 {
  m_token.token[0]=*prog;
  m_token.token[1]='';
  m_token.token_type=ENTER;
  prog++;
  return m_token;
 }
 if( isdelim(*prog)) // 如果找得到运算符号标记
 {
    *m_token.token=*prog; 
    *(m_token.token+1)='';
    m_token.tok=0;
    m_token.token_type=DELIMITER;
    prog++;
    return m_token;            // 譬如 token[0]='+' token[1]='';
 }

 if(*prog=='"')   // 如果是字符串
 {
  prog++;
  int i=0;
  while(*prog!='"' && *prog!=' ')
  {
   m_token.token[i]=*prog;
   i++;
   prog++;
  }
  prog++;
  m_token.token[i]='';
  m_token.token_type=QUOTE;
  return m_token;
 }

 if( isdigit(*prog)) // 如果找到数字标记
 {
  int i=0;
  while(isdigit(*prog) && i<TOKEN_MAX) // 小于token最长为80个字符
  {
   m_token.token[i]=*prog;
   i++;
   prog++;
  }
  m_token.token[i]='';
  m_token.token_type=NUMBER;
  return m_token;
 }
 if( isalpha(*prog)) // 如果是命令COMMAND或是一般标记STRING
 {
  int i=0;
  while(!isdelim(*prog) && *prog!=' ') // 不能是运算符号和空格
  {
   m_token.token[i]=*prog;
   i++;
   prog++;
  }
  m_token.token[i]='';
  if(look_up(m_token.token)) // 如果能查到它是命令COMMAND
  {
   m_token.token_type=COMMAND;
   m_token.tok=look_up(m_token.token);
  }
  else
  {
   m_token.token_type=STRING;
  }
  return m_token;
 }
 

 m_token.token_type=NONE;
 prog++;
 return m_token;
}

int CMake::iswhite(char c)
{
 if(c==' '||c==' ') return 1;
 else return 0;
}

int CMake::isdelim(char c)
{
 if( findchar(STRDELIMITER,*prog) >= 0 || c==9 || c==' ' || c==0)
  return 1;
 return 0;
}

int CMake::findchar(char *str,char ch) 
{
 int length=strlen(str);
 if(length>0)
 {
  for(int i=0;i<length;i++)
   if(str[i]==ch)
      return i;
   return -1;
 }
 else return -1;
}

int CMake::look_up(char *c)
{
 if(strcmp(c,"print")==0)
  return PRINT;
    if(strcmp(c,"Integer")==0)
  return INTEGER;
 if(strcmp(c,"Dim")==0)
  return DIM;
 if(strcmp(c,"As")==0)
  return AS;

    return 0;
}

这是执行代码的CExecutable封装

//////////////////////////////////////////////////
// CExecutable.h
////////////////////////////////////////////////

class CintMember
{
public:
 char name[64];
 int value;
};

class CExecutable  
{
public:
 CExecutable(vector <CToken> tokens);
 virtual ~CExecutable();
 void Run();
private:
 vector <CToken> m_tokens; file://装所有标记的数据库
 vector <CintMember> m_intArray; file://装所有int类型的变量
 void Run_Print(int *index); file://*index是重要的m_tokens里的指针
 void Run_Dim(int *index); file://~~ 
 void Run_Assignment(int *index);// 赋值语句
 file://Ai是辅助的意思,Ai_*()是辅助函数
 int Ai_GetNextValue(void* result,int type,int *index); file://得到代数式的值result
 int Ai_GetVarNo(char *name,int *result,int type);//得到变量在Array中的引索result
 void get_exp(int *result,int *index);
 void level2(int *result,int *index);
 void level3(int *result,int *index);
 void level4(int *result,int *index);
 void level5(int *result,int *index);
    void level6(int *result,int *index);
 void primitive(int *result,int *index);
 void arith(char o,int *r,int *h);
 void serror(int error);
 int look_up(char *c);
 int find_var(char *var_name,void *value); // 查找变量,将变量值装在*value
 int Isvar(char *name); // 看name是否是变量,返回变量类型 0:什么都不是,1:Integer,2:string
};


/////////////////////////////////////////

// Executable.cpp: implementation of the CExecutable class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Executable.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CExecutable::CExecutable(vector <CToken> tokens)
{
 m_tokens=tokens;
}

CExecutable::~CExecutable()
{
 m_intArray.clear();
 m_tokens.clear();
}

void CExecutable::Run(void)
{
   for(int i=0;i<=m_tokens.size()-1;i++)//注意:i是个十分重要的读取指针
   {
  if(m_tokens.at(i).token_type==COMMAND)
  {
   switch(m_tokens.at(i).tok) file://tok表示是什么命令
   {
   case PRINT: Run_Print(&i);
         break;
   case DIM:   Run_Dim(&i);
            break;
   default:   break;
   }
  }
  file://赋值语句一定要在最后来判断,因为这样如果是if后的条件判断就可以在
  file://前面的if命令中跳过
  if(*m_tokens.at(i).token=='=') file://如果是赋值语句
   Run_Assignment(&i);
   }
}

void CExecutable::Run_Print(int *index) file://*index是m_tokens里的指针
{
 if(*index<m_tokens.size()-1) // 如果下面还有token
 {   
  if(m_tokens.at((*index)+1).token_type==ENTER) file://如果接下来是命令
  {
   printf(" ");
   return;
  }
  (*index)++;   
  int token_type=m_tokens.at(*index).token_type;
  if(Isvar(m_tokens.at(*index).token)) file://如果接下来是变量
   token_type=VARIABLE; 
        
  switch(token_type)
  {
  case QUOTE: file://如果是要打印字符串
   {
    printf(m_tokens.at(*index).token);
    return;
   }
  case VARIABLE:  file://打印代数式 type只要不是COMMAND就是可以当代数式处理
  case NUMBER:
  case DELIMITER:     
   {
    int result;
          Ai_GetNextValue(&result,INTEGER,index);
    printf("%d",result);
    return;
   }
  default: printf(" ");
     return;
  }
 }
 printf(" "); 
 
}

void CExecutable::Run_Dim(int *index) file://~~
{
 int i=*index;
 if(i<m_tokens.size()-1)//~~
  if(m_tokens.at(i+1).token_type==STRING)
  {
   if(i<m_tokens.size()-3) file://如果下面还应该有 变量名,As,类型 三个tokens
   {
    CintMember member;
    if(m_tokens.at(i+2).token_type==COMMAND && 
     m_tokens.at(i+2).tok==AS) file://如果接下来的token是As
    {
    if(m_tokens.at(i+3).token_type==COMMAND)//接下来是变量类型
     switch(m_tokens.at(i+3).tok) file://看看是什么变量类型
     {
          case INTEGER: // 如果是Integer类型
        strcpy(member.name,m_tokens.at(i+1).token);
        member.value=0;
        m_intArray.push_back(member);
        *index+=3; // 将m_tokens里的指针跳3个
        break;
          default:     
        break;
     }
    }
   }
  }
}

void CExecutable::Run_Assignment(int *index) file://index必须指到'='的token
{
 int var_type=Isvar(m_tokens.at(*index - 1).token);
 if(!var_type) // 如果等号前面不是个变量
 {
  serror(0);
  return;
 }
 switch(var_type)
 {
 case INTEGER:
  {
   int Var_No,value;
   if(!Ai_GetVarNo(m_tokens.at(*index-1).token,&Var_No,INTEGER))
               break;
   (*index)++;
            if(!Ai_GetNextValue(&value,INTEGER,index))
      break;
   m_intArray.at(Var_No).value=value;
   break;
  }
 default: break;
 }
}

 

int CExecutable::Ai_GetNextValue(void *result,int type,int *index) file://index指到代数式的第一个token
{