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

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

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 ที่เกี่ยวข้อง
ขยายขั้วที่ไม่ใช่ขั้ว	ลดขั้วที่ไม่ใช่ขั้ว
อ่านเทอร์มินัลเมื่อมันโผล่ออกมาจากสแต็ก	อ่านเทอร์มินัลในขณะที่มันดันไปที่สแต็ก
พรีออเดอร์ข้ามเส้นทางของทรีแยกวิเคราะห์	โพสต์ออร์เดอร์การส่งผ่านของทรีแยกวิเคราะห์