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

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

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

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

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

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

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

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

Take Note of the Melody (จดจำทำนอง)

"Over the Rainbow" เป็นหนึ่งในเพลงที่ได้รับความนิยมมากที่สุดในศตวรรษที่ 20 ในสหรัฐอเมริกา 1 มันถูกประพันธ์โดย Harold Arlen 2 สำหรับภาพยนตร์ The Wizard of Oz ในตอนต้นของภาพยนตร์ โดโรธี รับบทโดย Judy Garland สงสัยว่ามีที่ไหนสักแห่งที่ไม่มีปัญหา ซึ่งนำไปสู่การที่เธอร้องเพลงนี้

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

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

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

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

สิ่งที่น่าทึ่งเกี่ยวกับ music notation คือมันช่วยให้สามารถสร้างทำนองเพลงขึ้นมาใหม่ได้อย่างเที่ยงตรง แม้กระทั่งโดยคนที่ไม่เคยได้ยินมาก่อน Harold Arlen นักแต่งเพลง ผู้คิดค้นทำนองแล้วบันทึกมันโดยการเขียนลงใน music notation เพียงแค่ส่งโน้ตเพลงให้ Judy Garland เท่านี้ก็เพียงพอที่จะทำให้เธอร้องเพลงได้อย่างถูกต้อง หากไม่มีโน้ตเช่นนี้ หนทางเดียวที่จะแชร์ดนตรีคือผ่านการบันทึกเสียงหรือการบอกต่อ (hearplay?) นั่นคือการแสดงต่อหน้าผู้อื่นซึ่งจะต้องจำมันเพื่อสร้างใหม่ หากคุณเคยเล่นเกมโทรศัพท์ (telephone game) คุณจะรู้ว่ากระบวนการเช่นนี้เชื่อถือได้แค่ไหน 3

เมื่อพิจารณาการออกแบบของ staff notation เราจะสังเกตได้ว่ามันค่อนข้างจะไร้กฎเกณฑ์ แม้ว่าโน้ตจะเป็น indexical sign (ดู บทที่ 3 ) ซึ่งความสูงของมันสะท้อนถึงระดับเสียงของโน้ตที่ถูกแทน แต่ดูเหมือนจะไม่มีเหตุผลเฉพาะเจาะจง สำหรับการมีห้าเส้นในบรรทัดโน้ต การมีรูปร่างรีของโน้ต หรือความยาวและทิศทางเฉพาะของก้านโน้ต ทั้งหมดนี้อาจถูกออกแบบให้แตกต่างไปมากก็ได้ ที่จริงแล้ว บางครั้งก็ทำแตกต่างออกไป

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

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

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

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

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

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

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

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

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

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

ตาราง 8.1

Grammars (ไวยากรณ์)	Equations (สมการ)	Algorithms (อัลกอริทึม)
Nonterminal	Variable (ตัวแปร)	Parameter (พารามิเตอร์)
Terminal	Constant, operation (ค่าคงที่, การดำเนินการ)	Value, instruction (ค่า, คำสั่ง)
Sentence (ประโยค)	Fact (ข้อเท็จจริง)	Algorithm with only values (อัลกอริทึมที่มีเฉพาะค่า)
Rule (กฎ)		Instruction (คำสั่ง)

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

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

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

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

รูป 8.2 กฎของ grammar ที่นิยามการแทนที่ที่เป็นไปได้สำหรับ nonterminal ของโน้ต เนื่องจากโน้ตตามอำเภอใจ ถูกแทนด้วย nonterminal ตัวเดียว จึงต้องมีกฎแยกต่างหากสำหรับแต่ละการผสมผสานของระดับเสียงและระยะเวลา แต่ละคอลัมน์แสดงกฎสำหรับโน้ตของระยะเวลาเฉพาะ: ซ้าย , half notes (โน้ตที่กินเวลาครึ่งหนึ่งของห้องเพลง); กลาง , quarter notes; ขวา , eighth notes.

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

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

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

กฎข้อที่สอง NewMeasure คล้ายกับกฎข้อแรกและยังช่วยให้สามารถสร้าง nonterminal ของโน้ตซ้ำๆ ได้ อย่างไรก็ตาม นอกจากนี้ มันยังสร้าง terminal symbol ของบาร์ ซึ่งบ่งบอกจุดสิ้นสุดของห้องเพลงหนึ่งและจุดเริ่มต้นของห้องเพลงใหม่

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

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

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

