วิธีการเขียนล่ามตั้งแต่เริ่มต้น

บางคนบอกว่า "ทุกอย่างกลายเป็นหนึ่งและศูนย์" แต่เราเข้าใจจริง ๆ หรือไม่ว่าโปรแกรมของเราแปลเป็นบิตเหล่านั้นได้อย่างไร

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

สิ่งที่ควรทำและไม่ควรทำในการเขียนล่ามของคุณเอง

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

การเขียน parsers อย่างถูกต้องด้วยมืออาจเป็นเรื่องยากสำหรับ edge case ทั้งหมดที่เกี่ยวข้อง นั่นเป็นสาเหตุว่าทำไมมีเครื่องมือยอดนิยม เช่น ANTLR ที่สามารถสร้าง parsers สำหรับภาษาโปรแกรมยอดนิยมมากมาย นอกจากนี้ยังมีไลบรารี่ที่เรียกว่า parser combinators ซึ่งช่วยให้นักพัฒนาสามารถเขียน parsers ได้โดยตรงในภาษาโปรแกรมที่ต้องการ ตัวอย่าง ได้แก่ FastParse สำหรับ Scala และ Parsec สำหรับ Python

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

ภาพรวมของส่วนประกอบล่าม

ล่ามเป็นโปรแกรมที่ซับซ้อน ดังนั้นจึงมีหลายขั้นตอน:

1. lexer เป็นส่วนหนึ่งของล่ามที่เปลี่ยนลำดับของอักขระ (ข้อความธรรมดา) เป็นลำดับของโทเค็น
2. ในทางกลับกัน parser ใช้ลำดับของโทเค็นและสร้างแผนผังไวยากรณ์นามธรรม (AST) ของภาษา กฎที่ parser ดำเนินการมักจะถูกระบุโดยไวยากรณ์ที่เป็นทางการ
3. ล่าม เป็นโปรแกรมที่ตีความ AST ของแหล่งที่มาของโปรแกรมได้ทันที (โดยไม่ต้องคอมไพล์ก่อน)

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

 val input = "2 * 7 + 5" val tokens = Lexer(input).lex() val ast = Parser(tokens).parse() val res = Interpreter(ast).interpret() println(s"Result is: $res")

จากสามขั้นตอน เราจะคาดหวังให้รหัสนี้คำนวณค่าสุดท้ายและ Result is: 19 กวดวิชานี้เกิดขึ้นเพื่อใช้ Scala เพราะมันคือ:

• กระชับมาก ใส่โค้ดได้เยอะในหน้าจอเดียว
• เน้นนิพจน์ โดยไม่จำเป็นต้องใช้ตัวแปรที่ยังไม่ได้กำหนดค่าเริ่มต้น/ค่าว่าง
• พิมพ์ safe ด้วยไลบรารีคอลเลกชันที่มีประสิทธิภาพ enums และ case class

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

สุดท้าย ส่วนของ Lexer, Parser และ Interpreter มี ตัวอย่างไวยากรณ์ที่แตกต่างกัน ตามที่ repo GitHub ที่เกี่ยวข้องแสดงให้เห็น การพึ่งพาในตัวอย่างในภายหลังจะเปลี่ยนไปเล็กน้อยเพื่อใช้ไวยากรณ์เหล่านี้ แต่แนวคิดโดยรวมยังคงเหมือนเดิม

ส่วนประกอบล่าม 1: การเขียน Lexer

สมมติว่าเราต้องการระบุสตริงนี้: "123 + 45 true * false1" ประกอบด้วยโทเค็นประเภทต่างๆ:

• อักษรจำนวนเต็ม
• A + โอเปอเรเตอร์
• ตัวดำเนินการ *
• ตัวหนังสือ true
• ตัวระบุ false1

ช่องว่างระหว่างโทเค็นจะถูกข้ามไปในตัวอย่างนี้

