CGen：用最原始的方法生成中间指令

CGen是自己的一个最近要实现的库,能够在小范围自由度的情况下配置C89的语法的编译器生成器（期间不直接用到语法树adt）。

这几天开始投入，目前只做了一点点（等能支持80%左右的C89，再提供代码下载）。

1、词法分析器全程hash（一开始的词法分析效率是每240万个词法标记需要780ms左右，后来发现这其实是重复了1000次内部预处理的结果，如果是直接240万个词法标记一次性扫描完的话，效率估计应该在每240万个词法标记需要200ms以内的时间）。
2、语法分析器的一部分（越到后面，越发现，如果自己做的功能比C89还强大应该不难，但是要严格按照C89去实现功能所有细节，就有阻力了，因为它不是自动一条规则在起作用）
3、期间发现C/C++几乎是唯内存分配是从，你可以在不引起内存冲突的情况下做如下事情：
         a、定义一个未声明和定义的结构体类型的指针
                      struct fuckfuck * fuck2; /* fuckfuck 从未在代码里涉及,按照vc的说法- -bnr 其实关乎一种对称美的东西. */
         b、定义一个没定义的enum类型(这一点gcc是不允许的,但是tc和vs2008的c和C++编译器是允许的)
                      enum fuckfuck fuck2;
         c、union由于在没定义类型之前无法确定内存大小，所以和enum有所不同。
4、到后面我认为本来很容易解决的比如inc和dec等等运算符，由于涉及到更加奇妙的细节而增加了考虑的时间：
         a、左结合递增（a++）和右结合的递增(++a)除了在更新a的值的阶段有所不同外，还有不同的是（C++与C89之间的不同）：
                   ++(++a); C中会报错,C++中不会报错
                   ++(a++); C中会报错,C++中也会报错
                    对于这种对应具备提前、延迟语义的IL的生成，我之前想了几种方法，不过都会让token读取look back,后来想到一种利用临时栈的方法插入指令，可以做到线性生成关于它的IL。
5、对于优化指令，我觉得那个最好还是等全部都生成好了再搞更为妥当，匹配可优化的指令模式应该不会有很大问题。
6、为了尽量避免后期的其它bug,预先定义了很多东西。
7、目前还没开始做CGenVM，不过那个东西由于我的IL还是很简化的，不会有很大问题了。
8、写到此处，我认为，考虑到一些C语言很复杂的隐性语法内容，比如很自由的语法组合和多级函数指针、以及地址引用与解引用神马的，如果严格按照C89去实现，那么投入的时间应该比写一个按自己便捷情况设计的OO语言编译器要付出更多。

代码如下：

/*CGen.cpp :vgl::CGen*/
2

/*----------------------------------------------------------------------------
3

Simple v1.2
4

Developer: Zblc
5

vgl::numberSystem
6

namespace:
8

CGen ：C89中间代码编译器生成器
9

classes:
12

Scanner ：词法分析器
13

Parser ：分析器
14

(内部聚合类不一一列出)
15

macros:
17

#define DEBUG_EXPECT(_mark) ：词法不匹配报错
18

#define DEBUG_NOTIDENT(_mark) ：未定义的词法标记
19

#define DEBUG_CGEN ：调试信息控制
20

global variable:
22

include:
25

iostream ：用于调试信息输出
26

--------------------------- --------------------------------------------------*/
27

#include <iostream>
28

#define DEBUG_CGEN
31

namespace CGen/* C中间代码生成 */
36

