ในวิทยาการคอมพิวเตอร์ตัวแยก วิเคราะห์ ลำดับความสำคัญของตัวดำเนินการ(operator-precedence parser)คือตัว แยกวิเคราะห์แบบ จากล่างขึ้นบน (bottom-up parser ) ที่ตีความไวยากรณ์ ลำดับความสำคัญของตัวดำเนินการ ตัวอย่างเช่น เครื่องคิดเลขส่วนใหญ่ใช้ตัวแยกวิเคราะห์ลำดับความสำคัญของตัวดำเนินการเพื่อแปลงจากสัญกรณ์แบบอินฟิกซ์ ที่มนุษย์อ่านได้ ซึ่งอาศัยลำดับการดำเนินการไปเป็นรูปแบบที่เหมาะสมที่สุดสำหรับการประเมินผล เช่นสัญกรณ์แบบ Reverse Polish Notation (RPN)

อัลกอริทึมลานสับเปลี่ยนขบวนรถของEdsger Dijkstraมักถูกนำมาใช้ในการสร้างตัวแยกวิเคราะห์ลำดับความสำคัญของผู้ปฏิบัติงาน

ตัวแยกวิเคราะห์ลำดับความสำคัญของตัวดำเนินการคือตัวแยกวิเคราะห์แบบ shift-reduce ที่ เรียบง่าย ซึ่งสามารถแยกวิเคราะห์ไวยากรณ์LR(1)บางส่วนได้ กล่าวคือ ตัวแยกวิเคราะห์ลำดับความสำคัญของตัวดำเนินการสามารถแยกวิเคราะห์ไวยากรณ์ LR(1) ทั้งหมดได้ โดยที่nonterminal สองตัวที่อยู่ติดกัน และepsilonจะไม่ปรากฏในด้านขวามือของกฎใดๆ

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

Rakuแทรกตัวแยกวิเคราะห์ลำดับความสำคัญของตัวดำเนินการไว้ระหว่างตัวแยกวิเคราะห์แบบเรียกซ้ำ สองตัว เพื่อให้ได้สมดุลระหว่างความเร็วและความยืดหยุ่นตัวแยกวิเคราะห์ C และ C++ ของGCC ซึ่งเป็นตัวแยกวิเคราะห์แบบเรียกซ้ำที่เขียนด้วยมือ ต่างก็ได้รับการเร่งความเร็วด้วยตัวแยกวิเคราะห์ลำดับความสำคัญของตัวดำเนินการที่สามารถตรวจสอบนิพจน์ทางคณิตศาสตร์ได้อย่างรวดเร็ว นอกจากนี้ ตัวแยกวิเคราะห์ลำดับความสำคัญของตัวดำเนินการยังถูกฝังอยู่ภายในตัวแยกวิเคราะห์ที่สร้าง โดยคอมไพเลอร์เพื่อเร่งความเร็ววิธีการเรียกซ้ำในการแยกวิเคราะห์นิพจน์อย่างเห็นได้ชัด^{[ 1 ]}

วิธีการไต่ลำดับความสำคัญเป็นอัลกอริทึมที่กระชับ มีประสิทธิภาพ และยืดหยุ่นสำหรับการแยกวิเคราะห์นิพจน์ ซึ่งได้รับการอธิบายครั้งแรกโดย Martin Richards และ Colin Whitby-Strevens ^{[ 2 ]}

ไวยากรณ์นิพจน์แบบอินฟิกซ์ใน รูปแบบ EBNFโดยทั่วไปจะมีลักษณะดังนี้:

นิพจน์ :: = นิพจน์ความเท่าเทียมกัน นิพจน์ความเท่าเทียมกัน :: = นิพจน์การบวก( ( ' == ' | '! = ' ) นิพจน์การบวก) * นิพจน์การบวก :: = นิพจน์การคูณ( ( '+' | '-' ) นิพจน์การคูณ) * นิพจน์การคูณ :: = หลัก( ( ' * ' | ' / ' ) หลัก) * หลัก :: = ' ( ' นิพจน์ ' ) ' | ตัวเลข | ตัวแปร | '-' หลัก

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

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

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

รหัสเทียมสำหรับอัลกอริธึมมีดังนี้ ตัวแยกวิเคราะห์เริ่มต้นที่ฟังก์ชันparse_expressionระดับความสำคัญมากกว่าหรือเท่ากับ 0

parse_expression() return parse_expression_1(parse_primary(), 0) 

