เราใช้ภาษาได้อย่างคล่องแคล่วในชีวิตประจำวัน โดยไม่รู้ตัวถึงกลไกซับซ้อนที่เกิดขึ้นเมื่อภาษาทำงาน เปรียบได้กับการเดิน: เมื่อเรียนรู้แล้ว เราสามารถลุยน้ำ พรวนทราย เดินขึ้นบันได และก้าวข้ามสิ่งกีดขวางได้อย่างราบรื่น ความซับซ้อนของงานจะปรากฏเมื่อเราพยายามสร้างหุ่นยนต์ให้เลียนแบบพฤติกรรมนั้น เรื่องของภาษาก็เช่นกัน เมื่อพยายามสอนเครื่องให้ใช้ภาษาอย่างมีประสิทธิภาพ เราจะพบว่ามันยากเพียงใด คุณเคยรู้สึกหงุดหงิดกับ Siri หรือค้นหาใน Google แล้วไม่เจอสิ่งที่ต้องการไหม? แบบทดสอบทัวริง (Turing test) สะท้อนสถานการณ์นี้ได้อย่างชัดเจน — ตามแบบทดสอบดังกล่าว หากผู้ใช้ไม่สามารถแยกได้ในการสนทนาว่าเป็นคนหรือเครื่อง เครื่องนั้นจะถูกถือว่ามีความฉลาด กล่าวคือ ความสามารถด้านภาษาเป็นตัวชี้วัดสำคัญของปัญญาประดิษฐ์

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

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

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

เมื่อเราต้องอธิบายว่ารถหรือดอกไม้คืออะไร เราไม่ได้พูดถึงตัวอย่างเฉพาะ แต่อธิบายถึงสิ่งที่รถหรือดอกไม้ทุกคัน/ดอกมีร่วมกัน คือแก่นแท้ของรถหรือดอกไม้ ตัวอย่างเฉพาะอาจถูกยกขึ้นมาเป็นกรณีศึกษา แต่การพูดถึงรถหรือดอกไม้ในทุกความเป็นไปได้จำเป็นต้องพัฒนา model ของสิ่งนั้น โมเดลจะกำหนด type ของรถหรือดอกไม้ทั้งหมด (ดู chapter 14)

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

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

การมองว่าดนตรีเป็นภาษาไม่ใช่แนวคิดใหม่เลย ตัวอย่างเช่น โดยอาศัยแนวคิดที่ย้อนกลับไปถึงปิทาโกรัส นักดาราศาสตร์ Johannes Kepler ใช้แนวคิดทางดนตรีเพื่ออธิบายกฎที่ควบคุมความถี่การโคจรของดาวเคราะห์ Francis Godwin เล่าในนวนิยาย Man in the Moone (1638) ว่าผู้อาศัยบนดวงจันทร์สื่อสารกันด้วยภาษาดนตรี ในภาพยนตร์ Close Encounters of the Third Kind มนุษย์สื่อสารกับเอเลี่ยนโดยใช้สเกลห้าโน้ต เนื่องจากดนตรีมีโครงสร้างสูงแต่เป็นรูปธรรมและข้ามวัฒนธรรมได้ จึงเหมาะสมที่จะใช้เป็นตัวอย่างในการอธิบายแนวคิดของภาษา

Take Note of the Melody (สังเกตทำนอง)

“Over the Rainbow” เป็นหนึ่งในเพลงที่ได้รับความนิยมมากที่สุดในศตวรรษที่ยี่สิบในสหรัฐอเมริกา[1] แต่งโดย Harold Arlen[2] สำหรับภาพยนตร์ The Wizard of Oz. ตอนต้นของภาพยนตร์ Dorothy (แสดงโดย Judy Garland) สงสัยว่ามีที่ไหนที่ไม่มีความทุกข์หรือไม่ ซึ่งนำไปสู่การร้องเพลงนี้

