c - C 中 bool 表达式的解析和计算

Question

我有一个包含以下格式的 bool 表达式的文件:

x0 x3+x4
x1+x2

这些对应于:

x0 AND x3 OR x4
x1 OR x2

假设我们知道表达式的数量 (N=2) 和 x 的数量 (M=5)。 我想要一个大小为 N 的数组 A 和一个大小为 M 的数组 Y。 数组 A 应包含在:

A[0] = y[0] && y[3] || y[4]
A[1] = y[1] || y[2]

等等。

到目前为止，我已经实现了一个 python 脚本，该脚本生成一个 .c 文件，其中包含使用表达式初始化的给定数组。但这意味着我需要为每个不同的实例重新编译我的程序。我想避免这种情况。欢迎任何想法。

是否有一个“肮脏”或快速的技巧可以做到这一点？如果可能的话，我想使用纯C。提前致谢。

Answer 1

这是 C 语言解决方案的要点。它假定单字母变量名和单字母运算符。 (为了好玩，我为子表达式添加了“not”运算符和括号。) 它处理以下形式的字符串:

   a&b|(~c&~a)

(其中 a..z 对应于 OP 的 X 和 Y 实体)并计算表达式的 bool 值。

这是作为经典的递归下降解析器实现的；请参阅Is there an alternative for flex/bison that is usable on 8-bit embedded systems?有关如何执行此操作的更多详细信息。

我对其进行编码是为了指出这对于表达式来说是多么简单。这是未经测试的； OP 开始做他那份工作。

 #define syntax_error -1 // result of parser if expression is malformed

 bool variable_values[26]; // one for each letter a-z; initialized before parsing starts

 char* expression; // pointer to the expression string being processed

 int scan; // used to scan across the expression
 #define reject_character()  scan-- // used to back up scan when lexical error encountered
 #define skip_blanks() { while (expression[scan]==' ') scan++; }

 int boolean_primitive()
 // returns result of a subexpression consisting of just variable names or constants
 { int subexpression_result;
   skip_blanks();
   switch (expression[scan++])
   { case 'a','b', ... 'z': // variable name
       return variable_values[expression[scan-1]-"a"]; // look up value of variable
     case '0': // constant for "false"
       return 0;
     case '1': // constant for "true"
       return 1;
     default:
       return syntax_error;
   }
 }

 int boolean_term()
 // returns result of expression involving NOT or (...)
 { int subexpression_result;
   skip_blanks();
   switch (expression[scan++])
   { case '~': // not operator
       subexpression_result=boolean_primitive();
       if (subexpression_result==syntax_error)
          return syntax_error;
       return !subexpression_result;            
     case '(': // nested expression
       subexpression_result=boolean_or_sequence();
       if (subexpression_result==syntax_error)
          return syntax_error;
       skip_blanks();
       if (expression[scan++]==')')
          return subexpression_result;
       else return syntax_error;
     default:
       reject_character();
       return boolean_primitive();
   }
 }

 int boolean_and_sequence()
 // returns result of expression of form   s1 & s2 & ...
 { int subexpression_result=boolean_term();
   if (subexpression_result==syntax_error)
      return syntax_error;
   skip_blanks();
   while (expression[scan++]=='&') // "and" operator?
   { int subexpression2_result=boolean_term();
     if (subexpression2_result==syntax_error)
        return syntax_error;
     subexpression_result&=subexpression2_result;
     skip_blanks();
   }        
   reject_character; // undo overscan for '&'
   return subexpression_result;
}

 int boolean_or_sequence()
 // returns result of expression of form of s1 | s2 | ...
 { int subexpression_result=boolean_and_sequence();
   if (subexpression_result==syntax_error)
      return syntax_error;
   skip_blanks();
   while (expression[scan++]=='|') // "or" operator?
   { int subexpression2_result=boolean_primitive();
     if (subexpression2_result==syntax_error)
        return syntax_error;
     subexpression_result|=subexpression2_result;
     skip_blanks();
   }        
   reject_character; // undo overscan for '|'
   return subexpression_result;
}

 int calculate_boolean_expression(char* expression_to_evaluate)
 // returns int==0 for boolean false;
 // int==1 for boolean true
 // int==-1 for malformed expression
 {  int subexpression_result;
    scan=1;
    expression=expression_to_evaluate;
    subexpression_result=boolean_or_sequence();
    if (subexpression_result==syntax_error)
       return syntax_error;
    skip_blanks();
    if (expression[scan]==0) // expression ends without excess junk in string?
       return subexpression_result;
    else return syntax_error;
 }

初始化变量值后，您可以将其调用为:

 int the_answer=calculate_boolean_expression(&some_expression_string);

显然您想检查答案以查看解析器是否发现语法错误。

如果您坚持的话，您可以通过将全局变量全部作为参数传递来避免使用全局变量。

在 C 中返回/检查syntax_error 很尴尬，并且由于调用的子解析器的结果而需要重复检查它，因此使实现变得困惑。实现一个可抛出异常会更好，但 C 不允许这样做。你可以用 longjmp 来伪造它。

您必须扩展它来处理您的(多字符)词汇复杂性，无论它们是什么。为了快速而肮脏，坚持使用单字符运算符/操作数是非常干净的。处理多字符词位的秘诀是测试您期望遇到的每个词位，然后简单地将“扫描”指针备份到失败词位的开头。我为此使用了宏“reject”。