{
37

typedef wchar_t VWord;
39

typedef unsigned char VSmallSize;
40

typedef int VBigSize;
41

typedef short VBool;
42

enum eToken/* Token分类 */
45

{
46

T_LeftBrace, /* { */
47

T_RightBrace,/* } */
48

T_LeftSBrace, /* ( */
49

T_RightSBrace, /* ) */
50

T_LeftMBrace, /* [ */
51

T_RightMBrace, /* ] */
52

T_UserIdent, /* [_\b]+[_\d\b]* */
53

T_If,/* if */
54

T_Else,/* else */
55

T_Star,/* * */
56

T_Shop,/* # */
57

T_Include,/* include */
58

T_Define,/* define */
59

T_Do,/* do */
60

T_Semicolon,/* ; */
61

T_Comma,/* , */
62

T_Dot,/* . */
63

T_Arrow,/* -> */
64

T_Minus,/* - */
65

T_Add,/* + */
66

T_Div,/* / */
67

T_Mod,/* % */
68

T_QMark,/* ? */
69

T_Colon,/* : */
70

T_BitComplement,/* ~ */
71

T_Not,/* ! */
72

T_NotEqu,/* != */
73

T_Equ,/* == */
74

T_LargeThan,/* > */
75

T_LessThan,/* < */
76

T_EquLargeThan,/* >= */
77

T_EquLessThan,/* <= */
78

T_AssiAdd,/* += */
79

T_AssiMinus,/* -= */
80

T_AssiMul,/* *= */
81

T_AssiOr,/* |= */
82

T_AssiAnd,/* &= */
83

T_AssiExOr,/* ^= */
84

T_AssiDiv,/* /= */
85

T_AssiMod,/* %= */
86

T_Enum,/* enum */
87

T_Struct,/* struct */
88

T_Assi,/* = */
89

T_Addr,/* & */
90

T_LogicAnd,/* && */
91

T_LogicOr,/* || */
92

T_BitOr,/* | */
93

T_BitExOr,/* ^ */
94

T_Return,/* return */
95

T_Void,/* void */
96

T_Float,/* float */
97

T_Double,/* Double */
98

T_Int,/* int */
99

T_Unsigned,/* unsigned */
100

T_Signed,/* signed */
101

T_Auto,/* auto */
102

T_Static,/* static */
103

T_Register,/* register */
104

T_Extern,/* extern */
105

T_Break,/* break */
106

T_Continue,/* continue */
107

T_Case,/* case */
108

T_Switch,/* Switch */
109

T_Default,/* default */
110

T_For,/* for */
111

T_Volatile,/* volatile */
112

T_Const,/* const */
113

T_Sizeof,/* sizeof */
114

T_Typedef,/* typedef */
115

T_Union,/* union */
116

T_Long,/* long */
117

/* T_SinQuo,//' */
118

/* T_DouQuo,//" */
119

//T_LeftComment,
120

//T_RightComment,
121

T_Character,
122

T_String,
123

T_Integer,
124

T_Real,
125

T_Char,
126

T_Inc,
127

T_Dec,
128

T_Connect,
129

T_LeftBit,
130

T_RightBit,
131

T_AssiLeftBit,
132

T_AssiRightBit,
133

T_While,
134

T_END_
135

};
136

137

138

139

struct stToken
140

{
141

eToken e;
142

VWord szToken[10];
143

144

};
145

146

147

const VBigSize MAX_TOKEN=15000;
148

149

150

static stToken stTokens[100]={
151

{T_LeftBrace,L"{"},
152

{T_RightBrace,L"}"},
153

{T_LeftSBrace,L"("}, /* ( */
154

{T_RightSBrace,L")"}, /* ) */
155

{T_LeftMBrace,L"[" }, /* [ */
156

{T_RightMBrace,L"]" }, /* ] */
157

{T_UserIdent,L"\0" },/* [_\b]+[_\d\b]* */
158

{T_If,L"if"},/* if */
159

{T_Else,L"else"},/* else */
160

{T_Star,L"*"},/* * */
161

{T_Shop,L"#"},/* # */
162

{T_Include,L"include"},/* include */
163

{T_Define,L"define"},/* define */
164

{T_Do,L"do"},/* do */
165

{T_Semicolon,L";"},/* ; */
166

{T_Comma,L","},/* , */
167

{T_Dot,L"."},/* . */
168

{T_Arrow,L"->"},
169

{T_Minus,L"-"},
170

{T_Add,L"+"},
171

{T_Div,L"/"},
172

{T_Mod,L"%"},
173

{T_QMark,L"?"},
174

{T_Colon,L":"},
175

{T_BitComplement,L"~"},
176

{T_Not,L"!"},
177

{T_NotEqu,L"!="},
178

{T_Equ,L"=="},
179

{T_LargeThan,L">"},/* > */
180

{T_LessThan,L"<"},/* < */
181

{T_EquLargeThan,L">="},/* >= */
182

{T_EquLessThan,L"<="},/* <= */
183

{T_AssiAdd,L"+="},/* += */
184

{T_AssiMinus,L"-="},/* -= */
185

{T_AssiMul,L"*="},/* *= */
186

{T_AssiOr,L"|="},/* |= */
187

{T_AssiAnd,L"&="},/* &= */
188

{T_AssiExOr,L"^="},/* ^= */
189

{T_AssiDiv,L"/="},/* /= */
190

{T_AssiMod,L"%="},/* %= */
191

{T_Enum,L"enum"},/* enum */
192

{T_Struct,L"struct"},/* struct */
193

{T_Assi,L"="},/* = */
194

{T_Addr,L"&"},/* & */
195

{T_LogicAnd,L"&&"},/* && */
196

{T_LogicOr,L"||"},/* || */
197

{T_BitOr,L"|"},/* | */
198

{T_BitExOr,L"^"},/* ^ */
199

{T_Return,L"return"},/* return */
200

{T_Void,L"void"},/* void */
201

{T_Float,L"float"},/* float */
202

{T_Double,L"double"},/* Double */
203

{T_Int,L"int"},/* int */
204

{T_Unsigned,L"unsigned"},/* unsigned */
205

{T_Signed,L"signed"},/* signed */
206

{T_Auto,L"auto"},/* auto */
207

{T_Static,L"static"},/* static */
208

{T_Register,L"register"},/* register */
209

{T_Extern,L"extern"},/* extern */
210

{T_Break,L"break"},/* break */
211

{T_Continue,L"continue"},/* continue */
212

{T_Case,L"case"},/* case */
213

{T_Switch,L"switch"},/* Switch */
214

{T_Default,L"default"},/* default */
215

{T_For,L"for"},/* for */
216

{T_Volatile,L"volatile"},/* volatile */
217

{T_Const,L"const"},/* const */
218

{T_Sizeof,L"sizeof"},/* sizeof */
219

{T_Typedef,L"typedef"},/* typedef */
220

{T_Union,L"union"},/* union */
221

{T_Long,L"long"},/* long */
222

/* {T_SinQuo,L"\'"},//' */
223

/* {T_DouQuo,L"\""},//" */
224

/*{T_LeftComment,L"/*"},*/
225

//{T_RightComment,L"*/"},
226

{T_Character,L"\0"},
227

{T_String,L"\0"},
228

{T_Integer,L"\0"},
229

{T_Real,L"\0"},
230

{T_Char,L"char"},
231

{T_Inc,L"++"},
232

{T_Dec,L"--"},
233

{T_Connect,L"\\"},
234

{T_LeftBit,L"<<"},
235

{T_RightBit,L">>"},
236

{T_AssiLeftBit,L"<<="},
237

{T_AssiRightBit,L">>="},
238

{T_While,L"while"},
239

{T_END_,L"\0"}};
240

241

242

#define DEBUG_EXPECT(_mark) {std::wcout<<L"\' "<<_mark<<L" \'"<<L" Expected.\n"; return 0;}
243

#define DEBUG_NOTIDENT(_mark) {std::wcout<<L"\' "<<_mark<<L" \'"<<L" Not Identified.\n"; return 0;}
244

#define DEBUG_ERROR(_mark) {std::wcout<<_mark<<" Error.\n"; return 0;}
245

246

247

/* */
248

class Parser
249

{
250

public:
251

class IlGen;
252

class Scanner
253

{
254

friend class IlGen;
255

private:
256

template<typename T>
257

int lenof(T* str,T end)
258

{
259

static T* init;
260

init=str;
261

for(;*str!=end;str++);
262

return str-init;
263

}
264

265

266

267

struct stUserString /* 存储用户自定义标示符位置 */
268

{
269

VWord* begin;
270

int len;
271

stUserString*& operator=(stUserString & _user)
272

{
273

begin=_user.begin;
274

len=_user.len;
275

}
276

};
277

278

279

280

281

template<typename T> /* Delta Bubble Sort */
282

void sort(T*a,int n)
283

{
284

static int delta,i;
285

T temp;
286

delta=n;
287

for(;delta>=1;)
288

{
289

for(i=0;i+delta<n;i++)
290

if(lenof(stTokens[(int)a[i]].szToken,L'\0')<lenof(stTokens[(int)a[i+delta]].szToken,L'\0'))
291

{
292

temp=a[i];
293

a[i]=a[i+delta];
294

a[i+delta]=temp;
295

}
296

if(delta==1)break;
297

delta=(int)(delta/1.25);
298

}
299

return;
300

}
301

void initHash()
302

{
303

for(int j=0;j!=256;j++)
304

for(int i=0;i!=20;i++)
305

eHash[j][i]=T_END_;
306

307

for(int i=0;stTokens[i].e!=T_END_;i++)
308

{
309

for(int j=0;j!=20;j++)
310

if(eHash[stTokens[i].szToken[0]][j]==T_END_)
311

{
312

eHash[stTokens[i].szToken[0]][j]=stTokens[i].e;
313

break;
314

}else
315

continue;
316

}
317

318

for(int j=0;j!=256;j++)
319

sort(eHash[j],lenof(eHash[j],T_END_));
320

321

}
322

323

int isComment(VWord* _str)
324

{
325

if(_str[0]!=L'/'||_str[1]!=L'*')
326

return 0;
327

for(int i=2;_str[i]!=L'\0';++i)
328

if(_str[i]!=L'*'||_str[i+1]!=L'/')
329

continue;
330

else
331

return i+2;
332

return 0;
333

334

}
335

int isAlphaLine(VWord c)
336

{
337

return (c<=L'Z'&&c>=L'A')||(c<=L'z'&&c>=L'a')||c==L'_';
338

}
339

int isNum(VWord c)
340

{
341

return (c<=L'9'&&c>=L'0');
342

}
343

int isAlphaNumLine(VWord c)
344

{
345

return (c<=L'Z'&&c>=L'A')||(c<=L'z'&&c>=L'a')||(c<=L'9'&&c>=L'0')||c==L'_';
346

}
347

int isUserIdent(VWord* _ident)
348

{
349

if(!isAlphaLine(*_ident))
350

return 0;
351

int _len=1;
352

for(;isAlphaNumLine(_ident[_len]);_len++);
353

return _len;
354

}
355

int isReal(VWord* _szReal)
356

{
357

int _len=0;
358

for(;isNum(_szReal[_len]);_len++);
359

if(_szReal[_len++]!=L'.')
360

return 0;
361

for(;isNum(_szReal[_len]);_len++);
362

return _len;
363

}
364

int isInteger(VWord* _szInteger)
365

{
366

int _len=0;
367

for(;isNum(_szInteger[_len]);_len++);
368

return _len;
369

}
370

371

372

373

int isPrefix(VWord* _str,eToken _e)/* 关键字前缀检测 */
374

{
375

static VWord* _szBuf;
376

static VSmallSize i;
377

_szBuf=stTokens[_e].szToken;
378

379

for(i=0;_szBuf[i]!=L'\0';i++)
380

if(_str[i]!=_szBuf[i])
381

return 0;
382

383

if(isAlphaNumLine(_str[i-1])&&isAlphaNumLine(_str[i]))/* 区分用户标示符和关键字 */
384

return 0;
385

return i;
386

}
387

388

eToken eTokenList[MAX_TOKEN];
389

390

VBigSize tokenNum;
391

392

eToken eHash[256][20];
393

394

int userTokenIndexList[MAX_TOKEN];
395

396

stUserString userIndexList[MAX_TOKEN];
397

398

int userIndexNum;
399

400

401

public:
402

403

404

Scanner():userIndexNum(0),tokenNum(0)
405

{
406

}
407

408

409

#define IDENT_MAP(A,B,C,D) {userTokenIndexList[userIndexNum]=tokenNum;\
410

userIndexList[userIndexNum].begin=A;userIndexList[userIndexNum].len=B;\
411

++userIndexNum;\
412

_szProgram+=C;\
413

eTokenList[tokenNum]=D;\
414

++tokenNum;}
415

416

417

Scanner*& operator =(Scanner& _s)
418

{
419

for(int i=0;i!=tokenNum;i++)
420

eTokenList[i]=_s.eTokenList[i];
421

for(int i=0;i!=userIndexNum;i++)
422

{
423

userTokenIndexList[i]=_s.userTokenIndexList[i];
424

userIndexList[i]=_s.userIndexList[i];
425

}
426

427

}
428

429

430

VBool parse(VWord* _szProgram)/* 词法分析 */
431

{
432

#ifdef DEBUG_CGEN
433

std::cout<<"【词法分析】"<<std::endl;
434

435

VWord* szProgram=_szProgram;
436

#endif
437

438

static int step,temp,j;
439

tokenNum=0;
440

userIndexNum=0;
441

442

initHash();
443

444

for(;*_szProgram!=L'\0';)
445

{
446

if(*_szProgram==L'/'&&_szProgram[1]==L'*')
447

{
448

449

if(step=isComment(_szProgram))
450

{
451

_szProgram+=step;
452

}else
453

{
454

DEBUG_EXPECT(L"*/");
455

}
456

457

}else
458

{
459

temp=0;
460

{
461

462

for(j=0;j!=20;j++)
463

{
464

if(*_szProgram>255)
465

{
466

break;
467

}
468

step=isPrefix(_szProgram,eHash[*_szProgram][j]);
469

if(!step&&(eHash[*_szProgram][j]!=T_END_))
470

continue;
471

else if(step)
472

{
473

474

eTokenList[tokenNum]=eHash[*_szProgram][j];
475

++tokenNum;
476

_szProgram+=step;
477

temp=1;
478

}
479

break;
480

}
481

if(temp)
482

continue;
483

484

485

}
486

if(*_szProgram==L' '||*_szProgram==L'\t'||*_szProgram==L'\n')
487

{
488

_szProgram+=1;
489

}else if(*_szProgram==L'\'')
490

{
491

int _len=1;
492

for(;;_len++)
493

{
494

495

if(_szProgram[_len]==L'\0')
496

{
497

DEBUG_EXPECT(L"\'");
498

}else if(_szProgram[_len]==L'\''&&(_szProgram[_len-1]!=L'\\'||_szProgram[_len-2]==L'\\'))
499

{
500

501

IDENT_MAP(&_szProgram[1],_len-1,_len+1,T_Character);
502

503

break;
504

505

}
506

507

}
508

}else if(*_szProgram==L'\"')
509

{
510

int _len=1;
511

for(;;_len++)
512

{
513

514

if(_szProgram[_len]==L'\0')
515

{
516

DEBUG_EXPECT(L"\"");
517

}else if(_szProgram[_len]==L'\"'&&(_szProgram[_len-1]!=L'\\'||_szProgram[_len-2]==L'\\'))
518

{
519

520

IDENT_MAP(&_szProgram[1],_len-1,_len+1,T_String);
521

522

break;
523

524

}
525

526

}
527

}else if(step=isUserIdent(_szProgram))
528

{
529

530

IDENT_MAP(_szProgram,step,step,T_UserIdent);
531

532

533

}else if(step=isReal(_szProgram))
534

{
535

536

IDENT_MAP(_szProgram,step,step,T_Real);
537

538

539

}else if(step=isInteger(_szProgram))
540

{
541

IDENT_MAP(_szProgram,step,step,T_Integer);
542

543

544

}else
545

{
546

547

548

DEBUG_NOTIDENT(*_szProgram);
549

break;
550

}
551

}
552

553

}
554

555

#ifdef DEBUG_CGEN
556

int t=0;
557

j=0;
558

for(int i=0;i!=tokenNum;i++)
559

{
560

std::wcout<<eTokenList[i]<<L"::"<<stTokens[eTokenList[i]].szToken<<L"::";
561

if(userTokenIndexList[j]==i)
562

{
563

userIndexList[j].begin[userIndexList[j].len]=L'\0';
564

std::wcout<<userIndexList[j].begin;
565

j++;
566

}std::wcout<<std::endl;
567

}
568

569

std::cout<<"Tokens数："<<tokenNum<<std::endl;
570

#endif
571

572

573

return 1;
574

}
575

576

};
577

/* 中间语言生成器 */
578

class IlGen
579

{
580

581

Scanner * pSc;
582

int iToken;
583

int iUser;
584

int iGoto;
585

Scanner::stUserString * pIdent;
586

587

private:
588

void EmitLn(VWord* lStr,VWord* rStr,VWord* eStr)
589

{
590

std::wcout<<lStr<<rStr<<eStr<<std::endl;
591

}
592

void EmitLn(VWord* lStr,VWord* rStr)
593

{
594

std::wcout<<lStr<<rStr<<std::endl;
595

}
596

void EmitLn(VWord* lStr)
597

{
598

std::wcout<<lStr<<std::endl;
599

}
600

#define SetGoto(iGoto) {std::wcout<<L"mark["<<(iGoto)<<L"]:"<<std::endl;}
601

#define Goto(_I,iGoto) {std::wcout<<(_I)<<" mark["<<(iGoto)<<L"]"<<std::endl;}
602

#define NextGoto(iGoto) {iGoto++;}
603

604

int Match(eToken _token)
605

{
606

if(pSc->eTokenList[iToken++]==_token)
607

return 1;
608

else
609

DEBUG_EXPECT(stTokens[_token].szToken);
610

}
611

#define Peek(_mark) (_mark==pSc->eTokenList[iToken])
612

#define Peek2(_mark,_mark2) (_mark==pSc->eTokenList[iToken]||_mark2==pSc->eTokenList[iToken])
613

#define Peek3(_mark,_mark2,_mark3) (_mark==pSc->eTokenList[iToken]||_mark2==pSc->eTokenList[iToken]||_mark3==pSc->eTokenList[iToken])
614

VWord* GetIdent()
615

{
616

return pSc->userIndexList[iUser++].begin;
617

}
618

int isLeftUnaryOp()
619

{
620

switch(pSc->eTokenList[iToken])
621

{
622

case T_Not:
623

case T_BitComplement:
624

case T_Inc:
625

case T_Dec:
626

case T_Minus:
627

case T_Add:
628

case T_Star:
629

case T_Addr:
630

case T_Sizeof:
631

return 1;
632

}
633

return 0;
634

}
635

int isCompSymOp()
636

{
637

return Peek2(T_Equ,T_NotEqu);
638

}
639

640

int isCompAsyOp()
641

{
642

return Peek2(T_LargeThan,T_LessThan)||Peek2(T_EquLargeThan,T_EquLessThan);
643

}
644

int isBitShiftOp()
645

{
646

return Peek2(T_LeftBit,T_RightBit);
647

}
648

649

int isAddOp()
650

{
651

return Peek2(T_Add,T_Minus);
652

}
653

int isMulOp()
654

{
655

return Peek3(T_Star,T_Div,T_Mod);
656

}
657

658

659

void Factor()
660

{
661

662

663

664

if(Peek(T_UserIdent))
665

{
666

Match(T_UserIdent);
667

EmitLn(L"lea ebx, [",GetIdent(),L"]");
668

EmitLn(L"mov eax, dword ptr [ebx]");
669

}else if(Peek(T_Integer)){
670

Match(T_Integer);
671

EmitLn(L"mov eax, ",GetIdent());
672

}else if(Peek(T_LeftSBrace))
673

{
674

Match(T_LeftSBrace);
675

TernaryOp();
676

Match(T_RightSBrace);
677

}else if(Peek(T_Not))
678

{
679

int _iGoto,_iGoto2;
680

681

NextGoto(iGoto);
682

_iGoto=iGoto;
683

684

NextGoto(iGoto);
685

_iGoto2=iGoto;
686

687

Match(T_Not);
688

689

TernaryOp();
690

691

692

EmitLn(L"test eax, {fh, 8}");
693

Goto(L"jnz",_iGoto);
694

EmitLn(L"mov eax, 1");
695

Goto(L"jmp",_iGoto2);
696

697

SetGoto(_iGoto);
698

EmitLn(L"mov eax, 0");
699

SetGoto(_iGoto2);
700

}else if(Peek(T_BitComplement))
701

{
702

Match(T_BitComplement);
703

704

TernaryOp();
705

706

707

EmitLn(L"not eax");
708

}else if(Peek(T_Add))
709

{
710

Match(T_Add);
711

712

TernaryOp();
713

714

715

}else if(Peek(T_Minus))
716

{
717

Match(T_Minus);
718

719

TernaryOp();
720

721

EmitLn(L"neg eax");
722

}else if(Peek(T_Sizeof))
723

{
724

Match(T_Sizeof);
725

726

TernaryOp();
727

728

EmitLn(L"mov ecx, __atom__sizeof(eax)");
729

EmitLn(L"mov eax, ecx");
730

}
731

732

733

734

735

/*
736

-case T_Not:
737

-case T_BitComplement:
738

case T_Inc:
739

case T_Dec:
740

-case T_Minus:
741

-case T_Add:
742

case T_Star:
743

case T_Addr:
744

-case T_Sizeof:*/
745

}
746

void Term()
747

{
748

Factor();
749

750

while(isMulOp())
751

{
752

EmitLn(L"push eax");
753

if(Peek(T_Star))
754

{
755

Match(T_Star);
756

Factor();
757

758

EmitLn(L"pop ebx");
759

EmitLn(L"mul eax, ebx");
760

}else if(Peek(T_Div))
761

{
762

Match(T_Div);
763

Factor();
764

765

EmitLn(L"pop ebx");
766

EmitLn(L"div eax, ebx");
767

EmitLn(L"xchg eax, ebx");
768

}else if(Peek(T_Mod))
769

{
770

Match(T_Mod);
771

Factor();
772

773

EmitLn(L"pop ebx");
774

EmitLn(L"mod eax, ebx");
775

EmitLn(L"xchg eax, ebx");
776

}
777

}
778

}
779

void Expression()
780

{
781

782

Term();
783

784

while(isAddOp())
785

{
786

EmitLn(L"push eax");
787

if(Peek(T_Add))
788

{
789

Match(T_Add);
790

791

Term();
792

EmitLn(L"pop ebx");
793

EmitLn(L"add eax, ebx");
794

}else if(Peek(T_Minus))
795

{
796

Match(T_Minus);
797

798

Term();
799

EmitLn(L"pop ebx");
800

EmitLn(L"sub eax, ebx");
801

EmitLn(L"neg eax");
802

}
803

}
804

805

}
806

void BitShift()
807

{
808

Expression();
809

810

while(isBitShiftOp())
811

{
812

EmitLn(L"push eax");
813

if(Peek(T_LeftBit))
814

{
815

Match(T_LeftBit);
816

817

Expression();
818

EmitLn(L"pop ebx");
819

EmitLn(L"xchg eax, ebx");
820

EmitLn(L"shl eax, ebx");
821

}else if(Peek(T_RightBit))
822

{
823

Match(T_RightBit);
824

825

Expression();
826

EmitLn(L"pop ebx");
827

EmitLn(L"xchg eax, ebx");
828

EmitLn(L"shr eax, ebx");
829

}
830

}
831

}
832

void CompAsyOp()
833

{
834

BitShift();
835

836

while(isCompAsyOp())
837

{
838

EmitLn(L"push eax");
839

if(Peek(T_LargeThan))
840

{
841

Match(T_LargeThan);
842

843

BitShift();
844

EmitLn(L"pop ebx");
845

EmitLn(L"cmp eax, ebx");
846

EmitLn(L"mov eax, cf");
847

EmitLn(L"not zf");
848

EmitLn(L"mov eax, zf");
849

}else if(Peek(T_LessThan))
850

{
851

Match(T_LessThan);
852

853

BitShift();
854

EmitLn(L"pop ebx");
855

EmitLn(L"cmp eax, ebx");
856

EmitLn(L"not cf");
857

EmitLn(L"mov eax, cf");
858

EmitLn(L"not zf");
859

EmitLn(L"mov eax, zf");
860

}else if(Peek(T_EquLargeThan))
861

{
862

Match(T_EquLargeThan);
863

864

BitShift();
865

EmitLn(L"pop ebx");
866

EmitLn(L"cmp eax, ebx");
867

EmitLn(L"mov eax, cf");
868

EmitLn(L"mov eax, zf");
869

}else if(Peek(T_EquLessThan))
870

{
871

Match(T_EquLessThan);
872

873

BitShift();
874

EmitLn(L"pop ebx");
875

EmitLn(L"cmp eax, ebx");
876

EmitLn(L"not cf");
877

EmitLn(L"mov eax, cf");
878

EmitLn(L"mov eax, zf");
879

}
880

}
881

}
882

void CompSymOp()
883

{
884

CompAsyOp();
885

886

while(isCompSymOp())
887

{
888

889

EmitLn(L"push eax");
890

if(Peek(T_NotEqu))
891

{
892

Match(T_NotEqu);
893

894

CompAsyOp();
895

EmitLn(L"pop ebx");
896

EmitLn(L"cmp eax, ebx");
897

EmitLn(L"not zf");
898

EmitLn(L"mov eax, zf");
899

}else if(Peek(T_Equ))
900

{
901

Match(T_Equ);
902

903

CompAsyOp();
904

EmitLn(L"pop ebx");
905

EmitLn(L"cmp eax, ebx");
906

EmitLn(L"mov eax, zf");
907

}
908

}
909

}
910

void BitAnd()
911

{
912

CompSymOp();
913

914

while(Peek(T_Addr))
915

{
916

917

EmitLn(L"push eax");
918

919

Match(T_Addr);
920

CompSymOp();
921

EmitLn(L"pop ebx");
922

EmitLn(L"and eax, ebx");
923

924

}
925

}
926

void BitXor()
927

{
928

BitAnd();
929

930

while(Peek(T_BitExOr))
931

{
932

933

EmitLn(L"push eax");
934

935

Match(T_BitExOr);
936

BitAnd();
937

EmitLn(L"pop ebx");
938

EmitLn(L"xor eax, ebx");
939

940

}
941

}
942

void BitOr()
943

{
944

BitXor();
945

946

while(Peek(T_BitOr))
947

{
948

949

EmitLn(L"push eax");
950

951

Match(T_BitOr);
952

BitXor();
953

EmitLn(L"pop ebx");
954

EmitLn(L"or eax, ebx");
955

956

}
957

}
958

void LogicAnd()
959

{
960

int _iGoto=0,_iGoto2=0;
961

962

BitOr();
963

964

if(Peek(T_LogicAnd))
965

{
966

967

NextGoto(iGoto);/* 当iGoto被赋予前,更新iGoto */
968

_iGoto=iGoto;
969

970

NextGoto(iGoto);
971

_iGoto2=iGoto;
972

973

EmitLn(L"test eax, {fh: 8}");
974

Goto(L"jz",_iGoto);
975

while(Peek(T_LogicAnd))
976

{
977

Match(T_LogicAnd);
978

BitOr();
979

EmitLn(L"test eax, {fh: 8}");
980

Goto(L"jz",_iGoto);
981

982

if(!Peek(T_LogicAnd))
983

{
984

EmitLn(L"mov eax, 1");
985

Goto(L"jmp",_iGoto2);
986

}
987

}
988

SetGoto(_iGoto);
989

EmitLn(L"mov eax, 0");
990

SetGoto(_iGoto2);
991

992

}
993

994

995

}
996

void LogicOr()
997

{
998

LogicAnd();
999

1000

if(Peek(T_LogicOr))
1001

{
1002

1003

int _iGoto,_iGoto2;
1004

1005

NextGoto(iGoto);/* 当iGoto被赋予前,更新iGoto */
1006

_iGoto=iGoto;
1007

1008

NextGoto(iGoto);
1009

_iGoto2=iGoto;
1010

1011

EmitLn(L"test eax, {fh: 8}");
1012

Goto(L"jnz",_iGoto);
1013

while(Peek(T_LogicOr))
1014

{
1015

Match(T_LogicOr);
1016

LogicAnd();
1017

EmitLn(L"test eax, {fh: 8}");
1018

Goto(L"jnz",_iGoto);
1019

1020

if(!Peek(T_LogicOr))
1021

{
1022

EmitLn(L"mov eax, 0");
1023

Goto(L"jmp",_iGoto2);
1024

}
1025

}
1026

SetGoto(_iGoto);
1027

EmitLn(L"mov eax, 1");
1028

SetGoto(_iGoto2);
1029

1030

}
1031

1032

1033

}
1034

void TernaryOp()
1035

{
1036

1037

LogicOr();
1038

if(Peek(T_QMark))
1039

{
1040

int _iGoto,_iGoto2;/* 跳转标记 */
1041

1042

Match(T_QMark);
1043

1044

EmitLn(L"test eax, {fh: 8}");/* 三目运算符条件检测 */
1045

1046

NextGoto(iGoto);
1047

_iGoto=iGoto;
1048

1049

Goto(L"jz",_iGoto);/* 当表达式为假 */
1050

1051

1052

TernaryOp();
1053

1054

NextGoto(iGoto);
1055

_iGoto2=iGoto;
1056

1057

Goto(L"jmp",_iGoto2);
1058

1059

1060

Match(T_Colon);
1061

1062

SetGoto(_iGoto);
1063

TernaryOp();
1064

1065

SetGoto(_iGoto2);
1066

1067

}
1068

1069

1070

}
1071

void Assignment()
1072

{
1073

1074

1075

Match(T_UserIdent);
1076

1077

VWord* pName=GetIdent();
1078

1079

Match(T_Assi);
1080

TernaryOp();
1081

1082

1083

EmitLn(L"lea ebx, ",pName);
1084

EmitLn(L"mov [ebx], eax");
1085

1086

}
1087

void IfStatement()
1088

{
1089

int _iGoto=0,_iGotoEnd=0,_tag=0;
1090

Match(T_If);/* if(<expression>) */
1091

Match(T_LeftSBrace);
1092

TernaryOp();
1093

Match(T_RightSBrace);
1094

1095

NextGoto(iGoto);
1096

_iGoto=iGoto;
1097

NextGoto(iGoto);
1098

_iGotoEnd=iGoto;
1099

1100

EmitLn(L"test eax, {fh, 8}");
1101

Goto(L"jz",_iGoto);
1102

1103

1104

if(Peek(T_LeftBrace))
1105

{
1106

Match(T_LeftBrace);/* {<statement>*} */
1107

if(!Peek(T_RightBrace))
1108

{
1109

do{
1110

Statement();
1111

}while(!Peek(T_RightBrace));
1112

Match(T_RightBrace);
1113

}else
1114

{
1115

Match(T_RightBrace);
1116

}
1117

}else
1118

{
1119

Statement();
1120

}
1121

1122

1123

Goto(L"jmp",_iGotoEnd);
1124

1125

while(Peek(T_Else))
1126

{
1127

_tag=1;
1128

Match(T_Else);
1129

if(Peek(T_If))
1130

{
1131

SetGoto(_iGoto);
1132

Match(T_If);/* else if(<expression>) */
1133

Match(T_LeftSBrace);
1134

TernaryOp();
1135

Match(T_RightSBrace);
1136

1137

NextGoto(iGoto);
1138

_iGoto=iGoto;
1139

1140

EmitLn(L"test eax, {fh, 8}");
1141

Goto(L"jz",_iGoto);
1142

1143

1144

if(Peek(T_LeftBrace))
1145

{
1146

Match(T_LeftBrace);/* {<statement>*} */
1147

if(!Peek(T_RightBrace))
1148

{
1149

do{
1150

Statement();
1151

}while(!Peek(T_RightBrace));
1152

Match(T_RightBrace);
1153

}else
1154

{
1155

Match(T_RightBrace);
1156

}
1157

}else
1158

{
1159

Statement();
1160

}
1161

Goto(L"jmp",_iGotoEnd);
1162

1163

}else
1164

{
1165

SetGoto(_iGoto);
1166

if(Peek(T_LeftBrace))
1167

{
1168

1169

Match(T_LeftBrace);/* {<statement>*} */
1170

if(!Peek(T_RightBrace))
1171

{
1172

do{
1173

Statement();
1174

}while(!Peek(T_RightBrace));
1175

Match(T_RightBrace);
1176

}else
1177

{
1178

Match(T_RightBrace);
1179

}
1180

}else
1181

{
1182

Statement();
1183

}
1184

break;
1185

}
1186

}
1187

if(_tag==0)
1188

{
1189

SetGoto(_iGoto);
1190

}
1191

1192

SetGoto(_iGotoEnd);
1193

}
1194

void WhileStatement()
1195

{
1196

int _iGoto=0,_iGotoEnd=0;
1197

Match(T_While);
1198

1199

NextGoto(iGoto);
1200

_iGoto=iGoto;
1201

1202

NextGoto(iGoto);
1203

_iGotoEnd=iGoto;
1204

1205

1206

1207

SetGoto(_iGoto);
1208

1209

1210

Match(T_LeftSBrace);
1211

TernaryOp();
1212

Match(T_RightSBrace);
1213

EmitLn(L"test eax, {fh, 8}");
1214

Goto(L"jz",_iGotoEnd);
1215

1216

1217

if(Peek(T_LeftBrace))
1218

{
1219

1220

Match(T_LeftBrace);/* {<statement>*} */
1221

if(!Peek(T_RightBrace))
1222

{
1223

do{
1224

Statement();
1225

}while(!Peek(T_RightBrace));
1226

Match(T_RightBrace);
1227

}else
1228

{
1229

Match(T_RightBrace);
1230

}
1231

}else
1232

{
1233

Statement();
1234

}
1235

1236

1237

Goto(L"jmp",_iGoto);
1238

SetGoto(_iGotoEnd);
1239

}
1240

void DoWhileStatement()
1241

{
1242

int _iGoto=0,_iGotoEnd=0;
1243

Match(T_Do);
1244

1245

NextGoto(iGoto);
1246

_iGoto=iGoto;
1247

1248

NextGoto(iGoto);
1249

_iGotoEnd=iGoto;
1250

1251

SetGoto(_iGoto);
1252

1253

if(Peek(T_LeftBrace))
1254

{
1255

Match(T_LeftBrace);/* {<statement>*} */
1256

if(!Peek(T_RightBrace))
1257

{
1258

do{
1259

Statement();
1260

}while(!Peek(T_RightBrace));
1261

Match(T_RightBrace);
1262

}else
1263

{
1264

Match(T_RightBrace);
1265

}
1266

}else
1267

{
1268

Statement();
1269

}
1270

1271

Match(T_While);
1272

Match(T_LeftSBrace);
1273

TernaryOp();
1274

Match(T_RightSBrace);
1275

EmitLn(L"test eax, {fh, 8}");
1276

Goto(L"jz",_iGotoEnd);
1277

1278

Goto(L"jmp",_iGoto);
1279

SetGoto(_iGotoEnd);
1280

}
1281

void ForStatement()
1282

{
1283

int _iGoto=0,_iGotoEnd=0,_iGoto2=0,_iGoto3;
1284

NextGoto(iGoto);
1285

_iGoto=iGoto;
1286

1287

NextGoto(iGoto);
1288

_iGotoEnd=iGoto;
1289

1290

NextGoto(iGoto);
1291

_iGoto2=iGoto;
1292

1293

NextGoto(iGoto);
1294

_iGoto3=iGoto;
1295

1296

Match(T_For);
1297

Match(T_LeftSBrace);
1298

TernaryOp();/* init for */
1299

Match(T_Semicolon);
1300

1301

1302

TernaryOp();/* infer-expression */
1303

Match(T_Semicolon);
1304

1305

SetGoto(_iGoto3);
1306

EmitLn(L"test eax, {fh, 8}");
1307

Goto(L"jz",_iGotoEnd);
1308

Goto(L"jmp",_iGoto2);
1309

1310

SetGoto(_iGoto);
1311

TernaryOp();/* rear-set-expression */
1312

Match(T_RightSBrace);
1313

Goto(L"jmp",_iGoto3);
1314

1315

SetGoto(_iGoto2);
1316

1317

if(Peek(T_LeftBrace))
1318

{
1319

1320

Match(T_LeftBrace);/* {<statement>*} */
1321

if(!Peek(T_RightBrace))
1322

{
1323

do{
1324

Statement();
1325

}while(!Peek(T_RightBrace));
1326

Match(T_RightBrace);
1327

}else
1328

{
1329

Match(T_RightBrace);
1330

}
1331

}else
1332

{
1333

Statement();
1334

}
1335

1336

Goto(L"jmp",_iGoto2);
1337

SetGoto(_iGotoEnd);
1338

}
1339

void SemicolonStatement()
1340

{
1341

1342

}
1343

void Statement()
1344

{
1345

if(Peek(T_LeftBrace))
1346

{
1347

1348

Match(T_LeftBrace);
1349

if(!Peek(T_RightBrace))
1350

{
1351

do{
1352

Statement();
1353

}while(!Peek(T_RightBrace));
1354

Match(T_RightBrace);
1355

}else
1356

{
1357

Match(T_RightBrace);
1358

}
1359

1360

1361

}else if(Peek(T_If))
1362

{
1363

IfStatement();
1364

1365

1366

}else if(Peek(T_While))
1367

{
1368

WhileStatement();
1369

1370

1371

}else if(Peek(T_Do))
1372

{
1373

DoWhileStatement();
1374

1375

1376

}else if(Peek(T_For))
1377

{
1378

ForStatement();
1379

1380

1381

}else
1382

{
1383

TernaryOp();
1384

Match(T_Semicolon);
1385

1386

}
1387

1388

}
1389

1390

void Program()
1391

{
1392

while(iToken<pSc->tokenNum)
1393

{
1394

Statement();
1395

}
1396

}
1397

void Init()
1398

{
1399

iToken=0;/* Token当前位置 */
1400

iUser=0;/* 用户自定义标示符当前指向 */
1401

iGoto=0;/* 跳转标志产生序号 */
1402

}
1403

public:
1404

IlGen()
1405

{
1406

}
1407

1408

int parse(Scanner * _pSc)
1409

{
1410

#ifdef DEBUG_CGEN
1411

std::cout<<"【中间代码生成】"<<std::endl;
1412

#endif
1413

pSc=_pSc;/* 词法分析器初始化 */
1414

Init();
1415

Program();
1416

1417

return 1;
1418

1419

}
1420

};
1421

private:
1422

Scanner scanner;
1423

IlGen ils;
1424

public:
1425

Parser()
1426

{
1427

}
1428

int parse(VWord* _text)
1429

{
1430

1431

if(!scanner.parse(_text))
1432

DEBUG_ERROR(L"Scanning");
1433

if(!ils.parse(&scanner))
1434

DEBUG_ERROR(L"Interlingua");
1435

1436

1437

1438

return 1;
1439

1440

}
1441

};
1442