ถ้านี่เป็น audiobook หรือวิดีโอ YouTube คุณคงฟังเพลงได้ทันที แต่เมื่อไม่มีสื่อเสียง ฉันจะสื่อสารดนตรีให้คุณอย่างไร? ฉันสามารถแสดงการแทนรูปของดนตรีที่สามารถตีความเพื่อสร้างทำนองได้ รูปแบบหนึ่งที่ใช้กันแพร่หลายคือ standard music notation ซึ่งเรียกว่า staff notation นี่คือส่วนเล็ก ๆ ของเพลงที่แสดงในสัญกรณ์นี้:

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

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

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

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

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

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

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

Grammar Rules (กฎไวยากรณ์)

ไวยากรณ์ของภาษาสามารถกำหนดได้ด้วย grammar ซึ่งเข้าใจได้ว่าเป็นชุดกฎสำหรับสร้างประโยคของภาษา การใช้ภาษาธรรมชาติเช่นสเปนหรืออังกฤษเพื่ออธิบาย syntax ไม่ใช่ทางเลือกที่ดี เพราะคำอธิบายมักยาวและไม่แม่นยำ นี่เป็นเหตุผลว่าทำไมสมการทางคณิตศาสตร์หรือกฎทางฟิสิกส์จึงมักไม่ถูกแสดงเป็นข้อความยืดยาว แต่ใช้สัญกรณ์เฉพาะ ในความเป็นจริง หลายสาขาทางวิทยาศาสตร์และเทคนิคได้พัฒนาเทอมินอลและสัญกรณ์ของตนเองเพื่อให้สื่อสารความคิดในโดเมนนั้นได้อย่างมีประสิทธิผล และเรื่องนี้ก็เป็นจริงสำหรับการศึกษาภาษา ไม่ว่าจะเป็นในภาษาศาสตร์หรือวิทยาการคอมพิวเตอร์ หนึ่งในสัญกรณ์พิเศษที่ใช้กำหนดภาษาได้คือ grammars

ปัญหาหนึ่งในการพรรณนาภาษาคือวิธีแทนชุดประโยคที่อาจมีจำนวนอนันต์ด้วยชุดกฎที่จำกัด วิทยาศาสตร์เผชิญความท้าทายคล้ายกันเมื่อต้องอธิบายชุดความจริงที่ไม่มีที่สิ้นสุดด้วยกฎไม่กี่ข้อ วิธีแก้ของวิทยาศาสตร์ช่วยอธิบายแนวคิดของไวยากรณ์ ลองพิจารณาสมการทางฟิสิกส์ที่มีชื่อเสียง E = mc_2 ซึ่งเชื่อมพลังงาน (_E) กับมวล (m) ความหมายเชิงลึกของสมการนี้ไม่สำคัญที่นี่ สิ่งที่สำคัญคือสมการประกอบด้วยค่าคงที่ c และตัวแปรสองตัว m และ E ซึ่งสามารถแทนค่าจำนวนบวกใดๆ ก็ได้ โดยเฉพาะ ตัวแปรสองตัวนี้ทำให้สมการเดียวสามารถแทนข้อเท็จจริงทางฟิสิกส์จำนวนมากได้ ตัวแปรในสมการทำหน้าที่เช่นเดียวกับพารามิเตอร์ในอัลกอริทึม

เช่นเดียวกับสมการ ไวยากรณ์ก็มีองค์ประกอบเป็นค่าคงที่และตัวแปร ค่าคงที่เรียกว่า terminal symbols หรือ terminals ส่วนตัวแปรเรียกว่า nonterminal symbols หรือ nonterminals เหตุผลของชื่อนี้จะชัดเจนเร็วๆ นี้ ประโยคของภาษาเป็นลำดับของ terminal symbols และจะไม่มี nonterminals ซึ่งทำหน้าที่เป็นองค์ประกอบช่วยในการสร้างประโยค ในกรณีของ staff notation terminals ได้แก่ โน้ตแต่ละตัวและ bar ที่จัดโน้ตเป็น measures แน่นอนว่าสัญกรณ์มี terminal อื่นๆ แต่โน้ตและบาร์ก็เพียงพอที่จะอธิบายแนวคิดไวยากรณ์ที่จำเป็นสำหรับเมโลดี้อย่างง่าย

