كيفية تحويل مجرى رمزي إلى شجرة تحليل [مغلقة]

Question

ولدي lexer بنيت أن تيارات من الرموز من في المدخلات ولكن لست متأكدا من كيفية بناء الخطوة التالية في العملية - شجرة تحليل. هل لدى أي شخص أي موارد جيدة أو أمثلة على كيفية تحقيق ذلك؟

Answer 1

وأوصي حقا http://www.antlr.org/ و بالطبع التنين الكلاسيكية المجمعين الكتاب.

للغة سهلة مثل جافا سكريبت انها ليست من الصعب اليد لفة محلل النسب العودية، لكنه دائما أسهل للاستخدام أداة مثل ياك أو ANTLR.

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

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

Answer 2

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

%left PLUS, MINUS           # low precedence, evaluated left-to-right
%left TIMES, DIV            # high precedence, left-to-right

expr ::= INT
| expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIV expr
| LEFT_PAREN expr RIGHT_PAREN

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

ومعظم مولدات محلل هي بلغة معينة. ANTLR غير معروفة وتدعم C، C ++، C الهدف، جافا، وبيثون. لقد سمعت أنه من الصعب استخدام بالرغم من ذلك. لقد استعملت البيسون لC / C ++، CUP للجافا، وocamlyacc للغة كامل الموضوعية، وانهم جميعا جيدة. إذا كنت تستخدم بالفعل مولد lexer، يجب أن ننظر لمولد محلل متوافق تحديدا معها.

Answer 3

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

Answer 4

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

ANTLR سيكون اقتراحي إذا كنت ترغب في استخدام أداة (waaay أسرع وأقل اتساعا). حظا سعيدا!