محلل أسبقية العمليات

الشفرة الزائفة للخوارزمية هي كما يلي. يبدأ المحلل اللغوي من الدالة parse_expression . مستويات الأسبقية أكبر من أو تساوي صفرًا.

parse_expression() return parse_expression_1(parse_primary(), 0)

parse_expression_1(lhs, min_precedence) lookahead := peek next token while lookahead is binary operator who their precedence >= min_precedence op := lookahead انتقل إلى الرمز التالي rhs := parse_primary () lookahead := peek next token while lookahead هو عامل ثنائي تكون أسبقيته أكبر من عامل التشغيل ، أو عامل التجميع الأيمن الذي تكون أسبقيته مساوية لأسبقية العملية `op`، ` rhs := parse_expression_1 ( rhs , precedence of op + (1 if lookahead precedence is greater, else 0)) lookahead := peek next token lhs := the result of applied op with operators lhs and rhs return lhs `

لاحظ أنه في حالة قاعدة إنتاج كهذه (حيث لا يمكن أن يظهر العامل إلا مرة واحدة):

تعبير المساواة :: = تعبير الجمع ( ' == ' | '! = ' ) تعبير الجمع

يجب تعديل الخوارزمية لقبول عوامل التشغيل الثنائية فقط التي تكون أسبقيتها أكبر من min_precedence .

فيما يلي مثال على تنفيذ التعبير 2 + 3 * 4 + 5 == 19. نُعطي الأولوية 0 للتعبيرات المساواتية، و1 للتعبيرات الجمعية، و2 للتعبيرات الضربية.

parse_expression_1 ( lhs = 2, min_precedence = 0)

• رمز التطلع هو +، وله أسبقية 1. يتم الدخول إلى حلقة while الخارجية.
• العملية هي + (الأولوية 1) والمدخل متقدم
• اليمين هو 3
• رمز التوقع هو *، وله أولوية 2. يتم الدخول إلى حلقة while الداخلية. parse_expression_1 ( lhs = 3, min_precedence = 2)

• رمز التطلع هو *، وله الأسبقية 2. يتم الدخول إلى حلقة while الخارجية.

• العملية هي * (الأولوية 2) والمدخل متقدم
• اليمين هو 4
• الرمز التالي هو +، وله أولوية 1. لم يتم الدخول إلى حلقة while الداخلية.
• تم تخصيص 3 × 4 = 12 للطرف الأيسر
• الرمز التالي هو +، وله أولوية 1. يتم ترك حلقة while الخارجية.

• تم إرجاع الرقم 12.

• رمز التطلع هو +، وله أسبقية 1. لم يتم الدخول إلى حلقة while الداخلية.
• تم تعيين الطرف الأيسر 2+12 = 14
• رمز التطلع هو +، وله أسبقية 1. حلقة while الخارجية غير موجودة.
• العملية هي + (الأولوية 1) والمدخل متقدم
• الجانب الأيمن هو 5
• الرمز التالي هو ==، وله أسبقية 0. لم يتم الدخول إلى حلقة while الداخلية.
• تم تعيين الطرف الأيسر 14 + 5 = 19
• الرمز التالي هو ==، وله أسبقية 0. لم يتم ترك حلقة while الخارجية.
• العملية تساوي (الأسبقية 0) والمدخل متقدم
• اليمين هو 19
• الرمز المميز التالي هو نهاية السطر ، وهو ليس عاملاً. لم يتم الدخول إلى حلقة while الداخلية.
• يتم تعيين نتيجة تقييم 19 == 19 للطرف الأيسر ، على سبيل المثال 1 (كما هو الحال في معيار C).
• الرمز التالي هو نهاية السطر ، وهو ليس عاملًا. تم ترك حلقة while الخارجية.

يتم إرجاع الرقم 1.

ثمة طريقة أخرى تتمثل في وضع التعبير بين قوسين كاملين أولاً، وذلك بإضافة عدد من الأقواس حول كل عامل، بحيث تؤدي إلى الترتيب الصحيح حتى عند تحليلها باستخدام محلل خطي من اليسار إلى اليمين. وقد استُخدمت هذه الخوارزمية في مُصرّف FORTRAN I المبكر : ^{[ 7 ]}

كان مُترجم لغة فورتران 1 يُوسّع كل مُعامل بسلسلة من الأقواس. في شكل مُبسّط للخوارزمية، كان سيفعل

• استبدل +و –بـ ))+((و ))-((، على التوالي؛
• استبدل *و /بـ )*(و )/(، على التوالي؛
• أضف ((في بداية كل تعبير وبعد كل قوس مفتوح في التعبير الأصلي؛ و
• أضف ))في نهاية التعبير وقبل كل قوس أيمن في التعبير الأصلي.

على الرغم من أن الأمر لم يكن واضحًا، إلا أن الخوارزمية كانت صحيحة، وعلى حد تعبير كنوت ، "الصيغة الناتجة موضوعة بين قوسين بشكل صحيح، صدق أو لا تصدق." ^{[ 8 ]}

مثال على كود لتطبيق C بسيط يتعامل مع وضع الأقواس في عوامل الرياضيات الأساسية ( +،،،،، و -) :*/^()

#include <stdio.h> #include <string.h>// حدود وسيط سطر الأوامر هي محللنا المعجمي. int main ( int argc , char * argv []) { int i ; printf ( "((((" ); for ( i = 1 ; i != argc ; i ++ ) { // strlen(argv[i]) == 2 if ( argv [ i ] && ! argv [ i ][ 1 ]) { switch ( * argv [ i ]) { case '(' : printf ( "((((" ); continue ; case ')' : printf ( "))))" ); continue ; case '^' : printf ( ")^(" ); continue ; case '*' : printf ( "))*((") ; continue ; case '/' : printf ( "))/((" ); continue ; case '+' : // فحص أحادي: إما الأول أو كان لديه عامل يتوقع وسيطًا ثانويًا if ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "+" ); else printf ( ")))+(((" ); continue ; case '-' : if ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "-" ); else printf ( ")))-(((" ); continue ; } } printf ( "%s" ,argv [ i ]); } printf ( ")))) \n " ); return0 ; }

أولاً، عليك تجميع برنامجك. بافتراض أن برنامجك مكتوب بلغة C وأن شفرة المصدر موجودة في ملف باسم program.c، ستستخدم الأمر التالي:

gcc program.c -o program

يُخبر الأمر أعلاه gcc بتجميع program.c وإنشاء ملف تنفيذي باسم program.

أمر لتشغيل البرنامج مع المعاملات، على سبيل المثال: a * b + c ^ d / e

./program a '*' b + c '^' d / e

ينتج

((((أ))*((ب)))+(((ج)^(د))/((ه))))

كما يظهر في مخرجات وحدة التحكم.

من عيوب هذه الاستراتيجية أن المعاملات الأحادية يجب أن تكون لها أسبقية أعلى من المعاملات الوسطية. فالمعامل "السالب" في الكود أعلاه له أسبقية أعلى من الأس. تشغيل البرنامج بهذه المدخلات

- أ ^ 2

ينتج هذا المخرج

((((-a)^(2))))

وهو ما قد لا يكون المقصود.