ตัวอย่างเช่น terminals ที่ประกอบเป็นมาตรแรกของ “Over the Rainbow” คือสัญลักษณ์โน้ตสองตัว และ ตามด้วยบาร์ เช่นเดียวกับค่าคงที่ในสมการ terminal symbol แทนส่วนคงที่ที่ไม่เปลี่ยนแปลงของประโยค และประโยคหนึ่งประโยคเทียบได้กับข้อเท็จจริงทางวิทยาศาสตร์ที่ได้จากการแทนค่าตัวแปรในสมการ

ในทางตรงกันข้าม nonterminal symbol ทำหน้าที่เหมือนตัวแปรในสมการที่สามารถรับค่าได้หลากหลาย Nonterminal สามารถถูกแทนด้วยลำดับของสัญลักษณ์อื่นๆ (ทั้ง terminal และ nonterminal) อย่างไรก็ตาม การแทนที่ไม่ใช่แบบสุ่ม ทุกการแทนที่ที่เป็นไปได้ถูกกำหนดโดยชุดกฎ Nonterminal เปรียบเสมือนตัวว่าง (placeholder) และมักใช้แทนส่วนหนึ่งของภาษา กฎการแทนที่จะกำหนดรูปลักษณ์ของส่วนนั้นในแง่ของลำดับของ terminals ตัวอย่างเช่น ในการนิยามไวยากรณ์อย่างง่ายสำหรับ staff notation เราจะพบ nonterminal ชื่อ note ที่สามารถยืนแทนสัญลักษณ์โน้ต terminal ใดๆ ได้[5]

Table 1.1

Grammars	Equations	Algorithms
Nonterminal	Variable	Parameter
Terminal	Constant, operation	Value, instruction
Sentence	Fact	Algorithm with only values
Rule		Instruction

ไวยากรณ์ประกอบด้วยหลายกฎ แต่ละกฎประกอบด้วย nonterminal ที่จะถูกแทนที่ ลูกศรแสดงการแทนที่ และลำดับของสัญลักษณ์ที่ใช้แทน nonterminal นั้น ลำดับการแทนที่นี้เรียกว่าข้างขวาของกฎ (RHS) ตัวอย่างง่ายๆ หนึ่งกฎคือ ที่นี่ RHS มีเพียง terminal หนึ่งตัว ความสัมพันธ์ระหว่างส่วนประกอบของไวยากรณ์ สมการ และอัลกอริทึมสรุปไว้ในตาราง 8.1 ไวยากรณ์ประกอบด้วยกฎ คล้ายกับที่อัลกอริทึมประกอบด้วยคำสั่งทีละคำ ในขณะที่สมการไม่มีองค์ประกอบที่เทียบเคียงได้

เนื่องจากโน้ตมีความต่างกันทั้งความถี่และความยาว และเพราะเรามีเพียง nonterminal หนึ่งตัวสำหรับโน้ต เราจึงต้องมีกฎจำนวนมากสำหรับ note ตามที่แสดงใน figure 8.2.[6] nonterminal note แทนหมวดหมู่ของโน้ตแต่ละตัว และหมวดหมู่นี้ถูกกำหนดโดยกฎทั้งหมดสำหรับ note

