用yacclex设计实现小型basic语言.txt

本文包含简单中文说明和详细源代码

 

用YACC/LEX 设计计算机Basic语言

 

作者：王晓智

 

简介：使用 YACC/LEX 设计计算机语言的介绍和例子，同时对 YACC/LEX 的不同平台下的实现做了介绍。

 

关键词：YACC ，LEX，计算机语言。

 

前言：

YACC （Yet Another Compiler Compiler） 是1974年在 Unix 下设计出来的一个优秀的计算机语法分析工具。LEX 是相应的词法分析工具。在 Linux 下，也有 YACC/LEX 的实现版本及相关资料。通过这套工具，可以在只编写出计算机语言的语法后，就可以生成自底向上的语法分析程序（词法分析类似），可以大大加快计算机语言的实现速度。

 

Turbo Pascal/Free Pascal/Delphi 程序员请注意： Pascal 语言下的 YACC/LEX 实现可以在 http://www.musikwissenschaft.uni-mainz.de/~ag/tply/ 地址下找到详细信息。

 

有关YACC 和 LEX 的语法我们附在后面。这里，我们主要讨论一个具体的语言（如 Basic），如何用 YACC/LEX 编程实现。 代码存放在 www.ffvec.com 下的下载栏目中（c语言，用GCC 编译通过），可以任意使用，其它的源代码和例子也可以在那里找到。

 

有关问题：

 

1、  首要问题：编译还是解释。如果选择编译，那么生成了目标机器上的可执行代码。如果选择解释，那么在解释过程中（或完成后）执行中间代码。Java和.NET 已经混淆了这两方面的区分。

2、  数据属性问题：一个普通的编译/解释器必须随时跟踪变量、表达式的数据类型、作用范围等问题。最头疼的就是数据类型了。因为编译/解释器必须自己处理不同数据类型的转换工作，如果有六种数据类型如 Char、Byte、SmallInt、Word、LongInt、Dword，就必须处理32种计算方法。所以现在新的的语言如（VBScript 等）都采用了 Variant 数据类型，这样在计算过程中，不需要考虑过多的数据类型转换问题，在执行时才做类型检查。因为我们当时还不知道GCC的 Lib 中支持 Variant 数据类型，因此自己实现了Variant数据类型。

 

// Variant 数据类型

#define NOTYPE 0

#define CHARTYPE 1

#define BYTETYPE 2

#define INTEGERTYPE 3

#define DWORDTYPE 4

#define REALTYPE 5

#define STRINGTYPE 6

#define INFOTYPE 7

 

#define TMPSTRINGSIZE 128

 

/* Variant Structure */

 

typedef struct {

        int ValueType;

        union {

                Char Character;

                Byte BYTE;

                int Integer;

                DWord DWORD;

                double Real;

                PTString pString;

                void *pInfo;

        } Value;

} TVariant, *PVariant;

 

// Variant 过程

PVariant VarNew(void);

void VarFree(PVariant p);

int VarGetType(PVariant p);

void VarSetType(PVariant p,int tp);

void VarAssign(PVariant dest,PVariant src);

Char VarGetChar(PVariant p);

Byte VarGetByte(PVariant p);

int VarGetInteger(PVariant p);

DWord VarGetDWord(PVariant p);

double VarGetReal(PVariant p);

Char *VarGetString(PVariant p);

void *VarGetInfo(PVariant p);

void VarSetChar(PVariant p,Char c);

void VarSetByte(PVariant p,Byte b);

void VarSetInteger(PVariant p,int n);

void VarSetDWord(PVariant p,DWord d);

void VarSetReal(PVariant p,double e);

void VarSetString(PVariant p,Char *s);

void VarSetInfo(PVariant p,void *q);

 

int VarTypeCast(PVariant p,int datatype);

int VarMakeEqual(PVariant a,PVariant b);

 

void VarStrSetLength(PVariant p,DWord len);

void VarStrCompress(PVariant p);

DWord VarStrlen(PVariant p);

void VarStrToUpper(PVariant p);

void VarStrToLower(PVariant p);

int  VarStrCompare(PVariant p,PVariant q);

int VarStrCompareCase(PVariant p,PVariant q);

void VarStrAssign(PVariant dest,PVariant src);

void VarStrCat(PVariant dest,PVariant src);

void VarStrDelete(PVariant p,DWord begin,DWord len);

void VarStrGetChar(PVariant p,DWord offset);

void VarStrSetChar(PVariant p,DWord offset,Char c);

DWord VarStrLocChar(PVariant p,DWord begin,Char c);

DWord VarStrSubStr(PVariant p,PVariant sub);

 

 