parse_expression_1(lhs, min_precedence) lookahead  := peek next token ในขณะที่lookaheadเป็นตัวดำเนินการไบนารีที่มีลำดับความสำคัญ >= min_precedence op  := lookahead เลื่อนไปยังโทเค็นถัดไป rhs  := parse_primary () lookahead  := peek next token ในขณะที่lookaheadเป็นตัวดำเนินการไบนารีที่มีลำดับความสำคัญมากกว่า มากกว่าopหรือตัวดำเนินการเชื่อมโยงทางขวา ซึ่งมีลำดับความสำคัญเท่ากับrhsของ op  := parse_expression_1 ( rhs , ลำดับความสำคัญของop + (1 ถ้า ลำดับความสำคัญ ของ lookaheadมากกว่า มิฉะนั้น 0)) lookahead  := ดูโทเค็นถัดไป lhs  := ผลลัพธ์ของการใช้opกับตัวถูกดำเนินการlhsและrhs ส่งคืนlhs

โปรดทราบว่าในกรณีของกฎการผลิตแบบนี้ (ซึ่งตัวดำเนินการสามารถปรากฏได้เพียงครั้งเดียว):

นิพจน์ความเท่าเทียมกัน :: = นิพจน์การบวก( ' == ' | '! = ' ) นิพจน์การบวก

ต้องปรับเปลี่ยนอัลกอริธึมให้ยอมรับเฉพาะตัวดำเนินการไบนารีที่มีลำดับความสำคัญมากกว่าmin_precedenceเท่านั้น

ตัวอย่างการประมวลผลนิพจน์ 2 + 3 * 4 + 5 == 19 มีดังนี้ เรากำหนดลำดับความสำคัญ 0 ให้กับนิพจน์ความเท่าเทียมกัน 1 ให้กับนิพจน์การบวก และ 2 ให้กับนิพจน์การคูณ

parse_expression_1 ( lhs = 2, min_precedence = 0)

• โทเค็นการมองล่วงหน้าคือ + โดยมีลำดับความสำคัญ 1 ลูป while ภายนอกจึงเริ่มทำงาน
• opคือ + (ลำดับความสำคัญ 1) และอินพุตคือ advanced
• rhsคือ 3
• โทเค็นการมองล่วงหน้าคือ * โดยมีลำดับความสำคัญ 2 ลูป while ภายในถูกเรียกใช้parse_expression_1 ( lhs = 3, min_precedence = 2)

• โทเค็นการมองล่วงหน้าคือ * โดยมีลำดับความสำคัญ 2 ลูป while ภายนอกจึงเริ่มทำงาน

• opคือ * (ลำดับความสำคัญ 2) และอินพุตเป็นขั้นสูง
• rhsคือ 4
• โทเค็นถัดไปคือ + ซึ่งมีลำดับความสำคัญ 1 ลูป while ภายในจะไม่ถูกเรียกใช้งาน
• lhsถูกกำหนดให้เป็น 3*4 = 12
• โทเค็นถัดไปคือ + ซึ่งมีลำดับความสำคัญ 1 ลูป while ภายนอกจึงอยู่ทางซ้าย

• 12 ได้รับการส่งคืนแล้ว

• โทเค็นการมองล่วงหน้าคือ + โดยมีลำดับความสำคัญ 1 ลูป while ภายในจะไม่ถูกเรียกใช้งาน
• lhsถูกกำหนดให้เป็น 2+12 = 14
• โทเค็นการมองล่วงหน้าคือ + โดยมีลำดับความสำคัญ 1 ลูป while ภายนอกไม่ได้อยู่ทางซ้าย
• opคือ + (ลำดับความสำคัญ 1) และอินพุตคือ advanced
• rhsคือ 5
• โทเค็นถัดไปคือ == ซึ่งมีลำดับความสำคัญ 0 ลูป while ภายในจะไม่ถูกเรียกใช้งาน
• lhsได้รับการกำหนดค่า 14+5 = 19
• โทเค็นถัดไปคือ == ซึ่งมีลำดับความสำคัญ 0 ลูป while ภายนอกไม่ได้ออกจากด้านซ้าย
• opคือ == (ลำดับความสำคัญ 0) และอินพุตคือ advanced
• rhsคือ 19
• โทเค็นถัดไปคือสิ้นสุดบรรทัดซึ่งไม่ใช่ตัวดำเนินการ ลูป while ภายในจึงไม่ถูกเรียกใช้งาน
• ตัวแปร lhsจะได้รับค่าผลลัพธ์จากการประเมิน 19 == 19 เช่น 1 (ตามมาตรฐานภาษา C)
• โทเค็นถัดไปคือend-of-lineซึ่งไม่ใช่ตัวดำเนินการ ลูป while ภายนอกจึงอยู่ทางซ้าย

