นิพจน์ทั่วไป (RE) เป็นรูปแบบการเขียนที่สะดวกมากที่เรียกว่าภาษาปกติหรือภาษาอัตโนมัติ ดังนั้น RV จึงถูกใช้เป็นภาษาอินพุตในระบบประมวลผลลูกโซ่หลายระบบ ลองพิจารณาตัวอย่างของระบบดังกล่าว:
- คำสั่ง Grep ระบบปฏิบัติการ Unix หรือคำสั่งค้นหาสตริงที่คล้ายกัน ซึ่งพบได้ในเว็บเบราว์เซอร์หรือระบบการจัดรูปแบบข้อความ ในระบบดังกล่าว RT ใช้เพื่ออธิบายรูปแบบที่ผู้ใช้ค้นหาในไฟล์ เสิร์ชเอ็นจิ้นต่างๆ แปลง RT เป็นออโตเมติกไฟไนต์ดีเทอร์มินิสติก (DFA) หรือออโตมาตันไฟไนต์แบบกำหนดไม่ได้ (NFA) และใช้ออโตเมตันนี้กับไฟล์ที่กำลังค้นหา
- เครื่องกำเนิดไฟฟ้าของเครื่องวิเคราะห์คำศัพท์ Lexical analyzer เป็นส่วนประกอบคอมไพเลอร์ โดยจะแยกโปรแกรมต้นทางออกเป็นหน่วยตรรกะ (โทเค็น) ซึ่งสามารถประกอบด้วยอักขระได้ตั้งแต่หนึ่งตัวขึ้นไปและมีความหมายบางอย่าง ตัวสร้างคำวิเคราะห์ได้รับคำอธิบายอย่างเป็นทางการของโทเค็น ซึ่งโดยพื้นฐานแล้วคือ RV และสร้าง DFA ที่รับรู้ว่าโทเค็นใดปรากฏขึ้นที่อินพุต
- РВ ในภาษาโปรแกรม
ในบทความนี้ อันดับแรก เราจะทำความคุ้นเคยกับเครื่องสถานะจำกัดและประเภท (DFA และ NFA) จากนั้นพิจารณาตัวอย่างการสร้าง DFA ขั้นต่ำโดยใช้นิพจน์ทั่วไป
เครื่องไฟไนต์สเตท
ไฟไนต์ออโตมาตัน (KA) เป็นคอนเวอร์เตอร์ที่ให้คุณเชื่อมโยงอินพุทเข้ากับเอาท์พุตที่สอดคล้องกัน และเอาท์พุตนี้อาจขึ้นอยู่กับอินพุตปัจจุบันไม่เพียงเท่านั้น แต่ยังขึ้นกับสิ่งที่เกิดขึ้นก่อนหน้านี้ในประวัติของเครื่องสถานะด้วย แม้แต่พฤติกรรมของมนุษย์ ไม่ใช่แค่ระบบประดิษฐ์ ก็สามารถอธิบายได้โดยใช้ CA ตัวอย่างเช่น ปฏิกิริยาของคุณต่อเพื่อนบ้านที่ฟังเพลงเสียงดังในเวลากลางคืนจะเหมือนเดิมหลังจากเหตุการณ์ครั้งแรกและจะแตกต่างไปจากเดิมอย่างสิ้นเชิงหลังจากหลายครั้ง ยุคก่อนประวัติศาสตร์อาจมีจำนวนไม่ จำกัด คำถามเกิดขึ้น: CA ควรมีหน่วยความจำอะไรเพื่อที่จะประพฤติแตกต่างกันในแต่ละยุคก่อนประวัติศาสตร์? เป็นที่ชัดเจนว่าเป็นไปไม่ได้ที่จะเก็บเรื่องราวเบื้องหลังจำนวนนับไม่ถ้วน ดังนั้น ออโตเมตันจึงแบ่งยุคก่อนประวัติศาสตร์ที่เป็นไปได้ทั้งหมดออกเป็นคลาสที่เท่าเทียมกัน เรื่องราวสองเรื่องจะเทียบเท่ากันหากพวกเขามีผลเช่นเดียวกันกับพฤติกรรมของเครื่องในอนาคต คลาสสมมูลที่หุ่นยนต์กำหนดประวัติปัจจุบันเรียกอีกอย่างว่า สภาพภายในเครื่องจักร.ลองพิจารณาตัวอย่างการทำงานของ CA ดั้งเดิม:
ยานอวกาศลำนี้ประกอบด้วย:
- เทปที่แสดงโดยห่วงโซ่อินพุต
- ผู้อ่าน
- บล็อกควบคุมที่มีรายการกฎการเปลี่ยน
เครื่องอ่านสามารถเคลื่อนที่ไปในทิศทางเดียว โดยปกติจากซ้ายไปขวา ดังนั้นการอ่านอักขระของสตริงอินพุต สำหรับการเคลื่อนไหวแต่ละครั้ง สามารถนับหนึ่งสัญลักษณ์ นอกจากนี้ อักขระที่อ่านได้จะถูกโอนไปยังชุดควบคุม หน่วยควบคุมจะเปลี่ยนสถานะของเครื่องตามกฎการเปลี่ยน หากรายการกฎการเปลี่ยนภาพไม่มีกฎสำหรับอักขระที่อ่าน หุ่นยนต์จะ "ตาย"
ตอนนี้ให้เราพิจารณาว่าสามารถระบุ CA ได้อย่างไร สามารถระบุได้ในรูปแบบของกราฟหรือในรูปแบบของตารางควบคุม ในรูปแบบของกราฟ ยานอวกาศมีการระบุในลักษณะดังต่อไปนี้:
- จุดยอดของกราฟสอดคล้องกับสถานะของยานอวกาศ
- ขอบตรงสอดคล้องกับฟังก์ชันการเปลี่ยนภาพ (ถัดจากขอบแต่ละด้าน จะมีสัญลักษณ์ระบุตามการเปลี่ยนภาพ)
- จุดยอดที่มีขอบเข้ามา ซึ่งไม่เหลือมากกว่าหนึ่งสถานะ สอดคล้องกับสถานะเริ่มต้น
- สถานะสุดท้ายของยานอวกาศถูกทำเครื่องหมายด้วยโครงร่างหนา
ในรูปแบบของตารางควบคุมดังนี้:
- สถานะ CA จะอยู่ในแถวของตาราง
- อักขระของภาษาที่รู้จัก - ในคอลัมน์
- ที่สี่แยกจะมีการระบุสถานะว่าจะได้รับจากสถานะนี้ด้วยสัญลักษณ์นี้
ตัวอย่างของ CA ในรูปแบบของกราฟและในรูปแบบของตารางควบคุมจะถูกนำเสนอด้านล่าง
DKA และ NKA
ความแตกต่างหลักระหว่าง DFA และ NFA คือ DFA ระหว่างการดำเนินการสามารถอยู่ในสถานะเดียวเท่านั้น และ NFA ในหลายสถานะพร้อมกัน ตัวอย่างผลงานของ NCA เราสามารถอ้างถึงแนวคิดของฮิวจ์ เอเวอเร็ตต์ นักฟิสิกส์ชาวอเมริกันที่ว่าเหตุการณ์ใดก็ตามที่แบ่งโลกออกเป็นหลายโลก ซึ่งแต่ละเหตุการณ์จบลงด้วยวิถีของตนเอง ตัวอย่างเช่น ในโลกหนึ่ง ฮิตเลอร์ชนะโลกที่สอง สงครามโลกในอีกทางหนึ่ง - นิวตันแทนที่จะเป็นฟิสิกส์เข้าสู่ธุรกิจและการค้นพบกฎของกลศาสตร์คลาสสิกต้องถูกเลื่อนออกไปเป็นเวลา 50 ปี ในการสรุปข้อสรุปจากการทำงานของหุ่นยนต์เราควรศึกษา "โลก" ทั้งหมด หลังจากที่อ่านห่วงโซ่การป้อนข้อมูลทั้งหมดแล้ว เราคิดว่า NFA ยอมรับห่วงโซ่ที่กำหนด หากทำงานเสร็จสิ้นในสถานะยอมรับในชุดของ "โลก" อย่างน้อยหนึ่งชุด ดังนั้น หุ่นยนต์จะปฏิเสธรุ่งหากสิ้นสุดในสถานะที่ยอมรับไม่ได้ในแต่ละ "โลก" DFA ยอมรับสตริง ซึ่งจะเห็นได้ชัดว่าหลังจากอ่านสตริงอินพุตทั้งหมดแล้ว ปรากฏว่าอยู่ในสถานะยอมรับ
ในกรณีส่วนใหญ่ การสร้าง NCA ทำได้ง่ายกว่า DCA มาก แต่ถึงอย่างนั้น การใช้ NCA ในการสร้างแบบจำลองก็ไม่ใช่สิ่งที่ดีที่สุด ความคิดที่ดี... โชคดีสำหรับ NFA แต่ละรายการ สามารถสร้าง DFA ที่ยอมรับภาษาอินพุตเดียวกันได้ ในบทความนี้ เราจะไม่นำเสนออัลกอริทึมสำหรับการสร้าง DFA โดยใช้ NFA แต่ให้พิจารณาอัลกอริทึมนี้ตาม ตัวอย่างภาพประกอบด้านล่าง.
การสร้าง DFA ขั้นต่ำโดยใช้นิพจน์ทั่วไป
ในการเริ่มต้น เราแสดงรายการการดำเนินการ RT ที่ใช้ในบทความนี้ตามลำดับความสำคัญ:
- วนซ้ำ (ปิดคลีน) โดยใช้ "*"
- การต่อข้อมูลถูกระบุโดยใช้ช่องว่างหรือสตริงว่าง (เช่น: ab)
- การต่อกันโดยใช้ "|"
ลองพิจารณาตัวอย่างด้วยนิพจน์ทั่วไป:
Xy * (x | y *) | ab (x | y *) | (x | a *) (x | y *)
จำเป็นต้องสร้าง DFA ขั้นต่ำโดยใช้นิพจน์ทั่วไปและแสดงให้เห็นถึงการรับรู้สายโซ่ที่ถูกต้องและไม่ถูกต้อง
ในการเริ่มต้น เราลดความซับซ้อนของ RV ที่กำหนด โดยใช้กฎการกระจายทางขวาของการต่อสายสัมพันธ์กับสหภาพ เราได้รับ RV ต่อไปนี้:
(xy * | ab | (x | a *)) (x | y *)
ตอนนี้เรากำลังสร้างหุ่นยนต์สำหรับ PB นี้:
ตามกฎสำหรับการแปลงการเชื่อมต่อ (เราจะไม่ให้กฎสำหรับการแปลง PB เป็น CA เนื่องจากมีความชัดเจนมาก) เราได้รับหุ่นยนต์ดังต่อไปนี้:
ตามกฎการแปลงสหภาพ:
ตามกฎการแปลงการเรียงต่อกัน:
และในตอนท้าย เราใช้กฎการแปลงการปิดและได้ εНКА ควรสังเกตว่า εNKA เป็น NFA ที่มี ε-transitions ในทางกลับกัน ε-transition คือการเปลี่ยนแปลงที่หุ่นยนต์ไม่คำนึงถึงสตริงอินพุตหรือกล่าวอีกนัยหนึ่งคือการเปลี่ยนแปลงด้วยสัญลักษณ์ว่าง
เรากำจัด ε-transitions (สถานะสุดท้ายแสดงด้วยเครื่องหมายดอกจัน):
ใน NSA นี้ สถานะ s3 และ s5 เท่ากัน เนื่องจาก δ (s3, x) = δ (s5, x) = s1 และ δ (s3, y) = δ (s5, y) = s5, s7 เปลี่ยนชื่อสถานะ s6 -> s5 และ s7 -> s6:
เรากำลังสร้าง DCA สำหรับ NCA:
ใน DFA นี้ สถานะ p1 และ p5 มีค่าเท่ากัน เนื่องจาก
δ (p1, x) = δ (p5, x) = p4 และ δ (p1, y) = δ (p5, y) = p5 เปลี่ยนชื่อสถานะ p6 -> p5 และ p7 -> p6:
หุ่นยนต์นี้เป็น DFA ที่น้อยที่สุด
ให้ δ เป็นฟังก์ชันการเปลี่ยน จากนั้นฟังก์ชันการเปลี่ยนแบบขยายที่สร้างบน δ จะแสดงด้วย δ ’ และ ω คือห่วงโซ่อินพุต
สมมติว่าโซ่ ω = aaax ถูกป้อนเข้า เราคาดว่าหุ่นยนต์จะอยู่ในสถานะที่ยอมรับได้
δ ’(p0, ε) = p0
δ ’(p0, a) = δ (δ’ (p0, ε), a) = δ (p0, a) = p3
δ ’(p0, aa) = δ (δ’ (p0, a), a) = δ (p3, a) = p5
δ ’(p0, aaa) = δ (δ’ (p0, aa), a) = δ (p5, a) = p5
δ ’(p0, aaax) = δ (δ’ (p0, aaa), x) = δ (p5, x) = p4
P4 เป็นสถานะสุดท้ายที่ถูกต้อง ดังนั้น aaax chain จึงถูกต้องสำหรับหุ่นยนต์นี้
ทีนี้ลองสมมติว่า ω = xyyb:
δ ’(p0, ε) = p0
δ ’(p0, x) = δ (δ’ (p0, ε), x) = δ (p0, x) = p1
δ ’(p0, xy) = δ (δ’ (p0, x), y) = δ (p1, y) = p1
δ ’(p0, xyy) = δ (δ’ (p0, xy), y) = δ (p1, y) = p1
δ ’(p0, xyyb) = δ (δ’ (p0, xyy), b) = δ (p1, b) = ∅
ที่นี่เราจะเห็นว่าหากสัญลักษณ์ b ถูกป้อนเข้าสู่หุ่นยนต์เมื่ออยู่ในสถานะ p1 หุ่นยนต์นี้ก็จะตาย ดังนั้น xyyb ของลูกโซ่จึงไม่ถูกต้อง
ป.ล. ในบทความนี้มีการพิจารณาอัลกอริทึมสำหรับการสร้าง DFA จาก PB แต่มีอัลกอริทึมที่สะดวกกว่าโดยเฉพาะอย่างยิ่งสำหรับการเขียนโปรแกรม แต่นี่เป็นหัวข้อสำหรับบทความอื่นแล้ว ...
DKA เป็นกรณีพิเศษของ NKA ในตัวเขา:
ไม่มีสถานะที่มี ε-transitions;
สำหรับแต่ละสถานะ S และสัญลักษณ์อินพุต a จะมีส่วนโค้งที่ออกจาก S อย่างน้อยหนึ่งส่วนและติดป้ายกำกับด้วย a
DFA มีการเปลี่ยนแปลงได้ไม่เกินหนึ่งครั้งสำหรับสัญลักษณ์อินพุตใดๆ จากแต่ละสถานะ หากตารางถูกใช้เพื่อแสดงฟังก์ชันของการเปลี่ยน DFA แต่ละระเบียนจะมีเพียงสถานะเดียว ดังนั้นจึงง่ายที่จะตรวจสอบว่า DFA ที่กำหนดยอมรับบรรทัดใดบรรทัดหนึ่งหรือไม่ เนื่องจากมีเพียงเส้นทางเดียวจากสถานะเริ่มต้น ซึ่งทำเครื่องหมายด้วยบรรทัดนี้
รูปที่ 3 แสดงกราฟการเปลี่ยนแปลงของ DFA ที่ยอมรับภาษาเดียวกัน (a | b) * a (a | b) (a | b) เป็น NFA ในรูปที่ 1
รูปที่ 3 DFA ยอมรับสตริง (a | b) * a (a | b) (a | b)
เครื่องกำหนดสถานะจำกัด M ที่ยอมรับภาษาที่กำหนด:
M = ((1, 2, 3, 4, 5, 6, 7, 8), (a, b), D, 1, (3, 5, 6, 8))
ฟังก์ชันการเปลี่ยนแปลง D ถูกกำหนดดังนี้:
การสร้าง nka โดยใช้นิพจน์ทั่วไป
1. สำหรับ ε NSA มีรูปแบบดังต่อไปนี้ (0 คือสถานะเริ่มต้น 1 คือสถานะสุดท้าย):
2. สำหรับ a รวมอยู่ในภาษาที่กำหนดของ NCA:
3. ให้ N (s) และ N (t) เป็น NFA สำหรับ นิพจน์ทั่วไป s และ t
สำหรับนิพจน์ทั่วไป s | t คอมโพสิต NFA มีรูปแบบดังต่อไปนี้:
ข. สำหรับนิพจน์ทั่วไป st NFA:
กับ. สำหรับนิพจน์ s * NCA มีรูปแบบดังนี้:
ง. สำหรับนิพจน์ในวงเล็บ ให้ใช้ NFA N ตามวรรค a
แต่ละรัฐใหม่จะได้รับชื่อบุคคล การก่อสร้าง NSA N (r) มีคุณสมบัติดังต่อไปนี้:
N (r) มีจำนวนสถานะไม่เกินจำนวนสัญลักษณ์มากกว่า 2 เท่า
N (r) มีสถานะเริ่มต้นและสถานะสุดท้ายเพียงรายการเดียว สถานะสุดท้ายไม่มีช่วงการเปลี่ยนภาพขาออก
แต่ละสถานะ N (r) มีการเปลี่ยนแปลง 1 ครั้งสำหรับสัญลักษณ์จากตัวอักษร () หรือ ε-transitions ขาออกไม่เกิน 2 ครั้ง
แปลง nka เป็น dka
NFA ในรูปที่ 1 มีการเปลี่ยนสถานะ 2 ครั้งจากสถานะ 0 สำหรับสัญลักษณ์ a: สถานะ 0 และ 1 การเปลี่ยนแปลงนี้มีความคลุมเครือ เช่นเดียวกับการเปลี่ยนแปลงใน ε การสร้างแบบจำลอง NSV ดังกล่าวโดยใช้โปรแกรมคอมพิวเตอร์นั้นยากกว่ามาก คำจำกัดความของ validity ระบุว่า ต้องมี path จาก initial state ไปถึง Final state อยู่บ้าง แต่เมื่อมีหลาย path สำหรับ input string เดียวกัน ทั้งหมดต้องพิจารณาเพื่อหา path สู่ Final state หรือค้นหา ว่าไม่มีทางเป็นเช่นนั้น
ในตารางการเปลี่ยนแปลง NFA แต่ละระเบียนจะสอดคล้องกับชุดของสถานะ และในตารางการเปลี่ยนแปลง DFA จะมีเพียงรายการเดียวเท่านั้น สาระสำคัญของการเปลี่ยนแปลงคือแต่ละสถานะ DFA สอดคล้องกับชุดของสถานะ NFA DFA ใช้สถานะเพื่อติดตามสถานะที่เป็นไปได้ทั้งหมดที่ NFA สามารถอ่านได้หลังจากอ่านสัญลักษณ์อินพุตถัดไป นั่นคือ หลังจากอ่านสตรีมอินพุตแล้ว DFA จะอยู่ในสถานะที่แสดงถึงชุดของสถานะของ NFA ที่สามารถเข้าถึงได้จากค่าเริ่มต้นตามเส้นทางที่สอดคล้องกับบรรทัดอินพุต จำนวนสถานะดังกล่าวของ DFA สามารถเกินจำนวนสถานะของ NFA (การพึ่งพาแบบเอ็กซ์โปเนนเชียล) ได้อย่างมีนัยสำคัญ แต่ในทางปฏิบัติ ภาวะดังกล่าวพบได้ยากมาก และบางครั้งมีสถานะใน DFA น้อยกว่าใน NFA ด้วยซ้ำ
ลองพิจารณาการแปลงที่คล้ายกันโดยใช้ตัวอย่างเฉพาะ รูปที่ 4 แสดง NFA อื่นที่อนุญาตให้ใช้ภาษา (a | b) * a (a | b) (a | b) (ดังในรูปที่ 1 และ 3)
รูปที่ 4 NFA อนุญาตภาษา (a | b) * a (a | b) (a | b)
การเปลี่ยนจากสถานะ 13 เป็นสถานะ 14 ที่แสดงในรูปสามารถแสดงได้ในทำนองเดียวกันกับการเปลี่ยนจากสถานะที่ 8 เป็นสถานะที่ 13
มาสร้าง DFA สำหรับภาษาที่กำหนดกัน สถานะเริ่มต้นของ DFA ที่เทียบเท่ากันคือสถานะ A = (0, 1, 2, 4, 7) นั่นคือสถานะที่สามารถเข้าถึงได้จาก 0 โดย ε
ตัวอักษรของอักขระที่ป้อนคือ (a, b) จากสถานะเริ่มต้น A เราสามารถคำนวณสถานะที่ทำได้โดยเทียบกับ a เรียกสถานะนี้ว่า B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14)
ในบรรดารัฐต่างๆ ใน A มีเพียงรัฐ 4 เท่านั้นที่มีการเปลี่ยนผ่านตาม b เป็นสถานะ 5 ดังนั้น DFA จึงมีการเปลี่ยนแปลงตาม b จาก A เป็นสถานะ C = (1, 2, 4, 5, 6, 7)
หากเราดำเนินการตามกระบวนการนี้ต่อด้วยสถานะ B และ C ชุดของสถานะ NFA ทั้งหมดจะถูกทำเครื่องหมาย ดังนั้นเราจะมีหลายรัฐ:
เอ = (0, 1, 2, 4, 7)
B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14)
ค = (1, 2, 4, 5, 6, 7)
ง = (10, 12, 13, 14)
สถานะ A เป็นค่าเริ่มต้น และสถานะ B, D, E ถือเป็นที่สิ้นสุด
ตารางการเปลี่ยนแปลงทั้งหมดแสดงอยู่ด้านล่าง
รูปที่ 5 ด้านล่างแสดง DFA เองสำหรับภาษานี้
รูปที่ 5. DFA ยอมรับภาษา (a | b) * a (a | b) (a | b)
รายชื่อวรรณกรรมที่ใช้:
Pentus A.E., Pentus M.R. - ทฤษฎีภาษาทางการ
A. Aho, R. Seti, D, Ullman - คอมไพเลอร์: หลักการ, เทคโนโลยี, เครื่องมือ
จะสะดวกกว่าในการอธิบายคำศัพท์ของภาษาในรูปแบบของนิพจน์ทั่วไป และการจดจำภาษาโดยใช้ CA ดังนั้นจึงเป็นสิ่งสำคัญที่จะสามารถแปลงคำจำกัดความของภาษาในรูปแบบของนิพจน์ทั่วไปเป็นคำจำกัดความในรูปแบบของ CA การเปลี่ยนแปลงนี้เสนอโดย Kennet Thompson
หุ่นยนต์ไฟไนต์คือห้า (S, S, d, S 0, F)
S คือเซตของสถานะจำกัด
S คือชุดสัญญาณอินพุตที่ยอมรับได้จำกัด
d - ฟังก์ชันการเปลี่ยนแปลง มันสะท้อนถึงเซต Sx (SÈ (e)) ในชุดของสถานะของออโตเมติกไฟไนต์แบบกำหนดไม่ได้ สำหรับหุ่นยนต์ที่กำหนดขึ้นเอง ฟังก์ชันการเปลี่ยนแปลงสะท้อนถึง SxS ที่ตั้งค่าไว้ในชุดของสถานะของหุ่นยนต์ กล่าวอีกนัยหนึ่ง ขึ้นอยู่กับสถานะและสัญลักษณ์อินพุต d กำหนดสถานะใหม่ของหุ่นยนต์
S 0 - สถานะเริ่มต้นของหุ่นยนต์จำกัด S 0 Î S.
F คือเซตของสถานะจำกัดของหุ่นยนต์ F Î S
การทำงานของเครื่องรัฐเป็นลำดับขั้นตอน ขั้นตอนจะถูกกำหนดโดยสถานะของเครื่องและสัญลักษณ์อินพุต ขั้นตอนเองประกอบด้วยการเปลี่ยนสถานะของเครื่องและอ่านอักขระถัดไปของลำดับอินพุต
มีอยู่ ปฏิบัติตามกฎการแปลงนิพจน์ทั่วไปเป็นเครื่องสถานะ
1 นิพจน์ทั่วไป "e" ถูกแปลงเป็นกลไกอัตโนมัติของสองสถานะและการเปลี่ยนแปลงทางอิเล็กทรอนิกส์ระหว่างพวกเขา (รูปที่ 1)
รูปที่ 1 - เครื่องอัตโนมัติสำหรับ e-transition
2 นิพจน์ทั่วไปจากอักขระหนึ่งตัว "a" จะถูกแปลงเป็นเครื่องแสดงสถานะของสองสถานะ และการเปลี่ยนแปลงระหว่างพวกมันบนสัญญาณอินพุต a (รูปที่ 2)
รูปที่ 2 - เครื่องอัตโนมัติสำหรับการเปลี่ยนด้วยสัญลักษณ์ a
3 สมมติว่ามีนิพจน์ทั่วไป rs และ state machine สำหรับ expression r และ expression ถูกสร้างขึ้นแล้ว จากนั้นเครื่องทั้งสองจะเชื่อมต่อกันเป็นชุด รูปที่ 3 แสดงออโตมาตาดั้งเดิมสำหรับภาษา r และ s รูปแสดงหุ่นยนต์สำหรับจดจำการเรียงต่อกันของภาษาเหล่านี้
เครื่องอัตโนมัติสำหรับ r เครื่องอัตโนมัติสำหรับ s
รูปที่ 3 - ออโตมาตาเริ่มต้น
รูปที่ 4 - เครื่องสำหรับเชื่อมภาษา
4 ให้มีนิพจน์ทั่วไป r | s และ state machine สำหรับ expression r และ expression ถูกสร้างขึ้นแล้ว (ภาพที่ 3) จากนั้นออโตมาตันที่ได้จะต้องมีทางเลือกอื่นในการรันออโตมาตาตัวใดตัวหนึ่ง นั่นคือหุ่นยนต์สำหรับแสดง r | s สำหรับ automata สำหรับ r และ s จากรูปที่ 3 มีรูปแบบที่แสดงในรูปที่ 5
รูปที่ 5 - เครื่องสำหรับรวมภาษา
5 ปล่อยให้มีนิพจน์ทั่วไป r * ด้วยเครื่องสร้างสถานะ จำกัด r ในกรณีนี้ มีการแนะนำสถานะใหม่สองสถานะสำหรับความเป็นไปได้ในการข้ามกลไกของนิพจน์ r และการเปลี่ยนผ่านแบบอิเล็กทรอนิกส์ระหว่างสถานะสุดท้ายและสถานะเริ่มต้นสำหรับความเป็นไปได้ของการทำซ้ำหลายครั้งของหุ่นยนต์ r หากหุ่นยนต์ที่คล้ายกับรูปที่ 3 ถูกสร้างขึ้นสำหรับนิพจน์ทั่วไป r เครื่องแสดงสถานะที่แสดงในรูปที่ 6 จะสอดคล้องกับนิพจน์ทั่วไป r *
ในส่วนนี้ เราจะสร้างคำถามที่สำคัญเกี่ยวกับภาษาปกติ ก่อนอื่น คุณต้องหาว่าการถามคำถามเกี่ยวกับภาษาใดภาษาหนึ่งหมายความว่าอย่างไร ภาษาทั่วไปนั้นไม่มีที่สิ้นสุด ดังนั้นจึงไม่สมเหตุสมผลที่จะแสดงให้คนอื่นเห็นสายโซ่ของภาษานี้และถามคำถามที่ต้องตรวจสอบจำนวนไม่สิ้นสุดของสายโซ่ มีเหตุผลมากกว่ามากที่จะใช้การแสดงแทนอย่างจำกัดของภาษา กล่าวคือ DFA, NFA, ε-NFA หรือนิพจน์ทั่วไป
เห็นได้ชัดว่าภาษาที่นำเสนอในลักษณะนี้จะเป็นปกติ ไม่มีทางที่จะเป็นตัวแทนของภาษาตามอำเภอใจได้อย่างแท้จริง ในบทต่อไปนี้จะเสนอวิธีการ จำกัด ในการอธิบายคลาสที่กว้างกว่าคลาสของภาษาปกติและพิจารณาคำถามเกี่ยวกับภาษาจากพวกเขา อย่างไรก็ตาม อัลกอริทึมสำหรับการแก้ปัญหามากมายเกี่ยวกับภาษานั้นมีอยู่ในชั้นเรียนของภาษาปกติเท่านั้น คำถามเดียวกันนี้จะกลายเป็น "แก้ไม่ได้" (ไม่มีอัลกอริธึมสำหรับการตอบคำถามเหล่านี้) หากมีการตั้งคำถามโดยใช้สัญลักษณ์ที่ "แสดงออก" มากกว่า (ใช้เพื่อแสดงภาษาที่หลากหลายขึ้น) มากกว่าการนำเสนอที่พัฒนาขึ้นสำหรับภาษาปกติ
มาเริ่มการศึกษาอัลกอริทึมสำหรับคำถามเกี่ยวกับภาษาปกติกันโดยพิจารณาจากวิธีที่การแสดงภาษาหนึ่งเปลี่ยนเป็นอีกภาษาหนึ่ง โดยเฉพาะอย่างยิ่ง ให้พิจารณาความซับซ้อนของเวลาของอัลกอริทึมที่ทำการแปลง จากนั้นเราจะดูคำถามหลักสามข้อเกี่ยวกับภาษา
1. ภาษาที่อธิบายเป็นชุดว่างหรือไม่?
2. สตริง w เป็นภาษาที่นำเสนอหรือไม่?
3. มีสองจริงๆ คำอธิบายที่แตกต่างกันเป็นตัวแทนของภาษาเดียวกัน? (คำถามนี้มักเรียกว่า "ความเท่าเทียมกัน" ของภาษา)
2.1 การแปลงการแสดงแทนภาษาต่างๆ
การแสดงแทนภาษาปกติทั้งสี่แต่ละภาษาสามารถแปลงเป็นภาษาใดก็ได้จากอีกสามภาษา ในรูป 3.1 แสดงการเปลี่ยนจากมุมมองหนึ่งไปอีกมุมมองหนึ่ง แม้ว่าอัลกอริธึมที่มีอยู่สำหรับการแปลงใดๆ เหล่านี้ บางครั้งเราไม่เพียงสนใจในความเป็นไปได้ของการแปลงเท่านั้น แต่ยังรวมถึงในเวลาที่ใช้ในการทำให้เสร็จด้วย โดยเฉพาะอย่างยิ่ง สิ่งสำคัญคือต้องแยกความแตกต่างของอัลกอริธึมที่ใช้เวลาแบบเอ็กซ์โพเนนเชียล (เวลาเป็นฟังก์ชันของขนาดของข้อมูลที่ป้อนเข้า) ดังนั้นจึงสามารถดำเนินการได้เฉพาะข้อมูลอินพุตที่ค่อนข้างเล็กเท่านั้น จากอัลกอริธึมที่มีเวลาดำเนินการเป็นเส้นตรงและกำลังสอง หรือพหุนามที่มีขนาดเล็กเป็นฟังก์ชันของขนาดของข้อมูลที่ป้อน อัลกอริธึมหลังนั้น "สมจริง" ในการที่สามารถดำเนินการกับอินสแตนซ์ปัญหาในระดับที่กว้างขึ้นได้ พิจารณาความซับซ้อนของเวลาของการเปลี่ยนแปลงแต่ละครั้งที่กล่าวถึง
การแปลง NCA เป็น DCA
เวลาดำเนินการของการแปลง NFA หรือ ε-NFA เป็น DFA สามารถเป็นฟังก์ชันเลขชี้กำลังของจำนวนสถานะของ NFA เริ่มต้นด้วยการคำนวณ ε-ปิดของ n สถานะใช้เวลา O (n3) จำเป็นต้องค้นหาส่วนโค้งทั้งหมดที่มีป้ายกำกับ ε นำหน้าจากแต่ละสถานะ n หากมี n สถานะ ก็จะมีส่วนโค้งได้ไม่เกิน n2 ส่วน การใช้งานที่เหมาะสม ทรัพยากรระบบและโครงสร้างข้อมูลที่ออกแบบมาอย่างดีช่วยให้มั่นใจได้ว่าเวลาในการสำรวจของแต่ละรัฐจะไม่เกิน O (n2) อันที่จริง อัลกอริธึมการปิดสกรรมกริยา เช่น อัลกอริธึม Warshall 5 สามารถใช้ในการคำนวณ ε-close ทั้งหมดครั้งเดียว
หลังจากคำนวณ ε-ปิด เราสามารถดำเนินการสังเคราะห์ DFA โดยใช้การสร้างเซตย่อย อิทธิพลหลักในการใช้เวลาขึ้นอยู่กับจำนวนของสถานะ DFA ซึ่งสามารถเท่ากับ 2n สำหรับแต่ละรัฐ เป็นไปได้ที่จะคำนวณการเปลี่ยนแปลงในเวลา O (n3) โดยใช้ ε-close และตารางการเปลี่ยน NFA สำหรับสัญลักษณ์อินพุตแต่ละรายการ สมมติว่าคุณจำเป็นต้องคำนวณ δ ((q1, q2,…, qk), a) สำหรับ DFA แต่ละสถานะ qi สามารถไปถึงได้มากที่สุด n สถานะตามเส้นทางที่มีป้ายกำกับ ε และแต่ละสถานะเหล่านี้สามารถมีส่วนโค้งได้สูงสุด n สถานะที่มีป้ายกำกับ a เมื่อสร้างอาร์เรย์ที่จัดทำดัชนีโดยรัฐแล้ว เราสามารถคำนวณการรวมของชุดได้สูงสุด n ชุด ซึ่งประกอบด้วยสถานะไม่เกิน n สถานะในเวลาตามสัดส่วนของ n2
ด้วยวิธีนี้ สำหรับแต่ละรัฐฉี เราสามารถคำนวณชุดของสถานะที่สามารถเข้าถึงได้จากฉีตามเส้นทางที่มีป้ายกำกับ a (อาจรวมถึงส่วนโค้งที่มีป้ายกำกับ ε) เนื่องจาก k ≤ n มีมากที่สุด n สถานะดังกล่าว qi และสำหรับแต่ละรายการ การคำนวณสถานะที่เข้าถึงได้จะใช้เวลา O (n2) ทางนี้, เวลารวมการคำนวณสถานะที่เข้าถึงได้คือ O (n3) การรวมชุดของสถานะที่เข้าถึงได้จะต้องใช้เวลาเพิ่มเติมเพียง O (n2) ดังนั้น การคำนวณการเปลี่ยนแปลง DFA หนึ่งครั้งจะใช้เวลา O (n3)
โปรดทราบว่าจำนวนอักขระป้อนเข้าถือเป็นค่าคงที่และไม่ขึ้นกับ n ดังนั้น ทั้งในนี้และในการประมาณเวลาทำงานอื่นๆ จะไม่พิจารณาจำนวนอักขระที่ป้อนเข้า ขนาดของตัวอักษรอินพุตจะมีผลกับปัจจัยคงที่ที่ซ่อนอยู่ในสัญกรณ์ Big O เท่านั้น
ดังนั้น เวลาการแปลงของ NFA เป็น DFA รวมถึงสถานการณ์เมื่อ NFA มี ε-transitions คือ O (n32n) แน่นอน ในทางปฏิบัติ โดยปกติจำนวนรัฐที่สร้างขึ้นจะน้อยกว่า 2n มาก บางครั้งมีเพียง n ดังนั้นจึงเป็นไปได้ที่จะกำหนดระยะเวลาทำงานโดยประมาณเท่ากับ O (n3s) โดยที่ s คือจำนวนสถานะที่ DFA มีจริง
แปลง DKA เป็น NKA
นี่คือการเปลี่ยนแปลงอย่างง่ายที่ใช้เวลา O (n) สำหรับ n-state DFA สิ่งที่ต้องทำคือเปลี่ยนตารางการเปลี่ยนแปลงสำหรับ DFA โดยใส่สถานะไว้ในวงเล็บ () และเพิ่มคอลัมน์สำหรับ ε หากจำเป็นต้องได้รับ ε-NFA เนื่องจากจำนวนอักขระอินพุต (เช่น ความกว้างของตารางข้าม) ถือเป็นค่าคงที่ การคัดลอกและประมวลผลตารางจึงใช้เวลา O (n)
แปลงหุ่นยนต์เป็นนิพจน์ทั่วไป
ในแต่ละขั้นตอนของ n (โดยที่ n คือจำนวนสถานะ DFA) ขนาดของนิพจน์ทั่วไปที่สร้างอาจเพิ่มขึ้นเป็นสี่เท่า เนื่องจากแต่ละนิพจน์สร้างขึ้นจากนิพจน์สี่รายการของวงจรก่อนหน้า ทางนี้, รายการง่ายนิพจน์ n3 อาจใช้เวลา O (n34n) การก่อสร้างที่ได้รับการปรับปรุงจากส่วนที่ 3.2.2 ช่วยลดปัจจัยคงที่ แต่ไม่ส่งผลต่อการชี้แจงของปัญหานี้ (ในกรณีที่เลวร้ายที่สุด)
การออกแบบที่คล้ายกันต้องใช้เวลาในการทำงานเท่ากันหาก NFA หรือแม้แต่ ε-NFA ถูกแปลง แต่สิ่งนี้ไม่ได้รับการพิสูจน์ที่นี่ อย่างไรก็ตาม การใช้การออกแบบสำหรับ NSA ได้ สำคัญมาก... หากคุณแปลง NFA เป็น DFA ในครั้งแรก จากนั้น DFA เป็นนิพจน์ทั่วไป จะต้องใช้เวลา O (n34n32n) ซึ่งเป็นเลขชี้กำลังสองเท่า
แปลงนิพจน์ทั่วไปเป็นออโตมาตอน
ต้องใช้เวลาเชิงเส้นในการแปลงนิพจน์ทั่วไปเป็น ε-NFA คุณต้องแยกวิเคราะห์ regex อย่างมีประสิทธิภาพโดยใช้วิธีที่ใช้เวลา O (n) สำหรับ regex ที่มีความยาว n6 ด้วยเหตุนี้ เราจึงได้ต้นไม้ที่มีหนึ่งโหนดสำหรับอักขระแต่ละตัวของนิพจน์ทั่วไป (แม้ว่าวงเล็บจะไม่ปรากฏในแผนผังนี้ เนื่องจากพวกมันควบคุมเฉพาะการแยกวิเคราะห์ของนิพจน์)
แผนผังผลลัพธ์ของนิพจน์ทั่วไปที่กำหนดสามารถประมวลผลได้โดยการสร้าง ε-NFA สำหรับแต่ละโหนด กฎการแปลง regex ที่นำมาใช้ในหัวข้อ 3.2.3 จะไม่เพิ่มสถานะมากกว่าสองสถานะและสี่ส่วนโค้งให้กับแต่ละโหนดในแผนผังนิพจน์ ดังนั้น ทั้งจำนวนสถานะและจำนวนส่วนโค้งของผลลัพธ์ ε-NCA จะเท่ากับ O (n) นอกจากนี้ งานในการสร้างองค์ประกอบเหล่านี้ในแต่ละโหนดของแผนภูมิการวิเคราะห์จะคงที่ โดยที่ฟังก์ชันที่ประมวลผลแต่ละทรีย่อยจะส่งกลับพอยน์เตอร์ไปยังสถานะเริ่มต้นและสถานะที่ยอมรับของหุ่นยนต์นี้
เราได้ข้อสรุปว่าการสร้าง ε-NFA ด้วยนิพจน์ทั่วไปต้องใช้เวลา ซึ่งขึ้นอยู่กับขนาดของนิพจน์เชิงเส้น เป็นไปได้ที่จะแยก ε-transitions ออกจาก ε-NCA ที่มี n state โดยแปลงเป็น NCA ธรรมดาในเวลา O (n3) และไม่เพิ่มจำนวนสถานะ อย่างไรก็ตาม การแปลงเป็น DFA อาจต้องใช้เวลาแบบทวีคูณ
ต้องการโดยเครื่องสถานะจำกัดที่ไม่ได้กำหนดไว้ เอ็ม = (คิว, ตู่, ดี, q 0 , F) สร้างเครื่องกำหนดสถานะ จำกัด เอ็ม = (คิว ", ตู่, ดี ", คิว " 0 , เอฟ "). สถานะเริ่มต้นสำหรับหุ่นยนต์ที่กำลังก่อสร้างคือ ε-ปิดของสถานะเริ่มต้นของหุ่นยนต์เริ่มต้น ε-ปิดคือชุดของสถานะที่สามารถเข้าถึงได้จากสถานะที่กำหนดโดยการเปลี่ยนผ่าน ε นอกจากนี้ ในขณะที่มีสถานะต่างๆ ที่ไม่มีการสร้างการเปลี่ยนภาพ (การเปลี่ยนภาพเกิดขึ้นด้วยสัญลักษณ์ การเปลี่ยนผ่านซึ่งอยู่ในหุ่นยนต์ดั้งเดิม) สำหรับแต่ละสัญลักษณ์ ε-การปิดชุดสถานะจะคำนวณซึ่งสามารถเข้าถึงได้จาก รัฐที่อยู่ระหว่างการพิจารณาโดยเปลี่ยนตามสัญลักษณ์ที่พิจารณา หากสถานะที่สอดคล้องกับชุดที่พบมีอยู่แล้ว การเปลี่ยนแปลงจะถูกเพิ่มที่นั่น ถ้าไม่เช่นนั้น สถานะที่ได้รับใหม่จะถูกเพิ่มเข้าไป
ตัวอย่าง
การเริ่มต้น
สถานะที่สอดคล้องกับε-ปิดของค่าเริ่มต้นจะถูกทำเครื่องหมาย รัฐเหล่านี้จะสอดคล้องกับรัฐ อาดีเคเอในอนาคต
ทำซ้ำครั้งแรก
มีการเปลี่ยนจาก ε-close เป็นสถานะ NFA 3 และ 10 (ตาม เอและ คตามลำดับ) สำหรับสถานะ 3 การปิด ε คือเซตของสถานะ (3, 4, 6) สำหรับสถานะ 10 - (10) เราแสดงถึงสถานะ DFA ใหม่ที่สอดคล้องกับชุดเหล่านี้เป็น บีและ ค.
| รัฐ DKA | ชุดของรัฐของ NCA | |||
|---|---|---|---|---|
| เอ | ข | ค | ||
| อา | {1, 2, 9} | บี | - | ค |
| บี | {3, 4, 6} | - | - | - |
| ค | {10} | - | - | - |
ทำซ้ำครั้งที่สอง
จากชุดของสถานะ NFA (3, 4, 6) ซึ่งสอดคล้องกับสถานะ DFA บีมีสองช่วงการเปลี่ยนภาพ - เป็นสถานะ 5 (by ข) และ 7 (โดย ค). ตัวปิด ε ของพวกมันตัดกัน แต่เซตต่างกัน ดังนั้น พวกเขาจึงได้รับสถานะใหม่สองสถานะของ DFA - ดีและ อี... จากสถานะของ NFA ที่สอดคล้องกับสถานะของ DFA ค, ไม่มีช่วงการเปลี่ยนภาพ
| รัฐ DKA | ชุดของรัฐของ NCA | สัญลักษณ์นำทาง | ||
|---|---|---|---|---|
| เอ | ข | ค | ||
| อา | {1, 2, 9} | บี | - | ค |
| บี | {3, 4, 6} | - | ดี | อี |
| ค | {10} | - | - | - |
| ดี | {2, 5, 8, 9} | - | - | - |
| อี | {2, 7, 8, 9} | - | - | - |
การทำซ้ำครั้งที่สาม
จากชุดของสถานะของ NFA ที่สอดคล้องกับสถานะของ NFA ดีและ อีการเปลี่ยนแปลงเกิดขึ้นกับชุดของสถานะที่สอดคล้องกับสถานะที่มีอยู่ (จากชุด (2, 5, 8, 9) ที่สอดคล้องกับสถานะ ดี, บน เอเปลี่ยนเป็นสถานะ 3 ที่เป็นของชุด (3, 4, 6) ที่สอดคล้องกับสถานะของ DFA บี, บน ค- เปลี่ยนเป็นสถานะ 10 สอดคล้องกับสถานะ ค; ในทำนองเดียวกันสำหรับชุดที่สอดคล้องกับสถานะของ DFA อี). กระบวนการสร้างตารางสถานะและการเปลี่ยนผ่านของ DFA เสร็จสมบูรณ์
| รัฐ DKA | ชุดของรัฐของ NCA | สัญลักษณ์นำทาง | ||
|---|---|---|---|---|
| เอ | ข | ค | ||
| อา | {1, 2, 9} | บี | - | ค |
| บี | {3, 4, 6} | - | ดี | อี |
| ค | {10} | - | - | - |
| ดี | {2, 5, 8, 9} | บี | - | ค |
| อี | {2, 7, 8, 9} | บี | - | ค |
ผลลัพธ์:
การสร้างไวยากรณ์เชิงเส้นตรงจากเครื่องสถานะจำกัด
เรากำหนด nonterminal ให้กับแต่ละรัฐ หากมีการเปลี่ยนแปลงจากรัฐ Xอยู่ในสถานะ Yบน เอ, เพิ่มกฎ X → ใช่... เพิ่มกฎสำหรับสถานะสุดท้าย X→ ε. สำหรับ ε-การเปลี่ยน - X → Y.
ตัวอย่างที่ 1 (เครื่องกำหนดสถานะ)
- เอ → เอบี | คค
- ข → ขด | คอี
- C → ε
- ง → เอบี | คค
- อี → เอบี | คค
ตัวอย่างที่ 2 (เครื่องสถานะไม่กำหนด)
- 1 → 2 | 9
- 2 → เอ 3
- 3 → 4 | 6
- 4 → ข 5
- 5 → 8
- 6 → ค 7
- 7 → 8
- 8 → 2 | 9
- 9 → ค 10
- 10 → ε
การสร้าง DFA ตาม PB
ให้มีนิพจน์ปกติ r... สำหรับนิพจน์ทั่วไปนี้ จำเป็นต้องสร้างเครื่องกำหนดสถานะจำกัด ดีดังนั้น หลี่(ดี) = หลี่(r).
การปรับเปลี่ยนนิพจน์ปกติ
มาเพิ่มสัญลักษณ์ที่หมายถึงจุดสิ้นสุดของ PB - "#" กันเถอะ เป็นผลให้เราได้รับนิพจน์ปกติ ( r)#.
สร้างต้นไม้
มาแทนนิพจน์ทั่วไปในรูปแบบของต้นไม้ ใบไม้ซึ่งเป็นสัญลักษณ์ปลายทาง และจุดยอดด้านในคือการดำเนินการของการต่อกัน ".", ยูเนี่ยน "∪" และการวนซ้ำ "*" ใบไม้แต่ละใบของต้นไม้ (ยกเว้น ε-ใบ) ถูกกำหนดหมายเลขที่ไม่ซ้ำกัน และเราจะอ้างอิงถึงมันในด้านหนึ่งเป็นตำแหน่งในต้นไม้และในอีกทางหนึ่งเป็นตำแหน่งของสัญลักษณ์ที่สอดคล้องกับ ใบ
การประเมินฟังก์ชัน nullable, firstpos, lastpos
ตอนนี้ สำรวจต้นไม้ T จากล่างขึ้นบนจากซ้ายไปขวา เราคำนวณสามฟังก์ชัน: nullable, โพสแรก, และ โพสสุดท้าย... ฟังก์ชั่น nullable, โพสแรกและ โพสสุดท้ายถูกกำหนดไว้ที่โหนดของต้นไม้ ค่าของฟังก์ชันทั้งหมด ยกเว้น nullable,เป็นหลากหลายตำแหน่ง. การทำงาน โพสแรก(น) สำหรับแต่ละโหนด n ของแผนผังไวยากรณ์ regexp ให้ชุดของตำแหน่งที่ตรงกับอักขระตัวแรกใน subchains ที่สร้างโดยนิพจน์ย่อยที่มีจุดยอดที่ น... เช่นเดียวกัน, โพสสุดท้าย(น) ให้ชุดของตำแหน่งที่สอดคล้องกับอักขระสุดท้ายใน subchains ที่สร้างโดยนิพจน์ย่อยที่มีจุดยอด น... สำหรับโหนด นที่มีต้นไม้ย่อย (เช่น ต้นไม้ที่มีโหนด นเป็นรูท) สามารถสร้างคำที่ว่างเปล่าได้ เรากำหนด nullable(น) = จริงและสำหรับโหนดที่เหลือ เท็จ... ตารางการคำนวณ nullable, โพสแรก, โพสสุดท้าย:
| ปม น | nullable(น) | โพสแรก(น) | โพสสุดท้าย(น) |
|---|---|---|---|
| ε | จริง | ∅ | ∅ |
| ผม ≠ ε | เท็จ | {ผม} | {ผม} |
| คุณ ∪ v | nullable(ยู) หรือ nullable(วี) | โพสแรก(ยู) ∪ โพสแรก(วี) | โพสสุดท้าย(ยู) ∪ โพสสุดท้าย(วี) |
| ยู. วี | nullable(ยู) และ nullable(วี) | ถ้า nullable(ยู) แล้ว โพสแรก(ยู) ∪ โพสแรก(วี) อื่น โพสแรก(ยู) | ถ้า nullable(วี) แล้ว โพสสุดท้าย(ยู) ∪ โพสสุดท้าย(วี) อื่น โพสสุดท้าย(วี) |
| วี * | จริง | โพสแรก(วี) | โพสสุดท้าย(วี) |
การติดตามสิ่งปลูกสร้าง
การทำงาน ติดตามคำนวณผ่าน nullable, โพสแรกและ โพสสุดท้าย... การทำงาน ติดตามกำหนดไว้ตามตำแหน่งต่างๆ มูลค่า ติดตามเป็นตำแหน่งที่หลากหลาย ถ้า ผม- ตำแหน่ง แล้ว ติดตาม(ผม) มีหลายตำแหน่ง เจจนมีเส้นบางๆ ... ซีดี... รวมอยู่ในภาษาที่ PB อธิบายไว้เช่นนั้น ผมตรงกับรายการนี้ ค, แ เจ- รายการ d... การทำงาน ติดตามสามารถคำนวณได้ในการข้ามต้นไม้หนึ่งครั้งตามกฎสองข้อต่อไปนี้
- อนุญาต น- โหนดภายในพร้อมการทำงาน "." (ต่อกัน); เอ, ข- ลูกหลานของเขา แล้วสำหรับแต่ละตำแหน่ง ผมรวมอยู่ใน โพสสุดท้าย(เอ ติดตาม(ผม) พวงของ โพสแรก(ข).
- อนุญาต น- โหนดภายในพร้อมการทำงาน "*" (การวนซ้ำ) เอ- ทายาทของเขา แล้วสำหรับแต่ละตำแหน่ง ผมรวมอยู่ใน โพสสุดท้าย(เอ) เพิ่มเข้าไปในชุดของค่า ติดตาม(ผม) พวงของ โพสแรก(เอ).
ตัวอย่าง
คำนวณค่าของฟังก์ชัน ติดตามสำหรับ regex ( เอ(ข|ค))*ค.
| ตำแหน่ง | ความหมาย ติดตาม |
|---|---|
| 1: (เอ (ข|ค))*ค | {2, 3} |
| 2: (เอ(ข |ค))*ค | {1, 4} |
| 3: (เอ(ข|ค ))*ค | {1, 4} |
| 4: (เอ(ข|ค))*ค | {5} |
การสร้าง DFA
DCA คือชุดของสถานะและชุดการเปลี่ยนผ่านระหว่างรัฐทั้งสอง สถานะ DFA คือชุดของตำแหน่ง การสร้าง DFA ประกอบด้วยการเพิ่มสถานะที่จำเป็นอย่างค่อยเป็นค่อยไปและการสร้างการเปลี่ยนแปลงสำหรับพวกเขา เริ่มแรกมีรัฐหนึ่งคือ โพสแรก(ราก) (ราก- รากของต้นไม้) ซึ่งไม่มีการเปลี่ยนแปลง การเปลี่ยนดำเนินการโดยอักขระจากนิพจน์ทั่วไป อักขระแต่ละตัวสอดคล้องกับชุดของตำแหน่ง ( พี ผม). รวมกันเป็นหนึ่ง ติดตาม(x) คือสถานะที่จำเป็นต้องไป โดยที่ x คือตำแหน่งที่มีอยู่ทั้งในตำแหน่งของรัฐและในตำแหน่งของสัญลักษณ์จาก PB ซึ่งดำเนินการเปลี่ยนผ่าน หากไม่มีสถานะดังกล่าวจะต้องเพิ่ม กระบวนการต้องทำซ้ำจนกว่าจะสร้างช่วงการเปลี่ยนภาพทั้งหมดสำหรับสถานะทั้งหมด ทุกรัฐที่มีตำแหน่งของสัญลักษณ์ # ที่เพิ่มต่อท้าย PB ถือเป็นที่สิ้นสุด
DFA ที่ได้รับจาก PB ( เอ(ข|ค))*ค
ตัวอย่าง
สร้าง DFA โดยใช้นิพจน์ทั่วไป ( เอ(ข|ค))*ค.
| รัฐ DKA | สัญลักษณ์ | ||
|---|---|---|---|
| ก (1) | ข (2) | ค (3, 4) | |
| เอ (1, 4) | ข (2, 3) | - | ค (5) |
| ข (2, 3) | - | เอ (1, 4) | เอ (1, 4) |
| ค (5) | - | - | - |
การสร้าง DFA ด้วยจำนวนรัฐขั้นต่ำ
DFA ที่มีจำนวนรัฐขั้นต่ำถูกสร้างขึ้นสำหรับ DFA ที่กำหนดไว้ทุกที่ กล่าวคือ ดังนั้น. สำหรับ DFA ใดๆ จะมี DFA ที่กำหนดไว้ทุกที่ที่เทียบเท่ากับมัน
การสร้าง DFA ที่กำหนดไว้ทุกที่
มาแนะนำสถานะใหม่และกำหนดสถานะชุดใหม่กันเถอะ 
.
มากำหนดฟังก์ชันการเปลี่ยนแปลงใหม่ดังนี้:
ฉากกั้นห้อง (แบบเป็นทางการ)
มาสร้างพาร์ติชั่นเริ่มต้นกันเถอะ พีชุดของรัฐออกเป็นสองกลุ่ม: สถานะสุดท้าย Fและที่เหลือ S \ F, เช่น. พี = {F, Q \ F}.
สมัครได้ทุกกลุ่ม จี ∈ พีขั้นตอนต่อไปนี้ เลิกกัน จีเข้ากลุ่มย่อยเพื่อให้รัฐ สและ tจาก จีลงเอยในกลุ่มเดียวกันถ้าหากสำหรับแต่ละสัญลักษณ์อินพุต เอโชคลาภ สและ tมีการเปลี่ยนผ่านบน เอไปยังรัฐจากกลุ่มเดียวกันถึง พี.
กลุ่มย่อยที่เป็นผลลัพธ์จะถูกเพิ่มไปยังพาร์ติชันใหม่ พีใหม่.
พวกเรายอมรับ พี = พีใหม่และทำซ้ำการสร้างพาร์ติชั่นจนกว่าจะเสถียรนั่นคือจนกว่าพาร์ติชั่นจะหยุดเปลี่ยน
การแบ่งพาร์ติชัน (อัลกอริทึม)
มีอัลกอริทึมต่อไปนี้สำหรับการสร้างพาร์ติชัน เราสร้างตารางการเปลี่ยนแปลงสำหรับหุ่นยนต์ดั้งเดิม สร้างพาร์ติชั่นเริ่มต้น
แต่ละกลุ่มจากพาร์ติชันถูกกำหนดตัวระบุ (สำหรับพาร์ติชันเริ่มต้น เช่น 0 และ 1)
แต่ละรัฐ (แต่ละแถวของตาราง) ถูกกำหนดบรรทัดในรูปแบบ "a.bcd ... xyz" โดยที่เป็นตัวระบุของกลุ่มที่สถานะมาจาก [คอลัมน์แรก (ที่เราไป) คอลัมน์ที่สอง (ที่เราไปตามอักขระตัวแรก), ..., คอลัมน์สุดท้าย (ที่เราไปตามอักขระตัวสุดท้าย)]
เราสร้างกลุ่มใหม่โดยบังเอิญของบรรทัด กล่าวคือ เพื่อให้สถานะที่มีบรรทัดที่กำหนดเหมือนกันตกอยู่ในกลุ่มเดียว
จากนั้นทำซ้ำใหม่ เรากำหนดตัวระบุใหม่ให้กับกลุ่มผลลัพธ์ เช่น (0, 1, ..., n) และเราทำซ้ำการสร้างพาร์ติชั่นจนเสถียร
โปรดทราบว่าเมื่อเหลือเพียงสถานะเดียวในกลุ่ม ในขั้นตอนต่อๆ ไปของการสร้างพาร์ติชัน คุณจะไม่สามารถเขียนสตริงของตัวระบุสำหรับสถานะนี้ได้อีกต่อไป เนื่องจากสตริงนี้จะไม่ซ้ำกันเนื่องจากอักขระตัวแรกในทุกกรณี ของสตริง กล่าวอีกนัยหนึ่ง ระหว่างพาร์ติชั่น ไม่มีอะไรเกิดขึ้นกับกลุ่มจากสถานะหนึ่ง - มันจะถูกโอนไปยังพาร์ติชั่นใหม่ตามที่เป็นอยู่
การสร้างหุ่นยนต์ลดลง
กลุ่มผลลัพธ์แต่ละกลุ่มจะกลายเป็นสถานะของ DCA ใหม่ หากกลุ่มมีสถานะเริ่มต้น (สุดท้าย) ของหุ่นยนต์ดั้งเดิม กลุ่มนี้จะกลายเป็นสถานะเริ่มต้น (ตามลำดับ ขั้นสุดท้าย) ของ DFA ใหม่ ทรานสิชั่นถูกสร้างขึ้นในลักษณะที่ชัดเจน: การเปลี่ยนสถานะจากกลุ่มถือเป็นการเปลี่ยนผ่านสู่กลุ่ม
เราให้เครื่อง อันดับแรก เราเอาสิ่งที่ไม่ก่อกำเนิดออก (ปลอดเชื้อ "ตาย") แล้วสถานะที่ไม่สามารถเข้าถึงได้ (มีการกำหนดคำจำกัดความสำหรับสัญลักษณ์ แต่เห็นได้ชัดว่าส่งต่อไปยังสถานะของหุ่นยนต์)
โดยทั่วไป การกำจัดสถานะที่ตายแล้วจะเปลี่ยน DFA เป็น NFA เนื่องจากใน DFA การเปลี่ยนแปลงทั้งหมดจะต้องได้รับการกำหนด อย่างไรก็ตามใน Dragon Book การเบี่ยงเบนจากคำจำกัดความอย่างเป็นทางการนั้นถือว่ายอมรับได้
ตัวอย่าง
สำหรับ เราสร้าง DFA ด้วยจำนวนสถานะขั้นต่ำสำหรับ DFA ในรูปแบบต่อไปนี้:
- พาร์ติชั่นเริ่มต้น: (C) ( สถานะสุดท้าย), (A, B, D, E) ( รัฐอื่น ๆ ทั้งหมด).
- (ค) ( ไม่มีการเปลี่ยนแปลง), (A, D, E), (B), ( ตั้งแต่ A, D, E ตาม a, c เราไปที่ B และ C ตามลำดับ).
- เราไม่สามารถสร้างพาร์ติชั่นได้อีก
ให้สถานะ C สอดคล้องกับกลุ่ม (C) สถานะ A ถึงกลุ่ม (A, D, E) และสถานะ B ต่อกลุ่ม (B) จากนั้นเราจะได้ DFA ที่มีจำนวนสถานะขั้นต่ำ:
ตัวอย่าง (อัลกอริทึมการสร้างพาร์ติชัน)
ตารางการเปลี่ยนแปลงสำหรับ DFA ที่กำหนดไว้ทุกที่ (เพิ่มสถานะ Z) ที่สอดคล้องกับ PB (ab | ε) a * | abb | b * a จากงานสอบปี 2555
| เอ | ข | ฉัน 0 | ฉัน 1 | |
|---|---|---|---|---|
| → เอ * | บี | ค | 0.01 | 0.12 |
| ข * | ดี | อี | 0.00 | 1.01 |
| ค | F | ค | 1.01 | |
| ดี * | ดี | Z | 0.01 | 0.04 |
| อี * | ดี | Z | 0.00 | 1.03 |
| ฉ* | Z | Z | 0.11 | |
| Z | Z | Z | 1.11 |
การทำซ้ำ:
- ฉัน 0: ABCDEF (0), CZ (1)
- I 1: AD (0), พ.ศ. (1), C (2), F (3), Z (4)
- ฉัน 2: A, B, C, D, E, F, Z
ผลลัพธ์: เครื่องมีจำนวนสถานะขั้นต่ำอยู่แล้ว :-)
DFA อนุญาตให้เสริมภาษา
อัลกอริทึมสำหรับการสร้าง DFA โดยใช้ส่วนเสริมของภาษา L (L̅) ประกอบด้วยสองขั้นตอน:
- การสร้าง DFA . ที่สมบูรณ์
- การสร้างหุ่นยนต์ที่ต้องการจากมัน
อันที่จริงไม่มีสิ่งที่เรียกว่า DFA ที่สมบูรณ์ ภายใต้ DKA . เต็มรูปแบบ บางครูเข้าใจหุ่นยนต์ในตารางการเปลี่ยนแปลงซึ่งไม่มีเซลล์ว่าง อย่างไรก็ตาม ตามคำจำกัดความของ DFA - δ: Q × Σ → Q - ไม่สามารถมีเซลล์ว่างได้ในทุกกรณี อย่างไรก็ตาม หุ่นยนต์ที่มีเซลล์ว่างตรงตามคำจำกัดความของ NFA ในระหว่างการแก้ปัญหา มักจะได้รับเพียง NSC ดังกล่าว ซึ่งขาดเฉพาะช่วงการเปลี่ยนภาพไปยัง DSC
เพื่อเติมเต็มก็เพียงพอที่จะเพิ่มสถานะใหม่ Xและการเปลี่ยนที่ไม่มีอยู่ "แทน" จะเพิ่มช่วงการเปลี่ยนภาพไปยังสถานะใหม่นี้ ในกรณีนี้ อย่าลืมเพิ่มการเปลี่ยนจาก Xวี X... มันง่ายที่จะเห็นว่าเมื่อหุ่นยนต์ดั้งเดิมไม่ยอมรับสายโซ่ที่แน่นอนเนื่องจากไม่มีการเปลี่ยนแปลง เครื่องใหม่จะไปรัฐ Xและ "วางสาย" ในนั้น เนื่องจากสถานะใหม่ไม่ยอมรับ (สุดท้าย) หุ่นยนต์ใหม่จะไม่ยอมรับสายโซ่นี้เช่นกัน
ตอนนี้ เพื่อสร้างหุ่นยนต์ที่จำเป็น จำเป็นต้องเปลี่ยนบทบาทของสถานะการยอมรับและไม่ยอมรับเท่านั้น กล่าวอีกนัยหนึ่ง F "= Q \ F.
การสร้างเครื่องวิเคราะห์ LL (k)
การแปลงไวยากรณ์
ไม่ใช่ทุกไวยากรณ์ที่เป็น LL (k) -parsed ไวยากรณ์ที่ไม่มีบริบทเป็นของคลาส LL (1) หากไม่มีข้อขัดแย้งของประเภท FIRST-FIRST ในนั้น (การเรียกซ้ำด้านซ้าย - กรณีพิเศษความขัดแย้งดังกล่าว) และ FIRST-FOLLOW
บางครั้ง เป็นไปได้ที่จะแปลงไวยากรณ์ที่ไม่ใช่ LL (1) เพื่อให้กลายเป็น LL (1) การเปลี่ยนแปลงบางส่วน (ที่แม่นยำกว่าที่กล่าวถึงในหลักสูตร) แสดงไว้ด้านล่าง
การลบการเรียกซ้ำทางซ้าย
สมมติว่าเรามีกฎของแบบฟอร์ม (ต่อไปนี้ในหมวดนี้ ตัวพิมพ์ใหญ่ - สัญลักษณ์ที่ไม่ใช่เทอร์มินัล, ตัวพิมพ์เล็ก - สตริงของอักขระใด ๆ):
- เอ → เอ เอ| อา ข| … | อา k | ม | น | … | z
มันไม่ได้ให้การวิเคราะห์ที่ชัดเจน ดังนั้นควรเปลี่ยน
เป็นเรื่องง่ายที่จะแสดงว่ากฎนี้เทียบเท่ากับกฎคู่ต่อไปนี้:
- เอ → มบี | นบี | … | zบี
- ข → เอบี | ขบี | … | kบี | ε
แยกตัวประกอบด้านซ้าย
สาระสำคัญของขั้นตอนนี้คือการขจัดความคลุมเครือในการเลือกกฎสำหรับสัญลักษณ์ด้านซ้าย ในการทำเช่นนี้พบคำนำหน้าซ้ายทั่วไปและสิ่งที่อาจตามมาจะถูกใส่ลงในกฎใหม่ (ตัวอักษรตัวพิมพ์เล็ก - สตริงของอักขระใด ๆ)
ตัวอย่าง
- เอ → เอค | เอ df | เอ dg | ข
แปลงเป็น
- เอ → เอบี | ข
- ข → ค | dฉ | d g
ซึ่งจะกลายเป็น
- เอ → เอบี | ข
- ข → ค | dกับ
- C → ฉ | g
ตัวอย่างการแปลงไวยากรณ์
จี= ((S, A, B), (a, b, c), P, S)
- S → SAbB | เอ
- เอ → ab | aa | ε
- ข → ค | ε
การลบการเรียกซ้ำทางซ้ายสำหรับ S:
- S → AS 1
- S 1 → AbBS 1 | ε
แยกตัวประกอบด้านซ้ายสำหรับ A:
- A → aA 1 | ε
- A 1 → b | เอ
ไวยากรณ์สุดท้าย:
- S → AS 1
- S 1 → AbBS 1 | ε
- A → aA 1 | ε
- A 1 → b | เอ
- ข → ค | ε
สร้างก่อนและติดตาม
FIRST (α) โดยที่ α ∈ (N ∪ T) * คือชุดของเทอร์มินัลที่ α สามารถเริ่มต้นได้ ถ้า α ⇒ ε แล้ว ε ∈ FIRST (α) ดังนั้นค่าของ FOLLOW ( อา) สำหรับ nonterminal อา- ขั้วมากมายที่อาจปรากฏขึ้นทันทีหลังจาก อาในรูปแบบประโยคใด ๆ ถ้า อาสามารถเป็นอักขระขวาสุดในบางรูปแบบประโยค จากนั้นเครื่องหมาย $ สุดท้ายยังเป็นของ FOLLOW ( อา)
การคำนวณ FIRST
สำหรับขั้ว
- สำหรับเทอร์มินัลใด ๆ x, x ∈ ตู่, แรก ( x) = {x}
สำหรับไม่ใช่ขั้ว
- ถ้า Xเป็น nonterminal แล้วเราใส่ FIRST ( X) = {∅}
- หากมีกฎในไวยากรณ์ X→ ε จากนั้นเราเพิ่ม ε เป็น FIRST ( X)
- สำหรับทุก nonterminal Xและสำหรับกฎการอนุมานแต่ละข้อ X → Y 1 …Y k เพิ่มเป็น FIRST ( X) ของชุด FIRST ของสัญลักษณ์ทั้งหมดทางด้านขวามือของกฎจนถึงตัวแรกที่ ε ไม่ถูกอนุมาน รวมทั้ง
สำหรับโซ่
- สำหรับสตริงอักขระ X 1 …X k FIRST คือการต่ออักขระ FIRST ในสายโซ่จนถึงตัวแรกด้วย ε ∉ FIRST รวมทั้งอักขระนั้นด้วย
ตัวอย่าง
- S → AS 1
- S 1 → AbBS 1 | ε
- A → aA 1 | ε
- A 1 → b | เอ
- ข → ค | ε
nonterminals แรกในลำดับของการแก้ปัญหาการพึ่งพา:
- เฟิร์ส (ส) = (ก)
- แรก (A) = (a, ε)
- ครั้งแรก (A 1) = (b, a)
- ครั้งแรก (B) = (c, ε)
- แรก (S 1) = (a, b, ε)
ครั้งแรกสำหรับกฎการถอน:
- ครั้งแรก (aS 1) = (ก)
- ครั้งแรก (AbBS 1) = (a, b)
- ครั้งแรก (ε) = (ε)
- ครั้งแรก (aA 1) = (a)
- ครั้งแรก (ก) = (ก)
- ครั้งแรก (b) = (b)
- ครั้งแรก (c) = (c)
กำลังคำนวณ FOLLOW
การประเมินฟังก์ชัน FOLLOW สำหรับอักขระ X:
- ให้ FOLLOW (X) = (∅)
- ถ้า X เป็นสัจพจน์ของไวยากรณ์ ให้เพิ่ม $ token ใน FOLLOW
- สำหรับกฎของรูปแบบ A → αXβ ให้เพิ่ม FIRST (β) \ (ε) ลงใน FOLLOW (X) (X สามารถตามด้วยสัญลักษณ์ที่ β ขึ้นต้นด้วย)
- สำหรับกฎทั้งหมดของรูปแบบ A → αX และ A → αXβ ε ∈ FIRST (β) ให้เพิ่ม FOLLOW (A) เพื่อ FOLLOW (X) (นั่นคือ X สามารถตามด้วยสัญลักษณ์ทั้งหมดที่สามารถตามหลัง A ได้หากอยู่ในกฎเอาต์พุต , X อาจอยู่ทางด้านขวามือ)
- ทำซ้ำสองจุดก่อนหน้าให้นานที่สุดเพื่อเพิ่มอักขระลงในชุด
ตัวอย่าง
- S → AS 1
- S 1 → AbBS 1 | ε
- A → aA 1 | ε
- A 1 → b | เอ
- ข → ค | ε
ผลลัพธ์:
- ติดตาม (S) = ($)
- ติดตาม (S 1) = ($) (S 1 เป็นอักขระขวาสุดในกฎ S → aS 1)
- ติดตาม (A) = (b) (หลังจาก A ในกฎ S 1 → AbBS 1, b ตามมา)
- ติดตาม (A 1) = (b) (A 1 เป็นอักขระขวาสุดในกฎ A → aA 1 ดังนั้นให้เพิ่ม FOLLOW (A) เพื่อติดตาม (A 1))
- ติดตาม (B) = (a, b, $) (เพิ่ม FIRST (S 1) \ (ε) (ตามมาจากกฎ S 1 → AbBS 1), FOLLOW (S 1) (เนื่องจากมี S 1 → ε))
วาดรูปโต๊ะ
ในตาราง เอ็มสำหรับคู่ที่ไม่ใช่เทอร์มินอล-เทอร์มินอล (ในเซลล์ เอ็ม[อา, เอ]) ระบุกฎตามความจำเป็นในการพับคำที่ป้อน ตารางถูกกรอกดังนี้: สำหรับแต่ละกฎการอนุมานสำหรับไวยากรณ์ที่กำหนด A → α (โดยที่ α หมายถึงลูกโซ่ทางด้านขวาของกฎ) การดำเนินการต่อไปนี้:
- สำหรับแต่ละเทอร์มินัล เอ∈ FIRST (α) เพิ่มกฎ อา → α ถึง เอ็ม[อา, เอ]
- ถ้า ε ∈ FIRST (α) ดังนั้นสำหรับแต่ละ ข∈ ติดตาม ( อา) เพิ่ม อา → α ถึง เอ็ม[อา, ข]
- ε ∈ FIRST (α) และ $ ∈ FOLLOW ( อา), เพิ่ม อา → α ถึง เอ็ม[อา, $]
- เซลล์ว่างทั้งหมดเป็นข้อผิดพลาดในการป้อนคำ
ตัวอย่าง
สร้างตารางไวยากรณ์
- S → AS 1
- S 1 → AbBS 1 | ε
- A → aA 1 | ε
- A 1 → b | เอ
- ข → ค | ε
ผลลัพธ์:
| เอ | ข | ค | $ | |
|---|---|---|---|---|
| ส | S → AS 1 (กฎข้อแรก การอนุมาน S → เป็น 1, a ∈ FIRST (aS 1)) | ข้อผิดพลาด (กฎข้อที่สี่) | ข้อผิดพลาด (กฎข้อที่สี่) | ข้อผิดพลาด (กฎข้อที่สี่) |
| S 1 | S 1 → AbBS 1 (กฎข้อแรก เอาต์พุต S 1 → AbBS 1, a ∈ FIRST (AbBS 1)) | S 1 → AbBS 1 (กฎข้อแรก เอาต์พุต S 1 → AbBS 1, b ∈ FIRST (AbBS 1)) | ข้อผิดพลาด (กฎข้อที่สี่) | S 1 → ε (กฎข้อที่สาม การอนุมาน S 1 → ε, ε ∈ FIRST (ε), $ ∈ FOLLOW (S 1)) |
| อา | A → aA 1 (กฎข้อแรก การอนุมาน A → aA 1, a ∈ FIRST (aA 1)) | A → ε (กฎข้อที่สอง ข้อสรุป A 1 → ε, b ∈ FOLLOW (A 1)) | ข้อผิดพลาด (กฎข้อที่สี่) | ข้อผิดพลาด (กฎข้อที่สี่) |
| A 1 | A 1 → a (กฎข้อแรก สรุป A 1 → a, a ∈ FIRST (a)) | A 1 → b (กฎข้อแรก สรุป A 1 → b, b ∈ FIRST (b)) | ข้อผิดพลาด (กฎข้อที่สี่) | ข้อผิดพลาด (กฎข้อที่สี่) |
| บี | B → ε | B → ε (กฎข้อที่สอง การอนุมาน B → ε, a ∈ FOLLOW (B)) | ข → ค (กฎข้อแรก การอนุมาน B → c, c ∈ FIRST (c)) | B → ε (กฎข้อที่สาม การอนุมาน B → ε, $ ∈ FOLLOW (B)) |
การแยกสตริง
ขั้นตอนการแยกวิเคราะห์สตริงนั้นค่อนข้างตรงไปตรงมา สาระสำคัญมีดังนี้: ในแต่ละขั้นตอนจะอ่านอักขระบน วี คห่วงโซ่อินพุต
- ถ้า วี- สัญลักษณ์เทอร์มินัล
- ถ้า วีประจวบกับ กับแล้วทั้งสองก็พังทลาย กะเกิดขึ้น
- ถ้า วีไม่ตรงกัน กับจากนั้นจะส่งสัญญาณข้อผิดพลาดในการแยกวิเคราะห์
- ถ้า วี- สัญลักษณ์ที่ไม่ใช่เทอร์มินัล คกลับไปที่จุดเริ่มต้นของบรรทัดแทน วีกลับไปที่สแต็ก ส่วนขวากฎที่นำมาจากเซลล์ตาราง เอ็ม[วี, ค]
กระบวนการจะสิ้นสุดลงเมื่อทั้งเส้นและสแต็กถึงเครื่องหมายต่อท้าย (#)
ตัวอย่าง
ลองแยกบรรทัด "aabbaabcb":
| ซ้อนกัน | ไลน์ | หนังบู๊ |
|---|---|---|
| ส# | เอ abbaabcb $ | S → AS 1 |
| เอเอส 1 # | เอ abbaabcb $ | กะ |
| S 1# | เอ bbaabcb $ | S 1 → AbBS 1 |
| อาบีบีเอส 1 # | เอ bbaabcb $ | A → aA 1 |
| เอ A 1 bBS 1 # | เอ bbaabcb $ | กะ |
| A 1บีบีเอส 1 # | ข baabb $ | A 1 → b |
| ขบีบีเอส 1 # | ข baabb $ | กะ |
| ขบี 1 # | ข aabcb $ | กะ |
| บีเอส 1 # | เอ abcb $ | B → ε |
| S 1# | เอ abcb $ | S 1 → AbBS 1 |
| อาบีบีเอส 1 # | เอ abcb $ | A → aA 1 |
| อาบีบีเอส 1 # | เอ abcb $ | A → aA 1 |
| เอ A 1 bBS 1 # | เอ abcb $ | กะ |
| A 1บีบีเอส 1 # | เอ bcb $ | A 1 → a |
| เอบีบีเอส 1 # | เอ bcb $ | กะ |
| ขบี 1 # | ข cb $ | กะ |
| บีเอส 1 # | คข $ | ข → ค |
| คเอส 1 # | คข $ | กะ |
| S 1# | ข$ | S 1 → AbBS 1 |
| อาบีบีเอส 1 # | ข$ | A → ε |
| ขบี 1 # | ข$ | กะ |
| บีเอส 1 # | $ | B → ε |
| S 1# | $ | S 1 → ε |
| # | $ | พร้อม |
การสร้างเครื่องวิเคราะห์ LR (k)
การคำนวณ k ใน LR (k)
ไม่มีอัลกอริธึมที่อนุญาตให้ ในกรณีทั่วไป คำนวณ k สำหรับไวยากรณ์ตามอำเภอใจ โดยปกติแล้ว มันคุ้มค่าที่จะลองสร้างตัวแยกวิเคราะห์ LR (1) หากมีการดำเนินการไม่เกินหนึ่งชุดสำหรับแต่ละชุด (Shift, Reduce หรือ Accept) ไวยากรณ์จะเป็น LR (0) หากเมื่อสร้าง LR (1) -analyzer มีความขัดแย้งและการชนกัน ไวยากรณ์นี้ไม่ใช่ LR (1) และคุ้มค่าที่จะลองสร้าง LR (2) หากไม่สามารถสร้างได้ ก็ให้ใช้ LR (3) เป็นต้น
จบไวยกรณ์
มาเพิ่มกฎใหม่ S "→ S และทำให้ S" เป็นสัจพจน์ของไวยากรณ์ กฎเพิ่มเติมนี้จำเป็นในการพิจารณาว่าเมื่อใดที่เครื่องวิเคราะห์ถูกปิดและพิกัดความเผื่อของขั้นอินพุต การรับเข้าเรียนจะเกิดขึ้นก็ต่อเมื่อเป็นไปได้ที่จะทำการบิดตามกฎ S → S "
การสร้างระบบบัญญัติของชุด LR (1) ที่ยอมรับได้ -สถานการณ์
ในตอนเริ่มต้น มีชุด I 0 ที่มีการกำหนดค่าตัววิเคราะห์ S "→ .S, $ ถัดไป การดำเนินการปิดจะถูกนำไปใช้กับการกำหนดค่านี้จนกว่าจะไม่มีการเพิ่มการกำหนดค่าใหม่อันเป็นผลมาจากแอปพลิเคชันอีกต่อไป ถัดไป เปลี่ยนเป็นใหม่ ชุดถูกสร้างขึ้นโดยเลื่อนจุดไปทางขวาหนึ่งอักขระ (การเปลี่ยนทำตามอักขระที่ยืนอยู่หลังจุดก่อนการเปลี่ยนและก่อนหน้าหลังจากการเปลี่ยน) และการกำหนดค่าเหล่านั้นจะถูกเพิ่มเข้าไปในชุดเหล่านี้ที่ได้รับจาก ที่มีอยู่ด้วยวิธีนี้ สำหรับพวกเขา การดำเนินการปิดยังถูกนำไปใช้และกระบวนการทั้งหมดจะถูกทำซ้ำจนกว่าชุดใหม่จะหยุดปรากฏขึ้น
ตัวอย่าง
สร้างระบบบัญญัติของชุดของสถานการณ์ LR (1) ที่ยอมรับได้สำหรับไวยากรณ์ที่ระบุ:
- ส "→ ส
- S → ABA
- A → Aa | ε
- B → cBc | d
สารละลาย:
- สร้างการปิดสำหรับการกำหนดค่า S "→ .S, $:
- S → .ABA, $
- สำหรับการกำหนดค่าผลลัพธ์ (S → .ABA, $) เรายังสร้างการปิด:
- A → .Aa, c
- A → .Aa, d
- A →., C
- ก →., ด
- สำหรับการกำหนดค่าผลลัพธ์ (A → .Aa, c; A → .Aa, d) เรายังสร้างการปิด:
- A → .Aa, a
- เอ →., เอ
- ไม่สามารถสร้างการกำหนดค่าเพิ่มเติมในสถานะ I 0 ได้ - มีการสร้างการปิด
- จาก I 0 คุณสามารถทำการเปลี่ยนผ่าน S และ A และรับชุดการกำหนดค่า I 1 และ I 2 ซึ่งประกอบด้วยองค์ประกอบต่อไปนี้:
- ฉัน 1 = (S "→ S., $)
- ฉัน 2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a)
- ฉัน 1 ไม่ต้องปิด
- มาสร้างการปิดกัน I 2:
- B → .cBc, a
- B → .cBc, $
- B → .d, a
- B → .d, $
- ชุดอื่นๆ ทั้งหมดถูกสร้างขึ้นในทำนองเดียวกัน
การสร้างตาราง parser
ขั้นตอนสุดท้ายในการสร้างเครื่องวิเคราะห์ LR (1) คือการสร้างตาราง หนังบู๊และ ไปที่... ตาราง หนังบู๊ถูกสร้างขึ้นสำหรับอักขระของบรรทัดอินพุต นั่นคือ สำหรับเทอร์มินัลและเครื่องหมายท้ายบรรทัด $ ตาราง ไปที่สร้างขึ้นสำหรับสัญลักษณ์ไวยากรณ์ กล่าวคือ สำหรับเทอร์มินัลและไม่ใช่เทอร์มินัล
การสร้างโต๊ะ Goto
ตาราง Goto แสดงสถานะที่จะไปเมื่อพบสัญลักษณ์ไวยากรณ์ถัดไป ดังนั้นหากในระบบชุดบัญญัติมีการเปลี่ยนจาก ฉันวี ฉัน jโดยตัวอักษร A จากนั้นใน Goto ( ผม ผม, A) เราใส่สถานะ ผม เจ... หลังจากกรอกตารางแล้ว เราคิดว่าในเซลล์ว่างทั้งหมด ไปที่ ( ผม ผม, A) = ข้อผิดพลาด
การสร้างตารางการดำเนินการ
- หากมีการเปลี่ยนแปลงผ่านเทอร์มินัล a จากสถานะ I ฉัน เป็นสถานะ I j ดังนั้น Action (I i, a) = Shift (I j)
- หาก A ≠ S "คือการกำหนดค่า A → α., A ดังนั้น Action (I i, a) = ลด (A → α)
- สำหรับสถานะ I ผม ซึ่งมีการกำหนดค่า S "→ S. , $, Action (I i, $) = ยอมรับ
- สำหรับเซลล์ว่างทั้งหมด Action (I i, a) = Error
ตัวอย่าง
สร้างตาราง Action และ Goto สำหรับไวยากรณ์
- ส "→ ส
- S → ABA
- A → Aa | ε
- B → cBc | d
สารละลาย:
| หนังบู๊ | ไปที่ | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| เอ | ค | d | $ | ส | เอส " | อา | บี | เอ | ค | d | |
| ฉัน 0 | ลด (A → ε) | ลด (A → ε) | ลด (A → ε) | ฉัน 1 | ฉัน2 | ||||||
| ฉัน 1 | ยอมรับ | ||||||||||
| ฉัน2 | กะ (I 6) | กะ (I 4) | กะ (I 5) | ฉัน 3 | ฉัน6 | ฉัน 4 | ฉัน 5 | ||||
| ฉัน 3 | ลด (A → ε) | ลด (A → ε) | ฉัน13 | ||||||||
| ฉัน 4 | กะ (I 8) | กะ (I 9) | ฉัน7 | ฉัน8 | ฉัน 9 | ||||||
| ฉัน 5 | ลด (B → ง) | ลด (B → ง) | |||||||||
| ฉัน6 | ลด (A → Aa) | ลด (A → Aa) | ลด (A → Aa) | ||||||||
| ฉัน7 | กะ (I 10) | ฉัน 10 | |||||||||
| ฉัน8 | กะ (I 8) | กะ (I 9) | ฉัน 11 | ฉัน8 | ฉัน 9 | ||||||
| ฉัน 9 | ลด (B → ง) | ||||||||||
| ฉัน 10 | ลด (B → cBc) | ลด (B → cBc) | |||||||||
| ฉัน 11 | กะ (I 12) | ฉัน12 | |||||||||
| ฉัน12 | ลด (B → cBc) | ||||||||||
| ฉัน13 | กะ (I 14) | ลด (S → ABA) | ฉัน14 | ||||||||
| ฉัน14 | ลด (A → Aa) | ลด (A → Aa) | |||||||||
แยกโซ่
อักขระบนสุดจะอ่านในแต่ละขั้นตอน วีจาก parser stack และใช้ตัวอักษรสุดขั้ว คห่วงโซ่อินพุต
ถ้าตารางปฏิบัติการที่สี่แยก วีและ คตั้งอยู่:
- กะ ( ฉัน k) จากนั้น กับแล้วก็ ฉัน k... โดยที่ คจะถูกลบออกจากสตริง
- ลด ( อา → ยู) จากนั้นสัญลักษณ์เทอร์มินัลและไม่ใช่เทอร์มินัลทั้งหมดที่ประกอบเป็นสายโซ่จะถูกลบออกจากด้านบนของสแต็ก ยู, หลังจากที่รัฐมอง ฉันเหลืออยู่ด้านบน ตามตารางการเปลี่ยนแปลงที่สี่แยก ฉันและ อาพบสถานะต่อไป คือ... จากนั้น A จะถูกผลักไปที่สแต็กแล้ว คือ... เส้นยังคงไม่เปลี่ยนแปลง
- ยอมรับ จากนั้นการแยกวิเคราะห์สิ้นสุดลง
- ความว่างเปล่าคือความผิดพลาด
ตัวอย่าง
ลองแยกสตริง aaaccdcc:
| ซ้อนกัน | เส้น | หนังบู๊ |
| ฉัน 0 | เอ aaccdcc $ | ลด (A → ε) ไปที่ I 2 |
| ฉัน 0 ฉัน2 | เอ aaccdcc $ | กะ (I 6) |
| ฉัน 0 A ฉัน 2 a ฉัน6 | เอ accdcc $ | ลด (A → Aa) ไปที่ I 2 |
| ฉัน 0 ฉัน2 | เอ accdcc $ | กะ (I 6) |
| ฉัน 0 A ฉัน 2 a ฉัน6 | เอ ccdcc $ | ลด (A → Aa) ไปที่ I 2 |
| ฉัน 0 ฉัน2 | เอ ccdcc $ | กะ (I 6) |
| ฉัน 0 A ฉัน 2 a ฉัน6 | ค cdcc $ | ลด (A → Aa) ไปที่ I 2 |
| ฉัน 0 ฉัน2 | ค cdcc $ | กะ (I 4) |
| ฉัน 0 A ฉัน 2 c ฉัน 4 | คดีซีซี $ | กะ (I 8) |
| ฉัน 0 A ฉัน 2 c ฉัน 4 c ฉัน8 | dซีซี $ | กะ (I 9) |
| ฉัน 0 A ฉัน 2 c ฉัน 4 c ฉัน 8 วัน ฉัน 9 | คค $ | ลด (B → d) ไปที่ I 11 |
| ฉัน 0 A ฉัน 2 c ฉัน 4 c ฉัน 8 B ฉัน 11 | คค $ | กะ (I 12) |
| ฉัน 0 A ฉัน 2 c ฉัน 4 c ฉัน 8 B ฉัน 11 c ฉัน12 | ค$ | ลด (B → cBc) ไปที่ I 7 |
| ฉัน 0 A ฉัน 2 c ฉัน 4 B ฉัน7 | ค$ | กะ (I 10) |
| ฉัน 0 A ฉัน 2 c ฉัน 4 B ฉัน 7 c ฉัน 10 | $ | ลด (B → cBc) ไปที่ I 3 |
| ฉัน 0 A ฉัน 2 B ฉัน 3 | $ | ลด (A → ε) ไปที่ I 13 |
| ฉัน 0 A ฉัน 2 B ฉัน 3 A ฉัน13 | $ | ลด (S → ABA) ไปที่ I 1 |
| ฉัน 0 ส ฉัน 1 | $ | ยอมรับ |
การแปลนิพจน์เลขคณิต (อัลกอริทึม Seti-Ullman)
บันทึก.รหัสถูกสร้างขึ้นสไตล์คนชอบสุนัขโมโตโรล่าเช่น
ฝั่ง Arg1, Arg2
หมายถึง
Arg2 = Arg1 กับ Arg2
สร้างต้นไม้
ทรีถูกสร้างขึ้นตามปกติสำหรับนิพจน์เลขคณิต: ที่รูท การดำเนินการที่มีลำดับความสำคัญต่ำสุด ตามด้วยการดำเนินการที่มีลำดับความสำคัญสูงกว่าเล็กน้อย และอื่นๆ วงเล็บมีลำดับความสำคัญสูงสุด หากมีการดำเนินการหลายอย่างที่มีลำดับความสำคัญเท่ากัน - a op b op c ต้นไม้จะถูกสร้างขึ้นสำหรับนิพจน์ (a op b) op c
ตัวอย่าง
สร้างต้นไม้สำหรับนิพจน์ a + b / (d + a - b × c / d - e) + c × d
สารละลาย:มาเขียนนิพจน์ในรูป
((a) + ((b) / ((((d) + (a)) - ((b) × (c)) / (d)) - (e)))) + ((c) × ( ง))
จากนั้น ที่รูทของทรีย่อยแต่ละอันจะมีการดำเนินการ และนิพจน์ในวงเล็บทางซ้ายและขวาของทรีย่อยจะเป็นทรีย่อย ตัวอย่างเช่น สำหรับนิพจน์ย่อย ((b) × (c)) / (d) ที่รูทของทรีย่อยที่เกี่ยวข้องจะเป็นการดำเนินการ "/" และทรีย่อยของมันจะเป็นนิพจน์ย่อย ((b) × (c)) และ (ง)
แผนผังต้นไม้ (คำนวณจำนวนรีจิสเตอร์)
- หากจุดยอดเป็นใบไม้ด้านซ้าย (นั่นคือ ตัวแปร) ให้ทำเครื่องหมายด้วยศูนย์
- หากจุดยอดเป็นใบไม้ด้านขวา ให้ทำเครื่องหมายด้วยหนึ่ง
- หากเราทำเครื่องหมายทรีย่อยทั้งสองสำหรับจุดยอด เราจะทำเครื่องหมายดังนี้:
- หากทรีย่อยด้านซ้ายและขวาถูกทำเครื่องหมาย ตัวเลขต่างๆแล้วเราเลือกที่ใหญ่ที่สุดของพวกเขา
- หากทรีย่อยด้านซ้ายและขวาถูกทำเครื่องหมาย เลขเดียวกัน, จากนั้นทรีย่อยนี้สัมพันธ์กับจำนวนที่มากกว่าที่ทรีย่อยถูกทำเครื่องหมาย
| เครื่องหมายใบไม้ | เค้าโครงของต้นไม้ที่มีทรีย่อยเดียวกัน | ทรีย่อยด้านซ้ายมีเครื่องหมายจำนวนมาก | ทรีย่อยด้านขวามีเครื่องหมายจำนวนมาก |
|---|---|---|---|
 |  |  |  |
รหัสถูกสร้างขึ้นโดยการสำรวจต้นไม้จากล่างขึ้นบนดังนี้:
1. สำหรับจุดยอดที่มีป้ายกำกับ 0 จะไม่มีการสร้างรหัส
2. ถ้าด้านบนเป็น leaf X พร้อมป้าย 1 และลงทะเบียน R ผมจากนั้นรหัสจะถูกจับคู่กับมัน
MOVE X, รี
3. หากจุดยอดอยู่ภายในด้วยรีจิสเตอร์R ผมและลูกด้านซ้ายของมันคือ leaf X ที่มีป้ายกำกับ 0 จากนั้นจะสอดคล้องกับรหัส
<Код правого поддерева>Op X, รี
4. ถ้าทรีย่อยของจุดยอดที่มีรีจิสเตอร์R ผม- ไม่ใบไม้และฉลากของจุดยอดด้านขวามากกว่าหรือเท่ากับฉลากด้านซ้าย (ซึ่งรีจิสเตอร์ Rj, j = i + 1) จากนั้นจุดยอดจะสอดคล้องกับรหัส
<Код ขวาทรีย่อย><Код ซ้ายทรีย่อย> Op Rj, Ri
5. ถ้าทรีย่อยของจุดยอดที่มีการลงทะเบียนR ผม- ไม่ใช่ใบและฉลากของจุดยอดด้านขวา (ซึ่งรีจิสเตอร์ Rj, j = i + 1) น้อยกว่าป้ายกำกับด้านซ้ายจากนั้นจุดยอดจะสอดคล้องกับรหัส
การกระจายของการลงทะเบียนจะแสดงในกราฟทางด้านขวา รหัสที่สร้าง:
ย้าย d, R0; R0 = d ย้าย c, R1; R1 = c MUL b, R1; R1 = (b × c) DIV R1, R0; R0 = (b × c) / d ย้าย a, R1; R1 = a เพิ่ม d, R1; R1 = a + d SUB R1, R0; R0 = (a + d) - ((b × c) / d) ย้าย e, R1; R1 = e SUB R0, R1; R1 = ((a + d) - ((b × c) / d)) - e ย้าย R1, R0; R0 = ((a + d) - ((b × c) / d)) - e DIV b, R0; R0 = b / (((a + d) - ((b × c) / d)) - e) เพิ่ม a, R0; R0 = a + (b / (((a + d) - ((b × c) / d )) - จ)) ย้าย d, R1; R1 = d MUL c, R1; R1 = c × d เพิ่ม R0, R1; R1 = (a + (b / (((a + d)) - ((b × c ) / d)) - e))) + (c × d) ย้าย R1, R0; R0 = (a + (b / (((a + d) - ((b × c) / d)) - e) )) + (ค × ง)
การแปลนิพจน์บูลีน
ส่วนนี้แสดงวิธีสร้างโค้ดสำหรับการประเมินนิพจน์บูลีนแบบสันหลัง เป็นผลมาจากการทำงานของอัลกอริทึม ได้ชิ้นส่วนของโค้ดซึ่งใช้การดำเนินการ TST, BNE, BEQ คำนวณนิพจน์เชิงตรรกะโดยข้ามไปที่ป้ายกำกับ: TRUELAB หรือ FALSELAB
สร้างต้นไม้
ทรีนิพจน์เชิงตรรกะสะท้อนถึงลำดับของการคำนวณตามลำดับความสำคัญของการดำเนินการ นั่นคือ เพื่อคำนวณค่าของโหนดบางโหนดของทรี (ซึ่งเป็นการดำเนินการจากตัวถูกดำเนินการสองตัวที่เป็นทรีย่อยของโหนด) เราต้อง ขั้นแรกให้คำนวณค่าของทรีย่อยของมัน
ลำดับความสำคัญของการดำเนินงาน: NOT มีลำดับความสำคัญสูงสุด ตามด้วย AND แล้วตามด้วย OR ถ้านิพจน์ใช้ other การดำเนินการทางตรรกะจากนั้นจะต้องแสดงในแง่ของทั้งสามในลักษณะที่แน่นอน (โดยปกติไม่มีการดำเนินการอื่นและไม่จำเป็นต้องแปลงนิพจน์) การเชื่อมโยงของการดำเนินการที่มีลำดับความสำคัญเท่ากันคือจากซ้ายไปขวา นั่นคือ A และ B และ C จะถือว่าเป็น (A และ B) และ C
ตัวอย่าง
สร้างแผนผังสำหรับนิพจน์บูลีน ไม่ใช่ A หรือ B และ C และ (B หรือไม่ใช่ C)
สารละลาย:ดูแผนภาพทางด้านขวา
สำหรับแต่ละโหนดของต้นไม้ แอตทริบิวต์ 4 รายการจะถูกคำนวณ:
- หมายเลขโหนด
- เลเบลที่จะไปถ้านิพจน์ในโหนดเป็นเท็จ (false label, fl)
- เลเบลจะไปที่ไหนถ้านิพจน์ในโหนดเป็นจริง (true label, tl)
- ลงชื่อ (ดูรายละเอียดด้านล่าง)
จุดยอดมีหมายเลขในลำดับใด ๆ เงื่อนไขเดียวคือเอกลักษณ์ของตัวเลขของโหนด
ต้นไม้มีการทำเครื่องหมายดังนี้:
- Fl ระบุจำนวนจุดยอดที่เกิดการเปลี่ยนแปลงหรือ falselab หากจุดยอดนี้เป็นเท็จ
- tl ระบุจำนวนจุดยอดที่ทำการเปลี่ยนแปลงหรือ truelab หากจุดยอดนี้เป็นจริง
เครื่องหมายระบุว่าเมื่อใดควรหยุดการคำนวณทรีย่อยปัจจุบัน
สำหรับรากของต้นไม้ fl = falselab, tl = truelab, sign = false
ทางนี้:
ตัวอย่าง
ทำเครื่องหมายต้นไม้ที่สร้างขึ้นสำหรับนิพจน์บูลีน ไม่ใช่ A หรือ B และ C และ (B หรือไม่ใช่ C)
กำลังสร้างรหัส
คำสั่งเครื่องที่ใช้ในรหัสที่สร้างขึ้น:
- TST
- BNE - กระโดดขึ้นป้ายถ้าไม่ได้ตั้งค่าสถานะ นั่นคือ ตรวจสอบเงื่อนไขโดยใช้ TST แท้จริงแล้ว
- BEQ - ข้ามไปที่ฉลากหากตั้งค่าสถานะ นั่นคือ ตรวจสอบเงื่อนไขโดยใช้ TST เท็จ
รหัสถูกสร้างขึ้นดังนี้:
- ต้นไม้ถูกข้ามจากรูท สำหรับ AND และ OR ทรีย่อยทางซ้ายจะถูกข้ามก่อน จากนั้นไปทางขวา
- สำหรับแต่ละจุดยอดที่ผ่าน จะมีการพิมพ์หมายเลข (ฉลาก)
- สำหรับแผ่น A (หมายเลข, tl, fl, เครื่องหมาย) TST A จะถูกพิมพ์
- ถ้า sign == true, BNE tl จะถูกพิมพ์
- ถ้าเครื่องหมาย == เท็จ BEQ fl จะถูกพิมพ์
ตัวอย่าง
สำหรับนิพจน์ข้างต้น โค้ดต่อไปนี้จะถูกสร้างขึ้น:
1: 2: 4: TST A BEQ TRUELAB 3: 5: 7: TST B BEQ FALSELAB 8: TST C BEQ FALSELAB 6: 9: TST B BNE TRUELAB 10:11: TST C BNE FALSELAB TRUELAB: FALSELAB:
วิธีการจับคู่รูปแบบ
แนวคิดเบื้องหลังวิธีการคือสามารถสร้างโค้ดสำหรับส่วนเดียวกันของโปรแกรมได้ วิธีทางที่แตกต่างและด้วยเหตุนี้ จึงเป็นไปได้ที่จะบรรลุการปรับให้เหมาะสมสำหรับพารามิเตอร์ใดพารามิเตอร์หนึ่ง
การกำหนดปัญหา
มีตัวอย่างมากมาย โดยแต่ละตัวอย่างจะมีส่วนที่กำหนดไว้ของการแสดงระดับกลางที่ใช้ได้ น้ำหนักและโค้ดที่สร้างขึ้น มีแผนผังแสดงระดับกลาง ซึ่งเป็นส่วนย่อยของโปรแกรมที่คุณต้องการสร้างโค้ด เป้าหมายคือการสร้างความครอบคลุมของแผนผังตัวแทนระดับกลางกับตัวอย่าง เพื่อให้น้ำหนักรวมของกลุ่มตัวอย่างน้อยที่สุด
รูปแบบคือคำแนะนำในการประกอบและแยกวิเคราะห์ต้นไม้ที่สอดคล้องกับพวกมัน สำหรับแต่ละตัวอย่าง จะทราบเวลาดำเนินการ (เป็นขีด) ด้วยความช่วยเหลือของพวกเขา เราจะสร้างโค้ดที่เหมาะสมที่สุด (ในแง่ของเวลาดำเนินการ)
ตัวอย่างตัวอย่าง
การสร้างตัวแทนระดับกลาง
อันดับแรก เราสร้าง parse tree สำหรับนิพจน์ทั้งหมด
การสร้างความคุ้มครอง
ตอนนี้ สำหรับแต่ละจุดยอด (เราวนซ้ำตามลำดับจากใบไม้ถึงราก) เราจะสร้างรหัสที่เหมาะสมที่สุดสำหรับทรีย่อยของมัน ในการทำเช่นนี้ เพียงวนซ้ำทุกรูปแบบที่เกี่ยวข้องที่จุดยอดนี้ เวลาดำเนินการเมื่อใช้ตัวอย่างเฉพาะจะเป็นผลรวมของเวลาที่ใช้ในการคำนวณอาร์กิวเมนต์ (และเราทราบรหัสที่เหมาะสมที่สุดในการคำนวณเนื่องจากลำดับการข้ามต้นไม้) และเวลาดำเนินการของตัวอย่างเอง จากตัวเลือกที่ได้รับทั้งหมด เราเลือกตัวเลือกที่ดีที่สุด - มันจะเป็นรหัสที่เหมาะสมที่สุดสำหรับทรีย่อยของจุดสุดยอดนี้ ที่รากของต้นไม้ เราได้รับโค้ดที่เหมาะสมที่สุดสำหรับนิพจน์ทั้งหมด
กำลังสร้างรหัส
ไม่จำเป็นต้องเขียนรหัสสำหรับจุดยอดทั้งหมด - เพียงพอที่จะเขียนขั้นต่ำ เวลาที่ต้องการและตัวอย่างการใช้งาน ส่วนที่เหลือสามารถกู้คืนได้ง่าย
เรามีทะเบียนจำนวนไม่สิ้นสุดในงานเหล่านี้ ดังนั้นทุกครั้งที่คุณสามารถใช้การลงทะเบียนใหม่ได้
การสร้าง RT จาก DFA
การสร้าง NFA โดยใช้ไวยากรณ์เชิงเส้นตรง
ลดไวยกรณ์
ในการแปลงไวยากรณ์ CS โดยพลการเป็นรูปแบบย่อ คุณต้องดำเนินการขั้นตอนต่อไปนี้:
- ลบสัญลักษณ์ที่เป็นหมันทั้งหมด
- ลบอักขระที่ไม่สามารถเข้าถึงได้ทั้งหมด
การลบสัญลักษณ์ที่ไร้ประโยชน์
ทางเข้า: KS-ไวยากรณ์ G = (T, N, P, S)
ทางออก: KS-grammar G '= (T, N', P ', S) ไม่มีสัญลักษณ์ปลอดเชื้อ ซึ่ง L (G) = L (G')
วิธี:
สร้างชุดซ้ำ N 0, N 1, ...
- ยังไม่มีข้อความ 0 = ∅ ผม = 1
- ไม่มีฉัน = (A | (A → α) ∈ P และ α ∈ (N i - 1 ∪ T) *) ∪ N i-1
- ถ้า N i ≠ N i - 1 แล้ว i = i + 1 และไปที่ขั้นตอนที่ 2 มิฉะนั้น N ’= N i; P 'ประกอบด้วยกฎของชุด P ที่มีเฉพาะสัญลักษณ์จาก N' ∪ T; G '= (T, N', P ', S)
คำนิยาม:สัญลักษณ์ x ∈ (T ∪ N) เรียกว่าไม่สามารถเข้าถึงได้ในไวยากรณ์ G = (T, N, P, S) หากไม่ปรากฏในรูปแบบประโยคใด ๆ ของไวยากรณ์นี้
ตัวอย่าง
ลบอักขระที่ไม่มีประโยชน์ออกจากไวยากรณ์ G ((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)
- S → AcDe | CaDbCe | SaCa | aCb | dFg
- A → SeAd | cSA
- B → CaBd | aDBc | BSCf | bfg
- C → Ebd | Seb | aAc | cfF
- ด → fCE | ac | dEdAS | ε
- E → ESacD | aec | เอฟฟ
สารละลาย
- ยังไม่มีข้อความ 0 = ∅
- N 1 = (B (B → bfg), D (D → ac), E (E → aec))
- N 2 = (B, D, E, C (C → Ebd))
- N 3 = (B, D, E, C, S (S → aCb))
- N 4 = (B, D, E, C, S) = N 3
G "((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)
- S → CaDbCe | SaCa | aCb
- B → CaBd | aDBc | BSCf | bfg
- C → Ebd | เซบ
- ด → fCE | ac | ε
- E → ESacD | เออีซี
การลบอักขระที่ไม่สามารถเข้าถึงได้
ทางเข้า: KS-ไวยากรณ์ G = (T, N, P, S)
ทางออก: CS-grammar G '= (T', N ', P', S) ไม่มีอักขระที่ไม่สามารถเข้าถึงได้ ซึ่ง L (G) = L (G ')
วิธี:
- วี 0 = (ส); ผม = 1
- V i = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P และ A ∈ V i - 1) ∪ V i-1.
- ถ้า V i ≠ V i - 1 แล้ว i = i + 1 และไปที่ขั้นตอนที่ 2 มิฉะนั้น N ’= V i ∩ N; T '= V ฉัน ∩ T; P 'ประกอบด้วยกฎของชุด P ที่มีเฉพาะสัญลักษณ์จาก V i; G '= (T', N ', P', S)
คำนิยาม:กล่าวกันว่า CS-grammar G จะลดลงหากไม่มีสัญลักษณ์ที่ไม่สามารถบรรลุได้และเป็นหมัน
ตัวอย่าง
ลบอักขระที่ไม่สามารถเข้าถึงได้ออกจากไวยากรณ์ G "((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)
- S → CaDbCe | SaCa | aCb
- B → CaBd | aDBc | BSCf | bfg
- C → Ebd | เซบ
- ด → fCE | ac | ε
- E → ESacD | เออีซี
สารละลาย
- วี 0 = (ส)
- V 1 = (S, C (S → CaDbCe), D (S → CaDbCe), a (S → CaDbCe), b (S → CaDbCe), e (S → CaDbCe))
- V 2 = (S, C, D, a, b, e, E (C → Ebd), d (C → Ebd), f (D → fCE))
- V 3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD))
- V 4 = (S, C, D, E, a, b, d, e, f, c) = V 3
G "" ((C, D, E, S), (a, b, c, d, e, f), P "", S)
- S → CaDbCe | SaCa | aCb
- C → Ebd | เซบ
- ด → fCE | ac | ε
- E → ESacD | เออีซี