Code Editor ทำ Syntax highlight ยังไง

ปกติแล้วพอเปิด Editor มาตอนเขียนโค้ด แล้วถ้าลองเขียนอะไรเล่นๆ แบบโค้ดภาษา C ข้างล่างนี้ เราก็จะพอเห็นว่า คำว่า int มันมีสีนึง แล้วเลข 4 กับ 6 ก็เป็นอีกสีนึงใช่มะ

1
int a = 4 + 6;

แล้วตัว Editor มันรู้ได้ไงว่าต้องใส่ int เป็นสีนั้น แล้วตัวเลขเป็นอีกสีนึงล่ะ?

คำตอบคือมันสร้างต้นไม้มาต้นนึงเพื่อใช้แทนว่าโค้ดบรรทัดนั้น(หรือหลายบรรทัด) มีโครงสร้างยังไง และต้นไม้นี้เรียกว่า Abstract Syntax Tree(AST)

Abstract Syntax Tree (AST)

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

ตัวอย่างการแบ่งต้นไม้ AST จากโค้ดข้างบน:

AST ที่แตกออกมาจากโค้ด int a = 4 + 6 ต้นไม้ AST ที่แบ่งออกมาจากตัวโค้ด

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

แต่เรายังไม่ได้คุยเลยว่า แล้ว AST มันรู้ได้ไงว่าต้องแบ่งแบบไหน ถ้ามันแบ่งมั่วๆ ก็คงจะได้ต้นไม้หน้าตาประหลาดๆที่ใช้อะไรไม่ได้ใช่ไหมล่ะ

มันต้องมีกฎการแบ่งอะไรสักอย่างเพื่อให้มันแบ่งได้ถูกต้อง แล้วกฎที่ว่านั้นเรียกว่า Context-Free Grammar หรือ CFG

Context-Free Grammar

แล้วมันคืออะไร?

Context-Free Grammar หรืออีกชื่อนึงว่า CFG เป็นหนึ่งในวิธีการสร้างรูปแบบของข้อมูล ที่เกิดจากการกำหนดกฎต่างๆ ขึ้นมาเพื่อบอกว่า อะไรต้องประกอบด้วยอะไรบ้าง

อย่างเช่น if statement ต้องประกอบไปด้วย คำว่า if, ตัวเงื่อนไขที่จะเปรียบเทียบ, สิ่งที่จะทำถ้าเข้าเงื่อนไข และ สิ่งที่จะทำถ้าไม่เข้าเงื่อนไข (ไม่จำเป็น) ตอนเอามาเขียนเป็นกฎก็จะได้ประมาณนี้:

\text{IF} \rightarrow \text{if}( \text{Condition}) \{\text{Expr}\} \\ \text{IF} \rightarrow \text{if}( \text{Condition}) \{\text{Expr}\} \text{else} \{\text{Expr}\}

ซึ่งแปลว่า $\text{IF}$ เนี่ยสามารถแปลงตัวเองกลายเป็น คำว่า if ตามด้วย ประโยคที่เป็นประเภท Condition แล้วตามด้วยประโยคประเภท $\text{Expr}$ หรือ

เหมือนเดิมแค่เพิ่ม คำว่า else ตามหลังมาด้วย แล้วต่อด้วย $\text{Expr}$ อีกตัว

และในที่นี้ ทั้ง $\text{Condition}$ และ $\text{Expr}$ ก็สามารถไปแปลงต่อเพื่อเป็นประโยคอื่นๆต่อได้อีก

ถ้าเอาแบบ Formal หน่อยๆ ก็ตัวกฎจะประกอบไปด้วย 4 ส่วนด้วยกัน:

$V$ เป็นเซตของตัวแปรที่สามารถถูกเปลี่ยนเป็นตัวอื่นๆ ได้ (Non-terminal character) อย่างเช่น $\text{IF, Condition, Expr}$ (ซึ่งโดยมากใช้เป็นตัวพิมพ์ใหญ่)
$Σ$ เป็นเซตของตัวอักษรที่ไม่สามารถเปลี่ยนเป็นตัวอื่นๆ ได้อีก (Terminal character) เช่นคำว่า $\text{if, else}$
$R$ เป็นเซตของกฎที่จะบอกว่า ตัวแปรแต่ละตัวสามารถเปลี่ยนเป็นลักษณะยังไงได้บ้าง เช่น $A\rightarrow aA$ หรือ $B\rightarrow BAa$ โดยที่ฝั่งซ้ายจะเป็น non-terminal character แค่ตัวเดียวเท่านั้น เพื่อบอกว่าจะแปลงส่วนไหนไปเป็นอะไรได้บ้าง โดยที่ไม่มีเงื่อนไขอื่นๆ มาเกี่ยวข้อง
สุดท้ายคือ $S$ ที่เป็นตัวแปรที่จะเริ่มต้นในการเปลี่ยน และเป็นหนึ่งใน $V$ ด้วย

