การออกแบบคอมไพเลอร์ - ตารางสัญลักษณ์

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

ตารางสัญลักษณ์อาจใช้เพื่อวัตถุประสงค์ต่อไปนี้ขึ้นอยู่กับภาษาในมือ:

• เพื่อจัดเก็บชื่อของเอนทิตีทั้งหมดในรูปแบบที่มีโครงสร้างในที่เดียว

• เพื่อตรวจสอบว่ามีการประกาศตัวแปรหรือไม่

• ในการใช้การตรวจสอบประเภทโดยการตรวจสอบการกำหนดและนิพจน์ในซอร์สโค้ดนั้นถูกต้องตามความหมาย

• เพื่อกำหนดขอบเขตของชื่อ (การแก้ไขขอบเขต)

ตารางสัญลักษณ์เป็นเพียงตารางที่สามารถเป็นตารางเชิงเส้นหรือตารางแฮช จะเก็บรักษารายการสำหรับแต่ละชื่อในรูปแบบต่อไปนี้:

<symbol name,  type,  attribute>

ตัวอย่างเช่นหากตารางสัญลักษณ์ต้องเก็บข้อมูลเกี่ยวกับการประกาศตัวแปรต่อไปนี้:

static int interest;

จากนั้นควรจัดเก็บรายการเช่น:

<interest, int, static>

ประโยคแอตทริบิวต์ประกอบด้วยรายการที่เกี่ยวข้องกับชื่อ

การนำไปใช้

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

• รายการเชิงเส้น (เรียงลำดับหรือไม่เรียงลำดับ)
• ต้นไม้ค้นหาแบบไบนารี
• ตารางแฮช

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

การดำเนินงาน

ตารางสัญลักษณ์ไม่ว่าจะเป็นเชิงเส้นหรือแฮชควรมีการดำเนินการต่อไปนี้

แทรก()

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

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

ตัวอย่างเช่น:

int a;

ควรได้รับการประมวลผลโดยคอมไพเลอร์ดังนี้:

insert(a, int);

ค้นหา ()

lookup () การดำเนินการใช้เพื่อค้นหาชื่อในตารางสัญลักษณ์เพื่อกำหนด:

• หากมีสัญลักษณ์อยู่ในตาราง
• หากมีการประกาศก่อนใช้งาน
• ถ้าชื่อถูกใช้ในขอบเขต
• หากสัญลักษณ์ถูกเริ่มต้น
• หากสัญลักษณ์ประกาศหลายครั้ง

รูปแบบของฟังก์ชัน lookup () จะแตกต่างกันไปตามภาษาโปรแกรม รูปแบบพื้นฐานควรตรงกับสิ่งต่อไปนี้:

lookup(symbol)

วิธีนี้จะคืนค่า 0 (ศูนย์) หากสัญลักษณ์ไม่มีอยู่ในตารางสัญลักษณ์ หากสัญลักษณ์มีอยู่ในตารางสัญลักษณ์จะส่งคืนแอตทริบิวต์ที่เก็บไว้ในตาราง

การจัดการขอบเขต

คอมไพเลอร์รักษาตารางสัญลักษณ์สองประเภท: ก global symbol table ซึ่งสามารถเข้าถึงได้โดยขั้นตอนทั้งหมดและ scope symbol tables ที่สร้างขึ้นสำหรับแต่ละขอบเขตในโปรแกรม

ในการกำหนดขอบเขตของชื่อตารางสัญลักษณ์จะถูกจัดเรียงตามโครงสร้างลำดับชั้นดังที่แสดงในตัวอย่างด้านล่าง:

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }
. . .

โปรแกรมข้างต้นสามารถแสดงในโครงสร้างลำดับชั้นของตารางสัญลักษณ์:

ตารางสัญลักษณ์ส่วนกลางประกอบด้วยชื่อสำหรับตัวแปรส่วนกลางหนึ่งตัว (ค่า int) และชื่อโพรซีเดอร์สองชื่อซึ่งควรพร้อมใช้งานสำหรับโหนดลูกทั้งหมดที่แสดงด้านบน ชื่อที่กล่าวถึงในตารางสัญลักษณ์ pro_one (และตารางลูกทั้งหมด) ไม่สามารถใช้ได้กับสัญลักษณ์ pro_two และตารางลูก

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

• อันดับแรกสัญลักษณ์จะถูกค้นหาในขอบเขตปัจจุบันนั่นคือตารางสัญลักษณ์ปัจจุบัน

• หากพบชื่อการค้นหาจะเสร็จสมบูรณ์มิฉะนั้นจะถูกค้นหาในตารางสัญลักษณ์หลักจนถึง

• มีการค้นหาชื่อหรือตารางสัญลักษณ์ส่วนกลางสำหรับชื่อ