Javascript recursive descent parser generator

Here is a recursive descent parser generator for javascript. As always, I'm too lazy to document how it works. I did not test it much. Just play with it if you like.

In the first section, you define the tokens. There is a special token called SKIP, which is ignored.

In the second section, you define the grammar of your language. Some examples:

C = { 
  A A;
  B;
};

means C is A followed by A, or C is B.

You can add types to your productions:

C = { 
  [A_PAIR] A A;
  [JUST_B] B;
};

You can name the symbols in the productions:

C = { 
  [A_PAIR] first:A second:A;
  [JUST_B] value:B;
};

Say that A denotes the token /[a-z]/, than the parse result of "x y" is an object like this:
{ Type: "A_PAIR", first:"x", second:"y" }

You can omit braces if there is only one production for a rule:

C = A A;

You can also inherit the parse result of a sub-rule. So instead of:

C = A A;
X = lbrace value:C rbrace;

then using x.value.first, you can do:

C = A A;
X = lbrace #C rbrace;

then use x.first.

You can also use wildcards in restricted cases:

Alist = A+;
Blist = B*;

in which case the result object will be an array.

Serializing JavaScript objects

I once have written a JavaScript function that dumps a JavaScript object in a human readable format. It was something like JSON, but it also handled objects containing circular references shared object references. I must admit that it was written badly.

After reading this, I thought that maybe it's a good idea to change the previous code for serializing JavaScript objects. I also refactored the code. You can find it below. I didn't test it thoroughly, so be careful.

An example of what it can do:

var x = {};

x.foo  = new Object();
x.self = x;
x.arr  = [x.self];
x.bar  = x.foo;

var s = serialize(x);
var y = deserialize(s);
alert(y == y.self);    // true
alert(y == y.arr[0]);  // true
alert(y.foo == y.bar); // true

alert(s);
// {
//     'foo': {},
//     'self': { _root_: [  ] },
//     'arr': [
//         { _root_: [  ] }
//     ],
//     'bar': { _root_: [ "foo" ] }
// }

Addition: I think that I have to express that better: don't expect it to serialize functions, regular expressions, images (or any other browser object), etc. It's just something like JSON, but it also handles shared object references. Code:

//============================================================================//
//  JavaScript object de/serialization with circular references.              //
//                                                                            //
//  author: Mehmet Yavuz Selim Soyturk                                        //
//  e-mail: Mehmet dot Yavuz dot Selim at gmail dot com                       //
//============================================================================//

Array.prototype.findIf = function(predicate) {
    for(var i in this) {
        if (predicate(this[i]))
            return i;
    }
    return -1;
};
Array.prototype.map = function(func) {
    var len = this.length;
    var result = [];
    for (var i=0; i<len; i++) {
        result[i] = func(this[i]);
    }
    return result;
};
Array.prototype.appended = function(value) {
    var copy = this.slice(0);
    copy[copy.length] = value;
    return copy;
};

//============================================================================//
//  SERIALIZATION                                                             //
//============================================================================//

function indented(n) {
    var s = '';
    for(var i=0; i<n; i++) s += '    ';
    return s;
}

function serializePrimitive(value) {
    if (typeof value == 'string')
        return '"' + value + '"';
    else
        return '' + value;
}

function serializePrimitiveArray(arr) {
    var s = "[ ";
    s += arr.map(serializePrimitive).join(', ');
    s += " ]";
    return s;
}

function serializeArray(arr, seen, indices, depth) {
    if (arr.length == 0)
        return '[]';

    seen[seen.length] = {obj: arr, indices: indices};
    
    var result = '[\n';
    for (var i=0; i<arr.length; i++) {
        result += indented(depth + 1);
        result += serializeAny(arr[i], seen, indices.appended(i), depth + 1);
        result += (i == arr.length - 1) ? '' : ', ';
        result += '\n';
    }
    result += indented(depth) + ']';

    return result;
}

function serializeObject(obj, seen, indices, depth) {
    seen[seen.length] = {obj: obj, indices: indices};
    
    var result = '{\n';
    var count = 0;
    for (var i in obj) {
        if (typeof obj[i] != 'function') {
            count++;
            result += indented(depth+1);
            result += "'" + i + "': ";
            result += serializeAny(obj[i], seen, indices.appended(i), depth + 1);
            result += ", \n"; // bad hack, see next
        }
    }
    if (count > 0) {
        result = result.substring(0, result.length-3) + '\n'; // bad hack
        return result + indented(depth) + '}';
    }
    else {
        return '{}';
    }
}