ลองดูตัวอย่างประโยคจากการสร้างด้วย CFG กันสักหน่อย:

ถ้าเราให้

\begin{aligned}V & = \{N,S\}\\ \Sigma & = \{\text{`apple'},\text{`orange'},\text{`there's one'}\} \\R & = \{\text{N} \rightarrow \text{`apple'} | \text{`orange'}, S \rightarrow \text{`there's one'} \text{ N}\} \\S &= S\end{aligned}

ก่อนอื่นเราก็เริ่มจากตัวแปร Non-terminal ตัวแรกคือ $S$ หลังจากนั้นก็ค่อยๆแปลงต่อไปเรื่อยๆ จะได้ว่า:

\begin{aligned} S & \rightarrow \text{there's one} \text{ N}\\ & \rightarrow \text{there's one apple} \end{aligned}

หรือถ้าเราไม่ได้แปลง $N$ เป็น apple แต่เป็น orange แทนก็จะได้ว่า

\begin{aligned} S & \rightarrow \text{there's one} \text{ N}\\ & \rightarrow \text{there's one orange} \end{aligned}

ทำให้จากกฎที่เราตั้งมาก่อนหน้านี้ เราสามารถสร้างประโยคขึ้นมาได้สองแบบคือ “there’s one apple” กับ “there’s one orange”

และเพราะตัวกฎของ CFG เนี่ย ทางฝั่งซ้ายจะต้องเป็นตัวแปรแบบ Non-terminal อย่างเดียว ทำให้เราไม่ต้องสนใจว่าตัวก่อนหน้านั้นหรือตัวหลังจากนั้นคืออะไร เราแค่ไล่แปลงตัว Non-terminal อย่างเดียวก็พอ ซึ่งถ้ามี Non-terminal หลายตัว เราจะแปลงตัวไหนก่อนก็ได้เพราะทุกตัวไม่ส่งผลถึงกัน

เดี๋ยวเรามาดูตัวอย่างอื่นที่มันไม่ยากนักกันก่อน

ภาษาวงเล็บสมดุล

วงเล็บสมดุลคือวงเล็บที่จับคู่เปิด-ปิดได้ทุกคู่วงเล็บ เช่น $()(),(()())$ ส่วนตัวอย่างที่ไม่เป็นวงเล็บสมดุลเช่น $)()(,(()$

ทีนี้เราสามารถสร้างตัว CFG ผ่านการกำหนดกฎการแปลงตัวอักษรได้ดังนี้

S\rightarrow SS \\ S\rightarrow (S) \\ S\rightarrow ()

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

สมมติเราจะดูวงเล็บ $(()(()))$ จะมีขั้นตอนตามนี้

S\rightarrow (S) \\ (S)\rightarrow (SS) \\ (SS)\rightarrow (()S) \\ (()S)\rightarrow (()(S)) \\ (()(S))\rightarrow (()(()))

ซึ่งเราเห็นว่ามันแปลงได้ ก็แปลว่า”ประโยค”นี้สามารถเข้ากันได้กับ กฎที่เราตั้งไว้ ซึ่งก็แปลว่าเราสามารถแปลงมันให้กลายเป็นต้นไม้ AST ได้

Syntax Highlighting

พอมันอยู่ใน Editor กฎที่ใช้ก็มากขึ้นตามๆ ไป (ไม่เหมือนแค่จับคู่วงเล็บ) เพราะต้องจับ pattern หลายๆ อย่าง แล้วแต่ละภาษาก็มี pattern ของตัวเองที่ต่างกันไป

ซึ่งเราก็เอาตัวนี้นี่แหละไปทำการสร้างตัวของ AST เพื่อทำ syntax highlighting ให้ต้นไม้แบ่งได้ตรงตามประเภทและสีที่ต้องการ highlight และเจ้าตัวนี้ก็กลายมาเป็นส่วนนึงของ Code Editor ที่เราใช้ๆ กันอยู่ (และคงชินแล้ว)ในปัจจุบันอ่ะนะ