void input(VWord* _list,VWord end)
1443

{
1444

setlocale(LC_ALL, "");
1445

int i=0;
1446

for(;(_list[i]=std::wcin.get())!=end;i++);
1447

_list[i]=L'\0';
1448

1449

}
1450

1451

};
1452

#include <iostream>
2

#include "CGen.h"
3

#include <string>
5

#include <locale>
6

#include "runtime.h"
9

using namespace std;
10

int main()
13

{
14

CGen::Parser parser;
15

os::runtime rt;
17

const CGen::VBigSize MAX_CODE=CGen::MAX_TOKEN*5;
20

CGen::VWord list[MAX_CODE];
22

CGen::input(list,L'$');
23

//rt.begin();
27

//for(int i=0;i!=1000;i++)
28

parser.parse(list);
30

//rt.end();
32

//cout<<"处理"<<2456*1000/10000.0<<"万个词法标记所用的时间:"<<rt.getDTime()<<"ms"<<endl;
33

return 0;
34

}

先给出一个运行的case（片段代码的IL生成）:
2

if(1>2+(5+1)/(3-2*5/(3123213))&2)
4

{ for(1;a!=10;135){ a>50?a:b>10?1:2;}
5

}$
6

【词法分析】
7

7::if::
8

2::(::
9

73::::1
10

28::>::
11

73::::2
12

19::+::
13

2::(::
14

73::::5
15

19::+::
16

73::::1
17

3::)::
18

20::/::
19

2::(::
20

73::::3
21

18::-::
22

73::::2
23

9::*::
24

73::::5
25

20::/::
26

2::(::
27

73::::3123213
28

3::)::
29

3::)::
30

43::&::
31

73::::2
32

3::)::
33

