编译原理的龙书和虎书，各看了两章之后，￥……&……*……@%￥
好吧，既然是码农，就要从基层做起，我尝试handwritten一下C或者C的极小子集的one-pass编译器先，等有了深切的体会再去研究那些高深的形式理论也不迟。于是，我花了几天搞了简单的词法分析，还费了一包子力，凭我那捉急的智商，凑出来一个像是语法树的东西，能解析四则运算表达式。书上说手写编译器用递归下降法最合适，我想了半天也不知道咋递归下降。。刚才看了看书上的简化手写语法分析器，一共才100行不到，我只好望书兴叹了，唉，底子完全不够硬啊，差得远啊。
写了几天hardcode的一点心得：
终于有点明白为什么书上要我们把文法的BNF产生式都列出来，然后再相应的为每个产生式写实现函数了，这其实是在算法解耦。 比如我们可以测试发现，下面的递归下降语法器是不支持unary operator的，比如3*-2。如果想加入这个运算规则，我们只需在文法中新加入一条规则，然后修缮文法，最后编码：在递归下降的层次中加入一个unary()函数，下层是factor()，上层是term()，完成。如此便可以通过加新的函数来扩展支持逻辑运算，比较运算。而如果像我那样hardcode的话。。。。。。。扩展的时候翔的感觉一下子就出来了。
而且考虑到类似这样的语法特性:
a = b = c = 1;
利用递归下降法也能完美简洁的解决啊！
为什么要编译原理?因为我手写的玩意已经越来越意大利面条了,每扩充一个feature真是牵一发而动全身,自己都完全不能确定有没有给其他地方引入bug,也许最后能编译一般的C代码文件了,但是我TM都不知道为什么它能运作,当要移植到其它平台或者想复用来做个其它语言的编译器时,只能傻眼了.这正是所谓的"靠人品编程".此乃码农的标志性特征:先把功能赶完,bug可不敢说没有有的话大不了加班修修补补呗...大神们做最基础的编译器时可不敢怀着这种大无畏精神...虽然我的意大利面条杯具了,但是不错的是认识到了编译原理的重要性..
贴上代码：
标准的递归下降语法器：
#include <stdio.h>
#include <stdlib.h> char token; /*全局标志变量*/ /*递归调用的函数原型*/
int exp( void );
int term( void );
int factor( void ); void error( void ) /*报告出错信息的函数*/
{
fprintf( stderr, "错误\n");
exit( );
} void match( char expectedToken ) /*对当前的标志进行匹配*/
{
if( token == expectedToken ) token = getchar(); /*匹配成功，获取下一个标志*/
else error(); /*匹配不成功，报告错误*/
}
void Message(void)
{
printf("================================================================\n");
printf("* 递归实现的四则运算表达式求值程序 *\n");
printf("****************************************************************\n");
printf("使用方法:请从键盘上直接输入表达式,以回车键结束.如45*(12-2)[回车]\n");
printf("*****************************************************************\n\n");
}
main()
{
int result; /*运算的结果*/
Message();
printf(" >> 请输入表达式: ");
token = getchar(); /*载入第一个符号*/ result = exp(); /*进行计算*/
if( token == '\n' ) /* 是否一行结束 */
printf( " >> 表达式的计算结果为 : %d\n", result );
else error(); /* 出现了例外的字符 */
puts("\n\n 请按任意键退出 ...\n");
getch();
return ;
} int exp( void )
{
int temp = term(); /*计算比加减运算优先级别高的部分*/
while(( token == '+' ) || ( token == '-' ))
switch( token ) {
case '+': match('+'); /*加法*/
temp += term();
break;
case '-': match('-');
temp -= term(); /*减法*/
break;
}
return temp;
} int term( void )
{
int div; /*除数*/
int temp = factor(); /*计算比乘除运算优先级别高的部分*/
while(( token == '*' ) || ( token == '/' ))
switch( token ) {
case '*': match('*'); /*乘法*/
temp *= factor();
break;
case '/': match('/'); /*除法*/
div = factor();
if( div == ) /*需要判断除数是否为0*/
{
fprintf( stderr, "除数为0.\n" );
exit();
}
temp /= div;
break;
}
return temp;
} int factor( void )
{
int temp;
if( token == '(' ) /*带有括号的运算*/
{
match( '(' );
temp = exp();
match(')');
}
else if ( isdigit( token )) /*实际的数字*/
{
ungetc( token, stdin ); /*将读入的字符退还给输入流*/
scanf( "%d", &temp ); /*读出数字*/
token = getchar(); /*读出当前的标志*/
}
else error(); /*不是括号也不是数字*/
return temp;
}
我那翔一般的代码：
#include "StdAfx.h"
#include "SyntaxTree.h"
#include "Compiler.h" eTokenType SyntaxTree::lastTokenType = eTokenType_Invalid; int SyntaxTreeOpNode::Evaluate()
{
if (!strcmp(op, "+"))
{
return lchild->Evaluate() + rchild->Evaluate();
}
else if (!strcmp(op, "-"))
{
return lchild->Evaluate() - rchild->Evaluate();
}
else if (!strcmp(op, "*"))
{
return lchild->Evaluate() * rchild->Evaluate();
}
else if (!strcmp(op, "/"))
{
return lchild->Evaluate() / rchild->Evaluate();
}
else
{
//TODO: refactoring for no ugly if-else
assert();
return ;
}
} bool SyntaxTreeOpNode::IsThisOpPriorityHigher( const char* s )
{
return cl.opPriorityMap[op] >= cl.opPriorityMap[s];
} int SyntaxTreeLeafNode::Evaluate()
{
return value;
} int SyntaxTreeRootNode::Evaluate()
{
assert(rchild && "WTF!? This is not my tree!");
return rchild->Evaluate();
} SyntaxTree::SyntaxTree()
:root(nullptr)
{
} SyntaxTree::~SyntaxTree()
{
ResetTree();
} bool SyntaxTree::ConstructTree(int len)
{
const char* expstart = cl.sentence + cl.sentence_curpos;
assert(expstart[] != );
char op[MAX_IDENT_LEN];
eTokenType type;
SyntaxTreeNode* curNode = root;
std::vector<int> vecNums;
std::vector<SyntaxTreeOpNode*> vecFlatNodes; //1.首先构建运算符的树结构
while (cl.sentence_curpos < len)
{
type = cl.ScanWord(op);
if (type == eTokenType_Operator)
{
auto iter = cl.opPriorityMap.find(op);
assert(iter != cl.opPriorityMap.end() && "Invalid op!");
SyntaxTreeOpNode* node = new SyntaxTreeOpNode;
strcpy_s(node->op, ARRAYSIZE(node->op), op); //unary op process
bool bUnary = op[]== && (op[]=='+' || op[]=='-');
if (lastTokenType==eTokenType_Operator || lastTokenType==eTokenType_LBracket && bUnary)
{
vecNums.push_back();
curNode->rchild = node;
node->parent = curNode;
}
else if (curNode->IsThisOpPriorityHigher(op))
{
assert(node->parent == nullptr);
curNode->parent = node;
node->lchild = curNode;
//降低root高度
root->rchild = node;
node->parent = root;
}
else
{
curNode->rchild = node;
node->parent = curNode;
}
curNode = node;
vecFlatNodes.push_back(node);
}
else if (type == eTokenType_ConstantNumber)
{
vecNums.push_back(atoi(op));
}
else if (type == eTokenType_LBracket)
{
int substr_len = len - ;
//must find a matching r-bracket!
bool bFind = false;
while (substr_len >= cl.sentence_curpos)
{
if(cl.sentence[substr_len] == ')')
{
bFind = true;
break;
}
--substr_len;
}
if (bFind)
{
//对于括号,我们利用递归来求值...
SyntaxTree tmpTree;
tmpTree.ResetTree();
if(tmpTree.ConstructTree(substr_len))
vecNums.push_back(tmpTree.Evaluate());
else
return false; assert(cl.sentence[cl.sentence_curpos] == ')' && "Can't be true!...");
++cl.sentence_curpos;
}
else
{
LOG_ERR(eErr_NotMatchBracket);
return false;
}
type = eTokenType_ConstantNumber;
}
else
{
LOG_ERR(eErr_InvalidExpression);
return false;
}
lastTokenType = type;
} //2.然后为每个运算符插入叶节点
if (root->rchild == nullptr)
{
LOG_ERR(eErr_InvalidExpression);
return false;
} size_t leaf = , totalLeaf = vecNums.size();
for (size_t i=; i<vecFlatNodes.size(); ++i)
{
SyntaxTreeOpNode* node = vecFlatNodes[i];
if (!node->lchild)
{
if (leaf < totalLeaf)
{
SyntaxTreeLeafNode* leafNode = new SyntaxTreeLeafNode;
leafNode->value = vecNums[leaf];
node->lchild = leafNode;
leafNode->parent = node;
++leaf;
}
else
{
LOG_ERR(eErr_InvalidExpression);
return false;
}
}
if (!node->rchild)
{
if (leaf < totalLeaf)
{
SyntaxTreeLeafNode* leafNode = new SyntaxTreeLeafNode;
leafNode->value = vecNums[leaf];
node->rchild = leafNode;
leafNode->parent = node;
++leaf;
}
else
{
LOG_ERR(eErr_InvalidExpression);
return false;
}
}
} return true;
} void SyntaxTree::ResetTree()
{
SAFE_DELETE(root);
root = new SyntaxTreeRootNode;
} int SyntaxTree::Evaluate()
{
return root->Evaluate();
}
最后，无意中看到了这哥们摆弄的玩意，貌似也比我好不到哪去。。。。。。哇哈哈哈，可悲的咱码农啊