ในขั้นตอนนี้ สำนวนไม่จำเป็นต้องมีเหตุผล lexer แปลงสตริงอินพุตเป็นรายการโทเค็น (งานของ "การทำความเข้าใจโทเค็น" ถูกทิ้งให้เป็นผู้แยกวิเคราะห์)

เราจะใช้รหัสนี้เพื่อแสดงโทเค็น:

 case class Token( tpe: Token.Type, text: String, startPos: Int ) object Token: enum Type: case Num case Plus case Times case Identifier case True case False case EOF

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

โทเค็น EOF เป็นโทเค็นพิเศษที่ทำเครื่องหมายจุดสิ้นสุดของอินพุต ไม่มีอยู่ในข้อความต้นฉบับ เราใช้เพื่อทำให้ขั้นตอน parser ง่ายขึ้นเท่านั้น

นี่จะเป็นผลลัพธ์ของ lexer ของเรา:

 Lexing input: 123 + 45 true * false1 Tokens: List( Token(tpe = Num, text = "123", tokenStartPos = 0), Token(tpe = Plus, text = "+", tokenStartPos = 4), Token(tpe = Num, text = "45", tokenStartPos = 6), Token(tpe = True, text = "true", tokenStartPos = 9), Token(tpe = Times, text = "*", tokenStartPos = 14), Token(tpe = Identifier, text = "false1", tokenStartPos = 16), Token(tpe = EOF, text = "<EOF>", tokenStartPos = 22) )

มาตรวจสอบการใช้งานกัน:

 class Lexer(input: String): def lex(): List[Token] = val tokens = mutable.ArrayBuffer.empty[Token] var currentPos = 0 while currentPos < input.length do val tokenStartPos = currentPos val lookahead = input(currentPos) if lookahead.isWhitespace then currentPos += 1 // ignore whitespace else if lookahead == '+' then currentPos += 1 tokens += Token(Type.Plus, lookahead.toString, tokenStartPos) else if lookahead == '*' then currentPos += 1 tokens += Token(Type.Times, lookahead.toString, tokenStartPos) else if lookahead.isDigit then var text = "" while currentPos < input.length && input(currentPos).isDigit do text += input(currentPos) currentPos += 1 tokens += Token(Type.Num, text, tokenStartPos) else if lookahead.isLetter then // first must be letter var text = "" while currentPos < input.length && input(currentPos).isLetterOrDigit do text += input(currentPos) currentPos += 1 val tpe = text match case "true" => Type.True // special casing literals case "false" => Type.False case _ => Type.Identifier tokens += Token(tpe, text, tokenStartPos) else error(s"Unknown character '$lookahead' at position $currentPos") tokens += Token(Type.EOF, "<EOF>", currentPos) // special end marker tokens.toList

เราเริ่มต้นด้วยรายการโทเค็นที่ว่างเปล่า จากนั้นเราตรวจสอบสตริงและเพิ่มโทเค็นตามที่ได้รับ

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

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

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

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

ด้วยเหตุนี้ lexer ของเราจึงได้จัดทำรายการโทเค็น

ส่วนประกอบล่าม 2: การเขียน Parser

เราต้อง กำหนดโครงสร้าง บางอย่างให้กับโทเค็นของเรา เราไม่สามารถทำอะไรได้มากกับรายการเพียงอย่างเดียว ตัวอย่างเช่น เราต้องรู้ว่า:

นิพจน์ใดที่ซ้อนกัน? โอเปอเรเตอร์ใดบ้างที่ใช้ในลำดับใด กฎการกำหนดขอบเขตใดที่ใช้ หากมี

โครงสร้างแบบต้นไม้รองรับการทำรังและการจัดลำดับ แต่ก่อนอื่น เราต้องกำหนดกฎเกณฑ์บางประการสำหรับการสร้างต้นไม้ เราต้องการให้ parser ของเรามีความชัดเจน—เพื่อส่งคืนโครงสร้างเดิมสำหรับอินพุตที่กำหนดเสมอ

