الحفاظ على الدولة في عالم عديمي الجنسية

Question

أقوم بتحويل قواعد نحوية خالية من السياق إلى شكل طبيعي Greibach (GNF). التحول الرئيسي (من Hopcroft & Ullman) هو سلسلة من التكرارات على المتغيرات المفهرسة للقواعد. إنه أساسا "عديمي الجنسية". لقد قمت بتنفيذها كتسلسل من الطيات على المؤشرات المناسبة (التنفيذ واضح إلى حد ما):

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = foldl step1 rl [1..maxIndex rl]
 where step1 rl' k = foldl step2 rl' [1..k - 1]
        where step2 rl'' j = noLR k (subst rl'' k j)

MaxIndex RL إرجاع أقصى فهرس متغير في مجموعة من القواعد ؛ استبدال RL KJ يؤدي الاستبدال على ك-قواعد مثبتة من خلال القواعد التي يبدأ الجانب الأيمن بـ يمتغير فهرس. بعد الأداء GNF, ، أحتاج إلى إجراء تمريرة نهائية على القواعد النحوية بترتيب عكسي.

المشكلة هي نولر, الذي يحول قواعد اللغة مع اليسار كالقواعد الفهرسة. هذه وظيفة "دولة" ، حيث يجب إنشاء متغير فريد لكل قاعدة (أو ك-القاعدة الفهرسة) لها نولر يتم تطبيقه. لذلك كتبت وظيفة دولة

noLR :: Ord a => Int -> Set (Rule a) -> State [Sym a] (Set (Rule a))
noLR rl = do (n:ns) <- get; put ns;
             let rl' = ... remove left recursion rl n ...
              in return rl'

يمكنني تسلسل معا نولر من أجل تحديث ن أيّ نولر يأخذ كمعلمة. انا ليس تأكد من أداء الأداء نولر داخل الخطوة 2 في الوظيفة أعلاه ، على الرغم من. لا يبدو أنني قادر على استخدام اتركه المخطط ، لأن الحساب الهادئ مضمن داخل عدة وظائف متكررة.

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

Answer 1

من أجل استخدام NOLR مع النوع الذي قدمته ، سيتعين عليك إعادة كتابة وظيفة GNF الخاصة بك على الأسطر التالية:

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = evalState (foldM step1 rl [1..maxIndex rl]) ( ... generate the initial state [Sym a] here ...)
 where step1 rl' k = foldM step2 rl' [1..k - 1]
        where step2 rl'' j = noLR k (subst rl'' k j)

يوجد متغير حالتك أثناء الحساب بأكمله ، ويجب أن تكون هذه الحقيقة صريحة في الكود.

إذا كان كل ما تحتاجه هو أن الأسماء المتغيرة التي تم إنشاؤها حديثًا لا تصطدم ببعضها البعض ، فيمكنك جعل Nolr نقيًا من خلال إنشاء اسم رمز جديد من المؤشرات K و J - شيء مثل "Foo_42_16" لـ K == 42 و J == 16. إذا كانت قواعد الإدخال تحتوي بالفعل على أسماء رمز من هذا النوع ، فقد تكون في ورطة.

إذا كنت بحاجة إلى أن تكون رموزك فريدة من نوعها داخل القواعد ، فلماذا لا تقول ذلك فقط؟

newSymbol :: Set (Rule a) -> Sym a
newSymbol rl = ... find a symbol name not used in rl ...

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

Answer 2

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

noLR k j = noLR' k j $ newSymbol k j
    where newSymbol k j = ... -- some concatenation of k and j
          noLR' k j sym = ... -- your now pure function