ในวิทยาการคอมพิวเตอร์ตัว แยกวิเคราะห์แบบ เรียกซ้ำ (recursive descent parser) เป็นตัว แยกวิเคราะห์แบบบนลงล่าง (top-down parser ) ชนิดหนึ่งที่สร้างขึ้นจากชุดของ ขั้นตอนแบบ เรียกซ้ำซึ่งกันและกัน (หรือเทียบเท่าแบบไม่เรียกซ้ำ) โดยที่แต่ละขั้นตอน ดังกล่าวจะใช้เทอร์มินัลที่ไม่ใช่เทอร์มิ นัลตัวใดตัวหนึ่งของไวยากรณ์ดังนั้นโครงสร้างของโปรแกรมที่ได้จึงสะท้อนโครงสร้างของไวยากรณ์ที่มันรู้จักอย่างใกล้ชิด^{[ 1 ] [ 2 ]}

ตัวแยกวิเคราะห์เชิงทำนายคือตัวแยกวิเคราะห์แบบเรียกซ้ำที่ไม่ต้องการการย้อนกลับ [ ^{3 ] การ} แยกวิเคราะห์เชิงทำนายเป็นไปได้เฉพาะสำหรับไวยากรณ์คลาสLL( k )ซึ่งเป็นไวยากรณ์แบบไร้บริบทที่มีจำนวนเต็มบวกk บางตัว ที่อนุญาตให้ตัวแยกวิเคราะห์แบบเรียกซ้ำตัดสินใจว่าจะใช้กฎการผลิตใดโดยการตรวจสอบ โทเค็นอินพุต k ตัวถัดไปเท่านั้น ดังนั้นไวยากรณ์ LL( k ) จึงไม่รวมไวยากรณ์ที่กำกวม ทั้งหมด รวมถึงไวยากรณ์ทั้งหมดที่มีการเรียกซ้ำทางซ้ายไวยากรณ์แบบไร้บริบทใดๆ ก็สามารถแปลงเป็นไวยากรณ์ที่เทียบเท่ากันซึ่งไม่มีการเรียกซ้ำทางซ้ายได้ แต่การลบการเรียกซ้ำทางซ้ายไม่ได้ทำให้ได้ไวยากรณ์ LL( k ) เสมอไป ตัวแยกวิเคราะห์เชิงทำนายทำงานในเวลาเชิงเส้น

การไล่ระดับแบบเรียกซ้ำพร้อมการย้อนกลับ (Recursive descent with backtracking) เป็นเทคนิคที่ใช้ในการพิจารณาว่า ควรใช้ กฎการผลิต ใด โดยลองใช้กฎการผลิตแต่ละข้อทีละข้อ การไล่ระดับแบบเรียกซ้ำพร้อมการย้อนกลับไม่ได้จำกัดเฉพาะไวยากรณ์ LL( k ) เท่านั้น แต่ไม่รับประกันว่าจะสิ้นสุดเว้นแต่ไวยากรณ์จะเป็น LL( k ) แม้ว่าจะสิ้นสุดแล้วก็ตาม ตัวแยกวิเคราะห์ที่ใช้การไล่ระดับแบบเรียกซ้ำพร้อมการย้อนกลับอาจต้องใช้เวลาในระดับเลขชี้กำลัง

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

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

ไวยากรณ์ที่คล้ายกับEBNFต่อไปนี้(สำหรับ ภาษาโปรแกรม PL/0ของNiklaus WirthจากAlgorithms + Data Structures = Programs ) อยู่ใน รูปแบบ LL(1) ดังนี้ :

โปรแกรม= บล็อก". "block = [ "const" ident "=" number { "," ident "=" number } ";" ] [ "var" ident { "," ident } ";" ] { "procedure" ident ";" block ";" } statement .statement = ident ":=" expression | "call" ident | "begin" statement { ";" statement } "end" | "if" condition "then" statement | "while" condition "do" statement .เงื่อนไข= นิพจน์"คี่" | นิพจน์( "=" | "#" | "<" | "<=" | ">" | ">=" ) นิพจน์.expression = [ "+" | "-" ] term {( "+" | "-" ) term } .เทอม= แฟกเตอร์{( "*" | "/" ) แฟกเตอร์} .แฟกเตอร์= ตัวตน| ตัวเลข| "(" นิพจน์")" .

สัญลักษณ์เทอร์มินัลจะแสดงอยู่ในเครื่องหมายอัญประกาศ สัญลักษณ์ นอนเทอร์มินัล แต่ละตัว จะถูกกำหนดโดยกฎในไวยากรณ์ ยกเว้นidentและnumberซึ่งถือว่าถูกกำหนดไว้โดย ปริยาย