โดยทั่วไป RHS ของกฎสามารถประกอบด้วยสัญลักษณ์หลายตัว และสัญลักษณ์เหล่านั้นอาจเป็น terminals หรือ nonterminals ลำดับที่ประกอบด้วยเฉพาะ terminals เท่านั้นไม่สามารถถูกเปลี่ยนแปลงได้ เพราะกฎทำได้เพียงแทน nonterminals เท่านั้น นี่อธิบายชื่อทั้งสองคำ terminals และ nonterminals ลำดับที่เสร็จสมบูรณ์ของ terminals คือประโยคของภาษาที่ไวยากรณ์กำหนด ในขณะที่ลำดับที่ยังมี nonterminals อยู่คือยังไม่เสร็จและไม่ใช่ประโยคของภาษา ลำดับเช่นนี้เรียกว่า sentential form เพราะโดยทั่วไปมันอธิบายกลุ่มของประโยคที่ได้จากการแทน nonterminals ต่อไป Sentential form เปรียบเหมือนสมการที่มีตัวแปรบางตัวถูกแทนแล้ว แต่ยังมีตัวแปรอื่นเหลืออยู่ หรืออัลกอริทึมที่มีพารามิเตอร์บางตัวถูกตั้งค่าแล้วแต่ยังมีพารามิเตอร์อื่นเหลือ

Sentential forms สามารถเห็นได้ในกฎที่กำหนดเมโลดี้ Nonterminal melody แทนเมโลดี้ทั้งหมดที่ไวยากรณ์สามารถสร้างได้ ในแนวทางแรก เราสามารถกำหนดเมโลดี้ด้วยกฎสามข้อดังต่อไปนี้ (แต่ละกฎตั้งชื่อไว้เพื่ออ้างอิงภายหลัง)

Figure 8.2 กฎไวยากรณ์ที่กำหนดการแทนที่ที่เป็นไปได้สำหรับ nonterminal note เนื่องจากโน้ตทั่วไปถูกแทนด้วย nonterminal หนึ่งตัว จึงต้องมีกฎแยกสำหรับทุกการผสมของความสูง (pitch) และความยาว (duration) แต่ละคอลัมน์แสดงกฎสำหรับโน้ตที่มีความยาวแบบหนึ่ง: ซ้าย ครึ่งโน้ต (half notes); กลาง ควอเตอร์โน้ต (quarter notes); ขวา แปดโน้ต (eighth notes)

กฎแรก NewNote กล่าวว่าเมโลดี้เริ่มด้วยโน้ตบางตัวและตามด้วยเมโลดี้อีกชุดหนึ่ง อาจดูแปลกแรกๆ แต่หากเราพิจารณาว่าเมโลดี้คือลำดับของโน้ต กฎนี้บอกว่าลำดับของโน้ตเริ่มด้วยโน้ตหนึ่งตัวและตามด้วยลำดับของโน้ตอีกชุด รูปแบบของกฎดูแปลกเพราะมันแทนสัญลักษณ์ด้วย RHS ที่ประกอบด้วยสัญลักษณ์เดิมนั้นเอง กฎเช่นนี้เรียกว่า recursive ดูเหมือนว่ากฎ recursive จะไม่สามารถบรรลุการแทนที่ที่ตั้งใจจะทำ แต่ถ้าเรามีเพียงกฎ recursive สำหรับ melody จริงๆ แล้วไวยากรณ์จะมีปัญหาเพราะเราไม่สามารถกำจัด nonterminal ได้ อย่างไรก็ตาม ในตัวอย่าง กฎข้อที่สาม LastNote ไม่ใช่ recursive และสามารถใช้แทน melody nonterminal ด้วย note nonterminal ได้เสมอ ซึ่งสามารถแทนด้วย terminal note ได้ ในกรณีที่ไม่มี LastNote เราอาจใช้กฎทดแทนที่มี RHS ว่างเปล่าแทน

กฎนี้บอกให้แทน melody ด้วยลำดับว่าง (คือ ไม่มีอะไร) กฎเช่นนี้สามารถใช้เพื่อลบ nonterminal melody ออกจาก sentential form ได้อย่างมีประสิทธิผล

กฎเชิง recursive มักถูกใช้เพื่อสร้างสัญลักษณ์จำนวนหนึ่งผ่านการประยุกต์ใช้อย่างซ้ำๆ

กฎที่สอง NewMeasure คล้ายกับกฎแรกและอนุญาตให้สร้าง note nonterminals ซ้ำได้ นอกจากนี้มันยังสร้าง bar terminal ซึ่งบ่งชี้จุดสิ้นสุดของ measure หนึ่งและจุดเริ่มต้นของ measure ถัดไป

