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

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

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

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

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

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

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

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

<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 และตารางลูก

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

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

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

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