質問
ユーザーがExcelに似た式を記述できるようにする必要があるアプリケーションがあります:
(H1 +(D1 / C3))* I8
その他のより複雑なもの
If(H1 = 'True'、D3 * .2、D3 * .5)
私は正規表現でしかできません。これを行うための正しいアプローチに関する提案や、私が学ぶことができるリソースは大歓迎です。
ありがとう!
解決
他のヒント
同様の状況(短い1行の式を処理する必要性)に直面したとき、パーサーを作成しました。式は次の形式のブール論理でした
n1 = y and n2 > z
n2 != x or (n3 > y and n4 = z)
など。英語では、ANDとORで結合された原子があり、各原子には3つの要素(左側の属性、演算子、および値)があると言えます。とても簡潔だったので、解析は簡単だったと思います。可能な属性のセットは既知であり、制限されています(例:名前、サイズ、時間)。演算子は属性によって異なります。属性が異なれば、演算子のセットも異なります。また、可能な値の範囲と形式は、属性によっても異なります。
解析するために、String.Split()を使用して空白文字列を分割します。 後でSplit()の前に、入力文字列を正規化する必要があることに気付きました-括弧の前後に空白を挿入します。 regex.Replace()でそれを行いました。
スプリットの出力は、トークンの配列です。次に、左側の属性値にスイッチがある大きなforループで解析が行われます。ループの各ラウンドで、トークンのグループを丸inみするように設定されました。最初のトークンがオープン括弧である場合、グループは長さがたった1つのトークン、つまり括弧でした。よく知られている名前であるトークン-私の属性値-パーサーは、名前、演算子、および値ごとに1つずつ、3つのトークンのグループを丸hadみする必要がありました。いずれかの時点で十分なトークンがない場合、パーサーは例外をスローします。トークンのストリームに基づいて、パーサーの状態が変わります。接続詞(AND、OR、XOR)は、前の原子をスタックにプッシュすることを意味し、次の原子が終了したら、前の原子をポップし、これら2つの原子を結合して複合原子にします。等々。状態管理は、パーサーの各ループの終わりに行われました。
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
}
これは単純化されていますが、ほんの少しです。しかし、アイデアは、各caseステートメントはかなり単純であるということです。式の原子単位で解析するのは簡単です。トリッキーな部分は、それらをすべて適切に結合することでした。
このトリックは、各スラップループの最後にあるハウスキーピングセクションで、状態スタックとアトムスタックを使用して達成されました。パーサーの状態に応じて、さまざまなことが発生する可能性があります。前にも述べたように、各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);
}
もう1つの魔法は、EnumUtil.Parseでした。これにより、<!> quot; <!> lt; <!> quot;のようなものを解析できます。列挙値へ。次のように列挙型を定義するとします:
internal enum Operator
{
[Description(">")] GreaterThan,
[Description(">=")] GreaterThanOrEqualTo,
[Description("<")] LesserThan,
[Description("<=")] LesserThanOrEqualTo,
[Description("=")] EqualTo,
[Description("!=")] NotEqualTo
}
通常、Enum.Parseは、列挙値のシンボル名を検索し、<!> lt;有効なシンボル名ではありません。 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()を入手しました。たぶんここに?
これには、少し再帰的なパーサーが最適です。おそらく解析ツリーを構築する必要さえありません-解析しながら評価を行うことができます。
/* 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マクロの理由は、優先順位の中間レベルで演算子を追加しやすくするためです。
<!> quot; if <!> quot;を実行するにはステートメントはもう少し複雑です。各解析ルーチンには、追加の<!> quot; enable <!> quot;が必要です。引数なので、有効にしない限り計算は行われません。次に、単語<!> quot; if <!> quot;を解析し、テスト式を解析してから、非アクティブな式を無効にして2つの結果式を解析します。
.NET JScriptコンパイラを使用するか、IronPython、IronRuby、IronSchemeとのインターフェイスを使用できます(アルファベット順、優先順位はありません; p)。
しない方法の反例があります: o <!>#8217; Wisp (これは私自身のコードであるため、それを批判する自信があります)。
コードの良い点は何ですか?
- 結果的にデザインパターンを使用します:インタープリターパターン
- かなりきれいなデザインです
- 属性を適切に使用します。
- 優れたグラフィックスを生成します。 ;-)
コードの悪い点は何ですか?
- 遅い!
- 言語はリスト(データとコード)に関して不明確です。
ANTLR をご覧ください。言語構文を定義し、GUIツールを使用してテストし、さまざまな言語のソースコードを生成します。オープンソース。
Constructing Little Languages という本をお勧めします。このタスクを適切に完了するために必要な多くのコンパイラの基本を説明します。
言語に厳しい制限がない限り、正規表現は機能しないという事実を取り上げました。他の人が言ったように、再帰降下パーサーがトリックを行います。
次に選択するのは、
このオープンソースプロジェクトをご覧ください:
CoreCalc / FunCalcの動作を確認することをお勧めします。 http://www.itu.dk/people/sestoft/funcalc/
本番環境でCOCO \ Rパーサージェネレーターの文法を使用しましたが、非常に高速に動作します。
あなたがする必要があるのは: 1. corecalcから優れた文法を取得する 2. coco.exeを実行します(Excelのような式のパーサーを生成します) 3.式ツリーを逆ポーランド表記に変換します 4.簡単な計算