โปรดทราบว่า parser ต่อไปนี้ ไม่ได้ใช้ตัวอย่าง lexer ก่อนหน้า อันนี้ใช้สำหรับบวกตัวเลข ดังนั้นไวยากรณ์ของมันจึงมีเพียงสองโทเค็นคือ '+' และ NUM :

 expr -> expr '+' expr expr -> NUM

เทียบเท่าโดยใช้อักขระไพพ์ ( | ) เป็นสัญลักษณ์ “หรือ” เช่นในนิพจน์ทั่วไปคือ:

 expr -> expr '+' expr | NUM

ไม่ว่าจะด้วยวิธีใด เรามีกฎสองข้อ: ข้อหนึ่งที่บอกว่าเราสามารถรวมสอง expr และอีกกฎที่บอกว่า expr สามารถเป็นโทเค็น NUM ได้ ซึ่งในที่นี้จะหมายถึงจำนวนเต็มที่ไม่ติดลบ

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

เฉพาะ nonterminal เท่านั้นที่สามารถอยู่ทางด้านซ้ายของกฎ ด้านขวามีได้ทั้งขั้วและไม่ใช่ขั้ว ในตัวอย่างข้างต้น เทอร์มินัลคือ '+' และ NUM และเทอร์มินัลที่ไม่ใช่เทอร์มินัลเท่านั้นคือ expr สำหรับตัวอย่างที่กว้างขึ้น ในภาษา Java เรามีเทอร์มินัลเช่น 'true' , '+' , Identifier และ '[' และไม่ใช่เทอร์มินัลเช่น BlockStatements , ClassBody และ MethodOrFieldDecl

มีหลายวิธีที่เราสามารถใช้ parser นี้ได้ ในที่นี้ เราจะใช้เทคนิคการแยกวิเคราะห์ "recursive descent" เป็นประเภทที่พบบ่อยที่สุดเพราะเป็นประเภทที่เข้าใจและนำไปใช้ได้ง่ายที่สุด

parser แบบเรียกซ้ำใช้ ฟังก์ชันเดียวสำหรับแต่ละ nonterminal ในไวยากรณ์ มันเริ่มต้นจากกฎเริ่มต้นและลงไปจากที่นั่น (เพราะฉะนั้น "การสืบเชื้อสาย") การหากฎที่จะใช้ในแต่ละฟังก์ชัน ส่วน "แบบเรียกซ้ำ" มีความสำคัญเพราะเราสามารถซ้อน nonterminals แบบเรียกซ้ำได้! Regexes ทำไม่ได้: พวกเขาไม่สามารถจัดการวงเล็บที่สมดุลได้ ดังนั้นเราจึงต้องการเครื่องมือที่ทรงพลังกว่านี้

parser สำหรับกฎข้อแรกจะมีลักษณะดังนี้ (รหัสเต็ม):

 def expr() = expr() eat('+') expr()

ฟังก์ชัน eat() จะตรวจสอบว่า lookahead ตรงกับโทเค็นที่ต้องการหรือไม่ จากนั้นจึงย้ายดัชนี lookahead ขออภัย วิธีนี้ใช้ไม่ได้เนื่องจากเราต้องแก้ไขปัญหาเกี่ยวกับไวยากรณ์ของเรา

ความคลุมเครือของไวยากรณ์

ปัญหาแรกคือความกำกวมของไวยากรณ์ของเรา ซึ่งอาจไม่ชัดเจนในแวบแรก:

 expr -> expr '+' expr | NUM

จากอินพุต 1 + 2 + 3 parser ของเราสามารถเลือกที่จะคำนวณ expr expr ก่อนใน AST ที่เป็นผลลัพธ์:

นั่นเป็นเหตุผลที่เราต้องแนะนำ ความไม่สมมาตร :

 expr -> expr '+' NUM | NUM

ชุดของนิพจน์ที่เราสามารถแสดงด้วยไวยากรณ์นี้ไม่มีการเปลี่ยนแปลงตั้งแต่เวอร์ชันแรก ตอนนี้ ไม่ชัดเจน : parser ไปทางซ้ายเสมอ สิ่งที่เราต้องการ!