เริ่มจาก nonterminal เช่น melody เราสามารถสร้างลำดับของสัญลักษณ์ได้โดยการแทนที่ nonterminals อย่างซ้ำๆ ผ่านการประยุกต์ใช้กฎไวยากรณ์ ตัวอย่างเช่น มาตรแรกของ "Over the Rainbow" สามารถสร้างได้ดังนี้:

ลูกศรที่ติดป้ายในแต่ละบรรทัดบอกว่ากฎใดถูกใช้ เช่น เริ่มที่กฎ NewNote เพื่อสร้าง note nonterminal ตัวแรก จากนั้น nonterminal นี้ถูกแทนด้วย terminal ซึ่งแทนโน้ตแรกของเพลง กฎเฉพาะจาก figure 8.2 ที่ใช้จะแสดงด้วยการเพิ่มบอก pitch และ duration ของกฎ (เช่น C และ ½ สำหรับโน้ตที่มีความยาวครึ่งมาตรา) กระบวนการดำเนินต่อไปโดยใช้กฎ NewMeasure เพื่อสร้าง note nonterminal อีกตัว ตามด้วย bar terminal ที่จบมาตร ปัจจุบัน note nonterminal ใหม่ก็ถูกแทนด้วย terminal note ต่อไป

การตัดสินใจว่าใช้กฎใดจะกำหนดเมโลดี้ที่สร้างขึ้น โปรดสังเกตว่าลำดับการใช้กฎสามารถยืดหยุ่นได้ในระดับหนึ่ง ตัวอย่างเช่น เราอาจสลับการประยุกต์ของกฎบางตัวและยังได้ sentential form เดียวกัน

เราสามารถยุติการประยุกต์กฎโดยใช้กฎข้อที่สาม (ทั้ง LastNote หรือ EndMelody) ซึ่งจะกำจัด melody nonterminal ที่เหลืออยู่ (หากใช้ LastNote จะต้องใช้กฎ Note อีกครั้งหนึ่งเพื่อกำจัด note nonterminal ที่เกิดขึ้น) ลำดับของ terminals ที่ได้เป็นประโยคของภาษา และลำดับของ sentential forms และการประยุกต์กฎตั้งแต่ nonterminal เริ่มต้นจนถึงประโยคสุดท้ายเรียกว่า derivation ประโยคหนึ่งเป็นสมาชิกของภาษาได้ก็ต่อเมื่อมี derivation ที่สอดคล้อง การตัดสินสมาชิกภาพของประโยคในภาษาเท่ากับการหาหลักฐาน (derivation) ที่สอดคล้องกัน

หนึ่งใน nonterminals ของไวยากรณ์ถูกแต่งตั้งเป็น start symbol ซึ่งแทนหมวดหลักของประโยคที่ไวยากรณ์กำหนด nonterminal นี้ยังให้ชื่อกับไวยากรณ์ด้วย เช่น หากจุดประสงค์ของไวยากรณ์คือการกำหนดเมโลดี้ start symbol ก็ควรเป็น melody และเราสามารถเรียกไวยากรณ์นั้นว่า melody grammar ภาษาที่ไวยากรณ์ melody กำหนดคือชุดของประโยคทั้งหมดที่สามารถได้มาจาก start symbol melody

Structure Grows on Trees (โครงสร้างเติบโตบนต้นไม้)

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

