Membuat Parser LISP (delphi)

Beberapa hari yang lalu saya membuat parser untuk LISP. Lebih tepatnya LISP-like syntax karena saya membuatnya untuk melakukan parsing terhadap CLIPS (C Language Integrated Production System) yaitu shell untuk sistem berbasis pengetahuan (sistem pakar). Parser ini digunakan untuk membuat antarmuka Desktop(GUI) untuk sistem pakar yang dibuat dengan CLIPS.

Kodenya dibuat masih belum dioptimasi, struktur proses yang direalisasi dibuat menjadi dua kelas yaitu LISPLexer dan LISPParser sedangkan struktur yang menampung representasi list-nya sendiri menjadi satu kelas LISPNode. OK, let’s jump to the code. kita mulai dari LISPNode.

TLISPNode
List di LISP sebetulnya dinotasikan sebagai S-Expression. jadi List seperti ini

(a b)
(a b c)
(a (b))

sebetulnya dalam notasi S-expression akan menjadi seperti ini

(a.(b.NIL))
(a.(b.(c.NIL)))
(a.((b.NIL).NIL))

setiap pasangan (a.t) merupakan sebuah simpul dengan a adalah head dan t adalah tail. Setiap simpul dapat merupakan atom/nilai atomik (number, symbol, string) atau list (pointer ke s-expression lainnya, seperti pada baris ke-tiga). Berikut ini deklarasi kelas TLISPNode.

type
  TLISPNodeType = (ntAtom, ntList);
  TLISPAtomType = (atSymbol, atString, atNumber);
  TLISPNode = class
  protected
    vtype     : TLISPNodeType;
    Fatomtype  : TLISPAtomType;
    atomval   : string;
    Fchild : TLISPNode;
    Fnext : TLISPNode;
  public
    constructor Create;
    destructor Free;
    function ToString:string;
    function Clone : TLISPNode;
    function GetHead : TLISPNode;
    function GetTail : TLISPNode;
    property Child : TLispNode read FChild write FChild;
    property Next : TLispNode read FNext write FNext;
    property Value : string read atomval write atomval;
    property NodeType : TLISPNodeType read vtype write vtype;
    property AtomType : TLISPAtomType read FAtomType write FAtomType;
  end;

Keterkaitan antar simpul dibuat sebagai list satu arah yang menunjuk ke sibling dan child (jika simpul tersebut bukan atom).

TLISPLexer
kelas LISPLexer berfungsi untuk melakukan pemisahan string menjadi bagian-bagian yang diberi label (token). Pemisahan dan pemberian label ini disebut juga sebagai analisis leksikal. Hal yang dilakukan sebetulnya dapat dibilang parsing, namun tujuannya lebih sederhana (tanpa pohon sintaks yang rumit). Kode interface bagian Lexer ditunjukkan dalam potongan kode berikut.