ต่อไปนี้คือการใช้งานตัวแยกวิเคราะห์แบบเรียกซ้ำ (recursive descent parser) สำหรับภาษาข้างต้นในภาษาซีตัวแยกวิเคราะห์จะอ่านโค้ดต้นฉบับ และจะออกจากโปรแกรมพร้อมข้อความแสดงข้อผิดพลาดหากไม่สามารถแยกวิเคราะห์โค้ดได้ และจะออกจากโปรแกรมโดยไม่มีข้อความแสดงข้อผิดพลาดหากสามารถแยกวิเคราะห์โค้ดได้อย่างถูกต้อง

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

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

extern void error ( const char msg []); extern void consumesym ();typedef enum Symbol { ident , number , lparen , rparen , times , slash , plus , minus , eql , neq , lss , leq , gtr , geq , callsym , beginsym , semicolon , endsym , ifsym , whilesym , becomes , thensym , dosym , constsym , comma , varsym , procsym , period , oddsym } Symbol ; extern Symbol peeksym ();bool accept ( Symbol s ) { if ( peeksym () == s ) { consumesym (); return true ; } return false ; }bool expect ( Symbol s ) { if ( accept ( s )) { return true ; } error ( "expect: unexpected symbol" ); return false ; }void factor () { if ( accept ( ident ) || accept ( number )) { return ; } if ( accept ( lparen )) { expression (); expect ( rparen ); } else { error ( "factor: syntax error" ); consumesym (); } }void term () { factor (); while ( peeksym () == times || peeksym () == slash ) { consumesym (); factor (); } }void expression () { if ( peeksym () == plus || peeksym () == minus ) { consumesym (); } term (); while ( peeksym () == plus || peeksym () == minus ) { consumesym (); term (); } }void condition () { if ( accept ( oddsym )) { expression (); return ; } expression (); if ( peeksym () == eql || peeksym () == neq || peeksym () == lss || peeksym ( ) == leq || peeksym () == gtr || peeksym () == geq ) { consumesym (); expression (); } else { error ( "condition: invalid operator" ); consumesym (); } }void statement () { if ( accept ( ident )) { expect ( becomes ); expression (); } else if ( accept ( callsym )) { expect ( ident ); } else if ( accept ( beginsym )) { do { statement (); } while ( accept ( semicolon )); expect ( endsym ); } else if ( accept ( ifsym )) { condition (); expect ( thensym ); statement (); } else if ( accept ( whilesym )) { condition (); expect ( dosym ); statement (); } else { error ( "statement: syntax error" ); consumesym (); } }void block () { if ( accept ( constsym )) { do { expect ( ident ); expect ( eql ); expect ( number ); } while ( accept ( comma )); expect ( semicolon ); } if ( accept ( varsym )) { do { expect ( ident ); } while ( accept ( comma )); expect ( semicolon ); } while ( accept ( procsym )) { expect ( ident ); expect ( semicolon ); block (); expect ( semicolon ); } statement (); }void program () { block (); expect ( period ); }

ตัวอย่างตัวสร้างตัวแยกวิเคราะห์แบบเรียกซ้ำบางส่วน:

• TMG – คอมไพเลอร์รุ่นแรกๆ ที่ใช้ในช่วงทศวรรษ 1960 และต้นทศวรรษ 1970
• JavaCC
• โคโค่/อาร์
• แอนท์แอลอาร์
• Spirit Parser Framework – เฟรมเวิร์กสร้างตัวแยกวิเคราะห์แบบเรียกซ้ำ (recursive descent parser) ที่เขียนด้วยภาษา C++ โดยไม่ต้องมีการคอมไพล์ล่วงหน้า
• parboiled (Java) – ไลบรารีการแยกวิเคราะห์PEG แบบเรียกซ้ำ สำหรับJava

ส่วนหน้า C++ ของ คอมไพเลอร์ Clangประกอบด้วยตัวแยกวิเคราะห์ที่เขียนด้วยมือโดยอิงตามอัลกอริทึมการแยกวิเคราะห์แบบเรียกซ้ำ^{[ 5 ]}

• ตัวรวมการวิเคราะห์ (Parser combinator) – ฟังก์ชันลำดับสูงที่ใช้ในการวิเคราะห์เชิงรวม (combinatory parsing) ซึ่งเป็นวิธีการแยกตัวประกอบการออกแบบตัววิเคราะห์แบบเรียกซ้ำ (recursive descent parser designs)
• ไวยากรณ์การแยกวิเคราะห์นิพจน์ – รูปแบบอื่นที่แสดงถึงไวยากรณ์การสืบแบบเรียกซ้ำ
• ตัวแยกวิเคราะห์การขึ้นแบบเรียกซ้ำ
• ตัวแยกวิเคราะห์แบบเรียกซ้ำส่วนท้าย – รูปแบบหนึ่งของตัวแยกวิเคราะห์แบบเรียกซ้ำลง

• Jack W. Crenshaw: มาสร้างคอมไพเลอร์กันเถอะ (1988-1995)ในภาษา Pascalพร้อม เอาต์พุต เป็นภาษาแอสเซมบลีโดยใช้แนวทาง "ทำให้ง่ายเข้าไว้"