كيف يمكنني بناء مولد طاولة الحقيقة؟

Question

أنا أتطلع إلى كتابة مولد طاولة الحقيقة كمشروع شخصي.

هناك العديد من تلك على شبكة الإنترنت هنا و هنا.

(Example screenshot of an existing Truth Table Generator)

لديك على الأسئلة التالية:

• كيف يجب أن أذهب حول تحليل التعبيرات مثل: ((p => q) و (q => r)) => (p => r)
• هل يجب علي استخدام مولد محلل محلل مثل Antlr أو YACC، أو استخدم تعبيرات منتظمة مستقيمة؟
• بمجرد تحليل التعبير، كيف يجب أن أذهب في توليد طاولة الحقيقة؟ يجب تقسيم كل قسم من التعبير إلى أصغر مكوناته وإعادة البناء من الجانب الأيسر من الجدول إلى اليمين. كيف يمكنني تقييم شيء من هذا القبيل؟

هل يمكن لأي شخص أن يقدم لي نصائح بشأن تحليل هذه التعبيرات التعسفية وتقييم التعبير المحلي في النهاية؟

Answer 1

هذا يبدو وكأنه مشروع شخصي رائع. سوف تتعلم الكثير حول كيفية عمل الأجزاء الأساسية من برنامج التحويل البرمجي. أود أن تخطي محاولة استخدام مولد المحللين؛ إذا كان هذا هو لتصوير الخاص بك، فسوف تتعلم المزيد عن طريق القيام بذلك من الصفر.

الطريقة التي تعمل بها مثل هذه الأنظمة هي إضفاء الطابع الرسمي على كيف نفهم اللغات الطبيعية. إذا أعطيك جملة: "الكلب، روفر، أكل طعامه."، أول شيء تفعله هو كسره في الكلمات والعلامات الترقيم. "الفضاء"، "الفضاء"، "الكلاب"، "فاصلة"، "الفضاء"، "روفر"، ... هذا "يلغي" أو "Lexing".

الشيء التالي الذي تقوم به هو تحليل مجرى الرمز المميز لمعرفة ما إذا كانت الجملة النحوية. قواعد اللغة الإنجليزية معقدة للغاية، لكن هذه الجملة واضحة جدا. موضوعية - الفعل - كائن. هذا هو "تحليل".

بمجرد أن تعرف أن الجملة هي نحوية، يمكنك بعد ذلك تحليل الجملة للحصول على معنى في الواقع. على سبيل المثال، يمكنك أن ترى أن هناك ثلاثة أجزاء من هذه الجملة - الموضوع، المآدي، "له" في الكائن - يشير جميعها إلى نفس الكيان، أي الكلب. يمكنك معرفة أن الكلب هو الشيء الذي يقوم بالأكل، والطعام هو الشيء الذي يتم تناوله. هذه هي مرحلة التحليل الدلالي.

يتم الحصول على المجمعين ثم مرحلة رابعة أن البشر لا يفعلون ذلك، وهو ما يقومون بإنشاء التعليمات البرمجية التي تمثل الإجراءات الموضحة باللغة.

لذلك، افعل كل ذلك. ابدأ بتحديد ما هي رموز اللغة الخاصة بك، حدد رمزا فئة أساسية ومجموعة من الفئات المشتقة لكل منها. (محددة، ortoken، andtoken، articleiToken، referparentoken ...). ثم اكتب طريقة تأخذ سلسلة وإرجاع IEnumerable ". هذا Lexer الخاص بك.

ثانيا، معرفة ما هو قواعد اللغة لغتك هو، واكتب محلل نزولا متكررا ينفصل عن ienumerable في شجرة بناء الجملة مجردة يمثل الكيانات النحوية بلغتك.

ثم اكتب محلل ينظر إلى تلك الشجرة والأرقام الأشياء، مثل "كم عدد المتغيرات المجانية المميزة لدي؟"

ثم اكتب مولد رمز يبصق الكود الضروري لتقييم جداول الحقيقة. البصق il يبدو وكأنه مبالغة، ولكن إذا كنت تريد أن تكون حقا برتقالي، فيمكنك ذلك. قد يكون من الأسهل ترك مكتبة شجرة التعبير تفعل ذلك من أجلك؛ يمكنك تحويل شجرة تحليلك إلى شجرة تعبير، ثم تحويل شجرة التعبير إلى مندوب، وتقييم المندوب.

