编译器和语言
4.95/5 (17投票s)
设计你自己的语言并为其编写编译器/解释器
引言
设计一种计算机语言，并围绕它编写一个编译器和一个解释器。毋庸置疑，我们只是触及了皮毛（我希望深入探索）。
背景
你应该对 C/C++ 有一些了解，对算法（特别是：树）、x86 汇编（MASM）和图灵完备性（http://en.wikipedia.org/wiki/Turing_completeness）有基本理解。
我们设计的最简单的语言只支持一种类型（以避免类型上下文敏感语法），并且比图灵焦油坑（http://en.wikipedia.org/wiki/Turing_tarpit）更好。最好将你的语言规范保持为上下文无关，以避免解决不必要的歧义。例如：- C/C++ 为浮点型和整型生成不同的汇编代码（因此代码生成除了其他因素外，还对**类型**敏感）。由于这是我关于创建计算机语言的第一篇文章，我们保持其简单。此外，该语言的语法检查缺失，一旦你理解了与表达式处理相关的语法树的生成，就可以轻松添加。
本文还向读者介绍了商业编译器实现和语言评估的概况，而没有语法/类型检查的复杂性。
此外，本文不涉及优化（所有商业编译器都在这方面花费了大量的编译时间），我希望在我们的编译器中添加以下内容（可能在我的下一篇文章中）：
http://en.wikipedia.org/wiki/Dead_code_elimination http://en.wikipedia.org/wiki/Register_allocation使用代码
与我之前的文章一样，代码必须随时参考并进行调试，以更好地理解其工作原理。
**图灵完备性**的基础是
- 向/从任意内存位置写入/读取任意值，例如：a=10, b=b*2+a, c=b+a。
- 跳转，允许执行跳转以进行循环和程序的静态流控制（静态流不依赖于变量的运行时值）
- #ifdef, #else, #endif. if(false) 等可以在 C 语言中执行静态流控制。
- 流控制，例如：如果 a 等于 2 则跳转到 End1，这里的流在运行时控制（取决于变量的运行时值）。
通过流控制，我们可以创建循环、函数递归（随意使用**你的**语言构建它们）。
没有表达式求值器，任何语言都不完整
我们支持以下运算符的优先级：(), *, /, % (mod), +。我们不支持 '-'，因为我们将把所有类型为 a-b 的表达式替换为 a+(-1)*b，并将 -1*b 作为独立的子表达式处理（你可以通过将 -b 的值作为 b 的补码来处理，例如：-1 将表示为 0xffffffff，然后生成输出 a+b）。
首先我们从计算括号 '(' 开始
我们必须通过使用 **if(strstr(str,"("))** 来搜索 '('
如果找到它，我们调用 **string EvaluateBrackets(const char *ex_str,bool bBuildCode=false)**
我们通过查找第一个右括号 ')' 来评估最内层的括号，然后我们向后回溯到第一个左括号（在反向搜索中找到，这意味着在我们遇到第一个右括号之前找到的最后一个左括号），请参阅代码。
string EvaluateBrackets(const char *ex_str,bool bBuildCode=false) //will evaluate one set of inner most brackets only
{
string ret="";
stack<char,vector<char>> bracket_check;
for(UINT i=0;i<strlen(ex_str);++i)
{
bracket_check.push(ex_str[i]);
if(ex_str[i]==')')
{
int j=i;
string bracketed;
while(1)
{
bracketed+=bracket_check._Get_container()[j];
if(bracket_check._Get_container()[j]!='(')
{
bracket_check.pop();
--j;
}
else
{
reverse(bracketed.begin(),bracketed.end());
static UINT tempVarCnt=0;
char tempVar[STR_SIZE]={};
sprintf(tempVar,"__t%u",tempVarCnt);
ret=stringReplace(ex_str,bracketed.c_str(),tempVar);
++tempVarCnt;
variableList[tempVar]=expression(stringReplace(stringReplace(bracketed.c_str(),"(","").c_str(),")","").c_str(),tempVar,bBuildCode); //add the variable in the map
return ret;
}
}
}
}
return ret;
}
请注意，我们用一个临时变量替换最内层的括号来评估表达式，这是 C/C++ 和其他编译器必须做的：请参阅 http://msdn.microsoft.com/en-us/library/a8kfxa78.aspx
现在到了有趣的部分，表达式求值
最好通过构建一棵树来完成，并且很简单（前提是你了解数据结构：树）
struct Tree
{
Tree():r(0),l(0),m_expression(" "),m_data(" "){}
string m_expression;
string m_data;
Tree *l,*r; //as with all binary trees, a 'left' and 'right' pointer
void AddSubExpressions(string expression)
{
m_expression=expression;
bool bFound=false;
PairString pa;
//follow operator precendance + has least precendance, * has most precedance
if(Findoperator(expression,"+",pa)) // we look for '+' since it has the least precedance
{
this->m_data="+";
bFound=true;
}
else if(Findoperator(expression,"%",pa))
{
this->m_data="%";
bFound=true;
}
else if(Findoperator(expression,"/",pa))
{
this->m_data="/";
bFound=true;
}
else if(Findoperator(expression,"*",pa))
{
this->m_data="*";
bFound=true;
}
if(bFound)
{
this->l=new Tree;
this->r=new Tree;
this->l->AddSubExpressions(pa.first);
this->r->AddSubExpressions(pa.second);
}
}
}
对于表达式 **a=10+3*5**，会生成以下树。你可以提供更复杂的表达式来查看生成的树。此外，对这棵树进行前序、中序、后序遍历将为你提供前缀、中缀和后缀表达式。
我们来计算这个表达式
为此，我们将调用函数 **static int compute(Tree *tmp,bool &bFoundVariable)**
深度优先遍历（http://en.wikipedia.org/wiki/Depth-first_search）通过函数递归完成此操作。
if(strstr(tmp->m_data.c_str(),"+")!=0)
{
return compute(tmp->l,bFoundVariable)+compute(tmp->r,bFoundVariable);
}
if(strstr(tmp->m_data.c_str(),"%")!=0)
{
return ((int)compute(tmp->l,bFoundVariable))%((int)compute(tmp->r,bFoundVariable));
}....
指令指针：-
对于解释器
我们将使用文件指针本身指向下一行进行执行。作为解释器，我们将独立读取和评估每一行，只使用在执行前几行时生成的变量/标签表（及其值）（C/C++ 也独立评估每个语句，并使用在评估前几行时生成的与函数和变量相关的表）。
对于编译器
由于我们必须生成可执行文件，我们没有可以运行文件指针作为指令指针的源代码，可执行文件必须足以在没有源文件的情况下执行。在这里，我们将不得不生成完整的代码本身（我们将生成 x86 32 位汇编代码，供 MASM 使用）。
我们需要评估所有变量，因为它们出现在源代码中，我们通过调用 **void BuildASMCode(Tree *tmp,string Temp)** 来生成 x86 代码。
这里使用的优化：-
**static int compute(Tree *tmp,bool &bFoundVariable)** 用于查找变量的值，输入是表达式树（我们之前生成的）和 bFoundVariable，如果 bFoundVariable 返回 **false**，则变量被优化，生成的代码如下：
int y=compute(...)
MOV EAX, y MOV variable,EAX
例如：a=b+1，**a** 的值依赖于 **b** 的值，因此不会被优化（**bFoundVariable 将返回 true**），但 a=2+3 可以优化为 a=5（**bFoundVariable 将返回 false，因此进行优化**）
当 **bFoundVariable** 返回 true 时，我们将遍历表达式并构建汇编代码以计算其值
BuildASMCode(Tree tmp, string Variable variableName)
{
//Create 2 new variables templ (left) and tempr (right),
//evaluate these 2 new variables first using DFS
BuildASMCode(tmp->l,templ);
BuildASMCode(tmp->l,tempr);
MOV eax,templ //for temporary variable on left
MOV ebx,tempr //for temporary variable on right
if(tmp->m_data=="+")
{
ADD EAX,EBX
MOV variableName, EAX
}
}
我们还需要在 ASM 文件的数据区域中定义所有变量（包括临时变量）
fprintf(m_fp,"\n.DATA\n");
for(map<string,int>::iterator it=variableList.begin();;++it)
{
if(it==variableList.end()) break;
fprintf(m_fp," %s DD 0 \n",it->first.c_str());
}
现在我们已经了解了表达式求值，让我们看看流控制
请记住，图灵完备性要求流控制：通过分支进行受控循环
许多语言由于性能原因选择性能而非图灵完备性，因此选择不提供流控制。这对于高性能（简单）处理器的流水线性质来说是合理的，这些处理器不需要复杂的条件预测，并且不会因为分支预测失败而降低高性能吞吐量。例如：- 较旧的着色器语言（DX shader 1.0）：http://amd-dev.wpengine.netdna-cdn.com/wordpress/media/2012/10/HLSLNotes.pdf无条件跳转：**GOTO**，受控流以相同的方式实现
对于解释器
我们必须生成可用标签的表，因此我们必须完整解析一次整个源文件
while(!feof(fp))
{
fgets(Buffer,sizeof(Buffer),fp);
char *str=strstr(Buffer,"LABEL:");
if(str) //found label
{
stringArray strArr=tokenizer(Buffer,":");
strArr[1].at(strArr[1].length()-1)=NULL; //we expect 2 strings
::gotoLabelList[strArr[1]]=LineCnt;
}
LineCnt++;
}
gotoLabelList 将维护找到**标签**的行号位置。当找到 GOTO 语句时，我们将增加/减少文件指针到源代码中的该行号。
int iCurrentLine=0;
#define JMP(j) {fclose(fp);\
fp=fopen("program.txt","r");\
\
iCurrentLine=j+1;\
\
for(int i=0;i<j+1;i++)\
fgets(Buffer,sizeof(Buffer),fp);\
}
对于条件跳转，我们只允许在条件匹配时进行跳转。
对于编译器
这对于编译器来说很简单，因为 .asm 文件已经提供了**标签**和**jmp（带条件）指令**，我们只需要在源代码中遇到它们时（逐行读取源代码时）将它们写入 .asm 文件。
函数调用
对于解释器
我们使用现有的标签表，实现方式与 GOTO 类似，但我们必须维护堆栈以保存返回地址，**funcRet.push_back(iCurrentLine)** 维护遇到 **RETURN** 时必须返回的行号。
对于编译器
这很简单（就像之前讨论的 GOTO 语法一样），因为 .asm 文件已经提供了**标签**和**call/return 指令**，x86 维护调用堆栈。
数组支持
我目前不支持数组及其各自的基于索引的数组访问。我们将在另一篇文章中探讨。
最后一点
**BREAK**：这告诉解释器/编译器程序已到达末尾，必须退出执行
输出汇编
由编译器生成的文件可以使用 MASM (32 位) 进行汇编，MASM 随 VS2012 提供，请参阅随附代码中关于 MASM (ml.exe) 的说明。
添加了一个断点 **Int 3**，强制可执行文件进入调试器，这将允许您使用进程内存查看器（调试器的一部分）查看输出。
关注点
我希望本文能揭开定义编程语言和构建编译器/解释器的神秘面纱。我计划就此主题撰写更多文章，并为我们的语言添加更多功能。