สิ่งนี้ทำให้การดำเนินการ + ของเรา เหลือการเชื่อมโยง แต่สิ่งนี้จะชัดเจนเมื่อเราไปที่ส่วนล่าม

กฎการเรียกซ้ำทางซ้าย

ขออภัย การแก้ไขข้างต้นไม่สามารถแก้ปัญหาอื่นๆ ของเราได้ เหลือการเรียกซ้ำ:

 def expr() = expr() eat('+') eat(NUM)

เรามี การเรียกซ้ำที่ไม่สิ้นสุด ที่นี่ หากเราก้าวเข้าสู่ฟังก์ชันนี้ ในที่สุด เราก็จะได้รับข้อผิดพลาด stack-overflow แต่การแยกวิเคราะห์ทฤษฎีสามารถช่วยได้!

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

 A -> A alpha | B

เราสามารถเขียนไวยากรณ์นี้เป็น:

 A -> BA' A' -> alpha A' | epsilon

ที่นั่น epsilon เป็นสตริงว่าง ไม่มีอะไร ไม่มีโทเค็น

มาดูการแก้ไขไวยากรณ์ของเราในปัจจุบัน:

 expr -> expr '+' NUM | NUM

ตามวิธีการเขียนกฎการแยกวิเคราะห์ใหม่ที่มีรายละเอียดด้านบน โดย alpha เป็นโทเค็น '+' NUM ของเรา ไวยากรณ์ของเราจะกลายเป็น:

 expr -> NUM exprOpt exprOpt -> '+' NUM exprOpt | epsilon

ตอนนี้ไวยากรณ์ใช้ได้แล้ว และเราสามารถแยกวิเคราะห์ด้วย parser แบบเรียกซ้ำได้ มาดูกันว่า parser จะมองหาการวนซ้ำล่าสุดของไวยากรณ์ของเราอย่างไร:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Unit = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") private def expr(): Unit = eat(Type.Num) exprOpt() private def exprOpt(): Unit = if lookahead.tpe == Type.Plus then eat(Type.Plus) eat(Type.Num) exprOpt() // else: end recursion, epsilon private def eat(tpe: Type): Unit = if lookahead.tpe != tpe then error(s"Expected: $tpe, got: ${lookahead.tpe} at position ${lookahead.startPos}") tokens = tokens.tail lookahead = tokens.head

ที่นี่เราใช้โทเค็น EOF เพื่อทำให้ parser ของเราง่ายขึ้น เรามั่นใจเสมอว่ามีอย่างน้อยหนึ่งโทเค็นในรายการของเรา ดังนั้นเราจึงไม่จำเป็นต้องจัดการกับกรณีพิเศษของรายการว่าง

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

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

หากสตริงอินพุตมีโทเค็นมากกว่า จะต้องมีลักษณะดังนี้ + 123 นั่นคือสิ่งที่เรียกซ้ำใน exprOpt() !

กำลังสร้าง AST

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

 case class Expr(num: Int, exprOpt: ExprOpt) enum ExprOpt: case Opt(num: Int, exprOpt: ExprOpt) case Epsilon

ซึ่งคล้ายกับกฎของเรา โดยใช้คลาสข้อมูลอย่างง่าย

parser ของเราตอนนี้ส่งคืนโครงสร้างข้อมูลที่เป็นประโยชน์:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Expr = val res = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") else res private def expr(): Expr = val num = eat(Type.Num) Expr(num.text.toInt, exprOpt()) private def exprOpt(): ExprOpt = if lookahead.tpe == Type.Plus then eat(Type.Plus) val num = eat(Type.Num) ExprOpt.Opt(num.text.toInt, exprOpt()) else ExprOpt.Epsilon

สำหรับ eat() , error() และรายละเอียดการใช้งานอื่นๆ โปรดดูที่ GitHub repo ที่แนบมาด้วย

ลดความซับซ้อนของกฎ

ExprOpt nonterminal ของเรายังคงสามารถปรับปรุงได้:

 '+' NUM exprOpt | epsilon