حظ سعيد!

Answer 2

أعتقد أن مولد المحلل المحلل هو مبالغة. يمكنك استخدام فكرة تحويل تعبير إلى Postfix و تقييم تعبيرات postfix. (أو بناء شجرة تعبير مباشرة من تعبير Infix واستخدام ذلك لتوليد جدول الحقيقة) لحل هذه المشكلة.

Answer 3

كما يذكر Mehrdad، يجب أن تكون قادرا على تدميم تحليل التحليل في نفس الوقت حيث سيتطلب الأمر لتعلم بناء جملة Lexer / Garser. النتيجة النهائية التي تريدها هي بعض شجرة بناء الجملة مجردة (AST) للتعبير الذي قدمته.

تحتاج بعد ذلك إلى إنشاء بعض مولدات الإدخال التي تنشئ مجموعات الإدخال للرموز المعرفة في التعبير.

ثم تكرر عبر مجموعة الإدخال، مما يولد النتائج لكل كومبو إدخال إدخال، بالنظر إلى القواعد (AST) التي تحللها في الخطوة الأولى.

كيف سأفعل ذلك:

يمكن أن أتخيل استخدام وظائف Lambda للتعبير عن AST / LUBS أثناء تحليل الشجرة، وبناء جدول رمز أثناء تحليله، يمكنك بعد ذلك إنشاء مجموعة الإدخال، وتحليل جدول الرموز إلى شجرة التعبير Lambda، لحساب النتائج.

Answer 4

إذا كان هدفك هو معالجة التعبيرات المنطقية، ومولد محلل ومحلل وجميع الآلات التي تذهب مضيعة للوقت، إلا إذا كنت ترغب في تعلم كيفية عملها (ثم سيكون أي منهم على ما يرام).

ولكن من السهل إنشاء محلل نزود من النزول باليد تعبيرات منطقية، والتي تحسب وترجع نتائج "تقييم" التعبير. يمكن استخدام مثل هذا المحلل في تمريرة الأولى لتحديد عدد المتغيرات الفريدة، حيث يعني "التقييم" "Couunt 1 لكل اسم متغير جديد". كتابة مولد لإنتاج جميع قيم الحقيقة الممكنة لمتغيرات N تافهة؛ لكل مجموعة من القيم، ما عليك سوى الاتصال بالمحافظة مرة أخرى واستخدامها لتقييم التعبير، حيث تقيم الوسائل "الجمع بين قيم التعقب الفرعي وفقا للمشغل".

تحتاج إلى قواعد اللغة:

formula = disjunction ;
disjunction = conjunction 
              | disjunction "or" conjunction ;
conjunction = term 
              | conjunction "and" term ;
term = variable 
       | "not" term 
       |  "(" formula ")" ;

يمكن أن تكون لك أكثر تعقيدا، ولكن بالنسبة للتعبيرات المنطقية، لا يمكن أن يكون الأمر أكثر تعقيدا.

لكل قاعدة قواعد اللغة، اكتب روتين فرعي يستخدم فهرس عالمي "مسح" في السلسلة التي يتم تحليلها:

  int disjunction()
 // returns "-1"==> "not a disjunction"
 // in mode 1:
 // returns "0" if disjunction is false
 // return  "1" if disjunction is true
 { skipblanks(); // advance scan past blanks (duh)
   temp1=conjunction();
   if (temp1==-1) return -1; // syntax error
   while (true)
     { skipblanks();
       if (matchinput("or")==false) return temp1;
       temp2= conjunction();
       if (temp2==-1) return temp1;
       temp1=temp1 or temp2;
     }
  end

  int term()
  { skipblanks();
    if (inputmatchesvariablename())
       { variablename = getvariablenamefrominput();
         if unique(variablename) then += numberofvariables;
         return lookupvariablename(variablename); // get truthtable value for name
       }
     ...
  }

كل من روتات تحليلك سيكون حول هذا المعقد. عنجد.

Answer 5

يمكنك الحصول على شفرة المصدر برنامج Pyttgen في http://code.google.com/p/pyttgen/source/browse/#hg/src. يولد جداول الحقيقة للتعبيرات المنطقية. رمز بناء على مكتبة رقائق، لذلك بسيط جدا :)