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

เราได้เรียนรู้ในบทสุดท้ายแล้วว่าเทคนิคการแยกวิเคราะห์จากบนลงล่างจะแยกวิเคราะห์อินพุตและเริ่มสร้างต้นไม้แยกวิเคราะห์จากโหนดรากค่อยๆเคลื่อนลงไปที่โหนดใบไม้ ประเภทของการแยกวิเคราะห์จากบนลงล่างแสดงอยู่ด้านล่าง:

การแยกวิเคราะห์ Descent แบบเรียกซ้ำ

การสืบเชื้อสายซ้ำเป็นเทคนิคการแยกวิเคราะห์จากบนลงล่างที่สร้างแผนผังการแยกวิเคราะห์จากด้านบนและอินพุตจะอ่านจากซ้ายไปขวา ใช้โพรซีเดอร์สำหรับทุกเทอร์มินัลและเอนทิตีที่ไม่ใช่เทอร์มินัล เทคนิคการแยกวิเคราะห์นี้จะแยกวิเคราะห์ข้อมูลที่ป้อนซ้ำเพื่อสร้างโครงสร้างการแยกวิเคราะห์ซึ่งอาจต้องใช้การติดตามย้อนกลับหรือไม่ก็ได้ แต่ไวยากรณ์ที่เกี่ยวข้อง (หากไม่ได้แยกตัวประกอบ) ไม่สามารถหลีกเลี่ยงการติดตามย้อนกลับได้ รูปแบบของการแยกวิเคราะห์การสืบเชื้อสายซ้ำที่ไม่จำเป็นต้องมีการติดตามย้อนกลับเรียกว่าpredictive parsing.

เทคนิคการแยกวิเคราะห์นี้ถือได้ว่าเป็นแบบวนซ้ำเนื่องจากใช้ไวยากรณ์ที่ไม่มีบริบทซึ่งเป็นแบบวนซ้ำ

การติดตามย้อนกลับ

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

S → rXd | rZd
X → oa | ea
Z → ai

สำหรับสตริงอินพุต: read ตัวแยกวิเคราะห์จากบนลงล่างจะทำงานดังนี้:

มันจะเริ่มต้นด้วย S จากกฎการผลิตและจะจับคู่ผลตอบแทนกับตัวอักษรซ้ายสุดของอินพุตนั่นคือ 'r' การผลิต S (S → rXd) ที่ตรงกับมัน ดังนั้นตัวแยกวิเคราะห์จากบนลงล่างจะเลื่อนไปยังตัวอักษรอินพุตถัดไป (เช่น 'e') ตัวแยกวิเคราะห์พยายามขยาย 'X' ที่ไม่ใช่เทอร์มินัลและตรวจสอบการผลิตจากด้านซ้าย (X → oa) ไม่ตรงกับสัญลักษณ์อินพุตถัดไป ดังนั้นตัวแยกวิเคราะห์จากบนลงล่างจะติดตามเพื่อรับกฎการผลิตถัดไปของ X, (X → ea)

ตอนนี้โปรแกรมแยกวิเคราะห์จะจับคู่ตัวอักษรอินพุตทั้งหมดตามลำดับ ยอมรับสตริงแล้ว

Predictive Parser

Predictive parser คือตัวแยกวิเคราะห์การสืบเชื้อสายแบบเรียกซ้ำซึ่งมีความสามารถในการคาดเดาว่าจะใช้การผลิตใดเพื่อแทนที่สตริงอินพุต โปรแกรมวิเคราะห์คำทำนายจะไม่ประสบกับการย้อนรอย

ในการทำงานให้สำเร็จตัววิเคราะห์คำทำนายจะใช้ตัวชี้มองไปข้างหน้าซึ่งชี้ไปที่สัญลักษณ์อินพุตถัดไป ในการทำให้ตัวแยกวิเคราะห์กลับมาติดตามได้ฟรีตัวแยกวิเคราะห์เชิงคาดการณ์จะกำหนดข้อ จำกัด บางประการเกี่ยวกับไวยากรณ์และยอมรับเฉพาะระดับของไวยากรณ์ที่เรียกว่าไวยากรณ์ LL (k)

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

ในการแยกวิเคราะห์แบบเรียกซ้ำตัวแยกวิเคราะห์อาจมีการผลิตมากกว่าหนึ่งรายการให้เลือกสำหรับอินสแตนซ์อินพุตเดียวในขณะที่ในการแยกวิเคราะห์เชิงคาดการณ์แต่ละขั้นตอนจะมีการผลิตให้เลือกมากที่สุด อาจมีกรณีที่ไม่มีการผลิตที่ตรงกับสตริงอินพุตทำให้ขั้นตอนการแยกวิเคราะห์ล้มเหลว

LL Parser

LL Parser ยอมรับไวยากรณ์ LL ไวยากรณ์ LL เป็นชุดย่อยของไวยากรณ์ที่ไม่มีบริบท แต่มีข้อ จำกัด บางประการในการรับเวอร์ชันที่เรียบง่ายเพื่อให้สามารถใช้งานได้ง่าย ไวยากรณ์ LL สามารถใช้งานได้โดยใช้อัลกอริทึมทั้งสองแบบคือการสืบเชื้อสายซ้ำหรือการขับเคลื่อนด้วยตาราง

LL parser แสดงเป็น LL (k) L ตัวแรกใน LL (k) กำลังแยกวิเคราะห์อินพุตจากซ้ายไปขวา L ตัวที่สองใน LL (k) ย่อมาจากการได้มาจากซ้ายสุดและ k หมายถึงจำนวนการมองไปข้างหน้า โดยทั่วไป k = 1 ดังนั้น LL (k) จึงอาจเขียนเป็น LL (1)

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

เราอาจยึดติดกับดีเทอร์มินิสติก LL (1) สำหรับคำอธิบายตัวแยกวิเคราะห์เนื่องจากขนาดของตารางโตขึ้นแบบทวีคูณด้วยค่า k ประการที่สองถ้าไวยากรณ์ที่กำหนดไม่ใช่ LL (1) โดยปกติแล้วจะไม่ใช่ LL (k) สำหรับ k ใด ๆ ที่กำหนด

ด้านล่างนี้เป็นอัลกอริทึมสำหรับการแยกวิเคราะห์ LL (1):

Input: 
   string ω 
   parsing table M for grammar G

Output:
   If ω is in L(G) then left-most derivation of ω,
   error otherwise.

Initial State : $S on stack (with S being start symbol)
   ω$ in the input buffer

SET ip to point the first symbol of ω$.

repeat
   let X be the top stack symbol and a the symbol pointed by ip.

   if X∈ Vt or $
      if X = a
         POP X and advance ip.
      else
         error()
      endif
      
   else	/* X is non-terminal */
      if M[X,a] = X → Y1, Y2,... Yk    
         POP X
         PUSH Yk, Yk-1,... Y1 /* Y1 on top */
         Output the production X → Y1, Y2,... Yk 
      else
         error()
      endif
   endif
until X = $	/* empty stack */

ไวยากรณ์ G คือ LL (1) ถ้า A →α | βเป็นสองโปรดักชั่นที่แตกต่างกันของ G:

  • สำหรับไม่มีเทอร์มินัลทั้งαและβได้รับสตริงที่ขึ้นต้นด้วย.

  • มากที่สุดหนึ่งในαและ der สามารถหาสตริงว่างได้

  • ถ้าβ→ t ดังนั้นαจะไม่ได้รับสตริงใด ๆ ที่ขึ้นต้นด้วยเทอร์มินัลใน FOLLOW (A)