0::{::
34

64::for::
35

2::(::
36

73::::1
37

14::;::
38

6::::a
39

26::!=::
40

73::::10
41

14::;::
42

73::::135
43

3::)::
44

0::{::
45

6::::a
46

28::>::
47

73::::50
48

22::?::
49

6::::a
50

23:::::
51

6::::b
52

28::>::
53

73::::10
54

22::?::
55

73::::1
56

23:::::
57

73::::2
58

14::;::
59

1::}::
60

1::}::
61

Tokens数：54
62

【中间代码生成】
63

mov eax, 1
64

push eax
65

mov eax, 2
66

push eax
67

mov eax, 5
68

push eax
69

mov eax, 1
70

pop ebx
71

add eax, ebx
72

push eax
73

mov eax, 3
74

push eax
75

mov eax, 2
76

push eax
77

mov eax, 5
78

pop ebx
79

mul eax, ebx
80

push eax
81

mov eax, 3123213
82

pop ebx
83

div eax, ebx
84

xchg eax, ebx
85

pop ebx
86

sub eax, ebx
87

neg eax
88

pop ebx
89

div eax, ebx
90

xchg eax, ebx
91

pop ebx
92

add eax, ebx
93

pop ebx
94

cmp eax, ebx
95

mov eax, cf
96

