假设我在文本文件中有这样的字符串：
(((var1 AND var2 AND var3) OR var4) AND ((var5 OR var6) AND var7))
在将其解析到 C 程序中并正确处理和设置变量后，它将最终看起来像这样：
(((1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))
是否有任何有用的库可用于评估表示为这样一个字符串的表达式？我在想我可以用字符串作为参数调用一个 Perl 程序，这样就可以轻松地返回结果，但我不确定 C 中是否有一个库可以做到这一点，或者是否有任何已知的算法解决这样的表达？
我实际上正在寻找的是可以对这个表达式吐出答案的东西（也许 parse 是一个坏词），即 1 或 0。
简而言之，它是一个包含一堆随机表达式（已知格式正确）的文件，需要计算为 0 或 1。（上面的示例计算为 1，因为它导致 (1 AND 1) ）。
我尝试为这个布尔表达式求值问题编写最紧凑的 C 代码。这是我的最终代码：
编辑：已删除
这是添加的否定处理：
编辑：添加了测试代码
char *eval( char *expr, int *res ){
enum { LEFT, OP1, MID, OP2, RIGHT } state = LEFT;
enum { AND, OR } op;
int mid=0, tmp=0, NEG=0;
for( ; ; expr++, state++, NEG=0 ){
for( ;; expr++ )
if( *expr == '!' ) NEG = !NEG;
else if( *expr != ' ' ) break;
if( *expr == '0' ){ tmp = NEG; }
else if( *expr == '1' ){ tmp = !NEG; }
else if( *expr == 'A' ){ op = AND; expr+=2; }
else if( *expr == '&' ){ op = AND; expr+=1; }
else if( *expr == 'O' ){ op = OR; expr+=1; }
else if( *expr == '|' ){ op = OR; expr+=1; }
else if( *expr == '(' ){ expr = eval( expr+1, &tmp ); if(NEG) tmp=!tmp; }
else if( *expr == '\0' ||
*expr == ')' ){ if(state == OP2) *res |= mid; return expr; }
if( state == LEFT ){ *res = tmp; }
else if( state == MID && op == OR ){ mid = tmp; }
else if( state == MID && op == AND ){ *res &= tmp; state = LEFT; }
else if( state == OP2 && op == OR ){ *res |= mid; state = OP1; }
else if( state == RIGHT ){ mid &= tmp; state = MID; }
}
}
测试：
#include <stdio.h>
void test( char *expr, int exprval ){
int result;
eval( expr, &result );
printf("expr: '%s' result: %i %s\n",expr,result,result==exprval?"OK":"FAILED");
}
#define TEST(x) test( #x, x )
#define AND &&
#define OR ||
int main(void){
TEST( ((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1)) );
TEST( !(0 OR (1 AND 0)) OR !1 AND 0 );
}
您可以将lua嵌入您的程序中，然后调用它的解释器来评估表达式。
我有类似的程序来实现递归体面的解析器，所以我把它刷了一遍，就在这里。
#include <stdio.h>
#include <stdlib.h>
int doOR(int pOprd1, int pOprd2) {
if (pOprd1 == -1) return pOprd2;
return pOprd1 || pOprd2;
}
int doAND(int pOprd1, int pOprd2) {
if (pOprd1 == -1) return pOprd2;
return pOprd1 && pOprd2;
}
int doProcess(char pOpert, int pOprd1, int pOprd2) {
if (pOpert == '0') return pOprd2;
if (pOpert == 'O') return doOR (pOprd1, pOprd2);
if (pOpert == 'A') return doAND(pOprd1, pOprd2);
puts("Unknown Operator!!!");
exit(-1);
}
int* doParse(char pStr, int pStart) {
char C;
int i = pStart;
int Value = -1;
char Operator = '0';
for(; (C = pStr[i]) != 0; i++) {
if (C == '0') { Value = doProcess(Operator, Value, 0); continue; }
if (C == '1') { Value = doProcess(Operator, Value, 1); continue; }
if (C == ' ') continue;
if (C == ')') {
int aReturn;
aReturn = malloc(2*sizeof aReturn);
aReturn[0] = Value;
aReturn[1] = i + 1;
return aReturn;
}
if (C == '(') {
int * aResult = doParse(pStr, i + 1);
Value = doProcess(Operator, Value, aResult[0]);
i = aResult[1];
if (pStr[i] == 0) break;
continue;
}
if ((C == 'A') && ((pStr[i + 1] == 'N') && (pStr[i + 2] == 'D'))) {
if ((Operator == '0') || (Operator == 'A')) {
Operator = 'A';
i += 2;
continue;
} else {
puts("Mix Operators are not allowed (AND)!!!");
exit(-1);
}
}
if ((C == 'O') && (pStr[i + 1] == 'R')) {
if ((Operator == '0') || (Operator == 'O')) {
Operator = 'O';
i += 1;
continue;
} else {
puts("Mix Operators are not allowed (OR)!!!");
exit(-1);
}
}
printf("Unknown character: '%c (\"%s\"[%d])'!!!", C, pStr, i);
exit(-1);
}
int* aReturn;
aReturn = malloc(2*sizeof aReturn);
aReturn[0] = Value;
aReturn[1] = i;
return aReturn;
}
这是一个测试代码：
int main(void) {
char* aExpr = "1";
int* aResult = doParse(aExpr, 0);
printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
free(aResult);
aExpr = "0";
aResult = doParse(aExpr, 0);
printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
free(aResult);
aExpr = "1 AND 0";
aResult = doParse(aExpr, 0);
printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
free(aResult);
aExpr = "1 AND 1";
aResult = doParse(aExpr, 0);
printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
free(aResult);
aExpr = "0 OR 0 OR 0";
aResult = doParse(aExpr, 0);
printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
free(aResult);
aExpr = "1 OR 0 OR 0";
aResult = doParse(aExpr, 0);
printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
free(aResult);
aExpr = "1 OR 1 OR 0";
aResult = doParse(aExpr, 0);
printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
free(aResult);
aExpr = "(1 OR 0)";
aResult = doParse(aExpr, 0);
printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
free(aResult);
aExpr = "(0 OR 0)";
aResult = doParse(aExpr, 0);
printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
free(aResult);
aExpr = "((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))";
aResult = doParse(aExpr, 0);
printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
free(aResult);
puts("DONE!!!");
return EXIT_SUCCESS;
}
这很有趣:-D。
为像这样的简单表达式滚动你自己的递归下降解析器很容易。
@noɥʇʎԀʎzɐɹƆ 正在寻找可以在 x86 上构建并为任何布尔表达式生成 x86 asm JIT 评估器的规范解析器和评估器。
这是一个 ANSI C99 基本解析器和求值器，它使用 构建表达式树parse_tree并使用eval_expr. 这避免了大多数常见的指针算术，应该很容易翻译成许多语言。
错误管理设置为基本最小值（缺少或意外的表达式，错误的表达式，如 NOT 1 NOT 0）。如果解析时出现错误的表达式，它不应该泄漏内存，但没有真正以这种方式进行测试。
可以用eval_leaf一种 libc 替换strtol()，但这里似乎更好地执行由偏移量分隔的基本 int 解析以避免字符串分配，因为我们通常处理简单的 int 。
该compile_expr方法为表达式生成一个 x86 asm 求值器，该exec_expr_JIT方法执行生成的 x86 asm 求值器。exec_expr_JIT实际上只使用了Linux/BSD/MacOS和Windows的mmap和MapViewOfFile。更通用的方法是在学习中。
编辑：添加按位非运算符 (BNOT) 作为~in 表达式。
要对其进行测试，只需使用 ANSI C99 编译器构建它，然后使用预期的表达式启动它，以作为第一个参数进行解析和评估：
$ cc -o parser parser.c
$ ./parser '(NOT0AND(1OR(1 AND 0))AND(1OR(0OR0)))AND1ANDNOT!~0'
<<<<[NOT]0>[AND]<1[OR]<1 [AND] 0>>>[AND]<1[OR]<0[OR]0>>>[AND]1>[AND]<[NOT]<[NOT]<[BNOT]0>>>
=> 1
Compiled: 88 [B8 00 00 00 00 F7 D0 25 01 00 00 00 50 B8 01 00 00 00 50 B8 01 00 00 00 25 00 00 00 00 59 09 C1 59 21 C1 50 B8 01 00 00 00 50 B8 00 00 00 00 0D 00 00 00 00 59 09 C1 59 21 C1 25 01 00 00 00 50 B8 00 00 00 00 F7 D0 F7 D0 25 01 00 00 00 F7 D0 25 01 00 00 00 59 21 C1]
Res JIT : 1
它将首先使用<leaf>和以扁平树形式显示解析的表达式[operand]，然后使用 显示其评估结果 => <result>。接下来，它将显示为已解析表达式构建的求值器的 x86 asm 代码及其大小（以字节为单位），然后是该求值器的执行结果。
解析器和评估器来源：
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdint.h>
#ifdef _MSC_VER
#include <windows.h>
#include <memoryapi.h>
#else
#include <sys/mman.h>
#endif
enum e_operand { NONE, AND, OR, NOT, BNOT };
struct s_expr {
struct s_expr_leaf {
char* value;
int offset;
struct s_expr* expr;
} *left;
enum e_operand operand;
struct s_expr_leaf* right;
};
struct s_expr* build_expr() {
struct s_expr* lExpr = (struct s_expr*)malloc(sizeof(struct s_expr));
if (lExpr == NULL) return(NULL);
lExpr->left = NULL;
lExpr->operand = NONE;
lExpr->right = NULL;
return(lExpr);
}
struct s_expr_leaf* build_leaf(struct s_expr* pExpr) {
struct s_expr_leaf* lLeaf = (struct s_expr_leaf*)malloc(sizeof(struct s_expr_leaf));
if (lLeaf == NULL) return(NULL);
lLeaf->value = NULL;
lLeaf->offset = 0;
lLeaf->expr = pExpr;
return(lLeaf);
}
struct s_expr* left_expr(struct s_expr** pExpr) {
struct s_expr* lExprParent = build_expr();
if (lExprParent == NULL) {
perror("Can't allocate enough memory...");
return(NULL);
}
lExprParent->left = build_leaf(*pExpr);
if (lExprParent->left == NULL) {
perror("Can't allocate enough memory...");
free(lExprParent);
return(NULL);
}
*(pExpr) = lExprParent;
return lExprParent;
}
int free_expr(struct s_expr*);
struct s_expr* parse_tree(char** pExpr) {
if (pExpr == NULL || *pExpr == NULL) return(NULL);
struct s_expr* lExpr = build_expr();
if (lExpr == NULL) {
perror("Can't allocate enough memory...");
return(NULL);
}
struct s_expr_leaf** lSide = &lExpr->left;
while (**pExpr != 0) {
switch (**pExpr & 0xDF) {
case 8: // (
(*pExpr)++;
if (*lSide == NULL) {
*lSide = build_leaf(NULL);
}
if (*lSide != NULL) (*lSide)->expr = parse_tree(pExpr);
if (*lSide == NULL || (*lSide)->expr == NULL) {
perror("Can't allocate enough memory...");
free_expr(lExpr);
return(NULL);
}
break;
case 9: // )
return(lExpr);
case 'N': // NOT?
case 1:
if (**pExpr == '!' || (((*pExpr)[1] & 0xDF) == 'O' && ((*pExpr)[2] & 0xDF) == 'T')) {
if (lExpr->operand != NONE) {
if (lExpr->right != NULL) {
printf("Wrong expression\n");
free_expr(lExpr);
return(NULL);
}
lExpr->right = build_leaf(parse_tree(pExpr));
if (lExpr->right == NULL || lExpr->right->expr == NULL) {
perror("Can't allocate enough memory...");
free_expr(lExpr);
return(NULL);
}
return(lExpr);
}
lExpr->operand = NOT;
if (**pExpr != '!') (*pExpr) += 2;
lSide = &lExpr->right;
}
break;
case '^': // Bitwise NOT ?
if (**pExpr == '~') {
if (lExpr->operand != NONE) {
if (lExpr->right != NULL) {
printf("Wrong expression\n");
free_expr(lExpr);
return(NULL);
}
lExpr->right = build_leaf(parse_tree(pExpr));
if (lExpr->right == NULL || lExpr->right->expr == NULL) {
perror("Can't allocate enough memory...");
free_expr(lExpr);
return(NULL);
}
return(lExpr);
}
lExpr->operand = BNOT;
lSide = &lExpr->right;
}
break;
case 'A': // AND?
if (((*pExpr)[1] & 0xDF) == 'N' && ((*pExpr)[2] & 0xDF) == 'D') {
if (lExpr->operand != NONE) {
if (left_expr(&lExpr) == NULL) {
free_expr(lExpr);
return(NULL);
}
}
lExpr->operand = AND;
(*pExpr) += 2;
lSide = &lExpr->right;
}
break;
case 'O': // OR?
if (((*pExpr)[1] & 0xDF) == 'R') {
if (lExpr->operand != NONE) {
if (left_expr(&lExpr) == NULL) {
free_expr(lExpr);
return(NULL);
}
}
lExpr->operand = OR;
(*pExpr)++;
lSide = &lExpr->right;
}
break;
default:
if (*lSide == NULL) {
*lSide = build_leaf(NULL);
if (*lSide == NULL) {
perror("Can't allocate enough memory...");
free_expr(lExpr);
return(NULL);
}
(*lSide)->value = *pExpr;
}
if ((*lSide)->value == NULL) (*lSide)->value = *pExpr;
(*lSide)->offset++;
};
(*pExpr)++;
};
return(lExpr);
}
int free_expr(struct s_expr* pExpr) {
int lFlag = 0;
if (pExpr == NULL) return(0);
if (pExpr->left != NULL) {
lFlag = free_expr(pExpr->left->expr);
free(pExpr->left);
}
if (pExpr->right != NULL) {
lFlag = free_expr(pExpr->right->expr);
free(pExpr->right);
}
free(pExpr);
return(lFlag);
}
int display_expr(struct s_expr* pExpr) {
if (pExpr == NULL) return 0;
if (pExpr->left != NULL) {
if (pExpr->left->expr != NULL) {
printf("<");
display_expr(pExpr->left->expr);
printf(">");
} else {
if (pExpr->left->value != NULL) printf("%.*s", pExpr->left->offset, pExpr->left->value);
}
}
switch (pExpr->operand) {
case NONE:
break;
case AND:
printf("[AND]");
break;
case OR:
printf("[OR]");
break;
case NOT:
printf("[NOT]");
break;
case BNOT:
printf("[BNOT]");
break;
};
if (pExpr->right != NULL) {
if (pExpr->right->expr != NULL) {
printf("<");
display_expr(pExpr->right->expr);
printf(">");
} else {
if (pExpr->right->value != NULL) printf("%.*s", pExpr->right->offset, pExpr->right->value);
}
}
return(0);
}
int eval_leaf(struct s_expr_leaf* pValue, int* pRes) {
char* lValue;
int lLimit = 0;
int lStart = -1;
int lSign = 1;
if (pRes == NULL) return(1);
if (pValue == NULL) return(1);
lValue = pValue->value;
lLimit = pValue->offset;
if (lValue == NULL) return(1);
*pRes = 0;
while (lLimit > 0 && *lValue == ' ') { lValue++; lLimit--; }
if (lLimit > 0 && (*lValue == '-' || *lValue == '+')) {
if (*lValue == '-') lSign = -1;
lLimit--;
lValue++;
}
while (lLimit > 0 && *lValue != 0) {
if (*lValue >= 0x30 && *lValue <= 0x39) {
if (lStart == -1) lStart = lLimit;
} else {
break;
}
lLimit--;
lValue++;
}
if (lStart > 0) {
lStart -= lLimit;
lValue--;
lLimit = 1;
while (lStart > 0) {
*pRes += ((*lValue & 0xF) * lLimit);
lLimit *= 10;
lStart--;
lValue--;
};
} else {
printf("Expr or value missing ...\n");
return(2);
}
*pRes *= lSign;
return(0);
}
int eval_expr(struct s_expr* pExpr, int* pRes) {
int lResLeft = 0;
int lResRight = 0;
enum e_operand lOperand = NONE;
if (pRes == NULL) return(1);
*pRes = 0;
if (pExpr == NULL) return(1);
if (pExpr->left != NULL) {
if (pExpr->left->expr != NULL) {
if (pExpr->left->value != NULL) {
printf("Unexpected left value... %.*s\n", pExpr->left->offset, pExpr->left->value);
return(2);
}
switch (eval_expr(pExpr->left->expr, &lResLeft)) {
case 2:
display_expr(pExpr); printf("\n");
return(1);
case 1:
return(1);
};
} else {
if (pExpr->left->value != NULL) {
switch (eval_leaf(pExpr->left, &lResLeft)) {
case 2:
display_expr(pExpr); printf("\n");
return(1);
case 1:
return(1);
};
}
}
}
if (pExpr->right != NULL) {
if (pExpr->right->expr != NULL) {
if (pExpr->right->value != NULL) {
printf("Unexpected right value... %.*s\n", pExpr->right->offset, pExpr->right->value);
return(2);
}
switch (eval_expr(pExpr->right->expr, &lResRight)) {
case 2:
display_expr(pExpr); printf("\n");
return(1);
case 1:
return(1);
};
} else {
if (pExpr->right->value != NULL) {
switch (eval_leaf(pExpr->right, &lResRight)) {
case 2:
display_expr(pExpr); printf("\n");
return(1);
case 1:
return(1);
};
}
}
}
switch (pExpr->operand) {
case NONE:
if (pExpr->left == NULL) {
printf("Expr or value missing ...\n");
return(2);
}
*pRes = lResLeft;
break;
case AND:
if (pExpr->left == NULL || pExpr->right == NULL) {
printf("Expr or value missing ...\n");
return(2);
}
*pRes = (lResLeft & lResRight);
break;
case OR:
if (pExpr->left == NULL || pExpr->right == NULL) {
printf("Expr or value missing ...\n");
return(2);
}
*pRes = (lResLeft | lResRight);
break;
case NOT:
if (pExpr->right == NULL) {
printf("Expr or value missing ...\n");
return(2);
}
*pRes = !lResRight;
break;
case BNOT:
if (pExpr->right == NULL) {
printf("Expr or value missing ...\n");
return(2);
}
*pRes = ~lResRight;
break;
};
return(0);
}
// Expr compilation
struct s_expr_JIT {
unsigned char* JIT;
int size;
int nbargs;
};
struct s_expr_JIT* build_expr_JIT() {
struct s_expr_JIT* lExprJIT = (struct s_expr_JIT*)malloc(sizeof(struct s_expr_JIT));
if (lExprJIT == NULL) {
perror("Can't allocate enough memory...");
return(NULL);
}
lExprJIT->JIT = NULL;
lExprJIT->size = 0;
lExprJIT->nbargs = 0;
return(lExprJIT);
}
int free_expr_JIT(struct s_expr_JIT* pExpr) {
if (pExpr == NULL) return(1);
if (pExpr->JIT != NULL) free(pExpr->JIT);
free(pExpr);
return(0);
}
int set_expr_JIT(struct s_expr_JIT* pExpr, unsigned char* pOpCodes, int pNbOpCodes, int* pValue, unsigned char* pOpCodesNext, int pNbOpCodesNext) {
unsigned char* lOffset;
int lSizeref;
if (pExpr == NULL) return(1);
if (pExpr->JIT != NULL) {
lSizeref = pExpr->size;
pExpr->size += pNbOpCodes;
pExpr->size += pNbOpCodesNext;
if (pValue != NULL) pExpr->size += sizeof(int32_t);
lOffset = (unsigned char*)realloc(pExpr->JIT, pExpr->size);
if (lOffset == NULL) {
perror("Can't allocate enough memory...");
return(1);
}
pExpr->JIT = lOffset;
lOffset = &pExpr->JIT[lSizeref];
} else {
pExpr->size = pNbOpCodes;
pExpr->size += pNbOpCodesNext;
if (pValue != NULL) pExpr->size += sizeof(int32_t);
pExpr->JIT = (unsigned char*)malloc(pExpr->size);
if (pExpr->JIT == NULL) {
perror("Can't allocate enough memory...");
return(1);
}
lOffset = pExpr->JIT;
}
if (pOpCodes != NULL) {
if (memcpy(lOffset, pOpCodes, pNbOpCodes) == NULL) return(1);
lOffset += pNbOpCodes;
}
if (pValue != NULL) {
*((int32_t*)lOffset) = (int32_t)*pValue; // Keep endianness
lOffset += sizeof(int32_t);
}
if (pOpCodesNext != NULL) {
if (memcpy(lOffset, pOpCodesNext, pNbOpCodesNext) == NULL) return(1);
lOffset += pNbOpCodesNext;
}
return(0);
}
int merge_expr_JIT(struct s_expr_JIT* pExpr, unsigned char* pOpCodes, int pNbOpCodes, struct s_expr_JIT* pSrc, unsigned char* pOpCodesMerge, int pNbOpCodesMerge) {
unsigned char* lOffset;
int lSizeref;
if (pExpr == NULL) return(1);
if (pExpr->JIT != NULL) {
lSizeref = pExpr->size;
pExpr->size += pNbOpCodes;
pExpr->size += pNbOpCodesMerge;
if (pSrc != NULL) pExpr->size += pSrc->size;
lOffset = (unsigned char*)realloc(pExpr->JIT, pExpr->size);
if (lOffset == NULL) {
perror("Can't allocate enough memory...");
return(1);
}
pExpr->JIT = lOffset;
lOffset = &pExpr->JIT[lSizeref];
} else {
pExpr->size = pNbOpCodes;
pExpr->size += pNbOpCodesMerge;
if (pSrc != NULL) pExpr->size += pSrc->size;
pExpr->JIT = (unsigned char*)malloc(pExpr->size);
if (pExpr->JIT == NULL) {
perror("Can't allocate enough memory...");
return(1);
}
lOffset = pExpr->JIT;
}
if (pOpCodes != NULL) {
if (memcpy(lOffset, pOpCodes, pNbOpCodes) == NULL) return(1);
lOffset += pNbOpCodes;
}
if (pSrc != NULL) {
if (memcpy(lOffset, pSrc->JIT, pSrc->size) == NULL) return(1);
lOffset += pSrc->size;
}
if (pOpCodesMerge != NULL) {
if (memcpy(lOffset, pOpCodesMerge, pNbOpCodesMerge) == NULL) return(1);
lOffset += pNbOpCodesMerge;
}
return(0);
}
int compile_expr(struct s_expr* pExpr, struct s_expr_JIT** pRes) {
int lResLeftValue = 0;
int lResRightValue = 0;
if (pExpr == NULL) return(1);
if (pRes == NULL) return(1);
struct s_expr_JIT* lResLeft = NULL;
struct s_expr_JIT* lResRight = NULL;
enum e_operand lOperand = NONE;
*pRes = build_expr_JIT();
if (*pRes == NULL) {
return(1);
}
if (pExpr->left != NULL) {
if (pExpr->left->expr != NULL) {
if (pExpr->left->value != NULL) {
printf("Unexpected left value... %.*s\n", pExpr->left->offset, pExpr->left->value);
free_expr_JIT(*pRes);
return(2);
}
switch (compile_expr(pExpr->left->expr, &lResLeft)) {
case 2:
display_expr(pExpr); printf("\n");
free_expr_JIT(*pRes);
return(1);
case 1:
free_expr_JIT(*pRes);
return(1);
};
} else {
if (pExpr->left->value != NULL) {
switch (eval_leaf(pExpr->left, &lResLeftValue)) {
case 2:
display_expr(pExpr); printf("\n");
free_expr_JIT(*pRes);
return(1);
case 1:
free_expr_JIT(*pRes);
return(1);
};
}
}
}
if (pExpr->right != NULL) {
if (pExpr->right->expr != NULL) {
if (pExpr->right->value != NULL) {
printf("Unexpected right value... %.*s\n", pExpr->right->offset, pExpr->right->value);
free_expr_JIT(lResLeft); free_expr_JIT(*pRes);
return(2);
}
switch (compile_expr(pExpr->right->expr, &lResRight)) {
case 2:
display_expr(pExpr); printf("\n");
free_expr_JIT(lResLeft); free_expr_JIT(*pRes);
return(1);
case 1:
free_expr_JIT(lResLeft); free_expr_JIT(*pRes);
return(1);
};
} else {
if (pExpr->right->value != NULL) {
switch (eval_leaf(pExpr->right, &lResRightValue)) {
case 2:
display_expr(pExpr); printf("\n");
free_expr_JIT(lResLeft); free_expr_JIT(*pRes);
return(1);
case 1:
free_expr_JIT(lResLeft); free_expr_JIT(*pRes);
return(1);
};
}
}
}
switch (pExpr->operand) {
case NONE:
if (pExpr->left == NULL) {
printf("Expr or value missing ...\n");
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(2);
}
if (lResLeft != NULL) {
if (merge_expr_JIT(*pRes, NULL, 0, lResLeft, NULL, 0) != 0) {
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
} else {
if (set_expr_JIT(*pRes, (unsigned char[]) { 0xB8 }, 1, & lResLeftValue, NULL, 0) != 0) { // MOVL <int32 value>, %EAX
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
}
break;
case AND:
if (pExpr->left == NULL || pExpr->right == NULL) {
printf("Expr or value missing ...\n");
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(2);
}
if (lResLeft != NULL) {
if (merge_expr_JIT(*pRes, NULL, 0, lResLeft, NULL, 0) != 0) {
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
} else {
if (set_expr_JIT(*pRes, (unsigned char[]) { 0xB8 }, 1, & lResLeftValue, NULL, 0) != 0) { // MOVL <int32 value>, %EAX
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
}
if (lResRight != NULL) { // 0x91 XCHG %EAX,%ECX
if (merge_expr_JIT(*pRes, (unsigned char[]) { 0x50 }, 1, lResRight, (unsigned char[]) { 0x59, 0x21, 0xC1 }, 3) != 0) { // PUSH %EAX POP %ECX AND %EAX,%ECX
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
} else {
if (set_expr_JIT(*pRes, (unsigned char[]) { 0x25 }, 1, & lResRightValue, NULL, 0) != 0) { // AND %EAX, <int32 value>
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
}
break;
case OR:
if (pExpr->left == NULL || pExpr->right == NULL) {
printf("Expr or value missing ...\n");
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(2);
}
if (lResLeft != NULL) {
if (merge_expr_JIT(*pRes, NULL, 0, lResLeft, NULL, 0) != 0) {
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
} else {
if (set_expr_JIT(*pRes, (unsigned char[]) { 0xB8 }, 1, & lResLeftValue, NULL, 0) != 0) { // MOVL <int32 value>, %EAX
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
}
if (lResRight != NULL) { // 0x91 XCHG %EAX,%ECX
if (merge_expr_JIT(*pRes, (unsigned char[]) { 0x50 }, 1, lResRight, (unsigned char[]) { 0x59, 0x09, 0xC1 }, 3) != 0) { // PUSH %EAX POP %ECX OR %EAX,%ECX
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
} else {
if (set_expr_JIT(*pRes, (unsigned char[]) { 0x0D }, 1, & lResRightValue, NULL, 0) != 0) { // OR %EAX, <int32 value>
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
}
break;
case NOT:
if (pExpr->right == NULL) {
printf("Expr or value missing ...\n");
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(2);
}
if (lResRight != NULL) {
if (merge_expr_JIT(*pRes, NULL, 0, lResRight, (unsigned char[]) { 0xF7, 0xD0, 0x25, 0x01, 0x00, 0x00, 0x00 }, 7) != 0) { // NOT %EAX AND %EAX,1
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
} else {
if (set_expr_JIT(*pRes, (unsigned char[]) { 0xB8 }, 1, & lResRightValue, (unsigned char[]) { 0xF7, 0xD0, 0x25, 0x01, 0x00, 0x00, 0x00 }, 7) != 0) { // MOV %EAX, <int32 value> NOT %EAX
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
}
break;
case BNOT:
if (pExpr->right == NULL) {
printf("Expr or value missing ...\n");
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(2);
}
if (lResRight != NULL) {
if (merge_expr_JIT(*pRes, NULL, 0, lResRight, (unsigned char[]) { 0xF7, 0xD0 }, 2) != 0) { // NOT %EAX
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
} else {
if (set_expr_JIT(*pRes, (unsigned char[]) { 0xB8 }, 1, & lResRightValue, (unsigned char[]) { 0xF7, 0xD0 }, 2) != 0) { // MOV %EAX, <int32 value> NOT %EAX
free_expr_JIT(lResLeft); free_expr_JIT(lResRight); free_expr_JIT(*pRes);
return(1);
}
}
break;
};
if (lResLeft != NULL) free_expr_JIT(lResLeft);
if (lResRight != NULL) free_expr_JIT(lResRight);
return(0);
}
int dump_expr_JIT(struct s_expr_JIT* pExpr) {
unsigned char* lOffset;
int lSize;
if (pExpr != NULL) {
lOffset = pExpr->JIT;
lSize = pExpr->size;
while (lSize > 0) {
printf("%02X", lOffset[0]);
lOffset++;
lSize--;
if (lSize > 0) printf(" ");
}
}
return(0);
}
int exec_expr_JIT(struct s_expr_JIT* pExpr, int* pRes) {
unsigned char* lOffset;
int (*lJit)();
if (pRes == NULL) return(1);
if (pExpr != NULL) {
#ifdef _MSC_VER
HANDLE lHandle = CreateFileMappingA(INVALID_HANDLE_VALUE, NULL, PAGE_EXECUTE_READWRITE | SEC_COMMIT, 0, pExpr->size + 10, NULL);
if (lHandle == NULL) {
perror("Mapping failed...");
return 1;
}
lOffset = (unsigned char*)MapViewOfFile(lHandle, FILE_MAP_ALL_ACCESS | FILE_MAP_EXECUTE, 0, 0, pExpr->size + 10);
if (lOffset == NULL) {
perror("Mapping failed...");
return 1;
}
#else
lOffset = (unsigned char*)mmap(NULL, pExpr->size + 10, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
if (lOffset == MAP_FAILED) {
perror("Mapping failed...");
return 1;
}
#endif
lOffset[0] = 0x55; // PUSH %EBP
lOffset[1] = 0x48; // MOV %ESP, %EBP
lOffset[2] = 0x89;
lOffset[3] = 0xE5;
lOffset[4] = 0x9C; // PUSHFD
lOffset[5] = 0x51; // PUSH %ECX
if (memcpy(&lOffset[6], pExpr->JIT, pExpr->size) == NULL) {
#ifdef _MSC_VER
if (!UnmapViewOfFile(lOffset)) {
perror("Unmapping failed...");
return 1;
}
CloseHandle(lHandle);
#else
if (munmap(lOffset, pExpr->size + 10) != 0) {
perror("Unmapping failed...");
return 1;
}
#endif
return(1);
}
lOffset[pExpr->size + 6] = 0x59; // POP %ECX
lOffset[pExpr->size + 7] = 0x9D; // POPF
lOffset[pExpr->size + 8] = 0xC9; // LEAVE
lOffset[pExpr->size + 9] = 0xC3; // RETF
lJit = (int (*)())lOffset;
*pRes = lJit();
#ifdef _MSC_VER
if (!UnmapViewOfFile(lOffset)) {
perror("Unmapping failed...");
return 1;
}
CloseHandle(lHandle);
#else
if (munmap(lOffset, pExpr->size + 10) != 0) {
perror("Unmapping failed...");
return 1;
}
#endif
}
return(0);
}
int parse(char* pExpr, int* pRes) {
// Decomposing pExpr in tree form
struct s_expr* lRoot = parse_tree(&pExpr);
int lRes = 0;
if (lRoot == NULL) return(1);
display_expr(lRoot);
printf("\n");
if (eval_expr(lRoot, &lRes) == 0) {
printf(" => %d\n", lRes);
} else {
printf(" Error in expr...\n");
}
struct s_expr_JIT* lCompile;
if (compile_expr(lRoot, &lCompile) == 0) {
printf("Compiled: %d [", lCompile->size);
dump_expr_JIT(lCompile);
printf("]\n");
if (exec_expr_JIT(lCompile, &lRes) == 0) {
printf("Res JIT : %d\n", lRes);
} else {
printf("Failed to exec JIT..\n");
}
free_expr_JIT(lCompile);
}
free_expr(lRoot);
return(0);
}
int main(int nbargs, char* args[]) {
int lRes = 0;
if (nbargs > 0) parse(args[1], &lRes);
return(0);
}
我相信Lex 和 Yacc仍然是此类简单解析任务的最佳工具。
不久前，我为嵌入式系统上的命令行处理器和脚本语言编写了一个完整的 C 表达式求值器（即使用 C 语法编写的求值表达式）。我使用这个算法的描述作为起点。您可以直接使用随附的代码，但我不喜欢该实现，并根据算法描述编写了自己的代码。它需要一些工作来支持所有 C 运算符、函数调用和变量，但这是一个清晰的解释，因此是一个很好的起点，特别是如果您不需要那种级别的完整性。
基本原理是使用堆栈和“反向波兰表示法”的计算机更容易表达式评估，因此该算法将具有相关优先顺序和括号的固定表示法表达式转换为 RPN，然后通过弹出操作数对其进行评估，执行操作，并压入结果，直到堆栈上没有任何操作和一个值。
作为这个答案的附件，这里是使用 JIT asm 库 ( asmjit ) 来增强可移植性的解析器的 C++ 版本。感谢 @Kamiccolo 的 JIT 库理念。此代码需要C11 C++ 编译器和 asmjit 库。
使用 GCC/G++-8 和 VS2019（代码和 asmjit 库的 x86 构建）测试（编译和运行）。
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <iostream>
#include <asmjit/x86.h>
using namespace std;
//
// namespace for the expression parser
//
namespace parser {
enum e_operand { NONE, AND, OR, NOT, BNOT };
//
// expression class
//
class expression {
public:
//
// leaf class
//
class expression_leaf {
public:
char* value;
int offset;
expression* expr;
expression_leaf(expression* pExpr) {
this->value = NULL;
this->offset = 0;
this->expr = pExpr;
}
int eval_leaf(int* pRes) {
char* lValue;
int lLimit = 0;
int lStart = -1;
int lSign = 1;
if (pRes == NULL) return(1);
lValue = this->value;
lLimit = this->offset;
if (lValue == NULL) return(1);
*pRes = 0;
while (lLimit > 0 && *lValue == ' ') { lValue++; lLimit--; }
if (lLimit > 0 && (*lValue == '-' || *lValue == '+')) {
if (*lValue == '-') lSign = -1;
lLimit--;
lValue++;
}
while (lLimit > 0 && *lValue != 0) {
if (*lValue >= 0x30 && *lValue <= 0x39) {
if (lStart == -1) lStart = lLimit;
} else {
break;
}
lLimit--;
lValue++;
}
if (lStart > 0) {
lStart -= lLimit;
lValue--;
lLimit = 1;
while (lStart > 0) {
*pRes += ((*lValue & 0xF) * lLimit);
lLimit *= 10;
lStart--;
lValue--;
};
} else {
cerr << "eval_leaf: Expr or value missing ...\n";
return(2);
}
*pRes *= lSign;
return(0);
}
};
private:
expression_leaf* left;
enum e_operand operand;
expression_leaf* right;
public:
//
// Main constructor
//
expression() {
this->left = (expression_leaf*)NULL;
this->operand = NONE;
this->right = (expression_leaf*)NULL;
}
//
// expression fabrics
//
static expression* build_expression(char* pExpr) {
// Decomposing pExpr in tree form
return(expression::parse_tree(&pExpr));
}
static expression* left_expr(expression** pExpr) {
expression* lExprParent = new expression();
if (lExprParent == NULL) {
perror("Can't allocate enough memory...");
return(NULL);
}
lExprParent->left = new expression_leaf(*pExpr);
if (lExprParent->left == NULL) {
perror("Can't allocate enough memory...");
return(NULL);
}
*(pExpr) = lExprParent;
return lExprParent;
}
static expression* parse_tree(char** pExpr) {
if (pExpr == NULL || *pExpr == NULL) return(NULL);
expression* lExpr = new expression();
if (lExpr == NULL) {
perror("Can't allocate enough memory...");
return(NULL);
}
expression_leaf** lSide = &lExpr->left;
while (**pExpr != 0) {
switch (**pExpr & 0xDF) {
case 8: // (
(*pExpr)++;
if (*lSide == NULL) {
*lSide = new expression_leaf(NULL);
}
if (*lSide != NULL) (*lSide)->expr = parse_tree(pExpr);
if (*lSide == NULL || (*lSide)->expr == NULL) {
perror("Can't allocate enough memory...");
return(NULL);
}
break;
case 9: // )
return(lExpr);
case 'N': // NOT?
case 1:
if (**pExpr == '!' || (((*pExpr)[1] & 0xDF) == 'O' && ((*pExpr)[2] & 0xDF) == 'T')) {
if (lExpr->operand != NONE) {
if (lExpr->right != NULL) {
cerr << "parse_tree: Wrong expression\n";
return(NULL);
}
lExpr->right = new expression_leaf(lExpr->parse_tree(pExpr));
if (lExpr->right == NULL || lExpr->right->expr == NULL) {
perror("Can't allocate enough memory...");
return(NULL);
}
return(lExpr);
}
lExpr->operand = NOT;
if (**pExpr != '!') (*pExpr) += 2;
lSide = &lExpr->right;
}
break;
case '^': // Bitwise NOT ?
if ((*pExpr)[0] == '~') {
if (lExpr->operand != NONE) {
if (lExpr->right != NULL) {
cerr << "parse_tree: Wrong expression\n";
return(NULL);
}
lExpr->right = new expression_leaf(lExpr->parse_tree(pExpr));
if (lExpr->right == NULL || lExpr->right->expr == NULL) {
perror("Can't allocate enough memory...");
return(NULL);
}
return(lExpr);
}
lExpr->operand = BNOT;
lSide = &lExpr->right;
}
break;
case 'A': // AND?
if (((*pExpr)[1] & 0xDF) == 'N' && ((*pExpr)[2] & 0xDF) == 'D') {
if (lExpr->operand != NONE) {
if (lExpr->left_expr(&lExpr) == NULL) {
return(NULL);
}
}
lExpr->operand = AND;
(*pExpr) += 2;
lSide = &lExpr->right;
}
break;
case 'O': // OR?
if (((*pExpr)[1] & 0xDF) == 'R') {
if (lExpr->operand != NONE) {
if (lExpr->left_expr(&lExpr) == NULL) {
return(NULL);
}
}
lExpr->operand = OR;
(*pExpr)++;
lSide = &lExpr->right;
}
break;
default:
if (*lSide == NULL) {
*lSide = new expression_leaf(NULL);
if (*lSide == NULL) {
perror("Can't allocate enough memory...");
return(NULL);
}
(*lSide)->value = *pExpr;
}
if ((*lSide)->value == NULL) (*lSide)->value = *pExpr;
(*lSide)->offset++;
};
(*pExpr)++;
};
return(lExpr);
}
//
// expression methods
//
int display_expr() {
if (this->left != NULL) {
if (this->left->expr != NULL) {
cout << "<";
this->left->expr->display_expr();
cout << ">";
} else {
if (this->left->value != NULL) printf("%.*s", this->left->offset, this->left->value);
}
}
switch (this->operand) {
case NONE:
break;
case AND:
cout << "[AND]";
break;
case OR:
cout << "[OR]";
break;
case NOT:
cout << "[NOT]";
break;
case BNOT:
cout << "[BNOT]";
break;
};
if (this->right != NULL) {
if (this->right->expr != NULL) {
cout << "<";
this->right->expr->display_expr();
cout << ">";
} else {
if (this->right->value != NULL) printf("%.*s", this->right->offset, this->right->value);
}
}
return(0);
}
int eval_expr(int* pRes) {
int lResLeft = 0;
int lResRight = 0;
enum e_operand lOperand = NONE;
if (pRes == NULL) return(1);
*pRes = 0;
if (this->left != NULL) {
if (this->left->expr != NULL) {
if (this->left->value != NULL) {
fprintf(stderr, "eval_expr: Unexpected left value... %.*s\n", this->left->offset, this->left->value);
return(2);
}
switch (this->left->expr->eval_expr(&lResLeft)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
} else {
if (this->left->value != NULL) {
switch (this->left->eval_leaf(&lResLeft)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
}
}
}
if (this->right != NULL) {
if (this->right->expr != NULL) {
if (this->right->value != NULL) {
fprintf(stderr, "eval_expr: Unexpected right value... %.*s\n", this->right->offset, this->right->value);
return(2);
}
switch (this->right->expr->eval_expr(&lResRight)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
} else {
if (this->right->value != NULL) {
switch (this->right->eval_leaf(&lResRight)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
}
}
}
switch (this->operand) {
case NONE:
if (this->left == NULL) {
cerr << "eval_expr: Expr or value missing ...\n";
return(2);
}
*pRes = lResLeft;
break;
case AND:
if (this->left == NULL || this->right == NULL) {
cerr << "eval_expr: AND operator, Expr or value missing ...\n";
return(2);
}
*pRes = (lResLeft & lResRight);
break;
case OR:
if (this->left == NULL || this->right == NULL) {
cerr << "eval_expr: OR operator, Expr or value missing ...\n";
return(2);
}
*pRes = (lResLeft | lResRight);
break;
case NOT:
if (this->right == NULL) {
cerr << "eval_expr: NOT operator, Expr or value missing ...\n";
return(2);
}
*pRes = !lResRight;
break;
case BNOT:
if (this->right == NULL) {
cerr << "eval_expr: BNOT operator, Expr or value missing ...\n";
return(2);
}
*pRes = ~lResRight;
break;
};
return(0);
}
///////////////// JIT ///////////////////////////
int compile_expr(asmjit::CodeHolder* pCode, asmjit::x86::Assembler* pAssembly) {
if (pCode == NULL) return(1);
if (pAssembly == NULL) return(1);
int lResLeftValue = 0;
int lResRightValue = 0;
int lResLeft = 0;
int lResRight = 0;
enum e_operand lOperand = NONE;
if (this->left != NULL) {
if (this->left->expr != NULL) {
if (this->left->value != NULL) {
fprintf(stderr, "compile_expr: Unexpected left value... %.*s\n", this->left->offset, this->left->value);
return(2);
}
lResLeft = 1;
} else {
if (this->left->value != NULL) {
switch (this->left->eval_leaf(&lResLeftValue)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
}
}
}
if (this->right != NULL) {
if (this->right->expr != NULL) {
if (this->right->value != NULL) {
fprintf(stderr, "compile_expr: Unexpected right value... %.*s\n", this->right->offset, this->right->value);
return(2);
}
lResRight = 1;
} else {
if (this->right->value != NULL) {
switch (this->right->eval_leaf(&lResRightValue)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
}
}
}
switch (this->operand) {
case NONE:
if (this->left == NULL) {
cerr << "compile_expr: Expr or value missing ...\n";
return(2);
}
if (lResLeft == 1) {
switch (this->left->expr->compile_expr(pCode, pAssembly)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
} else {
pAssembly->mov(asmjit::x86::eax, (int32_t)lResLeftValue);
}
break;
case AND:
if (this->left == NULL || this->right == NULL) {
cerr << "compile_expr: AND operator, Expr or value missing ...\n";
return(2);
}
if (lResLeft == 1) {
switch (this->left->expr->compile_expr(pCode, pAssembly)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
} else {
pAssembly->mov(asmjit::x86::eax, (int32_t)lResLeftValue);
}
if (lResRight == 1) {
pAssembly->push(asmjit::x86::eax);
switch (this->right->expr->compile_expr(pCode, pAssembly)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
pAssembly->pop(asmjit::x86::ecx);
pAssembly->and_(asmjit::x86::eax, asmjit::x86::ecx);
} else {
pAssembly->and_(asmjit::x86::eax, (int32_t)lResRightValue);
}
break;
case OR:
if (this->left == NULL || this->right == NULL) {
cerr << "compile_expr: OR operator, Expr or value missing ...\n";
return(2);
}
if (lResLeft == 1) {
switch (this->left->expr->compile_expr(pCode, pAssembly)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
} else {
pAssembly->mov(asmjit::x86::eax, (int32_t)lResLeftValue);
}
if (lResRight == 1) {
pAssembly->push(asmjit::x86::eax);
switch (this->right->expr->compile_expr(pCode, pAssembly)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
pAssembly->pop(asmjit::x86::ecx);
pAssembly->or_(asmjit::x86::eax, asmjit::x86::ecx);
} else {
pAssembly->or_(asmjit::x86::eax, (int32_t)lResRightValue);
}
break;
case NOT:
if (this->right == NULL) {
cerr << "compile_expr: NOT operator, Expr or value missing ...\n";
return(2);
}
if (lResRight == 1) {
switch (this->right->expr->compile_expr(pCode, pAssembly)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
pAssembly->not_(asmjit::x86::eax);
pAssembly->and_(asmjit::x86::eax, (int32_t)1);
} else {
pAssembly->mov(asmjit::x86::eax, (int32_t)lResRightValue);
pAssembly->not_(asmjit::x86::eax);
pAssembly->and_(asmjit::x86::eax, (int32_t)1);
}
break;
case BNOT:
if (this->right == NULL) {
cerr << "compile_expr: BNOT operator, Expr or value missing ...\n";
return(2);
}
if (lResRight == 1) {
switch (this->right->expr->compile_expr(pCode, pAssembly)) {
case 2:
this->display_expr(); cout << "\n";
return(1);
case 1:
return(1);
};
pAssembly->not_(asmjit::x86::eax);
} else {
pAssembly->mov(asmjit::x86::eax, (int32_t)lResRightValue);
pAssembly->not_(asmjit::x86::eax);
}
break;
};
return(0);
}
int compile_expr_start(asmjit::JitRuntime* pRunTime, asmjit::CodeHolder* pCode, int (**pCompiled_function)(void)) {
if (pRunTime == NULL) return(1);
asmjit::x86::Assembler lAssembly(pCode);
lAssembly.push(asmjit::x86::ebp); // Prolog
lAssembly.mov(asmjit::x86::ebp, asmjit::x86::esp);
lAssembly.pushfd();
lAssembly.push(asmjit::x86::ecx);
if (this->compile_expr(pCode, &lAssembly) != 0) {
return(1);
}
lAssembly.pop(asmjit::x86::ecx);
lAssembly.popfd();
lAssembly.pop(asmjit::x86::ebp); // Epilog
lAssembly.ret();
asmjit::Error lErr = pRunTime->add(pCompiled_function, pCode);
if (lErr) return(1);
return(0);
}
int dump_expr(asmjit::CodeHolder* pCode, int (*pCompiled_function)(void)) {
if (pCode == NULL) return(1);
unsigned char* lOffset;
unsigned long lSize;
if (pCompiled_function != NULL) {
lOffset = (unsigned char*)pCompiled_function;
lSize = (unsigned long)pCode->codeSize();
while (lSize > 0) {
printf("%02X", lOffset[0]);
lOffset++;
lSize--;
if (lSize > 0) cout << " ";
}
}
return(0);
}
int exec_expr(int (*pCompiled_function)(void), int* pRes) {
if (pCompiled_function == NULL) return(1);
if (pRes == NULL) return(1);
*pRes = pCompiled_function();
return(0);
}
};
}
using namespace parser;
int main(int nbargs, char* args[]) {
expression* lExpression;
int lRes;
if (nbargs > 0) {
lExpression = expression::build_expression(args[1]);
lExpression->display_expr();
cout << "\n";
if (lExpression->eval_expr(&lRes) == 0) {
cout << " => " << lRes << "\n";
} else {
cerr << " Error in expr...\n";
}
// JIT
int (*compiled_function)(void) = NULL;
asmjit::JitRuntime* lRunTime = new asmjit::JitRuntime();
if (lRunTime == NULL) return(1);
asmjit::CodeHolder lCode;
lCode.init(lRunTime->environment());
if (lExpression->compile_expr_start(lRunTime, &lCode, &compiled_function) == 0) {
cout << "Compiled: " << lCode.codeSize() << " [";
lExpression->dump_expr(&lCode, compiled_function);
cout << "]\n";
if (lExpression->exec_expr(compiled_function, &lRes) == 0) {
cout << "Res JIT : " << lRes << "\n";
} else {
cerr << "Failed to exec JIT..\n";
}
lRunTime->release(compiled_function);
} else {
cerr << "Failed to build JIT..\n";
}
}
return(0);
}
编写表达式解析器原则上很容易，但需要付出相当大的努力。
这是我用 Java 编写的一个基本的向下递归下降表达式解析器：http: //david.tribble.com/src/java/tribble/parse/sql/QueryParser.java http://david.tribble.com/src /java/tribble/parse/sql/ExprLexer.java http://david.tribble.com/src/java/tribble/parse/sql/ExprLexer.java http://david.tribble.com/docs/tribble/parse /sql/package-summary.html
这可能不是您正在寻找的，但它会让您了解您需要什么。