function serializeAny(value, seen, indices, depth) {
    var t = typeof(value);
    var prevIndex;
    
    if (t == 'function') {
        throw new Error("Cannot serialize function. Keys from root: " + 
            serializePrimitiveArray(indices));
    }
    else if (t != 'object') {
        return serializePrimitive(value);
    }
    else if ( (prevIndex = seen.findIf
                    ( function(obj) { return obj.obj == value } )
              ) >= 0) {
        return '{ _root_: ' + serializePrimitiveArray(seen[prevIndex].indices) + ' }';
    }
    else if (value.constructor == Array) {
        return serializeArray(value, seen, indices, depth);
    }
    else {
        return serializeObject(value, seen, indices, depth);
    }
};

function serialize(obj) {
   return serializeAny(obj, [], [], 0);
}


//============================================================================//
//  DESERIALIZATION                                                           //
//============================================================================//

function followIndices(obj, indices) {
    for (var i=0; i<indices.length; i++)
        obj = obj[indices[i]];
        
    return obj;
}

function replaceRootRefs(obj, root) {
    if (typeof obj != 'object' || obj == null)
        return;
    
    for (var i in obj) {
        var prop = obj[i];
        if (typeof prop == 'object' && prop != null) {
            if ('_root_' in prop)
                obj[i] = followIndices(root, prop._root_);
            replaceRootRefs(prop, root);
        }
    }
}

function deserialize(str) {
    var obj = eval( '(' + str + ')' );
    if (str.indexOf('_root_') < 0)
        return obj;
    
    replaceRootRefs(obj, obj);
    return obj;
}

Kablosuz aglari dinlemek icin

Interface'i monitor moda getir:

$ sudo iwconfig eth1 mode monitor

Wireshark'i calistir:

$ sudo wireshark

Dinle ve interface'i eski haline getir:

$ sudo iwconfig eth1 mode managed

latex, html, plain text

Converting latex to html, if the tex file has utf8 encoding:

latex2html -html_version 4,unicode document.tex

If you want only one page:

latex2html -split 0 -html_version 4,unicode document.tex

Converting html to plain tex:

elinks -dump document.html

Output buffer unwinding for PHP?

PHP 5 supports exception handling. When an exception occurs, PHP does stack unwinding so that it restores the state of the script... does it? No. An important state of the script does not get restored: the output. Would it not be a good idea if PHP also did some sort of output buffer unwinding? That is the idea:

<?php

exceptional_ob_start();

echo "Begin\n";
try {
    echo "Exception\n";
    throw new Exception();
} catch (Exception $e) {}
echo "End\n";

exceptional_ob_end_flush();
    
?>

And that is the only output:

Begin
End

I am not a PHP (nor webscripting) guy so I may be wrong, but I think that something like that would be very useful. It is maybe even needed for making PHP exceptions useful.
 

Currying in JavaScript

We can make our functions curried in JavaScript:

function curry(f, needed_len) {
    if (needed_len == undefined)
        needed_len = f.length;
        
    var curried = function() {
        var curried_args = arguments;
        if (curried_args.length >= needed_len) {
            return f.apply(this, arguments);
        }
        else {
            var curry_result_function = function() {
                var args = [];
                for(var i=0; i<curried_args.length; i++)
                    args[args.length] = curried_args[i];
                
                for(var i=0; i<arguments.length; i++)
                    args[args.length] = arguments[i];

                return f.apply(this, args);
            };
            return curry(curry_result_function, needed_len-curried_args.length);
        }
    };
    return curried;
}

And usage:

var curried_add = curry(function (a, b, c) {
    return a + b + c;
});

print(curried_add(1)(2)(3));
print(curried_add(1)()(2)()(3));
print(curried_add(1,2,3));
print(curried_add(1)(2,3));
print(curried_add(1,2)(3));

See also next pages for other implementations: http://www.dustindiaz.com/javascript-curry http://www.svendtofte.com/code/curried_javascript/
 
