การออกแบบคอมไพเลอร์ - ตัวแยกวิเคราะห์ด้านล่าง

การแยกวิเคราะห์จากล่างขึ้นบนเริ่มต้นจากโหนดใบของต้นไม้และทำงานในทิศทางขึ้นไปจนถึงโหนดราก ที่นี่เราเริ่มจากประโยคจากนั้นใช้กฎการผลิตในลักษณะย้อนกลับเพื่อไปถึงสัญลักษณ์เริ่มต้น ภาพที่ให้ไว้ด้านล่างแสดงให้เห็นถึงตัวแยกวิเคราะห์จากล่างขึ้นบนที่มีอยู่

Shift- ลดการแยกวิเคราะห์

การแยกวิเคราะห์ลดกะใช้สองขั้นตอนที่ไม่ซ้ำกันสำหรับการแยกวิเคราะห์จากล่างขึ้นบน ขั้นตอนเหล่านี้เรียกว่า shift-step และ reduction-step

  • Shift step: ขั้นตอนการเลื่อนหมายถึงความก้าวหน้าของตัวชี้อินพุตไปยังสัญลักษณ์อินพุตถัดไปซึ่งเรียกว่าสัญลักษณ์เลื่อน สัญลักษณ์นี้ถูกผลักลงบนสแต็ก สัญลักษณ์ที่เลื่อนจะถือว่าเป็นโหนดเดียวของโครงสร้างการแยกวิเคราะห์

  • Reduce step: เมื่อตัวแยกวิเคราะห์พบกฎไวยากรณ์ (RHS) ที่สมบูรณ์และแทนที่เป็น (LHS) จะเรียกว่าลดขั้นตอน กรณีนี้เกิดขึ้นเมื่อด้านบนของสแต็กมีที่จับ ในการลดฟังก์ชัน POP จะดำเนินการบนสแต็กซึ่งโผล่ออกมาจากที่จับและแทนที่ด้วยสัญลักษณ์ที่ไม่ใช่ขั้ว LHS

LR Parser

ตัวแยกวิเคราะห์ LR เป็นตัวแยกวิเคราะห์แบบไม่วนซ้ำ, ลดการเลื่อน, จากล่างขึ้นบน ใช้ไวยากรณ์ที่ไม่มีบริบทซึ่งทำให้เป็นเทคนิคการวิเคราะห์ไวยากรณ์ที่มีประสิทธิภาพสูงสุด ตัวแยกวิเคราะห์ LR เรียกอีกอย่างว่าตัวแยกวิเคราะห์ LR (k) โดยที่ L หมายถึงการสแกนจากซ้ายไปขวาของอินพุตสตรีม R ย่อมาจากการสร้างรากศัพท์ด้านขวาสุดในทางกลับกันและ k หมายถึงจำนวนสัญลักษณ์ผู้มองหาเพื่อทำการตัดสินใจ

มีอัลกอริทึมที่ใช้กันอย่างแพร่หลายสามแบบสำหรับการสร้างตัวแยกวิเคราะห์ LR:

  • SLR (1) - ตัวแยกวิเคราะห์ LR แบบง่าย:
    • ทำงานกับระดับไวยากรณ์ที่เล็กที่สุด
    • มีเพียงไม่กี่รัฐดังนั้นตารางที่เล็กมาก
    • การก่อสร้างที่ง่ายและรวดเร็ว
  • LR (1) - ตัวแยกวิเคราะห์ LR:
    • ทำงานบนชุดไวยากรณ์ LR (1) ที่สมบูรณ์
    • สร้างตารางขนาดใหญ่และสถานะจำนวนมาก
    • การก่อสร้างช้า
  • LALR (1) - Look-Ahead LR Parser:
    • ทำงานกับขนาดกลางของไวยากรณ์
    • จำนวนสถานะเหมือนกับใน SLR (1)

อัลกอริทึมการแยกวิเคราะห์ LR

ที่นี่เราอธิบายอัลกอริทึมโครงกระดูกของตัวแยกวิเคราะห์ LR:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL เทียบกับ LR

นิติศาสตรบัณฑิต LR
อนุพันธ์ทางซ้ายสุด อนุพันธ์ทางขวาสุดในทางกลับกัน
เริ่มต้นด้วย root nonterminal บนสแต็ก ลงท้ายด้วย root nonterminal บนสแต็ก
สิ้นสุดเมื่อสแต็กว่างเปล่า เริ่มต้นด้วยสแตกว่าง
ใช้สแต็กเพื่อกำหนดสิ่งที่ยังคงคาดหวัง ใช้สแต็กเพื่อกำหนดสิ่งที่เห็นอยู่แล้ว
สร้างแผนผังการแยกวิเคราะห์จากบนลงล่าง สร้างแผนผังการแยกวิเคราะห์จากล่างขึ้นบน
ดึงส่วนที่ไม่ใช่เทอร์มินัลออกจากสแต็กอย่างต่อเนื่องและดันไปทางขวามือที่เกี่ยวข้อง พยายามที่จะรับรู้ด้านขวามือบนสแต็กเปิดและดัน nonterminal ที่เกี่ยวข้อง
ขยายขั้วที่ไม่ใช่ขั้ว ลดขั้วที่ไม่ใช่ขั้ว
อ่านเทอร์มินัลเมื่อมันโผล่ออกมาจากสแต็ก อ่านเทอร์มินัลในขณะที่มันดันไปที่สแต็ก
พรีออเดอร์ข้ามเส้นทางของทรีแยกวิเคราะห์ โพสต์ออร์เดอร์การส่งผ่านของทรีแยกวิเคราะห์