ในเรื่อง Syntax analysis จะเห็นได้ว่า Parse Tree ถูกนำมาใช้ในการวิเคราะห์รูปแบบ (syntax) ของภาษาตามไวยากรณ์หนึ่งๆ ที่กำหนดขึ้น และจะเห็นได้ว่า Parse tree สามารถใช้ตรวจสอบ syntax error (error จากการเขียนประโยคที่ไม่เป็นไปตาม Grammar ของภาษา) ได้
นอกจากนี้แล้ว Compiler ยังใช้ประโยชน์ในการตรวจสอบความกำกวมของการออกแบบไวยากรณ์ของภาษาอีกด้วย กล่าวคือในการออกแบบภาษาการโปรแกรมหนึ่งๆนั้นอาจเป็นไปได้ว่าผู้ออกแบบมีการกำหนดไวยากรณ์ที่กำกวมทำให้เกิดความหมายของการประเมินผลที่มากกว่า 1 รูปแบบได้
ขอยกตัวอย่างเช่น หากภาษา Anonymous (ภาษาสมมติขึ้นมา) กำหนดว่าเครื่องหมาย + (บวก) และ * (คูณ) มีลำดับความสำคัญจากต่ำไปสูงตามลำดับ แต่ Compiler สามารถพิจารณาลำดับการประเมินผลนิพจน์จาก Parse tree พบว่าสื่อความหมาย 2 แบบ แบบแรกคือประเมินผลนิพจน์ + ก่อน * และอีก Parse tree แสดงการประเมินนิพจน์ * ก่อน +
สมมติกำหนด Grammar คือ
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> + <expr>
| <expr> * <expr>
| ( <expr> )
| <id>
A = B + C * A สามารถแสดงได้ด้วย Parse tree คือ
การท่องต้นไม้แบบ Preorder จากต้นไม้ด้านซ้ายและขวาจะได้
A = B + (C * A)
A = (B + C) * A
ซึ่งแต่ละนิพจน์จะส่งผลลัพธ์ที่มีค่าไม่เท่ากัน ดังนั้นไวยากรณ์นี้จึงมีความกำกวม ซึ่งจะต้องมีการแก้ไขต่อไป ไวยากรณ์ควรจะเป็น
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> + <term> | <term>
<term> → <term> * <factor> | <factor>
<factor> → ( <expr> ) | <id>
ซึ่งเมื่อสร้าง Parse tree แล้วจะได้เพียงรูปแบบเดียว ซึ่งมีการประเมินผลนิพจน์ด้วย * ก่อน +
ตัวอย่างไวยากรณ์ที่มีความกำกวม
<if_stmt> → if <logic_expr> then <stmt> | if <logic_expr> then <stmt> else <stmt>
<stmt> → <if_stmt>
[ทำในแบบฝึกหัด]
จาก Parse tree เราจะเห็นได้ว่า Parse tree แสดงความสำคัญของเครื่องหมายดำเนินการ (operator) หรือที่เรียกว่า Precedence rule นอกจากนี้แล้ว Parse tree ยังแสดง Associativity อีกด้วย (อ่านต่อใน Blog)
No comments:
Post a Comment