Lexical analysis และ Syntax analysis

Lexical analysis และ Syntax analysis 
ในภาษาการโปรแกรม จะมีขั้นตอนของการทำ Lexical analysis และ Syntax analysis ไม่ว่าจะเป็นภาษาที่มีการนำไปใช้แบบ Compilation, Interpretation และแบบผสม  ขอยกตัวอย่างในกระบวนการต่างๆของ Compilation แสดงดังภาพ [1]

 กระบวนการที่เกี่ยวข้องกันในการตรวจสอบความถูกต้องของรูปแบบของโปรแกรมคือ
1. การสร้าง Symbol table
2. Lexical analysis
3. Syntax analysis
Symbol table เก็บข้อมูลได้แก่ Lexemes และ Token ซึ่ง Lexemes คือหน่วยเล็กที่สุดของภาษา และ Token คือข้อมูลรายละเอียดของ Lexemes

result = 3 *   number + 10;

Lexemes      Tokens
result          identifier
=               equal_sign
number       identifier
10              int_literal
*                mult_op
+                plus_op
;                 semicolon

Lexical analysis เกี่ยวข้องกับการวิเคราะห์รูปแบบนิพจน์  Lexical analyzer คือ Pattern matcher หรือตัวแมชรูปแบบ ที่พยายามหา Substring ของสตริงซึ่งแมชกับรูปแบบสตริงที่กำหนด  เช่น นิพจน์  result = 3 * number + 10; จะถูกนำไปวิเคราะห์ด้วย Lexical analysis เพื่อดูว่าภาษาสามารถสร้าง Substring ซึ่งแมชได้กับประโยคหรือไม่   ปกติแล้ว Lexical analyzer จะไม่สนใจ comment และ white space ต่างๆในโปรแกรม error ที่ตรวจพบในการวิเคราะห์ เช่น การกำหนดค่าคงที่ของ Floating point ที่ผิดรูปแบบของภาษา รูปแบบนิพจน์ เครื่องหมายต่างๆ  ชื่อตัวแปร และค่าคงที่ ซึ่งจะต้องอาศัยตาราง Symbol table ช่วยในการวิเคราะห์

แนวทางในการพัฒนา Lexical analyzer ที่นิยมเช่น 
1. การสร้าง Formal description ด้วยภาษาประเภท Descriptive language แล้วใช้เป็นเครื่องมือในการสร้าง Lexical analyzer
2. การออกแบบ State transition diagram แล้วทำการพัฒนาโปรแกรมตาม State transition diagram ที่ออกแบบ ซึ่งนิยมใช้ finite automata  (P.193)

Syntax analysis เป็นการวิเคราะห์รูปแบบของภาษา ซึ่งกระบวนการที่เกี่ยวข้องเรียกว่า Parsing โดย Parser สามารถจำแนกได้ 2 ลักษณะตามทิศทางในการทำงานคือ top-down parser และ bottom-up parser

Top-down Parser สร้าง Parse tree ในลักษณะ preorder การ parse มีลักษณะซ้ายไปขวา โดยเยี่ยมโหนดทุกโหนดจาก root ไปยัง leaf ก่อนที่จะไปโหนดข้างเคียง (โหนดเพื่อนบ้าน)
กำหนด Production rules ต่อไปนี้

A → bB
A → cBb
A → a

พิจารณาประโยค xAz
Parser ต้องเลือกกฎที่น่าจะสร้างประโยคได้ โดยพิจารณาประโยคด้านซ้าย (LHS) ของ Production rule เป็นหลัก ในที่นี้อาจจะตัดสินใจเลือก  A → a ซึ่งจะได้ xaz ซึ่งยังไม่แมชกับประโยค xAz  อย่างไรก็ตาม Parser จะต้องเลือกใช้กฎอื่นๆจนครบหรือจนกว่าจะหาได้ ในตัวอย่างนี้  xbBz, xcBbz และ xaz เป็นผลลัพธ์จากการ parse ซึ่งไม่สามารถสร้างประโยคที่ต้องการได้เลย

Bottom-up Parser ทำการสร้าง Parse tree โดยดูอักขระในประโยคที่อยู่ด้านขวา (RHS) ของ Production rule แล้วแทนที่ด้วย LHS

S → aAc
A → aA  | b
พิจารณาประโยค aabc
เมื่อดูที่ nonterminal symbol นั้น b มี nonterminal symbol ที่เกี่ยวข้องเพียงกฎเดียวดังนั้นจึงแทน LHS ของกฎในประโยค ได้  aaAc ขั้นตอนถัดไปดู RHS ที่แมชกับประโยคล่าสุดได้  aAc  ต่อด้วย S ซึ่งเป็น Start symbol หรือท้ายที่สุดจะได้ Derivation สอดคล้องกับ
S => aAc => aaAc => aabc

ไวยากรณ์
<program> → begin <stmt_list> end
<stmt_list> → <stmt>  | <stmt> ; <stmt_list>
<stmt> → <var> = <expression>
<var> → A | B | C
<expression> → <var> + <var> | <var> – <var> | <var>

 ต้องการวิเคราะห์ว่า ประโยค  begin  A=B+C ; B = C end เป็นส่วนหนึ่งของภาษาหรือไม่
แสดงได้ด้วย Parse tree ดังนี้

หมายเลขกำกับแสดงลำดับของการสร้าง path ที่สร้างขึ้น  จะเห็นว่าการสร้าง Parse tree ด้วย Top-down Parser จะพิจารณาในการต่อเติมพาธจากทางด้านซ้ายไปด้านขวา

อ้างอิง
[1] Robert W. Sebesta, "Concepts of Programming Languages", Pearson, 10th edition, 2013.