Finite State Machine, Lexical Analysis, PHP, Programming

Program Sederhana Lexical Analysis Menggunakan Bahasa Pemrograman PHP

Analisis leksikal adalah sebuah proses yang mendahului parsing sebuah rangkaian karakter. Ia menerima masukan serangkaian karakter (seperti dalam dokumen plain-text atau source code) dan menghasilkan deretan simbol yang masing-masing dinamakan token. Proses parsing akan lebih mudah dilakukan bila inputnya sudah berupa token.

Analisis leksikal terdiri dari dua tahap. Tahap pertama adalah pemindaian (scanning); scanner biasanya dibuat berdasarkan prinsip Finite State Machine (“mesin dengan jumlah keadaan terbatas”). Pada tahap ini, scanner akan membaca input karakter-ke-karakter, mengubah keadaannya sendiri berdasarkan karakter yang tengah dibaca. Setiap kondisi final (input dianggap valid) akan dicatat, bersama dengan lokasi input. Pada akhirnya scanner akan menemui keadaan penolakan, yang tidak akan berubah dengan input karakter apapun. Deteksi rekursi semacam ini akan mengakhiri proses pemindaian dan memindahkan keadaan scanner ke keadaan final terakhir, dan karenanya menyimpan informasi jenis dan besar lexeme valid yang terpanjang di dalam input.

Namun lexeme tersebut belum punya nilai semantik apapun; pemberian nilai semantik pada setiap unit leksikal adalah tugas dari evaluator yang memeriksa semua karakter setiap lexeme dan memberinya nilai tertentu. Saat sebuah lexeme telah memiliki informasi mengenai tipe dan nilainya, ia dapat secara valid disebut sebagai token.

Analisis leksikal membuat pekerjaan membuat sebuah parser jadi lebih mudah; ketimbang membangun nama setiap fungsi dan variabel dari karakter-karakter yang menyusunnya, dengan analisis leksikal parser cukup hanya berurusan dengan sekumpulan token dan nilai sintaksis masing-masing. Terlepas dari efisiensi pemrograman yang dapat dicapai dengan penggunaannya, proses kerja analisis leksikal yang membaca lebih dari sekali setiap karakter dari input yang diberikan menjadikan penganalisa leksikal sebagai sub-sistem yang paling intensif melakukan komputasi, terutama bila digunakan dalam sebuah kompilator.

Berikut adalah contoh sederhana program analisa leksikal menggunakan bahasa pemrograman php :

File ListLexer.php

<?php
require_once('lexer.php');
class ListLexer extends Lexer {
 const NAME = 2;
 const COMMA = 3;
 const LBRACK = 4;
 const RBRACK = 5;
 static $tokenNames = array("n/a", "<EOF>",
 "NAME", "COMMA",
 "LBRACK", "RBRACK" );
 
 public function getTokenName($x) {
 return ListLexer::$tokenNames[$x];
 }

 public function ListLexer($input) {
 parent::__construct($input);
 }
 
 public function isLETTER() {
 return $this->c >= 'a' &&
 $this->c <= 'z' ||
 $this->c >= 'A' &&
 $this->c <= 'Z';
 }

 public function nextToken() {
 while ( $this->c != self::EOF ) {
 switch ( $this->c ) {
 case ' ' : case '\t': case '\n': case '\r': $this->WS();
 continue;
 case ',' : $this->consume();
 return new Token(self::COMMA, ",");
 case '[' : $this->consume();
 return new Token(self::LBRACK, "[");
 case ']' : $this->consume();
 return new Token(self::RBRACK, "]");
 default:
 if ($this->isLETTER() ) return $this->NAME();
 throw new Exception("invalid character: " . $this->c);
 }
 }
 return new Token(self::EOF_TYPE,"<EOF>");
 }

 /** NAME : ('a'..'z'|'A'..'Z')+; // NAME is sequence of >=1 letter */
 public function NAME() {
 $buf = '';
 do {
 $buf .= $this->c;
 $this->consume();
 } while ($this->isLETTER());
 
 return new Token(self::NAME, $buf);
 }

 /** WS : (' '|'\t'|'\n'|'\r')* ; // ignore any whitespace */
 public function WS() {
 while(ctype_space($this->c)) {
 $this->consume();
 }
 }
}

?>

File Token.php

<?php
class Token {
 public $type;
 public $text;
 
 public function Token($type, $text) {
 $this->type = $type;
 $this->text = $text;
 }
 public function __toString() {
 $tname = ListLexer::$tokenNames[$this->type];
 return "<'" . $this->text . "'," . $tname . ">";
 }
}
?>

File test_lexer.php

<?php
require_once('ListLexer.php');
require_once('Token.php');
$input = '[ ahmad, sirojul, miftakh, UMM]';
$lexer = new ListLexer($input);
$token = $lexer->nextToken();
while($token->type != Lexer::EOF_TYPE) {
 echo $token . "<br>";
 $token = $lexer->nextToken();
}
?>

Hasil eksekusi kode program :

screen-shot-2016-12-16-at-8-13-38-pm

Terlihat bahwa input dapat dikenali berupa karakter kurung siku pembuka dan penutup, kata, dan sebagainya.

Sumber : Wikipedia

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s