เรายังสามารถสลับลำดับการแทนที่ของ nonterminal ของโน้ตทั้งสองตัวและยังคงได้ผลลัพธ์เดียวกัน

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

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

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

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

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

4d54 6864 0000 0006 0001 0002 0180 4d54 ⋯

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

การแปลระหว่าง notations ต่างๆ ทำได้ดีที่สุดผ่านการแทนความหมายระดับกลางที่เรียกว่า abstract syntax ซึ่งแตกต่างจาก concrete syntax ที่นิยามลักษณะที่ปรากฏ (appearance)_ทางข้อความหรือภาพของประโยค abstract syntax จะเปิดเผย _โครงสร้าง (structure) ของประโยคในรูปแบบลำดับชั้น (hierarchical) 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 เราเพียงแค่เพิ่ม node สำหรับแต่ละสัญลักษณ์ของ RHS และเชื่อมต่อมันด้วยขอบ (edge) ไปยัง nonterminal ดังนั้น แต่ละขั้นตอนของการ derivation จะขยาย abstract syntax tree โดยการเพิ่ม nodes ใหม่ไปยัง nonterminal ที่ขอบของต้นไม้ หากเราทำตาม derivation ก่อนหน้านี้ เราจะได้ลำดับของต้นไม้ดังต่อไปนี้ ซึ่งแสดงให้เห็นว่าการใช้กฎ ขยายต้นไม้ลงมาอย่างไร:

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

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

parse tree ในรูปเป็นผลลัพธ์โดยตรงของการเปลี่ยน derivation เป็นต้นไม้ มันคงรายละเอียดทั้งหมด ของ derivation ไว้ แม้แต่ส่วนที่ไม่จำเป็นสำหรับการแปลต้นไม้ไปเป็น notation อื่น ในทางตรงกันข้าม abstract syntax tree จะละเว้น terminals และ nonterminals ที่ไม่จำเป็น ต่อโครงสร้างของประโยค ตัวอย่างเช่น terminal ของบาร์ซ้ำซ้อน เนื่องจากการจัดกลุ่มโน้ตเป็นห้องเพลง ถูกจับไว้แล้วโดย nonterminal ของห้องเพลง nonterminal ของโน้ตก็ไม่จำเป็นเช่นกัน เพราะแต่ละตัวถูกขยายเป็น terminal ของโน้ตเพียงตัวเดียวเสมอ การเพิ่ม terminal ของโน้ตโดยตรง เป็นลูกของ nonterminal ของห้องเพลงก็ยังคงจับข้อมูลโครงสร้างเดียวกัน และดังนั้นจึงสมเหตุสมผล ที่จะลบ nonterminal ของโน้ตออก parse tree และ abstract syntax tree มีโครงสร้างร่วมกัน: รากทั้งสองต้นถูกกำหนดโดย nonterminal ของทำนองเพลง และใบทั้งหมดเป็น terminal symbols abstract syntax tree สะท้อนโครงสร้างของประโยคได้ตรงกว่าและเป็นพื้นฐานสำหรับการวิเคราะห์และการแปล มันยังช่วยให้นิยามความหมายของประโยคได้ง่ายขึ้น

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

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

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

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

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

การ parsing ยังเป็นขั้นตอนแรกที่จำเป็นในการกำหนดความหมายของประโยค เนื่องจากมันขึ้นอยู่กับ โครงสร้างของประโยค ซึ่งถูกแทนด้วย abstract syntax tree นี่คือข้อสังเกตที่สำคัญที่ควรกล่าวซ้ำ การจะเข้าใจประโยคหนึ่ง เราต้องสร้างโครงสร้างของประโยคในรูปแบบของ abstract syntax tree ก่อน 7 สิ่งนี้เป็นจริงเช่นเดียวกันกับการฟังเพลง การจะเข้าใจเพลง "Over the Rainbow" เราต้อง parse เสียง และระบุโน้ตต่างๆ ที่สร้างทำนองขึ้นมา นอกจากนี้ การจัดกลุ่มโน้ตเป็นห้องเพลงยังสอดคล้องกับการสังเกต การเน้นเสียงที่โน้ตและการทำความเข้าใจวลีต่างๆ ในฐานะส่วนหนึ่งของทำนอง ท้ายที่สุด การจัดโครงสร้างระดับสูงของเพลงเป็นท่อน chorus และ verse ก็เป็นกรอบในการจดจำการซ้ำและ motifs

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