ทำไมเราจึงมีภาษาต่างๆ มากมายทั้งที่มีต้นทุนมหาศาล? บ่อยครั้งภาษาถูกนำมาใช้เพราะมันตอบโจทย์เฉพาะบางอย่าง ตัวอย่างเช่น HTML หรือ JavaScript ช่วยแทนข้อมูลบนอินเทอร์เน็ต ซึ่งมีประโยชน์ต่อองค์กรจำนวนมาก ในโดเมนดนตรี แท็บทำงานได้ดีกับนักกีตาร์หลายคน โดยเฉพาะผู้ที่ไม่รู้จัก staff notation เมื่อมีเครื่องดนตรีโปรแกรมได้ (เช่น sequencers และ drum machines) ภาษาที่ชื่อ MIDI (Musical Instrument Digital Interface) ถูกพัฒนาขึ้นเพื่อเข้ารหัสข้อความควบคุมให้ synthesizers สร้างเสียง นี่คือตัวอย่างเริ่มต้นของเวอร์ชัน MIDI ของ “Over the Rainbow”:

4d54 6864 0000 0006 0001 0002 0180 4d54 ⋯

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

การแปลระหว่างสัญกรณ์ต่างๆ ทำได้ดีที่สุดโดยใช้ตัวแทนกลางที่เรียกว่า abstract syntax ตรงกันข้ามกับ concrete syntax ซึ่งกำหนดรูปลักษณ์ทางข้อความหรือภาพของประโยค abstract syntax เปิดเผยโครงสร้างของประโยคในรูปแบบลำดับชั้น Concrete syntax ของชิ้นงานดนตรีใน staff notation ถูกกำหนดด้วยลำดับของโน้ต บาร์ และสัญลักษณ์อื่นๆ ซึ่งไม่เพียงพอที่จะจับโครงสร้างเชิงลำดับชั้นของชิ้นงาน สำหรับเรื่องนี้เราสามารถใช้ trees ซึ่งได้ใช้ในบท 4 และ 5 เพื่อแทนลำดับชั้น Abstract syntax ถูกแทนโดย abstract syntax tree

การเปลี่ยนจาก concrete syntax เป็น abstract syntax tree ทำได้ในสองขั้นตอน ขั้นแรก ลำดับสัญลักษณ์ใน concrete syntax ถูกแปลงเป็น parse tree ซึ่งจับความสัมพันธ์เชิงลำดับชั้นระหว่างสัญลักษณ์ ขั้นที่สอง parse tree ถูกทำให้เรียบง่ายเป็น abstract syntax tree Parse tree สามารถถูกสร้างควบคู่กับการ derivation ของประโยค จำไว้ว่าในแต่ละก้าวของการ derivation จะมีการแทน nonterminal ด้วย RHS ของกฎสำหรับ nonterminal นั้น ตอนนี้ แทนที่จะแทน nonterminal ด้วย RHS เราเพิ่มโหนดสำหรับแต่ละสัญลักษณ์ของ RHS และเชื่อมมันด้วยขอบกับ nonterminal ด้วยวิธีนี้ ในแต่ละก้าวของการ derivation ต้นไม้ abstract syntax จะถูกขยายโดยการเพิ่มโหนดใหม่ให้กับ nonterminal ที่ขอบของต้นไม้ หากเราเดินตาม derivation ก่อนหน้า เราจะได้ลำดับของต้นไม้ดังต่อไปนี้ ซึ่งแสดงว่าเมื่อใช้กฎจะขยายต้นไม้ลงด้านล่างได้อย่างไร

ขั้นตอนทั้งสองนี้เรียบง่ายและตรงไปตรงมา สองขั้นตอนถัดไปนำไปสู่ผลลัพธ์ที่ค่อนข้างคาดไม่ถึงเพราะ parse tree ไม่ได้เปิดเผยโครงสร้างของเพลง Parse tree ไม่แสดงว่าเมโลดี้ประกอบด้วย measures และ measures ประกอบด้วยโน้ตได้อย่างไร

สาเหตุที่ขาดโครงสร้างเป็นผลมาจากการกำหนดไวยากรณ์ก่อนหน้านี้: กฎของมันขยายเมโลดี้เป็นลำดับของโน้ต ดังนั้นไม่แปลกใจเลยที่ parse tree จะไม่กล่าวถึง measures โดยการเปลี่ยนการนิยามไวยากรณ์ให้คำนึงถึง measures เราสามารถแก้ไขสถานการณ์ได้ Figure 8.3 แสดงส่วนของ parse และ abstract syntax trees ในวิทยาการคอมพิวเตอร์ ต้นไม้ถูกวาดโดยคว่ำหัว (root อยู่ด้านบน และ leaves อยู่ด้านล่าง) Nonterminals เป็นตำแหน่งที่มีการแตกกิ่งในต้นไม้ และ terminals ปรากฏเป็นใบของต้นไม้