Note: after some more googling about currying in JavaScript, it's very interesting to see that http://www.coryhudson.com/blog/2007/03/10/javascript-currying-redux/ contains an almost identical implementation.

JavaScript'de eval ve closure'un gucu

Kendi halinde basit bir fonksiyonumuz olsun:

function myEval(code) {
    return eval(code);
}

Simdi kendimize bir sayac yapalim:

var inject = 'var n=0; var f=function(){return n++}; f';
var sayac = myEval(inject);

alert(sayac()); // 0
alert(sayac()); // 1
alert(sayac()); // 2

vim ile dosya calistirmaca

bakiniz: http://blog.arsln.org/vim-icinden-python-kodu-calistirmak/ Simdi bunu F8'e basildiginda her dosyayi calistirir hale getirmek gerek. Bunu daha once emacs icin yapmistim, ancak isin mantigini da elisp ile yaptirmaya ugrastigim icin karman corman birsey olmustu ne yazik ki. Simdi aklim basima geldi, bu isi bir shell script'e yaptirmak gerek. Bu ~/bin/calistir dosyasinin icerigi:

#!/bin/bash

dosya=$1

case $dosya in

"")
   echo "Kullanim: $0 <dosya_ismi>"
   ;;
*.js)
   js $dosya
   ;;
*.py)
   python $dosya
   ;;
*.sh)
   /bin/bash $dosya
   ;;
*.rb)
   ruby $dosya
   ;;
*.c)
   gcc $dosya
   ./a.out
   ;;
*.cpp)
   g++ $dosya
   ./a.out
   ;;