เป็นการยากที่จะจดจำรูปแบบที่แสดงในไวยากรณ์ของเราเพียงแค่มองดู ปรากฎว่าเราสามารถแทนที่การเรียกซ้ำนี้ด้วยโครงสร้างที่ง่ายกว่า:

 ('+' NUM)*

โครงสร้างนี้หมายถึง '+' NUM เกิดขึ้นเป็นศูนย์หรือมากกว่านั้น

ตอนนี้ไวยากรณ์เต็มรูปแบบของเรามีลักษณะดังนี้:

 expr -> NUM exprOpt* exprOpt -> '+' NUM

และ AST ของเราก็ดูดีกว่า:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(num: Int)

Parser ที่ได้จะมีความยาวเท่ากันแต่ง่ายต่อการเข้าใจและใช้งาน เราได้กำจัด Epsilon ซึ่งตอนนี้มีนัยโดยเริ่มจากโครงสร้างที่ว่างเปล่า

เราไม่ต้องการคลาส ExprOpt ที่นี่ด้วยซ้ำ เราสามารถใส่ case class Expr(num: Int, exprOpts: Seq[Int]) หรือในรูปแบบไวยากรณ์ NUM ('+' NUM)* แล้วทำไมเราไม่ได้?

พิจารณาว่าถ้าเรามีตัวดำเนินการที่เป็นไปได้หลายตัว เช่น - หรือ * เราก็จะมีไวยากรณ์ดังนี้:

 expr -> NUM exprOpt* exprOpt -> [+-*] NUM

ในกรณีนี้ AST ต้อง ExprOpt เพื่อรองรับประเภทตัวดำเนินการ:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: String, num: Int)

โปรดทราบว่าไวยากรณ์ [+-*] ในไวยากรณ์หมายถึงสิ่งเดียวกับในนิพจน์ทั่วไป: "หนึ่งในสามอักขระนั้น" เราจะเห็นการดำเนินการนี้ในไม่ช้า

องค์ประกอบล่าม 3: การเขียนล่าม

ล่ามของเราจะใช้ประโยชน์จาก lexer และ parser เพื่อรับ AST ของนิพจน์อินพุตของเรา จากนั้นจึงประเมิน AST นั้นในแบบที่เราต้องการ ในกรณีนี้ เรากำลังจัดการกับตัวเลข และเราต้องการประเมินผลรวมของพวกมัน

ในการนำตัวอย่างล่ามไปใช้ เราจะใช้ไวยากรณ์ง่ายๆ นี้:

 expr -> NUM exprOpt* exprOpt -> [+-] NUM

และ AST นี้:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: Token.Type, num: Int)

(เราได้กล่าวถึงวิธีการใช้ lexer และ parser สำหรับไวยากรณ์ที่คล้ายกัน แต่ผู้อ่านที่ติดขัดสามารถอ่านการใช้งาน lexer และ parser สำหรับไวยากรณ์ที่แน่นอนนี้ได้ใน repo)

ตอนนี้เราจะมาดูวิธีการเขียนล่ามสำหรับไวยากรณ์ด้านบนนี้:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = expr.num expr.exprOpts.foreach { exprOpt => if exprOpt.op == Token.Type.Plus then tmp += exprOpt.num else tmp -= exprOpt.num } tmp

หากเราแยกวิเคราะห์ข้อมูลที่ป้อนเป็น AST โดยไม่พบข้อผิดพลาด เรามั่นใจว่าจะมี NUM อย่างน้อยหนึ่งรายการเสมอ จากนั้นเราจะนำตัวเลขที่เลือกได้และเพิ่มลงใน (หรือลบออกจาก) ผลลัพธ์ของเรา

