تحليل العمليات الحسابيه للحصول على الناتج

كنت انوي كتابة درس عن الـ Recursive Descent Compiler و الـ Parse Tree و لكن للأسف الوقت لا يسعفني لذا و حيث أني كتبت الكود بالفعل فرأيت أن الأفضل وضعه بدلا من الإنتظار إنتهاء درس قد لا ينتهي.

الكود يتمثل فى الفئه Parser و التى تحتوى على دوال الـ Lexer و الـ Parser، أيضا توجد عدة فئات سيأتي ذكرها بعد قليل تمثل الـ Expression Tree.

الـ Lexer هو من يقوم بقراءة الحروف و الحرف الذى يقرأه يعود بنوعه (مثل قوس أو رقم أو نقطه أو نهاية النص ... إلخ).

الـ Parser هو من يأخذ القيم من الـ Lexer و يقارنها بقواعد معينه (مثل الجمع و الطرح ... إلخ).

الـ Lexer يتعرف على character set تتألف من الحروف التاليه:

+ - * / ( ) . 0 1 2 3 4 5 6 7 8 9 space htab vtab cr ff newline

حيث ان الـ Lexer بسيط قمت بدمج عمله مع الـ parser - و هو بالتأكيد شي ليس جيد.

عناصر الـ Lexer هي:

enum Tokens
{ EOS, Digit, Period, PlusSign, MinusSign, MulSign, DivSign, LP, RP, Unknown };

void advance(bool ignoreWhite = true);
void getNext(bool ignoreWhite = true);
void pushBack(bool ignoreWhite = true);

unsigned getCurIndex() const;
bool toNumber(float& val, unsigned start, unsigned length);

القائمه Token تمثل جميع العناصر التى يتم التعامل معها.

الداله advance: تحرك تقوم بحفظ الحرف التالي - يسمي Lexeme - و الـ Token التى تمثله داخل المتغيرات curLex و curTok، المعامل ignoreWhite يستخدم للحصول على اول token ليست whitespace.

الداله getNext: تستخدم للحصول على الـ lexeme و الـ token التاليه بدون ان يتم تحريك المؤشر الداخلي و يتم حفظ الناتج داخل المتغيرات nextLex و nextTok، المعامل ignoreWhite يستخدم للحصول على اول token ليست whitespace.

الداله advance تستدعي الداله getNext بشكل إفتراضي.

الداله pushBack: تستخدم لإرجاع مؤشر القراءه، إذا كان المعامل ignoreWhite يحتوى على true حينها سيتم الإرجاع حتى يتم رؤية حرف ليس whitespace، إذا كان ignoreWhite بـ false سيتم إرجاع الحرف الحالي فقط.

المتغير index - ليس الكود بالأعلى - يستخدم فى متابعة الموقع الحالي داخل النص.

****************************

قبل سرد عناصر الـ parser سنتكلم عن عناصر الـ Expression Tree:

يقوم الـ parser بإنشاء parse tree تمثل المحتويات النصيه بشكل يسهل التعامل معه فى المراحل التاليه، فى حالتنا هذه المراحل التاليه هي واحده فقط و تستخدم فى الحصول على الناتج منها، توجد لدينا عدة فئات تمثل هذه الـ Tree:

           Expression
              │
    ┌─────────┴─────────┐
    │                   │
 Operand             Operator

الفئه Expression هى Abstract class و تمثل العناصر المشتركه بين كل الفئات التاليه و هي الداله Evaluate التى تستخدم فى الحصول على النتيجة المخزنه بالفئه.

الفئه Operator هى Abstract class و تمثل العمليه الحسابيه نفسها مثل عملية الجمع او عملية الطرح أو أى من العمليات الأخرى، هذه الفئه لا تحتوى على أى عناصر جديده.

الفئه Operand هى Abstract class و تمثل طرف العمليه الحسابيه مثل قيمه رقميه أو ثابت او متغير، حيث ان هذه الفئه تمثل طرف بالعمليه الحسابيه لذا لابد ان تحتوى على قيمه، هذه الفئه تحتوى على مشيد بأخذ قيمه float و يقوم بحفظها داخل متغير _value.

الفئتين Operator و Operand هما هيكل اساسي فى الفئات التاليه، و لنبدأ بالفئه Operand حيث تعتبر الفئه الأب للتاليين:

                     Operand
                        │
      ┌─────────────────┼───────────────────┐
      │                 │                   │
LiteralOperand   ConstantOperand   VariableOperand

