我有一个应用程序需要允许用户编写类似于 excel 的表达式：
(H1 + (D1 / C3)) * I8
还有更复杂的事情，比如
如果（H1 = '真'，D3 * .2，D3 * .5）
我只能用正则表达式做这么多。任何关于正确方法的建议以及我可以从中学习的任何资源都将不胜感激。
谢谢！
Micah
问问题
1570 次
9 回答
7
于 2009-03-05T14:44:19.807 回答
7
当遇到类似的情况时——需要处理短的单行表达式——我写了一个解析器。表达式是布尔逻辑，形式为
n1 = y and n2 > z
n2 != x or (n3 > y and n4 = z)
等等。在英语中，你可以说有由 AND 和 OR 连接的原子，每个原子都有三个元素 - 左侧属性、运算符和值。因为它非常简洁，我认为解析更容易。可能的属性集是已知的和有限的（例如：名称、大小、时间）。运算符因属性而异：不同的属性采用不同的运算符集。可能值的范围和格式也因属性而异。
为了解析，我使用 String.Split() 在空格上拆分字符串。后来我意识到，在 Split() 之前，我需要对输入字符串进行规范化——在括号前后插入空格。我用 regex.Replace() 做到了这一点。
拆分的输出是一个令牌数组。然后在一个大的 for 循环中进行解析，并在左侧属性值上进行切换。在循环的每一次循环中，我都被设置为啜饮一组代币。如果第一个令牌是一个开放括号，那么该组只是一个长度令牌：括号本身。对于众所周知的标记 - 我的属性值 - 解析器必须在一组 3 个标记中啜饮，每个标记用于名称、运算符和值。如果在任何时候没有足够的标记，解析器就会抛出异常。基于令牌流，解析器状态会改变。连接（AND，OR，XOR）意味着将前一个原子推入堆栈，当下一个原子完成时，我会弹出前一个原子并将这两个原子连接成一个复合原子。等等。
Atom current;
for (int i=0; i < tokens.Length; i++)
{
switch (tokens[i].ToLower())
{
case "name":
if (tokens.Length <= i + 2)
throw new ArgumentException();
Comparison o = (Comparison) EnumUtil.Parse(typeof(Comparison), tokens[i+1]);
current = new NameAtom { Operator = o, Value = tokens[i+2] };
i+=2;
stateStack.Push(ParseState.AtomDone);
break;
case "and":
case "or":
if (tokens.Length <= i + 3)
throw new ArgumentException();
pendingConjunction = (LogicalConjunction)Enum.Parse(typeof(LogicalConjunction), tokens[i].ToUpper());
current = new CompoundAtom { Left = current, Right = null, Conjunction = pendingConjunction };
atomStack.Push(current);
break;
case "(":
state = stateStack.Peek();
if (state != ParseState.Start && state != ParseState.ConjunctionPending && state != ParseState.OpenParen)
throw new ArgumentException();
if (tokens.Length <= i + 4)
throw new ArgumentException();
stateStack.Push(ParseState.OpenParen);
break;
case ")":
state = stateStack.Pop();
if (stateStack.Peek() != ParseState.OpenParen)
throw new ArgumentException();
stateStack.Pop();
stateStack.Push(ParseState.AtomDone);
break;
// more like that...
case "":
// do nothing in the case of whitespace
break;
default:
throw new ArgumentException(tokens[i]);
}
// insert housekeeping for parse states here
}
那是简化的，只是一点点。但想法是每个案例陈述都相当简单。在表达式的原子单元中解析很容易。棘手的部分是将它们适当地结合在一起。
这个技巧是在管理部分完成的，在每个 slurp 循环结束时，使用状态堆栈和原子堆栈。根据解析器状态，可能会发生不同的事情。正如我所说，在每个 case 语句中，解析器状态可能会发生变化，之前的状态会被压入堆栈。然后在 switch 语句的末尾，如果状态说我刚刚完成了一个原子的解析，并且有一个未决的连词，我会将刚刚解析的原子移动到 CompoundAtom 中。代码如下所示：
state = stateStack.Peek();
if (state == ParseState.AtomDone)
{
stateStack.Pop();
if (stateStack.Peek() == ParseState.ConjunctionPending)
{
while (stateStack.Peek() == ParseState.ConjunctionPending)
{
var cc = critStack.Pop() as CompoundAtom;
cc.Right = current;
current = cc; // mark the parent as current (walk up the tree)
stateStack.Pop(); // the conjunction is no longer pending
state = stateStack.Pop();
if (state != ParseState.AtomDone)
throw new ArgumentException();
}
}
else stateStack.Push(ParseState.AtomDone);
}
另一个神奇之处是 EnumUtil.Parse。这使我可以将诸如“<”之类的内容解析为枚举值。假设您像这样定义枚举：
internal enum Operator
{
[Description(">")] GreaterThan,
[Description(">=")] GreaterThanOrEqualTo,
[Description("<")] LesserThan,
[Description("<=")] LesserThanOrEqualTo,
[Description("=")] EqualTo,
[Description("!=")] NotEqualTo
}
通常 Enum.Parse 查找枚举值的符号名称，而 < 不是有效的符号名称。EnumUtil.Parse() 查找描述中的内容。代码如下所示：
internal sealed class EnumUtil
{
/// <summary>
/// Returns the value of the DescriptionAttribute if the specified Enum value has one.
/// If not, returns the ToString() representation of the Enum value.
/// </summary>
/// <param name="value">The Enum to get the description for</param>
/// <returns></returns>
internal static string GetDescription(System.Enum value)
{
FieldInfo fi = value.GetType().GetField(value.ToString());
var attributes = (DescriptionAttribute[])fi.GetCustomAttributes(typeof(DescriptionAttribute), false);
if (attributes.Length > 0)
return attributes[0].Description;
else
return value.ToString();
}
/// <summary>
/// Converts the string representation of the name or numeric value of one or more enumerated constants to an equivilant enumerated object.
/// Note: Utilised the DescriptionAttribute for values that use it.
/// </summary>
/// <param name="enumType">The System.Type of the enumeration.</param>
/// <param name="value">A string containing the name or value to convert.</param>
/// <returns></returns>
internal static object Parse(Type enumType, string value)
{
return Parse(enumType, value, false);
}
/// <summary>
/// Converts the string representation of the name or numeric value of one or more enumerated constants to an equivilant enumerated object.
/// A parameter specified whether the operation is case-sensitive.
/// Note: Utilised the DescriptionAttribute for values that use it.
/// </summary>
/// <param name="enumType">The System.Type of the enumeration.</param>
/// <param name="value">A string containing the name or value to convert.</param>
/// <param name="ignoreCase">Whether the operation is case-sensitive or not.</param>
/// <returns></returns>
internal static object Parse(Type enumType, string stringValue, bool ignoreCase)
{
if (ignoreCase)
stringValue = stringValue.ToLower();
foreach (System.Enum enumVal in System.Enum.GetValues(enumType))
{
string description = GetDescription(enumVal);
if (ignoreCase)
description = description.ToLower();
if (description == stringValue)
return enumVal;
}
return System.Enum.Parse(enumType, stringValue, ignoreCase);
}
}
我从其他地方得到了 EnumUtil.Parse() 东西。也许在这里？
于 2009-03-05T16:59:41.993 回答
4
一个小的递归下降解析器非常适合这个。您甚至可能不必构建解析树 - 您可以在解析时进行评估。
/* here's a teeny one in C++ */
void ScanWhite(const char* &p){
while (*p==' ') p++;
}
bool ParseNum(const char* &p, double &v){
ScanWhite(p);
if (!DIGIT(*p)) return false;
const char* p0 = p;
while(DIGIT(*p)) p++;
if (*p == '.'){
p++;
while(DIGIT(*p)) p++;
}
v = /* value of characters p0 up to p */;
return true;
}
bool ParseId(const char* &p, double &v){
ScanWhite(p);
if (ALPHA(p[0]) && DIGIT(p[1])){
v = /* value of cell whose name is p[0], p[1] */;
p += 2;
return true;
}
return false;
}
bool ParseChar(const char* &p, char c){
ScanWhite(p);
if (*p != c) return false;
p++;
return true;
}
void ParseExpr(const char* &p, double &v); /* forward declaration */
void ParsePrimitive(const char* &p, double &v){
if (ParseNum(p, v));
else if (ParseId(p, v));
else if (ParseChar(p, '(')){
ParseExpr(p, v);
if (!ParseChar(p, ')'){/* throw syntax error */}
}
else {/* throw syntax error */}
}
#define PARSE_HIGHER ParsePrimitive
void ParseUnary(const char* &p, double &v){
if (ParseChar(p, '-')){
ParseUnary(p, v);
v = -v;
}
else {
PARSE_HIGHER(p, v);
}
}
#undef PARSE_HIGHER
#define PARSE_HIGHER ParseUnary
void ParseProduct(const char* &p, double &v){
double v2;
PARSE_HIGHER(p, v);
while(true){
if (ParseChar(p, '*')){
PARSE_HIGHER(p, v2);
v *= v2;
}
else if (ParseChar(p, '/')){
PARSE_HIGHER(p, v2);
v /= v2;
}
else break;
}
}
#undef PARSE_HIGHER
#define PARSE_HIGHER ParseProduct
void ParseSum(const char* &p, double &v){
double v2;
PARSE_HIGHER(p, v);
while(true){
if (ParseChar(p, '+')){
PARSE_HIGHER(p, v2);
v += v2;
}
else if (ParseChar(p, '-')){
PARSE_HIGHER(p, v2);
v -= v2;
}
else break;
}
}
#undef PARSE_HIGHER
#define PARSE_HIGHER ParseSum
void ParseExpr(const char* &p, double &v){
PARSE_HIGHER(p, v);
}
double ParseTopLevel(const char* buf){
const char* p = buf;
double v;
ParseExpr(p, v);
return v;
}
现在如果你只是调用 ParseTop，它会为你计算一个表达式的值。
使用 PARSE_HIGHER 宏的原因是更容易在中间优先级添加运算符。
执行“if”语句涉及更多内容。每个解析例程都需要一个额外的“启用”参数，因此除非启用，否则它不会进行计算。然后解析单词“if”，解析测试表达式，然后解析两个结果表达式，禁用不活动的一个。
于 2009-03-05T17:22:56.930 回答
3
您可以使用 .NET JScript 编译器，或与 IronPython、IronRuby 或 IronScheme 接口（按字母顺序命名，而不是首选项 ;p）。
于 2009-03-05T17:21:23.720 回答
2
我有一个如何不这样做的反例：Will o' the Wisp（因为这是我自己的代码，我有信心批评它）。
守则有什么好处？
- 因此，它使用了一种设计模式：解释器模式
- 它有一个相当干净的设计
- 它以一种很好的方式使用属性。
- 它产生漂亮的图形。;-)
海龟图形 http://i3.codeplex.com/Project/Download/FileDownload.aspx?ProjectName=wisp&DownloadId=34823
代码有什么不好？
- 很慢！
- 该语言在列表（数据与代码）方面定义不明确。
于 2009-03-05T14:49:25.117 回答
2
查看ANTLR。您定义语言语法，使用 GUI 工具对其进行测试并生成各种语言的源代码。开源。
于 2009-03-05T18:10:42.090 回答
2
我会推荐这本书Constructing Little Languages。它带您了解正确完成此任务所需的许多编译器基础知识。
您提出了一个事实，即除非您对您的语言有一些严格的限制，否则正则表达式将不起作用。就像其他人所说的那样，递归下降解析器可以解决问题。
于 2009-03-05T18:24:20.497 回答
1
看看这个开源项目：
于 2009-03-05T15:05:40.553 回答
0
我建议查看 CoreCalc/FunCalc 的工作： http ://www.itu.dk/people/sestoft/funcalc/
我在生产中将他们的语法用于 COCO\R 解析器生成器，它运行得非常快。
您需要做的就是： 1. 从 corecalc 获取 excel 语法 2. 在其上运行 coco.exe（为类似 excel 的表达式生成解析器） 3. 将表达式树转换为反向波兰符号 4. 简单的计算
于 2012-05-18T03:26:03.173 回答