บันทึกจากจุดเริ่มต้นเกี่ยวกับการเชื่อมโยงด้านซ้ายของ + นั้นชัดเจนแล้ว: เราเริ่มจากตัวเลขซ้ายสุดและเพิ่มจำนวนอื่นๆ จากซ้ายไปขวา นี่อาจดูไม่สำคัญสำหรับการบวก แต่ให้พิจารณาการลบ: นิพจน์ 5 - 2 - 1 ถูกประเมินเป็น (5 - 2) - 1 = 3 - 1 = 2 และไม่เป็น 5 - (2 - 1) = 5 - 1 = 4 !

แต่ถ้าเราต้องการไปไกลกว่าการตีความตัวดำเนินการบวกและลบ มีกฎอื่นที่ต้องกำหนด

ลำดับความสำคัญ

เรารู้วิธีแยกวิเคราะห์นิพจน์ง่ายๆ เช่น 1 + 2 + 3 แต่เมื่อพูดถึง 2 + 3 * 4 + 5 เรามีปัญหาเล็กน้อย

คนส่วนใหญ่เห็นด้วยกับอนุสัญญาที่ว่าการคูณมีความสำคัญมากกว่าการบวก แต่พาร์เซอร์ไม่รู้เรื่องนั้น เราไม่สามารถประเมินมันเป็น ((2 + 3) * 4) + 5 ได้ เราต้องการแทน (2 + (3 * 4)) + 5

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

แก้ไขไวยากรณ์ไร้เดียงสาตั้งแต่ต้นจนจบ

นี่คือไวยากรณ์แบบเรียกซ้ำแบบเดิมของเรา ซึ่งไม่มีกฎการมาก่อน:

 expr -> expr '+' expr | expr '*' expr | NUM

อันดับแรก เราให้ กฎของความสำคัญ และลบ ความกำกวม :

 expr -> expr '+' term | term term -> term '*' NUM | NUM

จากนั้นจะได้รับ กฎ non-left-recursive :

 expr -> term exprOpt* exprOpt -> '+' term term -> NUM termOpt* termOpt -> '*' NUM

ผลลัพธ์ที่ได้คือ AST ที่แสดงออกอย่างสวยงาม:

 case class Expr(term: Term, exprOpts: Seq[ExprOpt]) case class ExprOpt(term: Term) case class Term(num: Int, termOpts: Seq[TermOpt]) case class TermOpt(num: Int)

สิ่งนี้ทำให้เรามีการใช้งานล่ามที่กระชับ:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = eval(expr.term) expr.exprOpts.foreach { exprOpt => tmp += eval(exprOpt.term) } tmp private def eval(term: Term): Int = var tmp = term.num term.termOpts.foreach { termOpt => tmp *= termOpt.num } tmp

ก่อนหน้านี้ แนวคิดใน lexer และ grammar จำเป็นได้รับการกล่าวถึงก่อนหน้านี้ แต่ผู้อ่านสามารถค้นหาได้ใน repo หากจำเป็น

ขั้นตอนต่อไปในการเขียนล่าม

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

ในการอธิบายตัวอย่าง lexers, parsers และ interpreters เราเพียงแต่เกาพื้นผิวของทฤษฎีที่อยู่เบื้องหลังคอมไพเลอร์และล่าม ซึ่งครอบคลุมหัวข้อต่างๆ เช่น:

• ตารางขอบเขตและสัญลักษณ์
• ประเภทคงที่
• การเพิ่มประสิทธิภาพเวลาคอมไพล์
• เครื่องวิเคราะห์และ Linters โปรแกรมคงที่
• การจัดรูปแบบโค้ดและการพิมพ์ที่สวยงาม
• ภาษาเฉพาะโดเมน

สำหรับการอ่านเพิ่มเติม ผมขอแนะนำแหล่งข้อมูลเหล่านี้:

• รูปแบบการใช้งานภาษา โดย Terence Parr
• หนังสือออนไลน์ฟรี Crafting Interpreters โดย Bob Nystrom
• Intro to Grammars and Parsing โดย Paul Klint
• การเขียนข้อความแสดงข้อผิดพลาดคอมไพเลอร์ที่ดี โดย Caleb Meredith
• บันทึกย่อจากหลักสูตร East Carolina University “Program Translation and Compiling”