المعادلة (التعبير) محلل مع الأسبقية?
https://stackoverflow.com/questions/28256
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لقد طورت معادلة محلل استخدام بسيط كومة الخوارزمية التي سوف تتعامل مع ثنائي (+, -, |, &, *, /, الخ) المشغلين ، الأحادية (!) المشغلين ، قوسين.
باستخدام هذا الأسلوب, لكن, يترك لي مع كل ما لها نفس الأسبقية - انها تقييمها من اليسار إلى اليمين بغض النظر عن المشغل ، على الرغم من أن الأسبقية يجب أن تنفذ باستخدام الأقواس.
حتى الآن "1+11*5" عوائد 60 ، ليس 56 كما قد يتوقع المرء.
في حين أن هذا هو مناسبة المشروع الحالي ، أريد أن يكون الغرض العام الروتينية يمكنني استخدامها في المشاريع.
التعديل للتوضيح:
ما هو خوارزمية جيدة لتحليل المعادلات مع الأسبقية?
أنا مهتم في شيء بسيط لتنفيذ وفهم أستطيع أن رمز نفسي لتجنب قضايا الترخيص المتاحة مع رمز.
قواعد اللغة:
أنا لا أفهم قواعد سؤال - لقد كتبت هذا من جهة.انها بسيطة بما فيه الكفاية أنني لا أرى ضرورة YACC أو البيسون.أنا فقط بحاجة لحساب الخيوط مع المعادلات مثل "2+3 * (42/13)".
اللغة:
أنا أفعل هذا في C ولكن أنا مهتم في خوارزمية وليس لغة معينة الحل.ج هو مستوى منخفض بما فيه الكفاية أنه سوف يكون من السهل تحويلها إلى لغة أخرى عند الحاجة.
التعليمات البرمجية المثال
نشرت لي اختبار مدونة بسيطة التعبير اللغوي كنت أتحدث عنه أعلاه.متطلبات المشروع تغييرها لا حاجة إلى تحسين رمز الأداء أو الفضاء كما لم تدرج في المشروع.هو في الأصل شكل مطول, و يجب أن تكون مفهومة بسهولة.إذا كنت تفعل أي شيء آخر معها من حيث الأسبقية المشغل ربما تختار الماكرو هاك لأنه يطابق بقية البرنامج في البساطة.إذا كنت تستخدم أي وقت مضى هذا في مشروع حقيقي ، على الرغم من أنني سوف تذهب أكثر إحكاما/عاجل محلل.
ذات السؤال
-آدم
المحلول
الطريق الصعب
تريد عودي النسب محلل.
للحصول على الأسبقية تحتاج إلى التفكير بشكل متكرر ، على سبيل المثال ، استخدام عينة السلسلة ،
1+11*5
للقيام بذلك يدويا ، عليك أن تقرأ 1, ثم انظر بالإضافة إلى والبدء من جديد عودي تحليل "الدورة" بدءا من 11...وتأكد من تحليل 11 * 5 إلى جانبها عامل ، مما أسفر تحليل شجرة 1 + (11 * 5).
كل هذا يشعر مؤلمة جدا حتى محاولة شرح, خصوصا مع عجز C.بعد تحليل 11, إذا * كان في الواقع + بدلا من ذلك, قد تضطر إلى التخلي عن محاولة جعل الأجل بدلا تحليل 11 نفسها كعامل.رأسي هو بالفعل تنفجر.فمن الممكن مع متكررة الكريم استراتيجية ، ولكن هناك طريقة أفضل...
سهلة (صحيح) الطريقة
إذا كنت تستخدم GPL أداة مثل البيسون ، ربما كنت لا داعي للقلق حول قضايا الترخيص منذ ج التعليمات البرمجية التي تم إنشاؤها بواسطة البيسون لا يشملها الترخيص (IANAL ولكن أنا متأكد من GPL أدوات لا قوة GPL على التعليمات البرمجية التي تم إنشاؤها/ثنائيات;على سبيل المثال التفاح يجمع رمز مثل الفتحة مع دول مجلس التعاون الخليجي وهم بيعها دون الحاجة إلى GPL قال البرمجية).
تحميل البيسون (أو ما يعادل ، ANTLR ، إلخ.).
عادة ما يكون هناك بعض التعليمات البرمجية التي يمكنك فقط تشغيل البيسون على الحصول على المطلوب ج التعليمات البرمجية التي يوضح هذا أربع وظيفة الحاسبة:
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
نظرة على التعليمات البرمجية التي تم إنشاؤها ، ونرى أن هذا ليس سهلا كما يبدو.كما مزايا استخدام أداة مثل البيسون 1) تتعلم شيئا (خصوصا إذا كنت تقرأ كتاب التنين ومعرفة قواعد النحو), 2) تجنب المعاهد الوطنية للصحة تحاول إعادة اختراع العجلة.مع محلل-مولد أداة, لديك فعلا الأمل في التوسع لاحقا تبين الآخرين تعلم أن موزعي هي مجال توزيع الأدوات.
تحديث:
الناس هنا قد عرضت الكثير من المشورة السليمة.بلدي فقط التحذير من تخطي تحليل أدوات أو فقط باستخدام تحويلة ساحة خوارزمية أو يد توالت العودية الكريم محلل هو أن لعبة صغيرة اللغات1 قد تتحول يوما ما إلى كبير الفعلية اللغات مع وظائف (sin, cos, log) و متغيرات ظروف الحلقات.
فليكس/بيسون قد يكون مبالغة صغيرة وبسيطة مترجم, ولكن واحدة من محلل+مقيم قد يسبب المتاعب على الانترنت عندما تحتاج إلى إجراء تغييرات أو الميزات تحتاج إلى إضافة.الوضع الخاص بك سوف تختلف وسوف تحتاج إلى استخدام الخاص بك الحكم ؛ فقط لا معاقبة الآخرين على خطاياك [2] وبناء أقل من كافية أداة.
المفضلة أداة تحليل
أفضل أداة في العالم للحصول على الوظيفة هو بارسيك مكتبة (العودية الكريم موزعي) الذي يأتي مع لغة البرمجة هاسكل.يبدو الكثير مثل BNF, أو بعض أداة متخصصة أو مجال محدد لغة إعراب (نموذج التعليمات البرمجية [3]) ، لكنها في الواقع مجرد مكتبة العادية في هاسكل, بمعنى أنه يجمع في نفسه بناء خطوة بقية هاسكل البرمجية ، يمكنك كتابة التعسفي هاسكل رمز المكالمات التي داخل محلل, و يمكنك مزيج المباراة المكتبات الأخرى في نفس المدونة.(تضمين تحليل لغة مثل هذا في لغة أخرى غير هاسكل النتائج في الكثير من النحوية الغبار المتراكم تحت السرير.بالمناسبة ، أنا فعلت هذا في C# و أنه يعمل بشكل جيد جدا ولكنها ليست جميلة جدا و مقتضبة.)
ملاحظات:
1 ريتشارد ستولمن يقول ، لماذا لا يجب استخدام Tcl
الدرس الرئيسي من إيماكس هو أن لغة امتداد لا ينبغي أن يكون مجرد "ملحق اللغة".ذلك يجب أن يكون حقيقيا لغة البرمجة ، مصممة الكتابة و الحفاظ على كبيرة من البرامج.لأن الناس سوف تريد أن تفعل ذلك!
[2] نعم ، أنا إلى الأبد ندوب من استخدام "اللغة".
لاحظ أيضا أنه عندما قدمت هذا الدخول معاينة الصحيح ، ولكن لذا هو أقل من كافية محلل أكل بلدي إغلاق مرساة الوسم على الفقرة الأولى, تثبت أن موزعي ليست شيئا يمكن العبث بها لأنه إذا كنت تستخدم regexes واحد قبالة الخارقة سوف تحصل على الأرجح شيء خفية وصغيرة على خطأ.
[3] مقتطف من هاسكل محلل باستخدام بارسيك:أربع وظيفة الحاسبة الموسعة مع الدعاة ، قوسين ، بيضاء من أجل الضرب و الثوابت (مثل بي و e).
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
نصائح أخرى
على تحويلة ساحة الخوارزمية هو الأداة المناسبة لهذا.ويكيبيديا هي مربكة حقا حول هذا الموضوع ، ولكن أساسا الخوارزمية تعمل مثل هذا:
تقول تريد تقييم 1 + 2 * 3 + 4.حدسي, أنت تعرف ما عليك القيام به 2 * 3 الأولى, ولكن كيف يمكنك الحصول على هذه النتيجة ؟ المفتاح هو أن ندرك أنه عندما كنت المسح الضوئي سلسلة من اليسار إلى اليمين ، سوف تقييم المشغل عند المشغل أن يلي أنه يحتوي على نسبة أقل (أو مساوية) الأسبقية.في سياق سبيل المثال, هنا ما تريد القيام به:
- أنظر:1 + 2, لا تفعل أي شيء.
- ننظر الآن 1 + 2 * 3 لا يزال لا تفعل أي شيء.
- ننظر الآن 1 + 2 * 3 + 4 أنت الآن تعرف أن 2 * 3 يجب أن يتم تقييمها لأن القادم المشغل لديه أقل الأسبقية.
كيف يمكن تنفيذ ذلك ؟
كنت تريد أن يكون اثنين من مداخن واحدة وأرقام أخرى للمشغلين.تضغط الأرقام إلى المكدس في كل وقت.قارنت كل المشغل الجديد مع واحد في الجزء العلوي من المكدس ، إذا كان واحد على الجزء العلوي من كومة له أولوية أعلى ، البوب قبالة المشغل المكدس ، البوب المعاملات من عدد المكدس, تطبيق مشغل دفع النتيجة على عدد المكدس.الآن يمكنك تكرار المقارنة مع الجزء العلوي من كومة المشغل.
بالعودة إلى المثال ، يعمل مثل هذا:
N = [ ] Ops = [ ]
- قراءة 1.N = [1] ، Ops = [ ]
- قراءة +.N = [1] ، Ops = [+]
- قراءة 2.N = [1 2] ، Ops = [+]
- قراءة
*.N = [1 2] ، Ops = [+ *] - قراءة 3.N = [1 2 3] ، Ops = [+ *]
- قراءة +.N = [1 2 3] ، Ops = [+ *]
- البوب 3 و 2 و تنفيذ 2
*3, ودفع النتيجة على N.N = [1 6] ، Ops = [+] +هو اليسار النقابي ، إذا كنت تريد أن بوب 1, 6 قبالة وكذلك تنفيذ +.N = [7] ، Ops = [].- وأخيرا دفع [+] على المشغل المكدس.N = [7] ، Ops = [+].
- البوب 3 و 2 و تنفيذ 2
- قراءة 4.N = [7 4].Ops = [+].
- أنت تهرب خارج المدخلات ، إذا كنت ترغب في تفريغ أكوام الآن.التي سوف تحصل على النتيجة 11.
هناك, هذا ليس من الصعب جدا ، أليس كذلك ؟ ويجعل أي الدعاء إلى أي قواعد أو محلل المولدات.
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
جيد جدا شرح نهج مختلفة:
- العودية-أصل الاعتراف
- تحويلة ساحة الخوارزمية
- الحل الكلاسيكي
- الأسبقية تسلق
مكتوبة بلغة بسيطة و الزائفة رمز.
أحب 'الأسبقية تسلق واحدة.
هناك مقالة رائعة هنا عن الجمع بسيطة متكررة-أصل محلل مع المشغل-الأسبقية تحليل.إذا كنت قد تم في الآونة الأخيرة كتابة موزعي ، ينبغي أن تكون مثيرة جدا للاهتمام ومفيدة القراءة.
منذ زمن طويل, أنا جعل بلدي تحليل الخوارزمية ، التي لم أجد في أي كتاب في إعراب (مثل التنين الكتاب).النظر في مؤشرات إلى تحويلة ساحة الخوارزمية, أنا لا أرى التشابه.
حول 2 منذ سنوات, أنا قدمت عن وظيفة كاملة مع بيرل شفرة المصدر ، http://www.perlmonks.org/?node_id=554516.فإنه من السهل أن منفذ إلى اللغات الأخرى:أول تنفيذ فعلته كان في Z80 المجمع.
انها مثالية المباشر الحساب مع الأرقام, ولكن يمكنك استخدامه لإنتاج تحليل شجرة إذا كنت لا بد منه.
التحديث لأن المزيد من الناس يمكن قراءة (أو تشغيل) جافا سكريبت, لقد ل reimplemented بلدي محلل في جافا سكريبت ، بعد التعليمات البرمجية قد تم تنظيمها.كل محلل تحت 5k من شفرة جافا سكريبت (حوالي 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>
سوف تفعل خدعة على سبيل المثال ، يمكن أن يكون مسلي المعزز أن تأخذ الرعاية من بعض التعبيرات المعقدة (بما في ذلك الوظائف على سبيل المثال ، أو القوى،...).
أقترح أن يكون لديك نظرة على هذا الموضوع على سبيل المثال.
تقريبا جميع مقدمات قواعد النحو/تحليل علاج التعبيرات الحسابية كمثال.
لاحظ أن استخدام قواعد اللغة لا يعني استخدام أداة معينة (a la Yacc ، البيسون،...).في الواقع, أنت بالتأكيد تستخدم بالفعل النحوية التالية:
<Exp> :: <Leaf> | <Exp> <Op> <Leaf>
<Op> :: + | - | * | /
<Leaf> :: <Number> | (<Exp>)
(أو شيئا من هذا النوع) دون أن يعرفوا ذلك!
هل فكرت باستخدام تعزيز روح?فإنه يسمح لك لكتابة EBNF مثل قواعد النحو في C++ مثل هذا:
group = '(' >> expression >> ')';
factor = integer | group;
term = factor >> *(('*' >> factor) | ('/' >> factor));
expression = term >> *(('+' >> term) | ('-' >> term));
كما يمكنك وضع سؤالك هناك حاجة إلى الإعادة مطلقا.الجواب هو ثلاثة أشياء:Postfix التدوين بالإضافة إلى تحويلة ساحة خوارزمية بالإضافة إلى Postfix تقييم التعبير:
1).Postfix التدوين = اخترع للقضاء على الحاجة صريحة الأسبقية المواصفات.اقرأ المزيد على النت ولكن هنا هو جوهر ذلك:أقحم التعبير ( 1 + 2 ) * 3 بينما من السهل على البشر أن القراءة عملية ليست فعالة جدا للحصول على الحوسبة عبر آلة.ما هو ؟ القاعدة البسيطة التي تقول "كتابة التعبير من خلال التخزين المؤقت في الأسبقية ثم دائما عملية اليسار إلى اليمين".حتى أقحم ( 1 + 2 ) * 3 يصبح postfix 12+3*.وظيفة مشغل يوضع دائما بعد المعاملات.
2).تقييم postfix التعبير.من السهل.قراءة الأرقام من postfix السلسلة.دفعهم على كومة حتى المشغل هو ينظر إليه.تحقق المشغل من النوع أحادي?ثنائي ؟ العالي?البوب العديد من المعاملات خارج المكدس حسب الحاجة لتقييم هذا المشغل.تقييم.دفع النتيجة مرة أخرى على المكدس!U r تقريبا.تستمر في فعل ذلك حتى كومة واحدة فقط الدخول = قيمة u r تبحث عنه.
دعونا نفعل ( 1 + 2 ) * 3 الذي هو في postfix هو "12+3*".قراءة العدد الأول = 1.دفع على المكدس.قراءة المقبل.عدد = 2.دفع على المكدس.قراءة المقبل.المشغل.أي واحد ؟ +.أي نوع ؟ ثنائي = يحتاج اثنين من المعاملات.البوب كومة مرتين = argright 2 و argleft هو 1.1 + 2 هو 3.دفع 3 مرة أخرى على المكدس.قراءة التالي من postfix السلسلة.لها عدد.3.دفع.قراءة المقبل.المشغل.أي واحد ؟ *.أي نوع ؟ ثنائي = يحتاج رقمين -> البوب كومة مرتين.أولا البوب في argright الثانية من الوقت في argleft.تقييم العملية 3 مرات 3 9.دفع 9 على المكدس.قراءة التالي postfix شار.إنه باطل.نهاية الإدخال.البوب كومة onec = هذا هو جوابك.
3).تحويلة ساحة يستخدم لتحويل الإنسان (بسهولة) للقراءة التعبير أقحم في postfix التعبير (الإنسان أيضا يمكن قراءتها بسهولة بعد بعض الممارسة).من السهل رمز يدويا.انظر التعليقات الواردة أعلاه و صافي.
ذلك يعتمد على كيفية "العامة" تريد لها أن تكون.
إذا كنت تريد أن تكون حقا حقا العامة مثل أن تكون قادرا على تحليل الدوال الرياضية مثل الخطيئة(4+5)*cos(7^3) سوف تحتاج على الأرجح تحليل شجرة.
والتي لا أعتقد أن التنفيذ الكامل السليم أن يكون لصق هنا.أود أن أقترح عليك أن تحقق من واحدة سيئة السمعة "التنين الكتاب".
ولكن إذا كنت ترغب فقط الأسبقية الدعم, ثم هل يمكن أن تفعل ذلك أولا تحويل تعبير إلى postfix الشكل الذي خوارزمية التي يمكنك نسخ ولصق ينبغي أن تكون متاحة من جوجل أو كنت تعتقد أنك يمكن أن رمز نفسك مع شجرة ثنائية.
عندما يكون لديك في postfix شكل ، ثم إنه قطعة من الكعكة منذ ذلك الحين منذ كنت بالفعل نفهم كيف كومة يساعد.
أود أن أقترح الغش باستخدام تحويلة ساحة الخوارزمية.انها وسيلة سهلة الكتابة آلة حاسبة بسيطة-نوع محلل و الأسبقية في الاعتبار.
إذا كنت ترغب في صحيح tokenise الأشياء متغيرات ، إلخ.المشاركة ثم أود أن استمر في الكتابة العودية النسب محلل كما اقترح من قبل الآخرين هنا ، ومع ذلك إذا كنت ببساطة تتطلب آلة حاسبة-أسلوب محلل ثم هذه الخوارزمية يجب أن تكون كافية :-)
لقد وجدت هذا على PIClist عن تحويلة ساحة الخوارزمية:
هارولد يكتب:
أذكر أني قرأت منذ زمن طويل, من خوارزمية تحويل جبري التعبيرات RPN لسهولة التقييم.كل أقحم القيمة أو المشغل أو قوس كان يمثله سيارة السكك الحديدية على المسار.واحد نوع السيارة انشقت إلى مسار آخر و آخر تابع مباشرة قدما.أنا لا أذكر التفاصيل (من الواضح!), ولكن دائما يعتقد أنه سيكون من المثير للاهتمام أن التعليمات البرمجية.هذا هو عندما كنت أكتب 6800 (لا 68000) رمز التجميع.
هذا هو "تحويلة ساحة الجوريثم" و هو ما معظم موزعي آلة استخدام.انظر المقال على تحليل في ويكيبيديا.طريقة سهلة رمز تحويلة ساحة الجوريثم هو استخدام اثنين مداخن.واحد هو "دفع" المكدس ، وغيرها من "الحد" أو "النتيجة" المكدس.على سبيل المثال:
pstack = () // فارغة rstack = () الإدخال:1+2*3 الأسبقية = 10 // أدنى تقليل = 0 // لا تقلل من
بداية:رمز '1':isnumber ، وضعت في pstack (دفع) رمز '+':isoperator مجموعة الأسبقية=2 إذا الأسبقية < previous_operator_precedence ثم خفض() // انظر أدناه وضع '+' في pstack (دفع) رمز '2':isnumber, وضعت في pstack (دفع) رمز '*':isoperator, مجموعة الأسبقية=1 ضع في pstack (دفع) // تحقق الأسبقية // فوق رمز '3':isnumber ، وضعت في pstack (دفع) نهاية المدخلات ، تحتاج إلى تقليل (الهدف فارغة pstack) تقليل() //يتم
للحد ، البوب عناصر من دفع كومة ووضعها في النتيجة كومة دائما مبادلة أعلى 2 البنود على pstack إذا كانوا من شكل 'المشغل' 'عدد':
pstack:'1' '+' '2' '''3' rstack:() ...pstack:() rstack:'3' '2' '' '1' '+'
إذا كان التعبير قد تم:
1*2+3
ثم خفض الزناد قد تم قراءة رمزية '+' التي لديها أقل من precendece '*' دفعت بالفعل, لذلك قد به:
pstack:'1' '''2' rstack:() ...pstack:() rstack:'1' '2' ''
ثم دفعت '+' ثم '3' ، ثم أخيرا تخفيض:
pstack:'+' '3' rstack:'1' '2' '' ...pstack:() rstack:'1' '2' '' '3' '+'
حتى النسخة القصيرة:دفع أرقام ، عندما دفع المشغلين التحقق الأسبقية من المشغل السابق.إذا كان أعلى من المشغل أن تكون دفعت الآن, الأولى الحد, ثم دفع الحالي المشغل.التعامل مع parens ببساطة حفظ وأسبقية 'السابق' المشغل ، ووضع علامة على pstack الذي يحكي تقليل الجوريثم إلى يتوقف الحد عند حل الداخل من paren الزوج.إغلاق paren يتسبب في انخفاض كما لا نهاية من المدخلات ، و أيضا يزيل فتح paren علامة من pstack ، يعيد 'العملية السابقة' الأسبقية حتى تحليل يمكن أن تستمر بعد إغلاق paren حيث ترك قبالة.ويمكن أن يتم هذا مع العودية أو بدون (تلميح:استخدام كومة لتخزين السابقة الأسبقية عندما مواجهة '(' ...).على المعمم نسخة من هذا هو استخدام محلل مولد تنفيذها تحويلة ساحة الجوريثم, f.ex.باستخدام yacc أو البيسون أو taccle (tcl التناظرية من yacc).
بيتر
-آدم
لقد نشرت مصدر الترا المدمجة (1 الطبقة ، < 10 وكالة: حكومة البحرين توافق) جافا الرياضيات المقيم على موقع الويب الخاص بي.هذا هو العودية النسب محلل من النوع الذي تسبب في الجمجمة انفجار ملصق الجواب المقبول.
وهو يدعم كامل الأسبقية ، قوسين اسمه المتغيرات واحدة-حجة وظائف.
لقد صدر التعبير اللغوي على أساس الخاص ديكسترا تحويلة الفناء الخوارزمية ، بموجب شروط رخصة أباتشي 2.0:
مورد آخر من أجل الأسبقية تحليل هو مشغل الأسبقية محلل الدخول على ويكيبيديا.يغطي الخاص ديكسترا تحويلة ساحة الخوارزمية و شجرة بديلة الخوارزمية ، ولكن أكثر من ذلك لا سيما يغطي بسيط حقا الكلي استبدال خوارزمية يمكن أن يكون مسلي تنفيذها أمام أي الأسبقية جاهل محلل:
#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))))
الذي هو رائع في بساطته و مفهومة جدا.
لقد نفذت عودي النسب محلل في جافا في MathEclipse محلل المشروع.فإنه يمكن أيضا أن تستخدم في Google Web Toolkit وحدة
أنا أعمل حاليا على سلسلة من المقالات بناء العادية التعبير اللغوي كأداة للتعلم من أجل تصميم أنماط للقراءة برمجة.يمكنك أن تأخذ نظرة على readablecode.ويعرض المقال واضح استخدام تحويلة ساحات الخوارزمية.
كتبت تعبير محلل في F# ، كتبت عن ذلك هنا.ويستخدم تحويلة ساحة الخوارزمية ، ولكن بدلا من تحويل من أقحم إلى RPN ، أضفت الثانية كومة تتراكم نتائج العمليات الحسابية.صحيح مقابض مشغل الأسبقية ولكن لا يدعم استخدام عوامل التشغيل الأحادية.كتبت هذا لتعلم F# لا يتعلم تحليل التعبير ، على الرغم من.
الثعبان الحل باستخدام pyparsing يمكن العثور عليها هنا.تحليل أقحم التدوين مع مختلف مشغلي مع الأسبقية هو شائع إلى حد ما و لذلك pyparsing يشمل أيضا infixNotation (سابقا operatorPrecedence) "منشئ التعبير".مع أنه يمكنك بسهولة تحديد التعبيرات المنطقية باستخدام "و", "أو", "لا", على سبيل المثال.أو يمكنك توسيع أربع وظيفة حسابية استخدام شركات أخرى ، مثل !من أجل مضروب أو '%' عن معامل أو إضافة P و ج مشغلي لحساب التباديل والتوافيق.يمكن أن تكتب أقحم محلل على مصفوفة التدوين ، ويشمل ذلك التعامل مع '-1' أو 'T' المشغلين (على عكس وتبديل).على operatorPrecedence مثال 4-وظيفة محلل (مع '!' ألقيت من أجل المتعة) ، هنا و أكثر واردة تماما محلل مقيم هو هنا.
أعرف أن هذا هو وقت متأخر من الإجابة, ولكن لقد كتبت صغيرة محلل أن يسمح لجميع المشغلين (البادئة ، postfix و أقحم اليسار ، أقحم-حق nonassociative) أن يكون التعسفي الأسبقية.
أنا ذاهب إلى توسيع هذه اللغة مع التعسفي DSL الدعم ، ولكن أردت فقط أن أشير إلى أنه لا يحتاج المرء مخصص موزعي مشغل الأسبقية, يمكن للمرء أن استخدام المعمم محلل التي لا تحتاج إلى الجداول في كل شيء ، و يبدو للتو أسبقية كل عامل كما يبدو.كان الناس بالذكر مخصص برات موزعي أو تحويلة ساحة موزعي التي يمكن أن تقبل غير قانونية المدخلات - هذه لا تحتاج إلى أن تكون مخصصة و (ما لم يكن هناك علة) لن تقبل سوء الإدخال.وأنها ليست كاملة بمعنى أنه كتب إلى اختبار خوارزمية و الإدخال في النموذج الذي سوف تحتاج إلى بعض تجهيزها ، ولكن هناك تعليقات التي تجعل من واضحة.
ملاحظة بعض الأنواع الشائعة من المشغلين في عداد المفقودين على سبيل المثال نوع من المشغل المستخدمة في فهرسة أي الجدول[فهرس] أو استدعاء دالة وظيفة(معلمة-التعبير،...) انا ذاهب لإضافة تلك ، ولكن التفكير على حد سواء كما postfix مشغلي حيث ما يأتي بين delimeters ' ["و"] " أو " ("و") ' تحليل مختلف سبيل المثال من التعبير اللغوي.آسف أن يكون ترك ذلك ، ولكن postfix جزء في إضافة بقية المحتمل أن ما يقرب من ضعف حجم التعليمات البرمجية.
منذ محلل بعد 100 خطوط من رمز مضرب, ربما يجب فقط لصق هنا, أتمنى ألا يكون هذا أطول من ستاكوفيرفلوو يسمح.
عدد قليل من التفاصيل على القرارات التعسفية:
إذا كان انخفاض الأسبقية postfix مشغل تتنافس على نفس أقحم كتل منخفضة الأسبقية البادئة مشغل البادئة مشغل انتصارات.هذا لا يأتي في معظم اللغات منذ أكثر لا يكون انخفاض الأسبقية postfix المشغلين. على سبيل المثال:((البيانات) (تركت 1 +) (متطلب سابق 2)(البيانات ب)(بعد 3 !) (من اليسار 1 +) (البيانات ج)) هو+لا ب!+ج حيث لا بادئة المشغل !هو postfix مشغل وكلاهما أقل الأسبقية من + حتى أنها تريد أن الفريق في تتعارض طرق إما (a+لا ب!)+ج أو كما a+(لا ب!+ج) في هذه الحالات البادئة مشغل يفوز دائما ، هو الطريقة التي يوزع
Nonassociative أقحم مشغلي حقا هناك بحيث لا يجب أن ندعي أن مشغلي أن عودة أنواع مختلفة من أنها تأخذ معنى معا ، ولكن دون وجود مختلف أنواع التعبير لكل انها الهمجية.في هذه الخوارزمية ، غير النقابي مشغلي رفض معاون ليس فقط أنفسهم ولكن مع أي مشغل مع نفس الأسبقية.هذا هو حالة شائعة كما < <= == >= الخ لا تربط مع بعضها البعض في معظم اللغات.
السؤال كيف أنواع مختلفة من المشغلين (يسار ، البادئة الخ) كسر الروابط على الأسبقية واحد هو أن لا تأتي ، لأنه لا يعقل أن تعطي المشغلين من أنواع مختلفة نفس الأسبقية.هذه الخوارزمية لا شيء في تلك الحالات, ولكن أنا حتى لا يكلف نفسه عناء معرفة بالضبط ما لأن مثل هذا النحو هو فكرة سيئة في المقام الأول.
#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)
هنا هو حالة بسيطة متكررة الحل مكتوب بلغة جافا.علما أنها لا تحمل أرقام سلبية ولكن يمكنك أن تفعل إضافة أنه إذا كنت ترغب في:
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;
}
القادم يبس قد تكون مفيدة: yupana - دقة العمليات الحسابية; tinyexpr - العمليات الحسابية + C وظائف الرياضيات + واحد المقدمة من قبل المستخدم ؛ mpc محلل combinators
تفسير
دعونا التقاط تسلسل من الرموز التي تمثل تعبير جبري.أول واحد هو رقم هذا هو أرقام عشرية تتكرر مرة واحدة أو أكثر.فإننا سوف تشير هذه الرموز الإنتاج القاعدة.
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);
}
نحن هنا eval term الأول وإعادته إذا كان هناك أي * حرف بعد ذلك هذا هو اليسار كويس في الإنتاج لدينا القاعدة وإلا تقييم الرموز بعد العودة term.value * product.value هذا هو الحق كويس في الإنتاج لدينا أي حكم term "*" product