not zf
97

mov eax, zf
98

push eax
99

mov eax, 2
100

pop ebx
101

and eax, ebx
102

test eax, {fh, 8}
103

jz mark[1]
104

mov eax, 1
105

lea ebx, [a]
106

mov eax, dword ptr [ebx]
107

push eax
108

mov eax, 10
109

pop ebx
110

cmp eax, ebx
111

not zf
112

mov eax, zf
113

mark[6]:
114

test eax, {fh, 8}
115

jz mark[4]
116

jmp mark[5]
117

mark[3]:
118

mov eax, 135
119

jmp mark[6]
120

mark[5]:
121

lea ebx, [a]
122

mov eax, dword ptr [ebx]
123

push eax
124

mov eax, 50
125

pop ebx
126

cmp eax, ebx
127

mov eax, cf
128

not zf
129

mov eax, zf
130

test eax, {fh: 8}
131

jz mark[7]
132

lea ebx, [a]
133

mov eax, dword ptr [ebx]
134

jmp mark[8]
135

mark[7]:
136

lea ebx, [b]
137

mov eax, dword ptr [ebx]
138

push eax
139

mov eax, 10
140

pop ebx
141

cmp eax, ebx
142

mov eax, cf
143

not zf
144

mov eax, zf
145

test eax, {fh: 8}
146

jz mark[9]
147

mov eax, 1
148

jmp mark[10]
149

mark[9]:
150

mov eax, 2
151

mark[10]:
152

mark[8]:
153

jmp mark[5]
154

mark[4]:
155

jmp mark[2]
156

mark[1]:
157

mark[2]:

发表于 2011-02-19 04:05 邱震钰(zblc) 阅读(2782) 评论(3) 编辑收藏引用所属分类: vgl::CGen

常用链接

留言簿(11)

随笔分类

随笔档案

文章分类

相册

搜索

最新评论

阅读排行榜

评论排行榜