...pak jsem objevil Windows NT, nejlepší operační systém vůbec... opravdový raketoplán.... -- rozhovor JXD s autorem virů

Scheme snadno a rychle - 2. Gramatiky a tak...

v beznem clanku o programovacich jazycich je minimalne jedna kapitola venovana gramatikam a podobnym vecem. abych pravdu rekl, neni to tema ktere by me nejak extra rajcovalo a teoreticky by se bez nej i interpretr mohl obejit. ale budiz. muj posledni prispevek na blogu abclinuxu budiz ukazkou toho, jak nektere nastroje mam rad. premyslel, jsem jestli parser udelat v ruce nebo generovat. ale jelikoz mam v nadpisu "snadno a rychle" a ne "slozitejc a poradne", tak jsem se rozhodl nakonec pouzit generatory.

gramatika scheme neni zavratne slozita ajak jsem rikal, bez problemu se da udelat v ruce, teda bez pouziti generatoru jako flex a bison, ale radsi jej pouzijeme. r5rs mluvi dokonce o tom, ze diky kvazikvotovani, se nejedna o bezkontextovou gramatiku a tudiz bison by na to mel byt kratky, ale kdyz se kvazikvotovani presune do standardni knihovny, uz tento problem odpada.

2.1. Flex

flex je generator lexikalnich analyzatoru, coz jsou funkce, ktere dokazi vzit jako vstup nejaky retezec a ten rozdelit na kousky (tokeny) a vracet jejich hodnoty. neni potreba nic svetoborneho, v zakladni verzi by stacily tokeny pro zavorky, tecku a symboly. v praxi se pak pouzivaji jeste zkratky pro kvotovani, tj. "'", "`", ",", ",@", ktere se prepisuji na (quote x), (quasiquote x), (unquote x) a (unquote-splicing x)

definice muze vypadat nejak takhle

scheme.l:

%{
#include <string.h>
#include "scheme.tab.h"
%}

INITIAL_CHAR    [[:alnum:]]|\+|\*|\-|\\|=|#|\?|\!|<|>|_|\/|~|:|%
INNER_CHAR      [[:alnum:]]|\+|\*|\-|\\|=|#|\?|\!|<|>|_|\/|~|:|%|'|,|@|`|\.
LEFT_PAREN      "("
RIGHT_PAREN     ")"
WHITE_SPACE     [[:space:]]
QUOTE           "'"
UNQUOTE         ","
UNQUOTE_SPLICING "@"
QUASIQUOTE      "`"
DOT             "."
SEMICOL         ";"

%%

{INITIAL_CHAR}{INNER_CHAR}* {
        yylval.symbol = GC_MALLOC(strlen(yytext) + 1);
        strcpy(yylval.symbol, yytext);
        return T_SYMBOL;
}

{LEFT_PAREN}    { return T_LEFT_PAREN; }
{RIGHT_PAREN}   { return T_RIGHT_PAREN; }
{SEMICOL}.*$    /* ignores comments */
{WHITE_SPACE}+  /* ignores white space*/
{QUOTE}         { return T_QUOTE; }
{UNQUOTE}       { return T_UNQUOTE; }
{QUASIQUOTE}    { return T_QUASIQUOTE; }
{UNQUOTE}{UNQUOTE_SPLICING}     { return T_UNQUOTE_SPLICING; }
{DOT}           { return T_DOT; }
%%

za pozornost maximalne stoji, ze cisla tokenu jsou brany z vystupu bisonu a pak dalsi definice, ktere se staraji o ignorovani komentaru. fakt bych nerad sel s touto tematikou nejak do hloubky, protoze o techto vecech byl uz napsan nejeden kilobyte textu.

2.2. Bison

pravidla pro sestaveni samotneho compileru jsou zase vcelku trivialni. a zase se nebudu zatezovat nejakou slozitou teorii a prenecham to povolanejsim.

scheme.y:

%{
#include <stdlib.h>
#include "types.h"
#include "scheme.tab.h"

#define YYERROR_VERBOSE

scm_value * result = NULL;

%}

%union {
        char * symbol;
        scm_value * parsed;
}

%token <symbol> T_SYMBOL
%token T_LEFT_PAREN
%token T_RIGHT_PAREN
%token T_QUOTE
%token T_UNQUOTE
%token T_UNQUOTE_SPLICING
%token T_QUASIQUOTE
%token T_DOT

%type <parsed> expressions symbol symbols list quote quasiquote unquote unquote_splicing

%start expressions

%%

expressions:    symbols { result = $1; }
;

symbol: T_SYMBOL { $$ = scm_value_new_symbol($1); }
| list
| quote
| quasiquote
| unquote
| unquote_splicing

;

symbols: symbol { $$ = scm_value_new_pair($1, SCM_CONST_NIL); }
| symbol T_DOT symbol { $$ = scm_value_new_pair($1, $3); }
| symbol symbols { $$ = scm_value_new_pair($1, $2); }

;

list:   T_LEFT_PAREN T_RIGHT_PAREN { $$ = SCM_CONST_NIL; }
| T_LEFT_PAREN symbols T_RIGHT_PAREN { $$ = $2; }
;


/* Quotation symbols */
quote:  T_QUOTE symbol  { $$ = scm_value_new_pair(
                        scm_value_new_symbol("quote"),
                        scm_value_new_pair($2, SCM_CONST_NIL)); }
;

quasiquote: T_QUASIQUOTE symbol { $$ = scm_value_new_pair(
                            scm_value_new_symbol("quasiquote"),
                            scm_value_new_pair($2, SCM_CONST_NIL)); }
;

unquote: T_UNQUOTE symbol { $$ = scm_value_new_pair(
                         scm_value_new_symbol("unquote"),
                         scm_value_new_pair($2, SCM_CONST_NIL)); }
;
%%

vsimnete si, ze si zatim vystacime s pouzitim, jenom datovych typu -- PAIR, SYMBOL, NIL. zadna cisla, zadne booleovske hodnoty. to vsechno je az soucasti semanticke analyzy, ktere se budu venovat priste.

uznavam, ze tato kapitola je hodne zalostna, ale o gramatikach a takovych tech vecech bylo napsano dost, obzvlast od fundovanejsich osob. dopriste se doufam polepsim.

Vytvořil(a) deda.jabko v 12. 03. 2007, 10:44

Přidat komentář

Fruit International

Scheme snadno a rychle - 2. Gramatiky a tak...

2.1. Flex

2.2. Bison