ส่งคืนค่า 1

ตัวแยกวิเคราะห์ลำดับความสำคัญอีกตัวหนึ่งที่เรียกว่าการแยกวิเคราะห์แบบ Pratt ได้รับการอธิบายครั้งแรกโดยVaughan Prattในบทความปี 1973 เรื่อง "Top Down Operator Precedence" ^{[ 3 ]}โดยอิงจากการลดระดับแบบเรียกซ้ำแม้ว่าจะมีมาก่อนการไต่ระดับลำดับความสำคัญ แต่ก็สามารถมองได้ว่าเป็นการวางนัยทั่วไปของการไต่ระดับลำดับความสำคัญ^{[ 4 ]}

Pratt ออกแบบตัวแยกวิเคราะห์เพื่อใช้งาน ภาษาโปรแกรม CGOL ในตอนแรก และมีการกล่าวถึงในรายละเอียดมากขึ้นในวิทยานิพนธ์ระดับปริญญาโทภายใต้การดูแลของเขา^{[ 5 ]}

บทแนะนำและการนำไปใช้งาน:

• Douglas Crockford ใช้การแยกวิเคราะห์ แบบ Pratt เป็นพื้นฐานสำหรับตัวแยกวิเคราะห์JavaScript ในJSLint ^{[ 6 ]}
• การเปรียบเทียบการใช้งานการจัดลำดับความสำคัญ (precedence climbing) และการแยกวิเคราะห์แบบ Pratt ในภาษา Python: "การแยกวิเคราะห์แบบ Pratt และการจัดลำดับความสำคัญเป็นอัลกอริทึมเดียวกัน" (2016) โดย Andy Chu
• บทช่วยสอนโดยใช้Rust : "การแยกวิเคราะห์ Pratt ที่เรียบง่าย แต่ทรงพลัง" (2020) โดย Aleksey Kladov
• คู่มือการใช้งานRust : "เทคนิคการวิเคราะห์ไวยากรณ์แบบ Pratt" (2024) โดย William Rågstad
• คู่มือการใช้งานPython : "การแยกวิเคราะห์แบบ Top-Down อย่างง่ายใน Python" (2008) โดย Fredrik Lundh เก็บถาวรเมื่อ 28 กุมภาพันธ์ 2015 ที่Wayback Machine
• คู่มือการใช้งานJava : "Pratt Parsers: Expression Parsing Made Easy" (2011) โดย Bob Nystrom ผู้เขียนหนังสือ Crafting Interpreters
• การใช้งานในC# : "Gratt: ตัวแยกวิเคราะห์ลำดับความสำคัญของตัวดำเนินการแบบบนลงล่างของ Vaughn Pratt ทั่วไปสำหรับ .NET Standard" ( เวอร์ชัน ทั่วไปที่ได้รับแรงบันดาลใจจากการใช้งานใน Java ที่นำเสนอโดย Bob Nystrom ใน"Pratt Parsers: Expression Parsing Made Easy" )

ยังมีวิธีอื่นๆ ในการใช้กฎลำดับความสำคัญของตัวดำเนินการ วิธีหนึ่งคือการสร้างโครงสร้างต้นไม้ของนิพจน์ดั้งเดิม แล้วจึงใช้กฎการเขียนใหม่ของโครงสร้างต้นไม้นั้นกับมัน

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

อีกแนวทางหนึ่งคือการใส่วงเล็บให้กับนิพจน์ทั้งหมดก่อน โดยใส่วงเล็บจำนวนหนึ่งรอบตัวดำเนินการแต่ละตัว เพื่อให้ได้ลำดับความสำคัญที่ถูกต้องแม้ว่าจะแยกวิเคราะห์ด้วยตัวแยกวิเคราะห์เชิงเส้นจากซ้ายไปขวา อัลกอริทึมนี้ถูกใช้ใน คอมไพเลอร์ FORTRAN I รุ่นแรกๆ : ^{[ 7 ]}

คอมไพเลอร์ Fortran I จะขยายโอเปอเรเตอร์แต่ละตัวด้วยลำดับของวงเล็บ ในรูปแบบที่ง่ายขึ้นของอัลกอริทึม มันจะเป็นเช่นนี้

