ผู้แต่ง: อะไรคือความแตกต่างระหว่างตัวแยกวิเคราะห์ LL (0) และ LR (0) มีสิ่งเช่น LL parsers (0)?


ตอบ 1:

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

เป้าหมาย: "Hello" whitespace "world" เครื่องหมายอัศเจรีย์;

โปรดทราบว่ารูปแบบที่อนุญาตเท่านั้นคือวิธีที่ lexer จับคู่กับโทเค็น

(ฉันหวังว่าสัญกรณ์จะชัดเจน - เป็นหลักที่ฉันใช้ใน Yacc ++ สตริงที่ยกมาเป็นโทเค็นเช่นเดียวกับตัวระบุใด ๆ ที่ไม่ได้กำหนด)

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

เป้าหมาย: hello-part whitespace end-part;

hello-part: hello1;

hello1: "สวัสดี";

ส่วนปลาย: ส่วนโลกส่วนสุดท้าย;

ส่วนโลก: "โลก";

ส่วนสุดท้าย: "!";

อย่างไรก็ตามโปรดสังเกตว่าไม่มีกฎใดที่มีตัวดำเนินการ "หรือ" (|) และมีเพียงหนึ่งกฎต่อหนึ่งที่ไม่ใช่เทอร์มินัล นี่คือสิ่งที่อนุญาตให้ parser รู้วิธีจับคู่แต่ละกฎโดยไม่ใช้โทเค็นที่แบ่งแยก (โทเค็นที่เลือกวิธีที่ parser ไป) ซึ่งทำให้ไวยากรณ์ LL (0)

ตอนนี้เป็นไปได้ไหมที่จะใช้การผลิตแบบเรียกซ้ำและยังมีไวยากรณ์ LL (0) อยู่? คำตอบคือ "ไม่" มาดูกันว่าจะเกิดอะไรขึ้นถ้าเรามีกฎแบบวนซ้ำ

เป้าหมาย: "x" เป้าหมาย "y";

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

ดังนั้นไวยากรณ์ LL (0) จะต้องแยกรายการที่แน่นอนของโทเค็นหนึ่งรายการแน่นอน (รายการเดียวกันทุกครั้ง)

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

เป้าหมาย: "x" | "(" เป้าหมาย ")";

ไวยากรณ์นี้แยกวิเคราะห์ "x" ที่ล้อมรอบด้วยวงเล็บจำนวนหนึ่ง โปรดทราบว่าสามารถใช้โทเค็น "x" และโทเค็น "(" เพื่อตัดสินใจว่าจะใช้กฎใด 0 ใน LR (0) ไม่ จำกัด การใช้โทเค็นภายในกฎเช่นเดียวกับที่ 0 ใน LL (0) สิ่งเดียวที่ จำกัด คือการใช้โทเค็น (ของบริบทหลังจากกฎในการใช้ที่ไม่ใช่เทอร์มินัล) เมื่อตัดสินใจที่จะลดไวยากรณ์นี้ไม่จำเป็นต้องใช้บริบทในการตัดสินใจที่จะลดในทางเลือกแรกมันลดลงเมื่อเห็น "x" ในวินาทีจะลดลงหลังจากเห็น ")" โทเค็นภายในกฎกำหนดว่าเมื่อใดควรลดกฎ


ตอบ 2:

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

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