3、  符号表：符号表用来登记各种常量、变量、函数、过程、结构的有关属性，因为一些数据类型是其它数据类型的导出，所以这里采用二叉数存放、检索信息。为了解决导出类型问题，此二叉数必须穿线。

 

typedef enum {

        eNoDefine,eConstDefine,eTypeDefine,eVarDefine,eValParamDefine,

        eVarParamDefine,eFieldDefine,

        eProgDefine,eFuncDefine,eProcDefine

} TDefineKey;

 

typedef enum {

        eDeclare,eForward,eStandard

} TRoutineKey;

 

typedef enum {

        eNoForm,eScalarForm,eEnumForm,eSubRangeForm,

        eArrayForm,eRecordForm

} TypeForm;

 

typedef struct {

        TDefineKey Key;

        union {

                PVariant pValue;  

                struct {

                        TRoutineKey Key;

                        int ParamCount;

                        int TotalParamSize;

                        int TotalLocalSize;

                        struct tagTSymbolTable *Params;

                        struct tagTSymbolTable *Locals;

                        struct tagTSymbolTable *LocalSymtab;

                        void *CodeSegment;

                } Routine; 

                struct {

                        int Offset;

                        struct tagTSymbolTable *RecordIDP;

                } Data; 

        }Info;

} TDefineStruct, *PDefineStruct;

 

typedef struct tagTypeStruct {

        TypeForm Form;

        int Size;

        struct tagTSymbolTable *TypeIDP;

        union {

                struct {

                        struct TypeStruct *ConstIDP;

                        int Max;

                } Enum;

                struct {

                        struct tagTypeStruct *IndexType,*ElemType;

                        int MinIndex,MaxIndex;

                        int ElemCount;

                } Array;

                struct {

                        struct tagTSymbolTable *FieldSymtab;

                } Record;

        } Info;

} TypeStruct, *PTypeStruct;

 

typedef struct tagTSymbolTable {

        char *Name;

        struct tagTSymbolTable *Left,*Right,*Next;  // 穿线二叉数

        char *Info;

        TDefineStruct Define;

        PTypeStruct TypeP;

        int Level;

        int LabelIndex;

} TSymbolTable, *PSymbolTable;

 

PSymbolTable NewSymtab(char *s);

void InitSymtabRoot(void);

 

extern TSymbolTable Root;

 

PSymbolTable SearchSymtab(char *s);

PSymbolTable EnterSymtab(char *s);

 

DWord GetVar(char *s);

void EnterVar(char *s,DWord index);

 

4、  虚拟计算机：如果生成的代码目标平台无法执行或执行有困难，可以考虑生成虚拟计算机的代码，然后用自己的虚拟计算机执行。我们这里的虚拟计算机采用了栈结构方式。可以使 YACC 在分析过程中同步生成代码。我们的虚拟机器代码和JAVA很相似（JAVA在 SUN 中的实现，起初肯定是YACC）。这台虚拟计算机连Print 命令都认识。

 

// 计算机的标志寄存器和控制寄存器

 

typedef struct tagTFlags {

        Char EQ,NE,LE,LT,GE,GT;

        Char Debug,Trace,Step;

} TFlags;

 

// 只有四个寄存器：当前代码地址、堆栈顶部、Stack  Frame Top、标志及控制。

typedef struct tagTCPU {

        DWord EIP;

        DWord ESP;

        DWord EBP;

        TFlags Flags;

} TCPU, *PCPU;

 

// 全局的 CPU 变量

extern TCPU CPU;

 

// CPU 的动作

void Reset(void);

void Start(void);

void DeCode(DWord d);

void SetFlags(double r);

void Print(PVariant p);

void EnterProc(DWord n); 

void LeaveProc(void);

 

void PushChar(Char c);

void PushByte(Byte b);

void PushInteger(int value);

void PushDWord(DWord d);

void PushReal(double r);

void PushString(char *s);

void PushVar(PVariant p);

PVariant PopVar(void);

PVariant GetTosVar(void);

 

// CPU 认识的指令

#define C_PUSHCHAR 101

#define C_PUSHBYTE 102

#define C_PUSHINTEGER 103

#define C_PUSHDWORD 104

#define C_PUSHREAL 105

#define C_PUSHSTRING 106

 

#define C_PUSHVAR 110

 

#define C_POPVAR 120

#define C_POPCMP 121

 

#define C_RELOP 200

#define C_ADDOP 201

#define C_MULOP 202

#define C_SIGNOP 203

 

#define C_PRINT_LINE 300

#define C_PRINT_COMMA 301

#define C_PRINT_SEMICOLON 302

#define C_PRINT_EXPR 303

 

#define C_JMP 400

#define C_JEQ 401

