The Lexical Analysis Driver (Scanner)

For lexical analysis , we can consider  the input  source program as a long sequence of characters with two pointers:  a current pointer and a lookahead pointer.

When lexical analysis begins to find the next token, current and lookahead both point to the same character:

In the algorithm , four actions will be performed on these pointers:

1.GetChar : Moves the lookahead pointer ahead one character and returns.

2.Retract : Moves the lookahead pointer back one character.

3.Accept : Moves the current pointer ahead to the lookahead pointer.

4.Return : Returns a token consisting of a class and value , as well as performs any actions associated with that state , e.g., installing an identifier into the name table.

The driver program scans the input program and consults the entry at Table[State,InputChar] for the new state. The entry at Table[State,InputChar] consists of a new state and perhaps an action to be performed before moving to the new state:

Algorithm : Driver for Lexical Analysis

WHILE there is more input

     InputChar := GetChar

     State := Table[0,InputChar]

     WHILE State <> Blank

          InputChar := GetChar

          State := Table[State,InputChar]

     ENDWHILE

     Retract

     Accept

     Return token = (Class,Value)

ENDWHILE

In the algorithm for the lexical analysis driver , retract is neccessary when a token is found because the algorithm will have scanned one character too far.

The Lex & Yacc

compiler หรือ interpreter สำหรับภาษาโปรแกรม(programming language) นั้นโดยปกติแล้วจะแบ่งออกเป็น 2 ส่วนคือ

1. ส่วนที่ใช้ในการอ่าน Source Program และตรวจสอบโครงสร้างหรือ Structure ของตัว Source Program
2. เป็นส่วนที่ใช้จัดการกับ Structure ของ Source Program

สิ่งที่ Lex และ Yacc ทำคือ

1. ตัดคำหรือแบ่ง Source file ออกเป็น token ย่อยๆ (Lex)
2. ตรวจสอบไวยากรณ์ของภาษาโปรแกรม โดยวิเคราะจากโครงสร้างที่แตกย่อยออกมาของ program (Yacc)

Lex – A Lexical Analyzer Generator

Lex นี้จะช่วยตัดคำ(Token) ของ source program จากการกำหนดโดย regular expressions ที่ได้รับมาจาก input stream แล้วส่งไปให้ parser ทำงานต่อ โดย source ของ Lex นี้ก็คือตาราง regular expressions และ คำหรือ Token ต่างๆที่ถูกกำหนดเอาไว้ในภาษาโปรแกรมที่ออกแบบไว้ โดยตารางนี้จะถูก translated เป็น program ที่จะใช้ในการอ่านข้อมูลจาก input stream โดยจะตัดคำ(Token) ที่ตรงกับ expressions ที่ได้กำหนดเอาไว้ โดย expression นี้จะถูกกำหนดโดย DFA หรือ deterministic finite automaton generated โดย Lex

 Yacc: Yet Another Compiler-Compiler

Yacc คือ tool ที่ใช้สำหรับอธิบายข้อมูลอินพุทให้กับ computer program ซึ่งผู้ที่ใช้ Yacc นี้จะกำหนดโครงสร้าง(Structure) ของข้อมูล input รวมไว้กับ code ที่จะถูกเรียกเอาไว้สำหรับในแต่ละ structure ที่ตรงกันสำหรับจัดการกับข้อมูลอินพุท โดยจะแบ่งออกเป็น subroutine ย่อยๆเอาไว้

 

เนื่องจาก lex กับ yacc มันเก่าแล้ว ก็เลยมีคนพัฒนา tool ตัวใหม่ๆออกมาหลายตัวดัวยกัน แต่สำหรับเอง ผมใช้

• flex อันนี้ใช้สำหรับ lex
• bison อันนี้ใช้สำหรับ yacc

*flex = lex,bison = yacc

ซึ่ง tool สองอันนี้เป็น OpenSource จึงสามารถนำมา compile และติดตั้งบน Linux ได้โดยไม่มีปัญหา

Flex,A fast scanner generator

Flex เป็น tool สำหรับสร้าง scanner (scanner generator) โดยprogramที่จะได้รับการยอมรับนั้นจะต้องตรงตาม lexical patterns โดยการทำงานของ flex นี้จะเริ่มจากการอ่านข้อมูล input จาก file เข้ามาหรือผ่านทาง stardard input ถ้าไม่มีการส่ง file name ให้กับ flex เพื่อใช้การอธิบายข้อกำหนดต่างๆ ก่อนที่จะทำการ generate scanner code ออกมา ดังนั้นก่อนที่จะใช้เจ้า flex นี้ได้ เราจะต้องมีการกำหนด regular expressions และชุดคำสั่งภาษา C ซึ่งเราจะเรียกว่า “RULES “ หลังจากที่กำหนด rules ต่างๆเรียบร้อยแล้วจึงใช้ flex นี้เป็น code generator ที่เราจะใช้เป็น scanner สำหรับตัดคำนั้นเอง โดย flex นี้จะ gen. ไฟล์ออกเป็นเป็นไฟล์ภาษา C ที่ชื่อว่า “lex.yy.c” ซึ่งใน file นี้จะมี routine ‘yylex()’ อยู่ภายใน จากนั้นก็เอาไฟล์ที่ได้มานี้ไปทำการ compile กับ c compiler ได้ออกมาเป็น executable ไฟล์สำหรับใช้งานอีกทีนึง

Bison, The Yacc-Compatible Parser Generator

Bison คือ parser generator ที่แปลงส่วนอธิบาย grammar ของ LALR context-free grammar (LALR parser generator เป็น software tool ที่ใช้ในการอ่าน BNF Grammar เข้ามาแล้ว generate code ให้เป็น LALR parser) ออกมาเป็น C program ที่ใช้ในการวิเคราะห์ไวยากรณ์

*Bison นี้ถูกพัฒนามาจาก Yacc ซึ่งการเขียน Yacc Grammar นี้จะสามารถนำไปใช้ได้กับ Bison ได้โดยไม่ต้องมีการเปลี่ยนแปลงเลย ซึ่งทำให้ผู้ที่มีความคุ้นเคยกับ Yacc นั้นสามารถเปลี่ยนมาใช้ Bison ได้โดยง่าย

วันนี้ง่วงนอนแระ เอาไว้รอบหน้าผมจะเอา Flex/Bison มาอธิบายให้ฟังกันอย่างละเอียดกันไปเลยทีเดียวละกันนะคับ อิอิ