القواعد الخالية من السياق وصف التعبيرات العادية؟

Question

أحاول كتابة محرك تعبير منتظم. أود أن أكتب محلل نزولا متكررا باليد. ما الذي سيعقد قواعد قواعد خالية من السياق دون العودية لغرض التعبيرات العادية (وليس اللغات التي يمكن وصفها بالتعبيرات العادية) تبدو وكأنها؟ هل سيكون الأمر أسهل في إعادة عامل السكر النحوي، أي التغيير a+ ل aa* ب شكرا لك مقدما!

Answer 1

recursion اليسار:

Expression = Expression '|' Sequence
           | Sequence
           ;

Sequence = Sequence Repetition
         | <empty>
         ;

العودية الصحيحة:

Expression = Sequence '|' Expression
           | Sequence
           ;

Sequence = Repetition Sequence
         | <empty>
         ;

شكل غامض:

Expression = Expression '|' Expression
           | Sequence
           ;

Sequence = Sequence Sequence
         | Repetition
         | <empty>
         ;

Answer 2

يمكنك أن تنظر إلى شفرة المصدر للتخطيط 9 Grep. وبعد الملف Grep.y لديه YACC (Lalr (1) إذا كنت أتذكر بشكل صحيح) Grammar للتعبيرات العادية. قد تتمكن من البدء من YACC Grammar، وإعادة كتابةها لتحليل النسب المتكرر.

Answer 3

مقالة ويكيبيديا recursion اليسار يعطي معلومات جيدة جدا حول كيفية سحب هذا قبالة.