const
  HTAB = #9;
  CRLF = #10#13;
  LBRA = '(';
  RBRA = ')';
  DQUO = '"';
  S_ALPHA = ['a'..'z','A'..'Z'];
  S_DIGIT = ['0'..'9'];
  S_ALNUM = S_ALPHA+S_DIGIT;
  S_WHITE = [' ',HTAB,#10,#13];

type
  TTokenType = (ttString, ttSymbol, ttNumber, ttLBRACKET, ttRBRACKET);
  TToken = record
    tokentype : TTokenType;
    sym : string;    
  end;

  TLispLexer = class
  private
    function GetCount: integer;
  protected
    FToken : array of TToken;
    FPita : string;
    FIdx : integer;
    function GetToken(tid : integer):TToken;
    procedure Proses;
    procedure skipwhite;
    function iswhite(c:char):boolean;
    function isalpha(c:char):boolean;
    function isalnum(c:char):boolean;
    function isdigit(c:char):boolean;
    procedure SetPita(const Value: string);
    procedure add_token(toktype: TTokenType; tokval:string);
  public
    constructor Create;overload;
    constructor Create(inputstring: string);overload;
    destructor Free;
    procedure Clear;
    function dumptoken(t:ttoken):string;
    function dump:string;
    property Token[tid : integer]: TToken read GetToken;
    property Pita: string read FPita write SetPita;
    property Count : integer read GetCount;
  end;

Tipe token untuk LISP untungnya cukup sederhana, karena pemisah antar ‘kata’-nya hanya whitespace dan tanda kurung ‘(‘ dan ‘)’. Bagian yang perlu diperlihatkan di sini adalah di prosedur proses.

procedure TLispLexer.Proses;
var
  cur_kata : string;
  cc : char;
  cur_token : TTokenType;
begin
  if length(FPita)=0 then exit;
  FIdx := 1;
  cur_kata := '';
  cur_token := ttLBRACKET;
  skipwhite;
  while (FIdx <= length(FPita)) do begin
    cc := FPita[FIdx];
    case cc of
      LBRA:add_token(ttLBRACKET, cc);
      RBRA:add_token(ttRBRACKET, cc);
      DQUO:begin
        inc(FIdx);
        cur_kata := '';
        while (FIdx <= length(FPita)) and (FPita[FIdx] <> DQUO) do begin
          cur_kata := cur_kata + FPita[FIdx];
          inc(FIdx);
        end;
        add_token(ttString, cur_kata);
      end;
      'a'..'z','A'..'Z':begin
        cur_kata := '';
        while (FIdx <= length(FPita)) and (FPita[FIdx] in S_ALNUM+['-']) do begin
          cur_kata := cur_kata + FPita[FIdx];
          inc(FIdx);
        end;
        dec(FIdx);
        add_token(ttSymbol, cur_kata);
      end;
      '0'..'9','-':begin
        cur_kata := '';
        while (FIdx <= length(FPita)) and (FPita[FIdx] in S_DIGIT+['-','e','E','.']) do begin
          cur_kata := cur_kata + FPita[FIdx];
          inc(FIdx);
        end;
        dec(FIdx);
        add_token(ttNumber, cur_kata);
      end;
    end;
    inc(FIdx);
    skipwhite;
  end;
end;

TLISPParser
Setelah string karakter dipisahkan dan diberi label menjadi list token, maka proses selanjutnya adalah menterjemahkan deretan token ini menjadi struktur list yang sesuai. Berikut ini deklarasi kelas LISPParser. Method utama yang diperlukan adalah fungsi ParseNode yang diantar oleh fungsi umum Parse.

type
  TLISPParser = class
  protected
    FLexer : TLISPLexer;
    FTokenPtr : integer;
    function GetToken:TToken;
    function ParseNode:TLISPNode;
    procedure NextToken;
  public
    function Parse(LISPString:string):TLISPNode;
  end;

Fungsi Parse merupakan antarmuka yang melakukan persiapan dan memanggil proses analisis leksikal sebelum diserahkan ke fungsi ParseNode yang berjalan secara rekursif.

function TLISPParser.Parse(LISPString:string): TLISPNode;
begin
  result := nil;
  FLexer := LISP_Lexer;
  FLexer.Clear;
  FLexer.SetPita(LISPString);
  FTokenPtr := 0;
  if (FLexer.Count <> 0) and (GetToken.tokentype=ttLBRACKET) then begin
    NextToken;
    result := ParseNode;
  end;
end;

function TLISPParser.ParseNode: TLISPNode;
var
  tmp : TLISPNode;
  t : TToken;
begin
  result := nil;
  { proses car }
  t := GetToken;
  case t.tokentype of
    { this is an empty list }
    ttRBRACKET:exit;

    { car is an atom }
    ttSYMBOL, ttSTRING, ttNumber:begin
      { check if nil }
      if t.sym = '' then exit;
      { normal atom value }
      result := TLISPNode.Create;
      result.NodeType := ntAtom;
      case t.tokentype of
        ttSYMBOL:result.atomtype := atSymbol;
        ttString:result.atomtype := atString;
        ttNumber:result.atomtype := atNumber;
      end;
      result.Value := t.sym;
    end;

    { car is a list }
    ttLBRACKET:begin
      result := TLISPNode.Create;
      result.NodeType := ntList;
      NextToken;
      { parse child }
      tmp := ParseNode;
      { configure node }
      result.Child := tmp;
    end;

  end; { case..of }

  { proses next }
  NextToken;
  if FTokenPtr < FLexer.Count then begin
    t := GetToken;
    tmp := ParseNode;
    result.Next := tmp;
  end;
end;

Untuk yang penasaran dengan keseluruhan kodenya bisa diunduh di sini.

2 comments

  1. petra · Agustus 3, 2008

    Yet another LISP Parser.
    TAnya si Roni juga pake modul itu, tapi pake Java sih emang😀

  2. Phewe · November 15, 2010

    maaf, saya mau tanya apa pengertian dari parser dan apa hubungannya dengan delphi 6..? boleh minta informasi..? trims

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s