• แทนที่+และ–ด้วย))+((และ))-((ตามลำดับ
• แทนที่*และ/ด้วย)*(และ)/(ตามลำดับ
• เพิ่ม((ที่จุดเริ่มต้นของแต่ละนิพจน์และหลังวงเล็บเปิดแต่ละอันในนิพจน์เดิม และ
• เพิ่ม))ต่อท้ายนิพจน์และก่อนวงเล็บปิดแต่ละอันในนิพจน์เดิม

แม้จะไม่ชัดเจน แต่อัลกอริทึมนั้นถูกต้อง และตามคำพูดของKnuth “สูตรที่ได้นั้นมีวงเล็บที่เหมาะสม เชื่อหรือไม่ก็ตาม” ^{[ 8 ]}

ตัวอย่างโค้ดของแอปพลิเคชัน C อย่างง่ายที่จัดการการใส่วงเล็บให้กับตัวดำเนินการทางคณิตศาสตร์พื้นฐาน ( +, -, *, /, ^, (และ)):

#include <stdio.h> #include <string.h>// ขอบเขตอาร์กิวเมนต์บรรทัดคำสั่งคือตัวแยกวิเคราะห์ของเราint main ( int argc , char * argv []) { int i ; printf ( "((((" ); for ( i = 1 ; i != argc ; i ++ ) { // strlen(argv[i]) == 2 if ( argv [ i ] && ! argv [ i ][ 1 ]) { switch ( * argv [ i ]) { case '(' : printf ( "((((" ); continue ; case ')' : printf ( "))))" ); continue ; case '^' : printf ( ")^(" ); continue ; case '*' : printf ( "))*((" ) ; continue ; case '/' : printf ( "))/((" ); continue ; case '+' : // ตรวจสอบเอกภาค: ตัวแรกหรือมีตัวดำเนินการที่คาดหวังอาร์กิวเมนต์รองif ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "+" ); else printf ( ")))+(((" ); continue ; case '-' : if ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "-" ); else printf ( ")))-(((" ); continue ; } } printf ( "%s" ,argv [ i ]); } printf ( ")))) \n " ); return0 ; }

ขั้นแรก คุณต้องคอมไพล์โปรแกรมของคุณก่อน สมมติว่าโปรแกรมของคุณเขียนด้วยภาษา C และซอร์สโค้ดอยู่ในไฟล์ชื่อ program.c คุณจะใช้คำสั่งต่อไปนี้:

gcc program.c -o program

คำสั่งข้างต้นบอกให้ gcc คอมไพล์ไฟล์ program.c และสร้างไฟล์ปฏิบัติการชื่อ program

คำสั่งสำหรับเรียกใช้โปรแกรมพร้อมพารามิเตอร์ ตัวอย่างเช่น; a * b + c ^ d / e

./program a '*' b + c '^' d / e

มันผลิต

((((a))*((b)))+(((c)^(d))/((e))))

แสดงผลออกทางคอนโซล

ข้อจำกัดของกลยุทธ์นี้คือ ตัวดำเนินการเอกภาคจะต้องมีลำดับความสำคัญสูงกว่าตัวดำเนินการอินฟิกซ์ทั้งหมด ตัวดำเนินการ "ลบ" ในโค้ดข้างต้นมีลำดับความสำคัญสูงกว่าการยกกำลัง การรันโปรแกรมด้วยข้อมูลป้อนเข้านี้

- a ^ 2

สร้างผลลัพธ์นี้

((((-a)^(2))))

ซึ่งอาจไม่ใช่สิ่งที่ตั้งใจไว้

• Clarke, Keith (26 พฤษภาคม 1992). "เรื่อง: การแยกวิเคราะห์นิพจน์แบบเรียกซ้ำที่กระชับ" . สืบค้นเมื่อ 24 มกราคม 2012 .
• ตัวอย่างโค้ด C++ โดย Keith Clarke สำหรับการแยกวิเคราะห์นิพจน์แบบอินฟิกซ์โดยใช้วิธีการไต่ลำดับความสำคัญ
• Samelson, Klaus ; Friedrich L. Bauer (กุมภาพันธ์ 1960). "การแปลสูตรตามลำดับ" . Communications of the ACM . 3 (2): 76– 83. doi : 10.1145/366959.366968 .
• ตัวแยกวิเคราะห์นิพจน์ที่มีสัญกรณ์แบบอินฟิกซ์โดยใช้รายการลำดับความสำคัญ