Non è necessario né ANTLR né il libro Dragon per scrivere manualmente un semplice analizzatore lessicale. Anche gli analizzatori lessicali per linguaggi più completi (come Java) non sono terribilmente complicati da scrivere a mano. Ovviamente se hai un compito industriale potresti prendere in considerazione strumenti di forza industriale come ANTLR o qualche variante lex, ma per imparare come funziona l'analisi lessicale, scriverne uno a mano potrebbe rivelarsi un utile esercizio. Suppongo che sia così, dal momento che hai detto che sei ancora un principiante.
Ecco un semplice analizzatore lessicale, scritto in Java, per un sottogruppo di un linguaggio simile a Scheme, che ho scritto dopo aver visto questa domanda. Penso che il codice sia relativamente facile da capire anche se non hai mai visto un lexer prima, semplicemente perché interrompere un flusso di caratteri (in questo caso uno String
) in un flusso di token (in questo caso uno List<Token>
) non è quello difficile. Se hai domande, posso provare a spiegare in modo più approfondito.
import java.util.List;
import java.util.ArrayList;
/*
* Lexical analyzer for Scheme-like minilanguage:
* (define (foo x) (bar (baz x)))
*/
public class Lexer {
public static enum Type {
// This Scheme-like language has three token types:
// open parens, close parens, and an "atom" type
LPAREN, RPAREN, ATOM;
}
public static class Token {
public final Type t;
public final String c; // contents mainly for atom tokens
// could have column and line number fields too, for reporting errors later
public Token(Type t, String c) {
this.t = t;
this.c = c;
}
public String toString() {
if(t == Type.ATOM) {
return "ATOM<" + c + ">";
}
return t.toString();
}
}
/*
* Given a String, and an index, get the atom starting at that index
*/
public static String getAtom(String s, int i) {
int j = i;
for(; j < s.length();) {
if(Character.isLetter(s.charAt(j))) {
j++;
} else {
return s.substring(i, j);
}
}
return s.substring(i, j);
}
public static List<Token> lex(String input) {
List<Token> result = new ArrayList<Token>();
for(int i = 0; i < input.length();) {
switch(input.charAt(i)) {
case '(':
result.add(new Token(Type.LPAREN, "("));
i++;
break;
case ')':
result.add(new Token(Type.RPAREN, ")"));
i++;
break;
default:
if(Character.isWhitespace(input.charAt(i))) {
i++;
} else {
String atom = getAtom(input, i);
i += atom.length();
result.add(new Token(Type.ATOM, atom));
}
break;
}
}
return result;
}
public static void main(String[] args) {
if(args.length < 1) {
System.out.println("Usage: java Lexer \"((some Scheme) (code to) lex)\".");
return;
}
List<Token> tokens = lex(args[0]);
for(Token t : tokens) {
System.out.println(t);
}
}
}
uso Esempio:
~/code/scratch $ java Lexer ""
~/code/scratch $ java Lexer "("
LPAREN
~/code/scratch $ java Lexer "()"
LPAREN
RPAREN
~/code/scratch $ java Lexer "(foo)"
LPAREN
ATOM<foo>
RPAREN
~/code/scratch $ java Lexer "(foo bar)"
LPAREN
ATOM<foo>
ATOM<bar>
RPAREN
~/code/scratch $ java Lexer "(foo (bar))"
LPAREN
ATOM<foo>
LPAREN
ATOM<bar>
RPAREN
RPAREN
Una volta scritto uno o due lexer semplici come questo, si otterrà una buona idea di come questo problema si decompone. Quindi sarebbe interessante esplorare come utilizzare strumenti automatici come lex. La teoria alla base degli abbinamenti basati su espressioni regolari non è troppo difficile, ma ci vuole un po 'per comprendere appieno. Penso che scrivere i lexer a mano motiva quello studio e ti aiuta ad affrontare meglio il problema piuttosto che immergerti nella teoria alla base della conversione delle espressioni regolari in automatiche finite (prima NFA, poi NFA in DFA), ecc ... che guado in quella teoria può essere molto da prendere in una volta, ed è facile essere sopraffatti.
Personalmente, mentre il libro del Drago è buono e molto completo, la copertura potrebbe non essere la più facile da capire perché mira a essere completa, non necessariamente accessibile. Potresti voler provare altri testi del compilatore prima di aprire il libro di Dragon.Qui ci sono un paio di libri gratuiti, che hanno abbastanza buona copertura introduttivo, IMHO:
http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
http://www.diku.dk/~torbenm/Basics/
Alcuni articoli sull'attuazione delle espressioni regolari (analisi lessicale automatizzata di solito usa le espressioni regolari)
http://swtch.com/~rsc/regexp/
Spero che questo aiuti. In bocca al lupo.
GRAZIE MOLTO SIR. Mi ha aiutato molto. Vorrei solo chiedere se è necessario per me studiare queste cose come studente di informatica. Qual è la rilevanza per il mio maggiore? – KLoverated
L'analisi lessicale è il primo passo che un compilatore o un interprete farà prima di analizzare. I compilatori (e gli interpreti) sono molto utili e senza di loro dovremmo scrivere il codice della macchina tutto il giorno. Non commenterò se uno studente di CS dovrebbe o non dovrebbe studiare compilatori. Penso che siano interessanti di per sé, e se sei un programmatore curioso potresti essere incline a chiedermi come funzionano. Ci sono molti argomenti in CS, e capire la compilazione potrebbe non essere interessante per te. Va bene anche questo. Detto questo, i compilatori sono certamente rilevanti per CS in generale. – spacemanaki
Grazie mille per aver condiviso i tuoi pensieri. Sono interessato a studiare il compilatore/processo di compilazione perché ho sognato di progettarne uno in futuro. Ciò di cui ho paura è che forse non riesco a capirlo molto bene. Come ho detto, sono ancora un principiante. Ho iniziato a studiare Informatica senza alcun background sulla programmazione di computer. Mi chiedo sempre da dove cominciare. – KLoverated