/*)
   $dosya
   ;;
*)
   ./$dosya
   ;;

esac

Ve ~/.vimrc dosyasina su satiri ekliyoruz:

map <F8> :!/home/kullanici/bin/calistir % <ENTER>

Bu da ~/.emacs dosyasina:

(defun exec-file () 
  "Execute a file, if possible."
  (interactive)
  (let ((curr-buf (buffer-name))
        (exec-buffer "execute-buffer"))
    (if (get-buffer exec-buffer) 
    
      ;; su anda bir calistirma buffer'i acik, kapat
      (kill-buffer exec-buffer)
      
      ;; calistir
      (progn
        (call-process "/home/kullanici/bin/calistir" nil exec-buffer t curr-buf)
        (switch-to-buffer-other-window exec-buffer)
        (switch-to-buffer-other-window curr-buf)))))

(global-set-key [f12] 'exec-file)

En cok kullandigim linux komutlari

Burada en cok kullandiginiz linux komutlarini ogrenmek icin bir yontem gosterilmis. Ben de hemen denedim, sonuc soyle:

$ history|awk '{print $2}'|awk 'BEGIN {FS="|"} {print $1}'|sort|uniq -c|sort -rn|head -10
  77 ls
  76 make
  50 cd
  34 pjs
  31 nano
  20 parrot
  19 rm
  18 js
  17 new
  16 svn

ls'in en cok kullandigim komut olmasina sasirmamak gerek. Terminalde yaptigim her hareketten once cagiririm onu. parrot, pjs, js, make ve svn komutlari da yapmakta oldugum proje nedeniyle bolca kullandigim komutlar.

Nurikabe

Vakit oldurmek icin birebir. Sudoku bana pek eglenceli gelmemisti, ama nurikabe bayagi zevkli geldi. Biraz bilgi edindikten sonra oynamaya buradan baslayabilirsiniz.

Elisp ile dosya calistirma

Emacs'da bir dosyayi calistirip, ciktisini yeni bir buffer'da gormek icin yazdigim bir script. Buradan da kopya cektim biraz. Eminim ki tekeri bastan icad ediyorum, hem de kagni tekeri (aklima bunu getirdi). Ama kucuk olsun benim olsun :) Bir de hala su degiskenlere dogru duzgun isim vermeyi ogrenemedim. Zamanimin yarisi bunu ne diye adlandirayim diye geciyor.

Not: daha duzgun degisken isimleri vermeye calistim.

; a list of triples that contain:
;  - the regex for the file name
;  - the name of the buffer that will be created
;  - a list containing the command to execute the file
(defvar exec-list nil)

(defun add-exec (regex buffer-name command-list)
  (let ((entry (list regex buffer-name command-list)))
    (setf exec-list (cons entry exec-list))))

(defun get-exec-help (filename execs)
  (unless (null execs)
    (let* ((entry (car execs))
       (regex (car entry)))
      (if (string-match regex filename)
      (cdr entry)
    (get-exec-help filename (cdr execs))))))

(defun get-exec (filename)
  (get-exec-help filename exec-list))


(defun exec-file () 
  "Execute a file, if possible."
  (interactive)
  (let* ((curr-buf (buffer-name))
     (exec-params (get-exec curr-buf)))
    (if exec-params
    (let ((exec-buffer (car exec-params))
          (exec-command-list (cadr exec-params)))
      (if (get-buffer exec-buffer) 
          (kill-buffer exec-buffer)
        (progn
          (eval (append
             (list 'start-process 
               exec-buffer
               exec-buffer)
             exec-command-list
             (list curr-buf)))
          (switch-to-buffer-other-window exec-buffer)
          (switch-to-buffer-other-window curr-buf)))))))

(add-exec "\\.js$" 
      "javascript" 
      (list "/usr/bin/rhino" "-f"))

(add-exec "\\.\\(pir\\|pasm\\)$" 
      "parrot" 
      (list "/home/yavuz/parrot_svn/parrot/parrot"))

(add-exec "\\.html$" 
      "html" 
      (list "/usr/bin/firefox"))

(global-set-key [f12] 'exec-file)

Iyi huylu böcek

Ruby ile yazdigim basit bir programda kullanicinin attigi her adim @lines adinda bir listede tutuluyor. Kullanici istedigi zaman bu adimlari gorebiliyor, ve "undo <n>" diyerek <n>'inci siradaki adimi iptal edebiliyor. Kullanicinin kafasini karistirmamak icin <n> 1'den basliyor (her ne kadar bu programi benden baska hickimse kullanmayacak olsa da :-) ). Iptal edici fonksiyon soyle birsey:

def undo(line)
    n = line.gsub(/undo\W+([^\W]*)/, '\1').to_i
    @lines.delete_at(n-1)
    rescue print("You did not give a valid line number!\n")
end

Daha sonra kullanici sadece "undo" yazdigi takdirde en son yaptigi islemin iptal edilmesinin faydali olacagini dusundum. Bunu programlamadan once su anda bu durumda ne oluyor bir bakayim dedim. Cok garip: tam da istedigim sey oluyordu.

Ben bir sayi ifade etmeyen bir string'e to_i metodu uygulandiginda hata firlatacagini dusunuyordum, fakat 0 donduruyormus. Yani kullanici "undo" komutunu verdiginde gsub'un sonucu regex uymadigi icin yine "undo" oluyor, onun da to_i metodu 0 donduruyor. Bir sonraki satirda @lines.delete(-1) ifadesi calisiyor, yani @lines'in son elemani siliniyor :)

Keske butun bocekler de bunun gibi olsa... demiyorum, bocegin gizlenmeyeni makbuldur.

Emacs notlari

Bir ogrendigimi fazla kullanmayinca kisa sure icerisinde unutuyorum. Bu da bilgi bir daha gerektiginde zaman kaybina neden oluyor. Not tutmaya karar verdim.
Buraya emacs notlarimi yazayim:

• C-h k : tus kombinasyonunun hangi komutu calistirdigini ogrenmek
• C-x ({ | }) : (enlarge | shrink)-window-horizontally
• C-x ^ : enlarge window
• C-x C-e : evaluate lisp expression

 

not: Rickdangerous'un tavsiyesi uzerine kopya cekmeye karar verdim. Isime de geldi. Ne de olsa ben tembel bir adamim.

xmms-ruby

fazlamesai.net'ten FZ ruby ile emacs icinden xmms'e parca sectiren bir program yazmis. Hazir ruby tutorial'ini biraz karistirmisken ruby ile birseyler yapayim dedim. Programi biraz daha gelistirdim.
Ekledigim seyler:

• Birden fazla kelime aranabiliyor, hepsinin parca ismine/dosya ismine uymasi lazim
• Sadece sayi girilirse xmms o siradaki parcaya atliyor
• Girdi ':' ile baslarsa xmms'e direkt ruby kodu ile hukmedebiliyoruz (:stop, :play :next gibi). eval fonksiyonu sagolsun.
• Eger ilk arguman --dialog ise girdi bir dialog yardimiyla aliniyor.

Ben gconf-editor yardimiyla C-M-j tus kombinasyonunu --dialog opsiyonuna atadim. Biraz yavas da olsa idare ediyor. Aslina bakarsaniz bunu zaten birinin yapmis olabilecegini dusunup kisa bir aramadan sonra xmmsfind'i buldum, fakat ne yazik ki cani istemedigi zaman acilmama gibi bir sorunu var.

#!/usr/bin/env ruby

require 'xmms'

def nextSong(args, xr) 
  matching = []
  i = 0
  xr.playlist.each do |entry|
    if match(entry, args) 
      matching << i
      $stderr.puts 'Matched: ' + entry[0]
    end
    i += 1
  end
  if matching.length == 0
    return false
  else
    xr.position = matching[rand(matching.length)]
    return true
  end
end

def match(entry, args) 
  title, file, time = entry
  args.each do |arg|
    regex = /#{arg}/i
    return false unless (title =~ regex or file =~ regex)
  end
  return true
end

def is_int(str)
  return str =~ /^[0-9]+$/
end


$stderr.puts 'Xmms-Ruby version ' << Xmms::Remote::VERSION

# allocate a new Xmms::Remote object
xr = Xmms::Remote::new

if ARGV.length == 1 and ARGV[0] == '--dialog'
  cmd = open('| zenity --entry --text "xmms: give some keywords"')
  argStr = cmd.gets.strip
  args = argStr.split
  cmd.close
  puts args.to_s
  exit if args.length == 0
else
  argStr = ARGV.map{|s| s.strip}.join(' ')
  args = argStr.split
end

if args.length == 0
  xr.next
  $stderr.puts 'next song'
elsif is_int(argStr) and argStr.to_i <= xr.playlist.length and argStr.to_i > 0
  xr.position = argStr.to_i - 1
  $stderr.puts 'jump to position: ' + argStr
elsif argStr[0] == ":"[0]
  $stderr.puts 'Evaluate: ' + argStr[1..-1]
  eval ('xr.' + argStr[1..-1])
elsif not nextSong(args, xr)
  $stderr.puts 'No match: ' +  argStr
end

/dev/dsp ile gurultu alarmi

cat /dev/dsp dedigimde ve yeteri kadar ses cikardigimda ekranda {}|~[] gibi karakterler goruyorum. Sessizlikte ise octal olarak 200 ile temsil edilen bir deger uretiliyor (fakat bu ekranda gorunmuyor). Gurultuyu yakalamak icin sunu yapiyorum:

cat /dev/dsp | tr '\200' '\n' | egrep '[{}|~]' -m 1

-m 1 parametresi grep'in ilk bulunan sonuctan sonra sona ermesini sagliyor.

Tamam, simdi gurultuyu yakaladik. Peki alarmi nasil verecegiz? Mesela bir ses dosyasi calabiliriz, veya aygitlarla oynamaya devam edebiliriz:

cp /dev/urandom /dev/dsp

Yani tek komut olarak yazmak istersek:

cat /dev/dsp | tr '\200' '\n' | egrep '[{}|~]' -m 1 ; cp /dev/urandom /dev/dsp

/dev

Bugun biraz /dev klasorundeki aygitlarin icerigini ekrana yazdirarak eglendim. Ilginc komutlar:

• Fare veya klavye icin:
  • sudo cat /dev/input/herhangibir_dosya
  • sudo cat /dev/psaux
• Asagidaki komuttan sonra microfona konusun:
  • cat /dev/audio
  • cat /dev/dsp
• Rastgele veri:
  • cat /dev/urandom
  • cat /dev/random

/dev/zero 'nun ekrana 0 yazdirmasini bekliyordum, ama hicbirsey olmadi. Daha sonra jeton dustu:
cat /dev/zero | tr '\0' 'x'

Harddiskinizin icinde neler var?
sudo head /dev/hda (bolumler icin hda1, hda2 ...)

Asagidaki komutu uygulamadan once acik dokumanlari kaydedin, linux'u gocertmeye hazir olun. Sorumluluk kabul etmiyorum. Ne yaptigi konusunda emin degilim:
sudo cat /dev/console

Hastalik

Şu grip yaz gribi, şu grip kuş gribi, ortada Yavuz garibi...