الفئه LiteralOperand تمثل قيمة رقميه تم كتابتها داخل التعبير الحسابي، القيمه يتم تخزينها داخل المتغير _value , الداله Evaluate تعيد قيمة _value فقط.

الفئات الباقيه وضعت إسمها هنا فقط لتقريب الصوره لك.

الفئه Operator تمثل الفئه الأب للفئات التاليه:

           Operator
              │
    ┌─────────┴─────────┐
    │                   │
UnaryOperator     BinaryOperator

الفئه UnaryOperator هى Abstract class و تمثل معامل يتم تنفيذه على طرف واحد فقط مثل معامل تغير الإشاره، تحتوى هذه الفئه على مشيد يطلب منك Expression الذى تمثله هذه الفئه، السبب وراء ان المشيد يأخذ Expression و ليس Operand مثلا هو ان المعامل الأحادي قد يعمل على رقم او على عملية حسابيه بأكملها مثلا 5- أو (3*4)- العمليه 3*4 ليست مبنيه على Operand و انما على Operator و حيث ان كلاهما مبني على Expression لذا كان هذا نوع المعامل الذى يتم تمريره للمشيد.

الفئه BinaryOperator هى Abstract class و تمثل معامل يتم تنفيذه على طرفين مثل معامل الجمع، هذه الفئه تحتوى على مشيد يأخذ معاملين كلاهما من نوع Expression و يمثلوا الطرف الأيمن و الطرف الأيسر.

المعامل UnaryOperator يمثل الفئه الأب للفئه UnaryMinus فقط، قد تتسائل عن سبب عدم وجود الفئه UnaryPlus، السبب هو داخل كود الـ Parser اقوم بإجراء Optimization و ذلك للتخلص من الإشاره الموجبه - بإستخدام قاعدة الإشارات، الفئه UnaryMinus لا تحتوى على أى شئ جديد و الداله Evaluate بها تعيد نتيجة الـ Expression الذى تمثله مع عكس إشارته.

الفئه BinaryOperator هى الفئه الأب لكل من الفئات التاليه:

                 BinaryOperator
                       │
                       │
   ┌─────────────┬─────┴──────┬───────────┐
   │             │            │           │
BinaryAdd    BinarySub    BinaryMul    BinaryDiv

الفئات BinaryAdd و BinarySub و BinaryMul و BinaryDiv يمثلوا عملية الجمع و الطرح و الضرب و القسمه على التوالي، أنظر بالكود الخاص بهم لتعرف كيفية عملهم.

الـ parser يقوم على عدة دوال هي:

Expression* getExpression();
Expression* getTerm();
Expression* getFactor();
Expression* getNumber();

الدوال السابقه تقوم كما يظهر بالـ Grammar التالي:

<expression> ::= <term> ( <add-op> <term> )*

<term>       ::= <factor> ( <mul-op> <factor> )*

<factor>     ::= <number> | <unary-op> <factor> | '(' <expression> ')'

<number>     ::= <digits> | <digits> '.' | '.' <digits> | <digits> '.' <digits>

<digits>     ::= <digit> <digit>*

<unary-op>   ::= '-' | '+'

<add-op>     ::= '-' | '+'

<mul-op>     ::= '*' | '/'

<digit>      ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

الفئه Parser تحتوي على الداله parse و التى تطلب منك null-terminated string و التى تحتوى على الـ expression الذى تود الحصول على قيمته، بعد الإستدعاء تعود الداله بـ true إذا تمت عملية الـ parse بنجاح - و هذا يعنى إنشاء الـ parse tree بنجاح - أو false لحدوث خطأ.

عند حدوث خطأ داخل الـ parser يتم كتابة رسائل الخطأ مباشرة داخل standard error و ذلك بإستخدام cerr.

إذا تمت عملية الـ parse بنجاح يمكنك إستدعاء الداله getResult للحصول على قيمة التعبير الحسابي.

الكود يحتوي على test unit ممثله بالداله main فقط قم بتنفيذ الكود و اتبع ما سيقوله لك.

exp_parser.rar

كتمرين لك:

1 - (سهل) حاول التعديل على كود الفئه Parser و ذلك لتدعم المعامل ** و الذى يمثل power operator

2 - (متوسط) حاول التعديل على كود الفئه Parser و ذلك لتدعم المعامل ! و الذى يمثل factorial operator - لاحظ ان معامل الـ factorial هو right associative و هذا يعنى ان الكتابه التاليه خاطئه 2! و الصحيح هو !2

3 - (صعب) حاول تضمين المعاملات المنطقيه == و =! و > و < و => و =< و المعامل :? و الكلمات المحجوزه true و false.

و الله ولي التوفيق