Parse tree ในรูปเป็นผลทันทีจากการเปลี่ยน derivation เป็นต้นไม้; มันเก็บรายละเอียดทั้งหมดของการ derivation แม้แต่ส่วนที่ไม่จำเป็นต่อการแปลต้นไม้เป็นสัญกรณ์อื่น ในทางตรงกันข้าม abstract syntax tree ละเว้น terminals และ nonterminals ที่ไม่จำเป็นต่อโครงสร้างของประโยค ตัวอย่างเช่น bar terminals เกินความจำเป็น เพราะการจัดกลุ่มโน้ตเป็น measures ถูกจับโดย measure nonterminals อยู่แล้ว Nonterminal ของโน้ตก็ไม่จำเป็นเช่นกัน เพราะแต่ละตัวมักขยายเป็น terminal note เพียงตัวเดียว การเพิ่มโน้ต terminal โดยตรงเป็นลูกของ measure nonterminals ให้ข้อมูลโครงสร้างเดียวกันและจึงเป็นเหตุผลให้เอา note nonterminals ออก Parse tree และ abstract syntax tree มีโครงสร้างร่วมกัน: ทั้งคู่มี root เป็น melody nonterminal และใบทั้งหมดเป็น terminal symbols Abstract syntax tree สะท้อนโครงสร้างของประโยคอย่างตรงไปตรงมามากกว่าและเป็นพื้นฐานสำหรับการวิเคราะห์และการแปล; มันยังช่วยในการกำหนดความหมายของประโยค

Figure 8.3 โครงสร้างของเมโลดี้ที่แสดงโดย syntax trees ต้นไม้ syntax จับผลโครงสร้างของการ derivation แต่ละต้นจะละรายละเอียด เช่น ว่ากฎใดถูกใช้ตามลำดับ ซ้าย: parse tree ซึ่งเก็บรายละเอียดทั้งหมดของการ derivation ขวา: abstract syntax tree ซึ่งตัดรายละเอียดที่ไม่จำเป็นออกและเก็บเฉพาะข้อมูลที่สำคัญต่อโครงสร้าง

กระบวนการสร้าง parse tree หรือ abstract syntax tree สำหรับประโยคหนึ่งๆ เรียกว่า parsing ความสัมพันธ์ระหว่างประโยค ต้นไม้ syntax และ parsing ถูกอธิบายไว้ใน figure 8.4 Parsing คือการคำนวณชนิดหนึ่งซึ่งมีอัลกอริทึมหลายแบบ ในขณะที่ไวยากรณ์ให้คำนิยามชัดเจนว่าประโยคใดอยู่ในภาษา การ parsing ยังต้องการยุทธศาสตร์สำหรับการแปลงประโยคที่กำหนดให้เป็น syntax tree ความยากของ parsing อยู่ที่การตัดสินใจเลือกกฎไวยากรณ์ใดระหว่างการวิเคราะห์ประโยค มียุทธศาสตร์ต่างๆ ในการ parsing หนึ่งที่เราเห็นคือ top-down parsing ซึ่งเริ่มจาก start symbol ของไวยากรณ์และประยุกต์กฎซ้ำๆ เพื่อขยายต้นไม้ syntax โดยขยาย nonterminals จนกระทั่งประโยคปรากฏเป็นลำดับของ terminals ในใบของต้นไม้ ในทางตรงกันข้าม bottom-up parsing พยายามแมตช์ RHS ของกฎในประโยคและประยุกต์กฎย้อนกลับ จุดมุ่งหมายคือสร้างต้นไม้ syntax โดยเพิ่ม nonterminals ที่เป็นด้านซ้ายของกฎที่ตรงกันเป็นพาเรนต์ของต้นไม้ ทำซ้ำจนได้ต้นไม้ที่มีรากเดียว

