Deviad
27-07-2006, 09:12
INTRODUZIONE
Ecco un qualcosa da the forge che ultimamente ho visto utilizzata per risolvere problemi di crash (si chiamano abend per dio) del pc.
Dunque, come tutti sapranno (se come no) i computer fino a qualche hanno fa erano tutti programmati in assembly e i programmi utente anch'essi erano scritti in assembly, ma non un assembly qualsiasi bensì l'assembly di quella macchina.
Risultato: se avevi una macchina olivetti dovevi acquistare la stampante olivetti, il mouse olivetti, il programma di videoscrittura della olivetti e così via.
Dei signori ai laboratori della Bell, successivamente, inventarono il C, tra questi i famosi Brian Kernighan e Dennis M. Ritchie.
Questi 2 "nerd" diedero il via non solo ad una rivoluzione nell'ambito informatico, ma anche ad una rivoluzione culturale.
Grazie al C abbiamo potuto avere periferiche compatibili con i vari calcolatori e la creazione di un qualcosa di veramente rivoluzionario, UNIX, che ancora oggi Bill Gates copia spudoratamente.
Come tutto ciò è possibile?
Perchè le istruzioni scritte in C da un compilatore vengono tradotte in istruzioni in linguaggio macchina e scritte in un file eseguibile che contiene anche tutti i link alle librerie necessarie affinchè il programma possa girare.
I 2 pezzi di codice che sto per postare, niente di speciale, sono quelli che si occupano di riconoscere i token di linguaggio e verificare che questi siano messi nell'ordine corretto secondo la grammatica utilizzata.
L'unica cosa che hanno di speciale è che gli ho creati io e danno vita ad un programma funzionante. Non mi aspettavo che ciò potesse darti una tale soddisfazione.
Il primo si chiama Lexer (analizzatore lessicale) il secondo parser (analizzatore sintattico).
/*************************************************
* *
* EASY JAVA PARSER *
* *
*************************************************/
// Grammatica generatrice di un sottolinguaggio del linguaggio Java scritta per ANTLR
class EasyJavaParser extends Parser;
options {
defaultErrorHandler = true; // Don't generate parser error handlers
k = 3;
buildAST = true;
exportVocab = EasyJava;
}
// PARSER
javaclass : (modifier)* "class" className LCBRACK! (method)* RCBRACK!
;
method : (modifier)* returnType methodName LRBRACK (param)? RRBRACK (bloccoIstr)*
;
methodName : IDENTIFIER ;
className : IDENTIFIER ;
bloccoIstr : LCBRACK! (statement)* RCBRACK!
;
statement
: varDeclaration | assignment | binSel | whileLoop
;
varDeclaration : type IDENTIFIER (COMMA IDENTIFIER)* SEMI!
| assignmentOnCasting
;
param
: (type)? (IDENTIFIER)+ (IDENTIFIER COMMA (type)? (IDENTIFIER)+)*
;
assignment : IDENTIFIER ASSIGN expression SEMI!
;
assignmentOnCasting : type (assignment) SEMI!
;
binSel : "if"^ parExpression bloccoIstr
{ System.out.println("Found IF Statement"); }
;
whileLoop : "while"^ parExpression bloccoIstr
{ System.out.println("Found While Statement"); }
;
modifier
:
"public"
| "protected"
| "private"
| "static"
| "abstract"
| "final"
| "native"
| "synchronized"
| "transient"
| "volatile"
| "strictfp"
;
returnType
: Type | "void" ;
type
: "boolean"
| "char"
| "byte"
| "int"
| "short"
| "long"
| "float"
| "double"
;
// EXPRESSIONS
parExpression : LRBRACK! expression RRBRACK!;
expression
: conditionalExpression (assOp expression)?
;
assOp : ASSIGN^ | BAND_ASSIGN^ | BOR_ASSIGN^ | BXOR_ASSIGN^ | SL_ASSIGN^ | BSR_ASSIGN^ | SR_ASSIGN^ | MOD_ASSIGN^
| MUL_ASSIGN^ | DIV_ASSIGN^ | MINUS_ASSIGN^ | PLUS_ASSIGN^
;
conditionalExpression : conditionalAndExpression ( LOR^ conditionalAndExpression )* ;
conditionalAndExpression : bitwiseor ( LAND^ bitwiseor )* ;
bitwiseor : bitwisexor ( BOR^ bitwisexor)* ;
bitwisexor : bitwiseand (BXOR^ bitwiseand)* ;
bitwiseand : equalityexpr ( BAND^ equalityexpr )* ;
equalityexpr : relationalexpr ( (EQUAL^ | NOT_EQUAL^) relationalexpr)* ;
relationalexpr : shiftexpr ((LTE^ | LT^ | GTE^ | GT^) shiftexpr)* ;
shiftexpr : addexpr ((SR^ | BSR^ | SL^) addexpr)* ;
addexpr : mulexpr ((PLUS^ | MINUS^) mulexpr)* ;
mulexpr : atom ((MUL^ | DIV^) atom)* ;
atom : parExpression | IDENTIFIER | numberString;
numberString: NUMBERS | DECIMAL_NUMBERS;
/*************************************************
* *
* EASY JAVA LEXER *
* *
*************************************************/
class EasyJavaLexer extends Lexer;
options {
charVocabulary='\u0003'..'\uFFFF';
exportVocab=EasyJava; // call the vocabulary "EasyJava"
testLiterals=false; // don't automatically test for literals
k=5; // lookahead
}
IDENTIFIER
options {testLiterals=true;}
: ('a'..'z'|'A'..'Z'|'_'|'$') ('a'..'z'|'A'..'Z'|'_'|'0'..'9'|'$')*
;
NUMBERS : ('0' | '1'..'9' ('0'..'9')*) (DOT ('0'..'9')+ { _ttype = DECIMAL_NUMBERS; })? ;
// OPERATORS
QUESTION options { paraphrase="?"; } : '?' ;
LRBRACK options { paraphrase="("; } : '(' ;
RRBRACK options { paraphrase=")"; } : ')' ;
LSBRACK options { paraphrase="["; } : '[' ;
RSBRACK options { paraphrase="]"; } : ']' ;
LCBRACK options { paraphrase="{"; } : '{' ;
RCBRACK options { paraphrase="}"; } : '}' ;
COLON options { paraphrase=":"; } : ':' ;
COMMA options { paraphrase=","; } : ',' ;
DOT options { paraphrase="."; } : '.' ;
LNOT options { paraphrase="!"; } : '!' ;
INC options { paraphrase="++"; } : "++" ;
DEC options { paraphrase="--"; } : "--" ;
MOD options { paraphrase="%"; } : '%' ;
SEMI options { paraphrase=";"; } : ';' ;
// ARITHMETIC OPERATORS
DIV : '/' ;
PLUS : '+' ;
MINUS : '-' ;
MUL : '*' ;
// LOGICAL OPERATORS
LAND options { paraphrase="&&"; } : "&&" ;
LOR options { paraphrase="||"; } : "||" ;
// RELATIONAL OPERATORS
LTE options { paraphrase="Less than or equal"; } : "<=" ;
LT options { paraphrase="Less than"; } : '<' ;
GTE options { paraphrase="Greater than or equal"; } : ">=" ;
GT options { paraphrase="Greater than"; } : '>' ;
// ASSIGN OPERATORS
ASSIGN options { paraphrase="="; } : '=' ;
BAND_ASSIGN options { paraphrase="&="; } : "&=" ;
BOR_ASSIGN options { paraphrase="|="; } : "|=" ;
BXOR_ASSIGN options { paraphrase="^="; } : "^=" ;
SL_ASSIGN options { paraphrase="<<="; } : "<<=" ;
BSR_ASSIGN options { paraphrase=">>>="; } : ">>>=" ;
SR_ASSIGN options { paraphrase=">>="; } : ">>=" ;
MOD_ASSIGN options { paraphrase="%="; } : "%=" ;
MUL_ASSIGN options { paraphrase="*="; } : "*=" ;
DIV_ASSIGN options { paraphrase="/="; } : "/=" ;
MINUS_ASSIGN options { paraphrase="-="; } : "-=" ;
PLUS_ASSIGN options { paraphrase="+="; } : "+=" ;
// BITWISE OPERATORS
BXOR options { paraphrase="^"; } : '^' ;
BOR options { paraphrase="|"; } : '|' ;
BAND options { paraphrase="&"; } : '&' ;
BNOT options { paraphrase="~"; } : '~' ;
// EQUALITY OPERATORS
EQUAL options { paraphrase="=="; } : "==" ;
NOT_EQUAL options { paraphrase="!="; } : "!=" ;
// SHIFT
SR options { paraphrase=">>"; } : ">>" ;
BSR options { paraphrase=">>>"; } : ">>>" ;
SL options { paraphrase="<<"; } : "<<" ;
// Whitespace -- ignored
WS : ( ' '
| '\t'
| '\f'
// handle newlines
| ( options {generateAmbigWarnings=false;}
: "\r\n" // Evil DOS
| '\r' // Macintosh
| '\n' // Unix (the right way)
)
{ newline(); }
)+
{ _ttype = Token.SKIP; }
;
// Single-line comments
SL_COMMENT
: "//"
(~('\n'|'\r'))* ('\n'|'\r'('\n')?)
{$setType(Token.SKIP); newline();}
;
// multiple-line comments
ML_COMMENT
: "/*"
(
options {
generateAmbigWarnings=false;
}
:
{ LA(2)!='/' }? '*'
| '\r' '\n' {newline();}
| '\r' {newline();}
| '\n' {newline();}
| ~('*'|'\n'|'\r')
)*
"*/"
{$setType(Token.SKIP);}
;
// character literals
CHAR_LITERAL
: '\'' ( ESC | ~('\''|'\n'|'\r'|'\\') ) '\''
;
// string literals
STRING_LITERAL
: '"' (ESC|~('"'|'\\'|'\n'|'\r'))* '"'
;
// escape sequence -- note that this is protected; it can only be called
// from another lexer rule -- it will not ever directly return a token to
// the parser
// There are various ambiguities hushed in this rule. The optional
// '0'...'9' digit matches should be matched here rather than letting
// them go back to STRING_LITERAL to be matched. ANTLR does the
// right thing by matching immediately; hence, it's ok to shut off
// the FOLLOW ambig warnings.
protected
ESC
: '\\'
( 'n'
| 'r'
| 't'
| 'b'
| 'f'
| '"'
| '\''
| '\\'
| '0'..'3'
(
options {
warnWhenFollowAmbig = false;
}
: '0'..'7'
(
options {
warnWhenFollowAmbig = false;
}
: '0'..'7'
)?
)?
| '4'..'7'
(
options {
warnWhenFollowAmbig = false;
}
: '0'..'7'
)?
)
;
PARTE ESPLICATIVA (under construction)
k=2 sarebbe il lookahead (guarda avanti)
Questa funzione ha un compito importante che è quello di distinguere i token.
Il lexer effettua un compito che è quello di "tokenizzare" un flusso di caratteri inizialmente privi di significato.
Ad esempio while il programma lo legge inizialmente come la sequenza di litteral 'w' 'h' 'i' 'l' 'e', poi i caratteri vengono messi insieme e formano la parola chiave while.
Esempio 1:
Con il lookhead a 1 lui per distinguere while da whine si ferma alla prima lettera. In questo caso in fase di creazione del lexer ANTLR vi dice che c'è una situazione di non-determinismo in quanto ci sono 2 regole che generano "w" e non sa quale delle 2 deve applicare:
Esempio 2:
a = bc
d = be
Queste 2 regole iniziano entrambe con la lettera b e con un lookhead impostato ad 1 per lui sono uguali.
Se impostiamo il lookahead a 2 questo non succede.
modifier
:
"public"
| "protected"
| "private"
| "static"
| "abstract"
| "final"
| "native"
| "synchronized"
| "transient"
| "volatile"
| "strictfp"
;
Questo in teoria andava messo nel Lexer e non nel Parser. Tuttavia, seguendo un suggerimento che mi è stato dato nella mailing list di ANTLR, ho preferito inserirlo nel parser, perchè mettendolo nel lexer avrei dovuto usare un lookahead di 12 per poter far riconoscere univocamente "synchronized" , rallentando successivamente l'esecuzione del programma.
Voglio farvi riflettere sul fatto che le regole del lexer iniziano con la lettera maiuscola, ma è buona norma per convenzione scriverle interamente in maiuscolo, mentre quelle del parser iniziano con la lettera minuscola.
To be continued
Ecco un qualcosa da the forge che ultimamente ho visto utilizzata per risolvere problemi di crash (si chiamano abend per dio) del pc.
Dunque, come tutti sapranno (se come no) i computer fino a qualche hanno fa erano tutti programmati in assembly e i programmi utente anch'essi erano scritti in assembly, ma non un assembly qualsiasi bensì l'assembly di quella macchina.
Risultato: se avevi una macchina olivetti dovevi acquistare la stampante olivetti, il mouse olivetti, il programma di videoscrittura della olivetti e così via.
Dei signori ai laboratori della Bell, successivamente, inventarono il C, tra questi i famosi Brian Kernighan e Dennis M. Ritchie.
Questi 2 "nerd" diedero il via non solo ad una rivoluzione nell'ambito informatico, ma anche ad una rivoluzione culturale.
Grazie al C abbiamo potuto avere periferiche compatibili con i vari calcolatori e la creazione di un qualcosa di veramente rivoluzionario, UNIX, che ancora oggi Bill Gates copia spudoratamente.
Come tutto ciò è possibile?
Perchè le istruzioni scritte in C da un compilatore vengono tradotte in istruzioni in linguaggio macchina e scritte in un file eseguibile che contiene anche tutti i link alle librerie necessarie affinchè il programma possa girare.
I 2 pezzi di codice che sto per postare, niente di speciale, sono quelli che si occupano di riconoscere i token di linguaggio e verificare che questi siano messi nell'ordine corretto secondo la grammatica utilizzata.
L'unica cosa che hanno di speciale è che gli ho creati io e danno vita ad un programma funzionante. Non mi aspettavo che ciò potesse darti una tale soddisfazione.
Il primo si chiama Lexer (analizzatore lessicale) il secondo parser (analizzatore sintattico).
/*************************************************
* *
* EASY JAVA PARSER *
* *
*************************************************/
// Grammatica generatrice di un sottolinguaggio del linguaggio Java scritta per ANTLR
class EasyJavaParser extends Parser;
options {
defaultErrorHandler = true; // Don't generate parser error handlers
k = 3;
buildAST = true;
exportVocab = EasyJava;
}
// PARSER
javaclass : (modifier)* "class" className LCBRACK! (method)* RCBRACK!
;
method : (modifier)* returnType methodName LRBRACK (param)? RRBRACK (bloccoIstr)*
;
methodName : IDENTIFIER ;
className : IDENTIFIER ;
bloccoIstr : LCBRACK! (statement)* RCBRACK!
;
statement
: varDeclaration | assignment | binSel | whileLoop
;
varDeclaration : type IDENTIFIER (COMMA IDENTIFIER)* SEMI!
| assignmentOnCasting
;
param
: (type)? (IDENTIFIER)+ (IDENTIFIER COMMA (type)? (IDENTIFIER)+)*
;
assignment : IDENTIFIER ASSIGN expression SEMI!
;
assignmentOnCasting : type (assignment) SEMI!
;
binSel : "if"^ parExpression bloccoIstr
{ System.out.println("Found IF Statement"); }
;
whileLoop : "while"^ parExpression bloccoIstr
{ System.out.println("Found While Statement"); }
;
modifier
:
"public"
| "protected"
| "private"
| "static"
| "abstract"
| "final"
| "native"
| "synchronized"
| "transient"
| "volatile"
| "strictfp"
;
returnType
: Type | "void" ;
type
: "boolean"
| "char"
| "byte"
| "int"
| "short"
| "long"
| "float"
| "double"
;
// EXPRESSIONS
parExpression : LRBRACK! expression RRBRACK!;
expression
: conditionalExpression (assOp expression)?
;
assOp : ASSIGN^ | BAND_ASSIGN^ | BOR_ASSIGN^ | BXOR_ASSIGN^ | SL_ASSIGN^ | BSR_ASSIGN^ | SR_ASSIGN^ | MOD_ASSIGN^
| MUL_ASSIGN^ | DIV_ASSIGN^ | MINUS_ASSIGN^ | PLUS_ASSIGN^
;
conditionalExpression : conditionalAndExpression ( LOR^ conditionalAndExpression )* ;
conditionalAndExpression : bitwiseor ( LAND^ bitwiseor )* ;
bitwiseor : bitwisexor ( BOR^ bitwisexor)* ;
bitwisexor : bitwiseand (BXOR^ bitwiseand)* ;
bitwiseand : equalityexpr ( BAND^ equalityexpr )* ;
equalityexpr : relationalexpr ( (EQUAL^ | NOT_EQUAL^) relationalexpr)* ;
relationalexpr : shiftexpr ((LTE^ | LT^ | GTE^ | GT^) shiftexpr)* ;
shiftexpr : addexpr ((SR^ | BSR^ | SL^) addexpr)* ;
addexpr : mulexpr ((PLUS^ | MINUS^) mulexpr)* ;
mulexpr : atom ((MUL^ | DIV^) atom)* ;
atom : parExpression | IDENTIFIER | numberString;
numberString: NUMBERS | DECIMAL_NUMBERS;
/*************************************************
* *
* EASY JAVA LEXER *
* *
*************************************************/
class EasyJavaLexer extends Lexer;
options {
charVocabulary='\u0003'..'\uFFFF';
exportVocab=EasyJava; // call the vocabulary "EasyJava"
testLiterals=false; // don't automatically test for literals
k=5; // lookahead
}
IDENTIFIER
options {testLiterals=true;}
: ('a'..'z'|'A'..'Z'|'_'|'$') ('a'..'z'|'A'..'Z'|'_'|'0'..'9'|'$')*
;
NUMBERS : ('0' | '1'..'9' ('0'..'9')*) (DOT ('0'..'9')+ { _ttype = DECIMAL_NUMBERS; })? ;
// OPERATORS
QUESTION options { paraphrase="?"; } : '?' ;
LRBRACK options { paraphrase="("; } : '(' ;
RRBRACK options { paraphrase=")"; } : ')' ;
LSBRACK options { paraphrase="["; } : '[' ;
RSBRACK options { paraphrase="]"; } : ']' ;
LCBRACK options { paraphrase="{"; } : '{' ;
RCBRACK options { paraphrase="}"; } : '}' ;
COLON options { paraphrase=":"; } : ':' ;
COMMA options { paraphrase=","; } : ',' ;
DOT options { paraphrase="."; } : '.' ;
LNOT options { paraphrase="!"; } : '!' ;
INC options { paraphrase="++"; } : "++" ;
DEC options { paraphrase="--"; } : "--" ;
MOD options { paraphrase="%"; } : '%' ;
SEMI options { paraphrase=";"; } : ';' ;
// ARITHMETIC OPERATORS
DIV : '/' ;
PLUS : '+' ;
MINUS : '-' ;
MUL : '*' ;
// LOGICAL OPERATORS
LAND options { paraphrase="&&"; } : "&&" ;
LOR options { paraphrase="||"; } : "||" ;
// RELATIONAL OPERATORS
LTE options { paraphrase="Less than or equal"; } : "<=" ;
LT options { paraphrase="Less than"; } : '<' ;
GTE options { paraphrase="Greater than or equal"; } : ">=" ;
GT options { paraphrase="Greater than"; } : '>' ;
// ASSIGN OPERATORS
ASSIGN options { paraphrase="="; } : '=' ;
BAND_ASSIGN options { paraphrase="&="; } : "&=" ;
BOR_ASSIGN options { paraphrase="|="; } : "|=" ;
BXOR_ASSIGN options { paraphrase="^="; } : "^=" ;
SL_ASSIGN options { paraphrase="<<="; } : "<<=" ;
BSR_ASSIGN options { paraphrase=">>>="; } : ">>>=" ;
SR_ASSIGN options { paraphrase=">>="; } : ">>=" ;
MOD_ASSIGN options { paraphrase="%="; } : "%=" ;
MUL_ASSIGN options { paraphrase="*="; } : "*=" ;
DIV_ASSIGN options { paraphrase="/="; } : "/=" ;
MINUS_ASSIGN options { paraphrase="-="; } : "-=" ;
PLUS_ASSIGN options { paraphrase="+="; } : "+=" ;
// BITWISE OPERATORS
BXOR options { paraphrase="^"; } : '^' ;
BOR options { paraphrase="|"; } : '|' ;
BAND options { paraphrase="&"; } : '&' ;
BNOT options { paraphrase="~"; } : '~' ;
// EQUALITY OPERATORS
EQUAL options { paraphrase="=="; } : "==" ;
NOT_EQUAL options { paraphrase="!="; } : "!=" ;
// SHIFT
SR options { paraphrase=">>"; } : ">>" ;
BSR options { paraphrase=">>>"; } : ">>>" ;
SL options { paraphrase="<<"; } : "<<" ;
// Whitespace -- ignored
WS : ( ' '
| '\t'
| '\f'
// handle newlines
| ( options {generateAmbigWarnings=false;}
: "\r\n" // Evil DOS
| '\r' // Macintosh
| '\n' // Unix (the right way)
)
{ newline(); }
)+
{ _ttype = Token.SKIP; }
;
// Single-line comments
SL_COMMENT
: "//"
(~('\n'|'\r'))* ('\n'|'\r'('\n')?)
{$setType(Token.SKIP); newline();}
;
// multiple-line comments
ML_COMMENT
: "/*"
(
options {
generateAmbigWarnings=false;
}
:
{ LA(2)!='/' }? '*'
| '\r' '\n' {newline();}
| '\r' {newline();}
| '\n' {newline();}
| ~('*'|'\n'|'\r')
)*
"*/"
{$setType(Token.SKIP);}
;
// character literals
CHAR_LITERAL
: '\'' ( ESC | ~('\''|'\n'|'\r'|'\\') ) '\''
;
// string literals
STRING_LITERAL
: '"' (ESC|~('"'|'\\'|'\n'|'\r'))* '"'
;
// escape sequence -- note that this is protected; it can only be called
// from another lexer rule -- it will not ever directly return a token to
// the parser
// There are various ambiguities hushed in this rule. The optional
// '0'...'9' digit matches should be matched here rather than letting
// them go back to STRING_LITERAL to be matched. ANTLR does the
// right thing by matching immediately; hence, it's ok to shut off
// the FOLLOW ambig warnings.
protected
ESC
: '\\'
( 'n'
| 'r'
| 't'
| 'b'
| 'f'
| '"'
| '\''
| '\\'
| '0'..'3'
(
options {
warnWhenFollowAmbig = false;
}
: '0'..'7'
(
options {
warnWhenFollowAmbig = false;
}
: '0'..'7'
)?
)?
| '4'..'7'
(
options {
warnWhenFollowAmbig = false;
}
: '0'..'7'
)?
)
;
PARTE ESPLICATIVA (under construction)
k=2 sarebbe il lookahead (guarda avanti)
Questa funzione ha un compito importante che è quello di distinguere i token.
Il lexer effettua un compito che è quello di "tokenizzare" un flusso di caratteri inizialmente privi di significato.
Ad esempio while il programma lo legge inizialmente come la sequenza di litteral 'w' 'h' 'i' 'l' 'e', poi i caratteri vengono messi insieme e formano la parola chiave while.
Esempio 1:
Con il lookhead a 1 lui per distinguere while da whine si ferma alla prima lettera. In questo caso in fase di creazione del lexer ANTLR vi dice che c'è una situazione di non-determinismo in quanto ci sono 2 regole che generano "w" e non sa quale delle 2 deve applicare:
Esempio 2:
a = bc
d = be
Queste 2 regole iniziano entrambe con la lettera b e con un lookhead impostato ad 1 per lui sono uguali.
Se impostiamo il lookahead a 2 questo non succede.
modifier
:
"public"
| "protected"
| "private"
| "static"
| "abstract"
| "final"
| "native"
| "synchronized"
| "transient"
| "volatile"
| "strictfp"
;
Questo in teoria andava messo nel Lexer e non nel Parser. Tuttavia, seguendo un suggerimento che mi è stato dato nella mailing list di ANTLR, ho preferito inserirlo nel parser, perchè mettendolo nel lexer avrei dovuto usare un lookahead di 12 per poter far riconoscere univocamente "synchronized" , rallentando successivamente l'esecuzione del programma.
Voglio farvi riflettere sul fatto che le regole del lexer iniziano con la lettera maiuscola, ma è buona norma per convenzione scriverle interamente in maiuscolo, mentre quelle del parser iniziano con la lettera minuscola.
To be continued