#define C_JNE 402

 

 

5、  词法分析：我们使用LEX来做词法分析，查看LEX的代码后发现，它本身是用YACC生成的，很有意思。

 

extern YYSTYPE yylval;

 

int yywrap(void) {

        return 1;

}

void SetReal(double r) {

        yylval.Real=r;

        yylval.Info.Type=REALTYPE;

}

void SetInteger(int n) {

        yylval.Integer=n;

        yylval.Info.Type=INTEGERTYPE;

}

void SetDWord(DWord n) {

        yylval.UnsignedNumber=n;

        yylval.Info.Type=DWORDTYPE;

}

void SetString(char *s) {

        yylval.String=strdup(s);

        yylval.Info.Type=STRINGTYPE;

}

/*         Delete any character in yyrval, normally is

        doublequota in string, etc:

        "AAAAA""aaaaaaa" =>  AAAAA"aaaaaaa

*/

void DeleteChar(char c) {

char *s;

int i,j;

        s=yylval.String;

        i=strlen(s);

        i-=2;

        memmove(s,s+1,sizeof(Char)*i);

        s[i]=0;

        if(strlen(s)<2)

                return;

        for(i=0,j=0;*(s+j);i++,j++) {

                *(s+i)=*(s+j);

                if((*(s+j)==c)&&(*(s+j+1)==c))

                        j++;

        }

        *(s+i)=0;

}

 

%}

SPACE         [ \r\n\t\f]

NQUOTE         [^\"\n]

Digit        [0-9]

DecDigit [1-9]

Zero        [0]

OctDigit [0-7]

HexPrev        [x|X]

HexDigit [0-7A-Fa-f]

Char        [ -~]

Letter        [A-Za-z_]

Id        [A-Za-z0-9_]

 

%%

 

"=="        { SetInteger(EQUAL);return EQUAL; }

"="        { SetInteger(ASSIGN);return ASSIGN; }

"<"        { SetInteger(LT);return LT; }

"<="        { SetInteger(LE);return LE; }

"<>"        { SetInteger(NE);return NE; }

">="        { SetInteger(GE);return GE; }

">"        { SetInteger(GT);return GT; }

"+"        { SetInteger(PLUS);return PLUS; }

"-"        { SetInteger(MINUS);return MINUS; }

"*"        { SetInteger(STAR);return STAR; }

"/"        { SetInteger(SLASH);return SLASH; }

"%"        { SetInteger(MOD);return MOD; }

"<<"        { SetInteger(SHL);return SHL; }

">>"        { SetInteger(SHR);return SHR; }

"&"        { SetInteger(BITAND);return BITAND; }

"|"        { SetInteger(BITOR);return BITOR; }

"!"        { SetInteger(BITNOT);return BITNOT; }

"("        { SetInteger(LPAREN);return LPAREN; }

")"        { SetInteger(RPAREN);return RPAREN; }

"["        { SetInteger(LBRACKET);return LBRACKET; }

"]"        { SetInteger(RBRACKET);return RBRACKET; }

"{"        { SetInteger(BIGLPAREN);return BIGLPAREN; }

"}"        { SetInteger(BIGRPAREN); return BIGRPAREN; }

","        { SetInteger(COMMA);return COMMA; }

";"        { SetInteger(SEMICOLON);return SEMICOLON; }

":"        { SetInteger(COLON);return COLON; }

"."        { SetInteger(DOT);return DOT;}

 

"and"        { SetInteger(AND);return AND; }

"not"        { SetInteger(NOT);return NOT; }

"or"        { SetInteger(OR);return OR; }

 

"dim"        { SetInteger(DIM);return DIM; }

"array" { SetInteger(ARRAY);return ARRAY; }

"as"        { SetInteger(AS);return AS; }

"byval" { SetInteger(BYVAL);return BYVAL;}

"case"  { SetInteger(CASE);return CASE; }

"const" { SetInteger(CONST);return CONST; }

"function" { SetInteger(FUNCTION);return FUNCTION;}

"goto"  { SetInteger(GOTO);return GOTO;}

"label"        { SetInteger(LABEL);return LABEL;}

"procedure" { SetInteger(PROCEDURE);return PROCEDURE;}

"program" { SetInteger(PROGRAM);return PROGRAM; }

 

"char"          { SetInteger(CHAR);return CHAR; }

"byte"    { SetInteger(BYTE);return BYTE; }

"integer" { SetInteger(INTEGER);return INTEGER; }

"dword"   { SetInteger(DWORD);return DWORD; }

"real"          { SetInteger(REAL);return REAL; }

"string"  { SetInteger(STRING);return STRING; }

 

 

"if"        { SetInteger(IF);return IF; }