方程式 (式) パーサーに優先順位はありますか?
https://stackoverflow.com/questions/28256
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は、二項 (+、-、|、&、*、/ など) 演算子、単項 (!) 演算子、および括弧を処理する単純なスタック アルゴリズムを使用して方程式パーサーを開発しました。
ただし、この方法を使用すると、すべてが同じ優先順位を持つことになります。括弧を使用して優先順位を強制することはできますが、演算子に関係なく左から右に評価されます。
したがって、現時点では、「1+11*5」は予想されるような 56 ではなく、60 を返します。
これは現在のプロジェクトには適していますが、後のプロジェクトでも使用できる汎用ルーチンが必要です。
わかりやすくするために編集しました:
優先順位を付けて方程式を解析するための優れたアルゴリズムは何ですか?
実装が簡単なものに興味があり、利用可能なコードのライセンスの問題を回避するために自分でコードを作成できることを理解しています。
文法：
文法の問題がわかりません。これを手書きで書きました。とてもシンプルなので、YACC や Bison の必要性は感じられません。「2+3 * (42/13)」などの式を使用して文字列を計算するだけです。
言語：
私はこれを C で実行していますが、言語固有のソリューションではなく、アルゴリズムに興味があります。C は十分に低レベルなので、必要に応じて別の言語に簡単に変換できます。
コード例
投稿しました 単純な式パーサーのテストコード 以上のことを話していました。プロジェクトの要件が変更されたため、コードはプロジェクトに組み込まれていなかったため、パフォーマンスやスペースに関してコードを最適化する必要はありませんでした。元の冗長な形式なので、すぐに理解できるはずです。演算子の優先順位に関してさらに何かを行う場合は、おそらく次のことを選択するでしょう。 マクロハック それは、プログラムの残りの部分と単純さの点で一致しているからです。ただし、これを実際のプロジェクトで使用する場合は、よりコンパクトで高速なパーサーを使用することになります。
関連する質問
-アダム
解決
困難な道
あなたが欲しいのは、 再帰降下パーサー.
優先順位を得るには、たとえばサンプル文字列を使用して、再帰的に考える必要があります。
1+11*5
これを手動で行うには、 1, 次に、プラスを見て、次から始まる全く新しい再帰的解析「セッション」を開始します。 11...そして必ず解析してください 11 * 5 独自の因子に取り込み、以下の解析ツリーを生成します。 1 + (11 * 5).
これはすべて、特に C の無力さが加わると、説明しようとするだけでもとても苦痛に感じられます。11 を解析した後、* が実際には + だった場合は、用語を作成する試みを放棄し、代わりに 11 を解析する必要があります。 11 それ自体が要因としてあります。もう頭が爆発しそうです。再帰的で適切な戦略を使えばそれは可能ですが、もっと良い方法があります...
簡単な（正しい）方法
Bison のような GPL ツールを使用する場合、Bison によって生成された C コードは GPL (IANAL) の対象になっていないため、おそらくライセンスの問題を心配する必要はありません。ただし、GPL ツールは GPL を強制しないと確信しています。生成されたコード/バイナリ。たとえば、Apple は Aperture などのコードを GCC でコンパイルし、そのコードを GPL にすることなく販売しています)。
バイソンをダウンロード (または同等のもの、ANTLR など)。
通常、bison を実行するだけで、この 4 つの関数電卓を示す目的の C コードを取得できるサンプル コードがいくつかあります。
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
生成されたコードを見て、これが思ったほど簡単ではないことがわかります。また、Bison のようなツールを使用する利点は、1) 何かを学ぶ (特にドラゴンブックを読んで文法を学ぶ場合)、2) 回避することです。 NIH（アメリカ国立衛生研究所） 車輪の再発明を試みています。実際のパーサー生成ツールを使用すると、実際に後でスケールアップして、パーサーが解析ツールの領域であることを他の知り合いに示すことができます。
アップデート：
ここの人々は多くの的確なアドバイスを提供してくれました。解析ツールをスキップしたり、Shanging Yard アルゴリズムや手動で再帰的にまともなパーサーを使用したりすることに対する唯一の警告は、その小さなおもちゃの言語です。1 いつか関数 (sin、cos、log) と変数、条件、for ループを備えた実際の大きな言語になるかもしれません。
Flex/Bison は、小規模で単純なインタプリタにとっては過剰である可能性がありますが、1 回限りのパーサ + エバリュエータでは、変更が必要な場合や機能を追加する必要がある場合に、将来的に問題が発生する可能性があります。状況はさまざまなので、自分で判断する必要があります。ただしないでください 自分の罪のために他人を罰する [2] そして十分とは言えないツールを構築します。
私のお気に入りの解析ツール
この仕事に最適な世界で最も優れたツールは、 パーセク プログラミング言語 Haskell に付属するライブラリ (再帰的で適切なパーサー用)。とても似ています BNF, 、または解析用の特殊なツールやドメイン固有の言語 (サンプル コード [3]) のようなものですが、実際には Haskell の通常のライブラリであり、Haskell コードの残りの部分と同じビルド ステップでコンパイルされることを意味します。任意の Haskell コードを記述してパーサー内で呼び出すことができ、他のライブラリを組み合わせて使用することもできます すべて同じコード内で. 。(ところで、このような解析言語を Haskell 以外の言語に埋め込むと、構文が大量に不細工になります。これを C# で実行したところ、非常にうまく機能しましたが、それほど美しく簡潔ではありませんでした。)
ノート：
1 リチャード・ストールマンは次のように述べています。 Tcl を使用してはいけない理由
EMACSの主な教訓は、拡張機能の言語は単なる「拡張言語」であってはならないということです。これは、実質的なプログラムを作成および維持するために設計された実際のプログラミング言語である必要があります。人々はそれをしたいと思うからです！
[2] はい、私はその「言語」を使用したことで永遠に傷を負っています。
また、このエントリーを送信したとき、プレビューは正しく表示されましたが、 SO の適切ではないパーサーが最初の段落の終了アンカー タグを食い込んでしまいました, 正規表現や 1 回限りのハックを使用する場合、パーサーは無視できるものではないことが証明されています。 おそらく何か微妙で小さな間違いを犯すでしょう.
[3] Parsec を使用した Haskell パーサーのスニペット:指数、括弧、乗算用の空白、および定数 (pi や e など) で拡張された 4 つの関数の計算機。
aexpr = expr `chainl1` toOp
expr = optChainl1 term addop (toScalar 0)
term = factor `chainl1` mulop
factor = sexpr `chainr1` powop
sexpr = parens aexpr
<|> scalar
<|> ident
powop = sym "^" >>= return . (B Pow)
<|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))
toOp = sym "->" >>= return . (B To)
mulop = sym "*" >>= return . (B Mul)
<|> sym "/" >>= return . (B Div)
<|> sym "%" >>= return . (B Mod)
<|> return . (B Mul)
addop = sym "+" >>= return . (B Add)
<|> sym "-" >>= return . (B Sub)
scalar = number >>= return . toScalar
ident = literal >>= return . Lit
parens p = do
lparen
result <- p
rparen
return result
他のヒント
の 操車場アルゴリズム はこれに最適なツールです。Wikipedia はこれについて非常にわかりにくいですが、基本的にアルゴリズムは次のように機能します。
たとえば、1 + 2 * 3 + 4 を評価したいとします。直感的には、最初に 2 * 3 を実行する必要があることは「わかっています」が、どうすればこの結果が得られるでしょうか?重要なのは、文字列を左から右にスキャンするときに、演算子が次の場合に評価されることを認識することです。 続く 優先順位はそれより低い (または同等) です。この例のコンテキストでは、やりたいことは次のとおりです。
- 見る：1 + 2、何もしません。
- ここで 1 + 2 * 3 を見てください。まだ何もしていません。
- 次に、1 + 2 * 3 + 4 を見てください。次の演算子の優先順位が低いため、2 * 3 を評価する必要があることがわかります。
これをどのように実装しますか?
スタックを 2 つ用意し、1 つは数値用、もう 1 つは演算子用とします。常に数値をスタックにプッシュします。新しい演算子をスタックの一番上にある演算子と比較し、スタックの一番上にある演算子の優先順位が高い場合は、その演算子を演算子スタックからポップし、オペランドを数値スタックからポップし、演算子を適用して結果をプッシュします。番号スタックに追加します。ここで、スタックの最上位演算子との比較を繰り返します。
例に戻ると、次のように動作します。
n = [] ops = [
- 1を読んでください。N = [1]、オペレーション = [ ]
- +を読んでください。N = [1]、Ops = [+]
- 2を読んでください。N = [1 2]、Ops = [+]
- 読む
*. 。N = [1 2]、Ops = [+ *] - 3を読んでください。N = [1 2 3]、オペレーション = [+ *]
- +を読んでください。N = [1 2 3]、オペレーション = [+ *]
- 3、2をポップして2を実行する
*3、結果を N にプッシュします。N = [1 6]、Ops = [+] +は左結合なので、1、6 もポップして + を実行したいとします。N = [7]、Ops = []。- 最後に [+] を演算子スタックにプッシュします。N = [7]、Ops = [+]。
- 3、2をポップして2を実行する
- 4を読んでください。N = [7 4]。作戦 = [+]。
- 入力がなくなったので、今すぐスタックを空にしたいとします。これにより、結果11が得られます。
あれ、そんなに難しくないですよね？また、文法やパーサー ジェネレーターを呼び出すことはありません。
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
さまざまなアプローチについての非常にわかりやすい説明:
- 再帰降下認識
- 操車場アルゴリズム
- 古典的な解決策
- 先行登山
簡単な言語と疑似コードで書かれています。
私は「先行登山」が好きです。
素敵な記事がありましたよ ここ 単純な再帰降下パーサーと演算子優先順位解析の組み合わせについて。最近パーサーを作成している場合は、読むと非常に興味深く、有益になるはずです。
昔、私は解析に関する本 (ドラゴンブックなど) には載っていなかった独自の解析アルゴリズムを作成しました。操車場アルゴリズムへのポインタを見ると、確かに類似点がわかります。
約 2 年前、私は Perl ソース コードを完備したこの記事を次のサイトに投稿しました。 http://www.perlmonks.org/?node_id=554516. 。他の言語への移植は簡単です。私が行った最初の実装は Z80 アセンブラでした。
これは数値を直接計算するのに最適ですが、必要に応じて解析ツリーを生成するために使用できます。
アップデート より多くの人が Javascript を読める (または実行できる) ため、コードを再編成した後、パーサーを Javascript で再実装しました。パーサー全体は、エラー報告とコメントを含めて 5k の Javascript コード (パーサーで約 100 行、ラッパー関数で 15 行) 未満です。
ライブデモは次の場所にあります。 http://users.telenet.be/bartl/expressionParser/expressionParser.html.
// operator table
var ops = {
'+' : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } },
'-' : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return l-r; } },
'*' : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } },
'/' : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } },
'**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } }
};
// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };
// input for parsing
// var r = { string: '123.45+33*8', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
var startOffset = r.offset;
var value;
var m;
// floating point number
// example of parsing ("lexing") without aid of regular expressions
value = 0;
while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
if(r.string.substr(r.offset, 1) == ".") {
r.offset++;
while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
}
if(r.offset > startOffset) { // did that work?
// OK, so I'm lazy...
return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
} else if(r.string.substr(r.offset, 1) == "+") { // unary plus
r.offset++;
return parseVal(r);
} else if(r.string.substr(r.offset, 1) == "-") { // unary minus
r.offset++;
return negate(parseVal(r));
} else if(r.string.substr(r.offset, 1) == "(") { // expression in parens
r.offset++; // eat "("
value = parseExpr(r);
if(r.string.substr(r.offset, 1) == ")") {
r.offset++;
return value;
}
r.error = "Parsing error: ')' expected";
throw 'parseError';
} else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) { // variable/constant name
// sorry for the regular expression, but I'm too lazy to manually build a varname lexer
var name = m[0]; // matched string
r.offset += name.length;
if(name in vars) return vars[name]; // I know that thing!
r.error = "Semantic error: unknown variable '" + name + "'";
throw 'unknownVar';
} else {
if(r.string.length == r.offset) {
r.error = 'Parsing error at end of string: value expected';
throw 'valueMissing';
} else {
r.error = "Parsing error: unrecognized value";
throw 'valueNotParsed';
}
}
}
function negate (value) {
return -value;
}
function parseOp(r) {
if(r.string.substr(r.offset,2) == '**') {
r.offset += 2;
return ops['**'];
}
if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
return ops[r.string.substr(r.offset++, 1)];
return null;
}
function parseExpr(r) {
var stack = [{precedence: 0, assoc: 'L'}];
var op;
var value = parseVal(r); // first value on the left
for(;;){
op = parseOp(r) || {precedence: 0, assoc: 'L'};
while(op.precedence < stack[stack.length-1].precedence ||
(op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) {
// precedence op is too low, calculate with what we've got on the left, first
var tos = stack.pop();
if(!tos.exec) return value; // end reached
// do the calculation ("reduce"), producing a new value
value = tos.exec(tos.value, value);
}
// store on stack and continue parsing ("shift")
stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
value = parseVal(r); // value on the right
}
}
function parse (string) { // wrapper
var r = {string: string, offset: 0};
try {
var value = parseExpr(r);
if(r.offset < r.string.length){
r.error = 'Syntax error: junk found at offset ' + r.offset;
throw 'trailingJunk';
}
return value;
} catch(e) {
alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset));
return;
}
}
現在解析に使用している文法を説明していただけると助かります。問題はそこにあるかもしれません!
編集：
あなたが文法の問題を理解しておらず、「これを手書きで書いた」という事実は、「1+11*5」の形式 (つまり、演算子の優先順位) の式で問題が発生している理由を説明している可能性が非常に高いです。 。たとえば、「算術式の文法」でグーグル検索すると、いくつかの適切なヒントが得られるはずです。このような文法は複雑である必要はありません。
<Exp> ::= <Exp> + <Term> |
<Exp> - <Term> |
<Term>
<Term> ::= <Term> * <Factor> |
<Term> / <Factor> |
<Factor>
<Factor> ::= x | y | ... |
( <Exp> ) |
- <Factor> |
<Number>
たとえば、これはうまく機能し、より複雑な式 (たとえば、べき乗などの関数を含む) を処理するために簡単に拡張できます。
見てみることをお勧めします これ たとえば、スレッド。
文法/構文解析のほとんどすべての入門書では、算術式が例として扱われます。
文法の使用は、特定のツールの使用を意味するものではないことに注意してください (ああ ヤック、バイソン、...)。実際、あなたはすでに次の文法を使用していることは間違いありません。
<Exp> :: <Leaf> | <Exp> <Op> <Leaf>
<Op> :: + | - | * | /
<Leaf> :: <Number> | (<Exp>)
（またはそのようなもの）知らずに！
使用することを考えましたか 精神を高める?これにより、次のように EBNF に似た文法を C++ で記述することができます。
group = '(' >> expression >> ')';
factor = integer | group;
term = factor >> *(('*' >> factor) | ('/' >> factor));
expression = term >> *(('+' >> term) | ('-' >> term));
質問をするとき、再帰はまったく必要ありません。答えは次の 3 つです。後置記法と操車場アルゴリズムと後置式の評価:
1)。後置表記 = 明示的な優先順位の指定の必要性を排除するために発明されました。詳細はネットで読んでくださいが、要点は次のとおりです。infix 式 ( 1 + 2 ) * 3 は人間にとっては読みやすく処理しやすいですが、マシンによる計算にはあまり効率的ではありません。とは？「優先的にキャッシュして式を書き換え、常に左から右に処理する」という単純なルール。したがって、中置 ( 1 + 2 ) * 3 は後置 12+3* になります。演算子は常にオペランドの後に配置されるため、POST になります。
2)。後置式を評価しています。簡単。後置文字列から数値を読み取ります。オペレーターが現れるまで、それらをスタックにプッシュします。演算子の種類を確認してください - 単項?バイナリ？三次？この演算子を評価するために必要な数のオペランドをスタックからポップします。評価する。結果をスタックにプッシュして戻します。そして、もうすぐ終わります。スタックが探しているエントリ = 値が 1 つだけになるまで、これを続けます。
後置にある ( 1 + 2 ) * 3 は "12+3*" にしてみましょう。最初の番号 = 1 を読み取ります。スタックにプッシュします。次に読んでください。数 = 2。スタックにプッシュします。次に読んでください。オペレーター。どれ？+。何の種類ですか？Binary = には 2 つのオペランドが必要です。スタックを 2 回ポップします = argright は 2、argleft は 1 です。1 + 2 は 3 です。3 をスタックに戻します。後置文字列から次を読み取ります。それは数字です。3.押します。次に読んでください。オペレーター。どれ？*。何の種類ですか？バイナリ = 2 つの数値が必要 -> スタックを 2 回ポップします。最初に argright にポップし、2 回目で argleft にポップします。操作を評価します - 3 の 3 倍は 9 です。スタックに 9 をプッシュします。次の接尾文字を読み取ります。ヌルですよ。入力終了。ポップ スタック onec = それがあなたの答えです。
3)。Shanting Yard は、人間が (簡単に) 読める中置式を後置式に変換するために使用されます (これも、ある程度練習すれば人間が簡単に読める)。手動でコーディングするのが簡単です。上記のコメントとネットを参照してください。
それはあなたがそれをどの程度「一般的」にしたいかによって異なります。
sin(4+5)*cos(7^3) のような数学関数を解析できるようにするなど、本当に一般的なものにしたい場合は、おそらく 解析ツリー。
その中で、完全な実装をここに貼り付けるのは適切ではないと思います。悪名高い「」の 1 つをチェックしてみることをお勧めします。ドラゴンブック".
ただし、優先サポートだけが必要な場合は、, 、その後、最初に式を後置形式に変換することで、コピーアンドペーストできるアルゴリズムを利用できるようにすることができます。 グーグル あるいは、バイナリ ツリーを使用して自分でコーディングすることもできると思います。
後置形式で作成すれば、スタックがどのように役立つかをすでに理解しているので、それ以降は簡単です。
不正行為をして使用することをお勧めします 操車場のアルゴリズム. 。これは単純な計算機タイプのパーサーを作成する簡単な手段であり、優先順位が考慮されます。
物事を適切にトークン化し、変数などを使用したい場合。関与している場合は、ここで他の人が提案しているように、再帰降下パーサーを作成します。ただし、単に計算機スタイルのパーサーが必要な場合は、このアルゴリズムで十分です:-)
PIClist でこれを見つけました。 操車場のアルゴリズム:
ハロルドはこう書いています。
ずっと前に、代数式をRPNに変換して簡単に評価したアルゴリズムを読んだことを覚えています。各INFIX値またはオペレーターまたは括弧は、トラック上の鉄道車両で表されました。あるタイプの車は別のトラックに分かれ、もう1つの車はまっすぐに続きました。私は詳細を覚えていません（明らかに！）が、コーディングするのは面白いといつも思っていました。これは、私が6800（68000ではない）アセンブリコードを書いていたときに戻ってきました。
これは「シャントヤードアルゴリスム」であり、ほとんどのマシンパーサーが使用するものです。ウィキペディアでの解析に関する記事をご覧ください。シャントヤードアルゴリスをコーディングする簡単な方法は、2つのスタックを使用することです。1つは「プッシュ」スタック、もう1つは「削減」または「結果」スタックです。例：
pstack =（）//空のrstack =（）input：1+2*3優先= 10 //最低減量= 0 //減少しないでください
始める：トークン「1」:isNumber、pstack（push）token '+'に入れます：ISOPERATOR SET PREDENCE = 2 PREDENCE <PROWER_OPERATOR_PRECEDENCEの場合、reduce（）isNumber、pstack（push）token '*'に入れます：ISOPERATOR、優先順位= 1を設定し、pstack（プッシュ）//優先順位を確認します//上記のトークン '3'：isNumber、入力の端にpstack（プッシュ）に入れ、削減する必要があります（目標は空のpstackです）reduce（）// done
プッシュスタックからポップ要素を削減し、結果スタックに入れて、「オペレーター」の形式の場合は、常にPSTackの上位2つのアイテムを交換します。
psスタック:'1' '+' '2' '' '3' rスタック:（）...psスタック:() rスタック:「3」「2」' '1' '+'
式が次のようになった場合:
1*2+3
その後、削減トリガーは、すでにプッシュされている「*」よりもPrecendeceが低いトークン '+'の読み物だったので、次のことができたはずです。
psスタック:'1' '' '2' rスタック:() ...psスタック:() rスタック:「1」「2」'
そして、「+」を押してから「3」を押してから、最後に減少しました。
psスタック:'+' '3' rスタック:「1」「2」'...psスタック:() rスタック:「1」「2」' '3' '+'
したがって、短いバージョンは次のとおりです。プッシュ番号を押すと、オペレーターが前のオペレーターの優先順位を確認します。今すぐプッシュされるオペレーターよりも高い場合は、最初に減少し、次に現在のオペレーターを押します。Parensを処理するには、単に「前の」演算子の優先順位を節約し、Parenペアの内部を解くときに削減を停止するように削減するように指示するPSTackにマークを付けます。クロージングパレンは、入力の終了と同様に削減をトリガーし、PSTackから開いたParenマークを削除し、「以前の操作」の優先順位を復元するため、ペルシングが締め切りの終わりの後に続くことができます。これは、再帰またはなしで行うことができます（ヒント：スタックを使用して、 '（' ...）に遭遇したときに前の優先順位を保存します。これの一般化されたバージョンは、Shunting Yard Algorythm、F.Exを実装したパーサージェネレーターを使用することです。YACCまたはバイソンまたはタックル（YACCのTCLアナログ）を使用します。
ピーター
-アダム
超コンパクト (1 クラス、< 10 KiB) のソースを投稿しました。 Java 数学評価者 私のウェブサイトで。これは、受け入れられた回答の投稿者の頭蓋爆発を引き起こしたタイプの再帰的降下パーサーです。
完全な優先順位、括弧、名前付き変数、および単一引数関数をサポートします。
に基づいた式パーサーをリリースしました ディクストラの操車場 の条件に基づくアルゴリズム Apache ライセンス 2.0:
優先順位解析のためのもう 1 つのリソースは、 演算子優先パーサー ウィキペディアの項目。ダイクストラの操車場アルゴリズムとツリー代替アルゴリズムをカバーしていますが、より注目すべきは、優先順位を無視したパーサーの前に簡単に実装できる非常に単純なマクロ置換アルゴリズムをカバーしていることです。
#include <stdio.h>
int main(int argc, char *argv[]){
printf("((((");
for(int i=1;i!=argc;i++){
if(argv[i] && !argv[i][1]){
switch(argv[i]){
case '^': printf(")^("); continue;
case '*': printf("))*(("); continue;
case '/': printf("))/(("); continue;
case '+': printf(")))+((("); continue;
case '-': printf(")))-((("); continue;
}
}
printf("%s", argv[i]);
}
printf("))))\n");
return 0;
}
次のように呼び出します。
$ cc -o parenthesise parenthesise.c
$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))
これはそのシンプルさにおいて素晴らしく、非常に理解しやすいものです。
を実装しました 再帰降下パーサー Javaでは MathEclipse パーサー プロジェクト。として使用することもできます Google ウェブ ツールキット モジュール
私は現在、デザイン パターンと可読プログラミングの学習ツールとして正規表現パーサーを構築する一連の記事に取り組んでいます。見てみることができます 読み取り可能なコード. 。この記事では、操車場アルゴリズムの明確な使用法を紹介しています。
F# で式パーサーを書きました。 ここでそれについてブログに書きました. 。操車場アルゴリズムを使用しますが、中置から RPN に変換する代わりに、計算結果を蓄積するために 2 番目のスタックを追加しました。演算子の優先順位は正しく処理されますが、単項演算子はサポートされません。ただし、これを書いたのは F# を学ぶためであり、式の解析を学ぶためではありません。
pyparsing を使用した Python ソリューションが見つかります。 ここ. 。優先順位を付けてさまざまな演算子を使用して中置表記を解析することはかなり一般的であるため、pyparsing には次のものも含まれます。 infixNotation (以前は operatorPrecedence) 式ビルダー。これを使用すると、たとえば「AND」、「OR」、「NOT」などを使用してブール式を簡単に定義できます。または、4 関数算術を拡張して、! などの他の演算子を使用することもできます。階乗の場合は '%'、係数の場合は '%'、または P 演算子と C 演算子を追加して順列と組み合わせを計算します。「-1」または「T」演算子 (反転および転置用) の処理を含む、行列表記用の中置パーサーを作成できます。4 関数パーサーの OperatorPrecedence の例 (楽しみのために「!」がスローされています) は次のとおりです。 ここ より完全な機能を備えたパーサーとエバリュエーターは、 ここ.
これが遅い答えであることは承知していますが、すべての演算子（前置、後置および中置左、中置右および非結合）に任意の優先順位を設定できる小さなパーサーを作成したところです。
これを任意の DSL サポートを持つ言語に拡張するつもりですが、演算子の優先順位を決めるためのカスタム パーサーは必要なく、テーブルをまったく必要としない汎用パーサーを使用できることを指摘したかっただけです。表示される各演算子の優先順位を調べるだけです。不正な入力を受け入れることができるカスタムの Pratt パーサーや操車場パーサーについて言及する人がいます。これはカスタマイズする必要がなく、(バグがない限り) 不正な入力を受け入れません。これはある意味で完全ではなく、アルゴリズムをテストするために書かれており、その入力は前処理が必要な形式になっていますが、それを明確にするコメントがあります。
注：いくつかの一般的な種類の演算子は、IEテーブル[インデックス]または関数関数の呼び出し（パラメーター - 発現など）に使用されるオペレーターの種類がありません。デリメーターの['と']または '（' and '）'の間にあるものが、式パーサーの別のインスタンスで解析される場合。省略して申し訳ありませんが、後置部分は含まれています。残りを追加すると、おそらくコードのサイズがほぼ 2 倍になります。
パーサーはわずか 100 行のラケット コードなので、おそらくここに貼り付けるだけでよいでしょう。スタックオーバーフローが許可する長さを超えないことを願っています。
恣意的な決定に関するいくつかの詳細:
優先順位の低い後置演算子が、優先順位の低い前置演算子と同じ中置ブロックをめぐって競合する場合、前置演算子が勝ちます。ほとんどの言語には優先順位の低い後置演算子がないため、これはほとんどの言語では発生しません。- 例えば：（（データa）（左1 +）（pre 2 not）（data b）（post 3！）（左1 +）（左1 +）（データc））a +not b！ +cは、プレフィックス演算子です。Postfix演算子であり、どちらも+よりも優先されないため、互換性のない方法で（a+not b！）+cまたはa+（b！+cではない）としてグループ化したいので、プレフィックス演算子は常に勝ちます。 2つ目は、それが解析する方法です
非結合中置演算子は、実際には、受け取った型とは異なる型を返す演算子が一緒に意味をなすかのように装う必要がないようにするために存在しますが、それぞれに異なる式の型を持たないと、それは面倒なことになります。そのため、このアルゴリズムでは、非結合演算子は、それ自体だけでなく、同じ優先順位を持つ演算子との関連付けも拒否します。ほとんどの言語では < <= == >= などは相互に関連付けられていないため、これは一般的なケースです。
異なる種類の演算子 (左、接頭辞など) が優先順位の関係をどのように破るかという問題は、浮上すべきではありません。異なる種類の演算子に同じ優先順位を与えるのは実際には意味がないからです。このアルゴリズムはそのような場合に何らかの処理を行いますが、そもそもそのような文法は悪い考えであるため、正確に何をするのかを理解する気にもなりません。
#lang racket
;cool the algorithm fits in 100 lines!
(define MIN-PREC -10000)
;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp)
;for example "not a*-7+5 < b*b or c >= 4"
;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))"
;is represented as '((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 <)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4))
;higher numbers are higher precedence
;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c))
(struct prec-parse ([data-stack #:mutable #:auto]
[op-stack #:mutable #:auto])
#:auto-value '())
(define (pop-data stacks)
(let [(data (car (prec-parse-data-stack stacks)))]
(set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))
data))
(define (pop-op stacks)
(let [(op (car (prec-parse-op-stack stacks)))]
(set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))
op))
(define (push-data! stacks data)
(set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks))))
(define (push-op! stacks op)
(set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks))))
(define (process-prec min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((>= (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-prec min-prec stacks))))))))
(define (process-nonassoc min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((> (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-nonassoc min-prec stacks))
((= (cadr op) min-prec) (error "multiply applied non-associative operator"))
))))))
(define (apply-op op stacks)
(let [(op-type (car op))]
(cond ((eq? op-type 'post)
(push-data! stacks `(,op ,(pop-data stacks) )))
(else ;assume infix
(let [(tos (pop-data stacks))]
(push-data! stacks `(,op ,(pop-data stacks) ,tos)))))))
(define (finish input min-prec stacks)
(process-prec min-prec stacks)
input
)
(define (post input min-prec stacks)
(if (null? input) (finish input min-prec stacks)
(let* [(cur (car input))
(input-type (car cur))]
(cond ((eq? input-type 'post)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(process-prec (cadr cur)stacks)
(push-data! stacks (cons cur (list (pop-data stacks))))
(post (cdr input) min-prec stacks))))
(else (let [(handle-infix (lambda (proc-fn inc)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(proc-fn (+ inc (cadr cur)) stacks)
(push-op! stacks cur)
(start (cdr input) min-prec stacks)))))]
(cond ((eq? input-type 'left) (handle-infix process-prec 0))
((eq? input-type 'right) (handle-infix process-prec 1))
((eq? input-type 'nonassoc) (handle-infix process-nonassoc 0))
(else error "post op, infix op or end of expression expected here"))))))))
;alters the stacks and returns the input
(define (start input min-prec stacks)
(if (null? input) (error "expression expected")
(let* [(cur (car input))
(input-type (car cur))]
(set! input (cdr input))
;pre could clearly work with new stacks, but could it reuse the current one?
(cond ((eq? input-type 'pre)
(let [(new-stack (prec-parse))]
(set! input (start input (cadr cur) new-stack))
(push-data! stacks
(cons cur (list (pop-data new-stack))))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks)))
((eq? input-type 'data)
(push-data! stacks cur)
(post input min-prec stacks))
((eq? input-type 'grouped)
(let [(new-stack (prec-parse))]
(start (cdr cur) MIN-PREC new-stack)
(push-data! stacks (pop-data new-stack)))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks))
(else (error "bad input"))))))
(define (op-parse input)
(let [(stacks (prec-parse))]
(start input MIN-PREC stacks)
(pop-data stacks)))
(define (main)
(op-parse (read)))
(main)
以下は、Java で書かれた単純なケース再帰ソリューションです。負の数は処理できないことに注意してください。ただし、必要に応じて追加できます。
public class ExpressionParser {
public double eval(String exp){
int bracketCounter = 0;
int operatorIndex = -1;
for(int i=0; i<exp.length(); i++){
char c = exp.charAt(i);
if(c == '(') bracketCounter++;
else if(c == ')') bracketCounter--;
else if((c == '+' || c == '-') && bracketCounter == 0){
operatorIndex = i;
break;
}
else if((c == '*' || c == '/') && bracketCounter == 0 && operatorIndex < 0){
operatorIndex = i;
}
}
if(operatorIndex < 0){
exp = exp.trim();
if(exp.charAt(0) == '(' && exp.charAt(exp.length()-1) == ')')
return eval(exp.substring(1, exp.length()-1));
else
return Double.parseDouble(exp);
}
else{
switch(exp.charAt(operatorIndex)){
case '+':
return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));
case '-':
return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));
case '*':
return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));
case '/':
return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));
}
}
return 0;
}
}
アルゴリズムは、再帰降下パーサーとして C で簡単にエンコードできます。
#include <stdio.h>
#include <ctype.h>
/*
* expression -> sum
* sum -> product | product "+" sum
* product -> term | term "*" product
* term -> number | expression
* number -> [0..9]+
*/
typedef struct {
int value;
const char* context;
} expression_t;
expression_t expression(int value, const char* context) {
return (expression_t) { value, context };
}
/* begin: parsers */
expression_t eval_expression(const char* symbols);
expression_t eval_number(const char* symbols) {
// number -> [0..9]+
double number = 0;
while (isdigit(*symbols)) {
number = 10 * number + (*symbols - '0');
symbols++;
}
return expression(number, symbols);
}
expression_t eval_term(const char* symbols) {
// term -> number | expression
expression_t number = eval_number(symbols);
return number.context != symbols ? number : eval_expression(symbols);
}
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != '*')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
expression_t eval_sum(const char* symbols) {
// sum -> product | product "+" sum
expression_t product = eval_product(symbols);
if (*product.context != '+')
return product;
expression_t sum = eval_sum(product.context + 1);
return expression(product.value + sum.value, sum.context);
}
expression_t eval_expression(const char* symbols) {
// expression -> sum
return eval_sum(symbols);
}
/* end: parsers */
int main() {
const char* expression = "1+11*5";
printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value);
return 0;
}
次のライブラリが役立つかもしれません: ユパナ - 厳密に算術演算。 tinyexpr - 算術演算 + C 数学関数 + ユーザーが提供する 1 つ; mpc - パーサーコンビネータ
説明
代数式を表す一連の記号を捉えてみましょう。最初の 1 つは数値、つまり 10 進数を 1 回以上繰り返すものです。このような表記を制作ルールと呼びます。
number -> [0..9]+
加算演算子とそのオペランドは別のルールです。それはどちらかです number またはそれを表す記号 sum "*" sum 順序。
sum -> number | sum "+" sum
代替品を試してみる number の中へ sum "+" sum それはそうなるだろう number "+" number これは次のように拡張できます [0..9]+ "+" [0..9]+ それは最終的に次のように削減できます 1+8 これは正しい加算式です。
他の置換でも正しい式が生成されます。 sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5
少しずつ、一連の制作ルールに似ていくことができます 別名文法 可能なすべての代数表現を表現します。
expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+
演算子の優先順位を制御するには、他の生成ルールに対する生成ルールの位置を変更します。上記の文法を見て、次の生成ルールに注目してください。 * 下に置かれています + これは強制的になります product 前に評価する sum。実装ではパターン認識と評価を組み合わせるだけなので、運用ルールが厳密に反映されます。
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != '*')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
ここで評価します term まず、ない場合は返却します * その後の文字 これは私たちの制作ルールで自由に選択できます それ以外の場合 - 後のシンボルを評価して返します term.value * product.value これは私たちの制作ルールでは正しい選択です。つまり、 term "*" product