Figure 8.4 Parsing คือกระบวนการระบุโครงสร้างของประโยคและแทนมันเป็น syntax tree Pretty printing แปลง syntax tree ให้เป็นประโยค เนื่องจาก abstract syntax tree อาจละ terminals บางตัว (เช่น bar) การ pretty printing ไม่สามารถรวบรวม terminals จากใบของต้นไม้เพียงอย่างเดียวได้ แต่โดยทั่วไปต้องใช้กฎไวยากรณ์เพื่อแทรก terminals เพิ่มเติม ลูกศร parsing หายไปสำหรับ notation แบบ tablature เพราะเป็นสัญกรณ์ที่คลุมเครือและจึงไม่อนุญาตให้สร้าง abstract syntax tree ที่เป็นเอกพจน์ได้

กระบวนการย้อนกลับ คือการแปลง syntax tree ให้เป็น concrete syntax เรียกว่า pretty printing ซึ่งโดยมากเป็นการคำนวณที่ตรงไปตรงมา เพราะโครงสร้างของประโยคถูกให้ไว้แล้วและให้แนวทางในการสร้างการแทนรูปแบบ concrete

ด้วยการ parsing และ pretty printing เรามีเครื่องมือที่จำเป็นเพื่อแปลระหว่างภาษา การแปลระหว่างสองภาษาที่มี abstract syntax เดียวกันได้มาจากการ parse ประโยคในภาษาแรกและใช้ pretty printing สำหรับภาษาที่สอง ตัวอย่างเช่น ใน figure 8.4 เราจะเห็นวิธีไปจาก staff notation เป็น tablature โดยการ parse ประโยคใน staff notation ก่อน แล้วใช้ tablature pretty printer กับ abstract syntax tree ที่ได้ การแปลระหว่างภาษาที่ไม่มี abstract syntax ร่วมกันต้องการการเปลี่ยนแปลงเพิ่มเติมระหว่าง abstract syntax trees

Parsing ยังเป็นขั้นตอนแรกที่จำเป็นในการกำหนดความหมายของประโยค เพราะความหมายขึ้นอยู่กับโครงสร้างของประโยคซึ่งแทนด้วย abstract syntax tree นี่เป็นข้อสังเกตสำคัญที่ควรย้ำอีกครั้ง ในการเข้าใจประโยคหนึ่งต้องตั้งโครงสร้างของประโยคนั้นในรูปของ abstract syntax tree ก่อน[7] สิ่งเดียวกันเป็นจริงกับการฟังดนตรี เพื่อเข้าใจเพลง “Over the Rainbow” ต้อง parse เสียงและระบุโน้ตต่างๆ ที่ก่อให้เกิดทำนอง นอกจากนี้ การจัดกลุ่มโน้ตเป็น measures เกี่ยวข้องกับการสังเกตการเน้นโน้ตและการตีความวลีในบริบทของทำนอง สุดท้าย การจัดโครงสร้างระดับสูงของเพลงเป็นท่อนคอรัสและบทช่วยให้กรอบในการจำแนกการทำซ้ำและ motif

เนื่องจาก syntax trees เป็นทางเข้าไปสู่ความหมายของประโยค คำถามจึงเกิดขึ้นว่า parsing จะสำเร็จเสมอหรือไม่และจะเกิดอะไรขึ้นกับความเข้าใจของประโยคถ้า.[8] ประโยคก่อนหน้านี้ (ที่ไม่ใช่ประโยค) ขาด syntax tree จึงไม่มีความหมายชัดเจน แต่จะเกิดอะไรขึ้นถ้าเราสร้าง หลาย syntax trees สำหรับประโยคเดียวกันได้? คำถามนี้จะถูกพิจารณาใน chapter 9