Trzeba ani ANTLR ani książki Smoka napisać prosty analizator leksykalny ręką. Nawet analizatory leksykalne dla pełniejszych języków (takich jak Java) nie są zbyt skomplikowane, by pisać ręcznie. Oczywiście, jeśli masz zadanie przemysłowe, możesz rozważyć przemysłowe narzędzia wytrzymałościowe, takie jak ANTLR lub jakiś wariant leksykalny, ale aby nauczyć się, jak działa analiza leksykalna, pisanie jedną ręką mogłoby okazać się użytecznym ćwiczeniem. Zakładam, że tak jest, ponieważ powiedziałeś, że wciąż jesteś początkujący.
Oto prosty analizator leksykalny, napisany w Javie, dla podzbioru schematu podobnego języka, który napisałam po obejrzeniu to pytanie. Myślę, że kod jest stosunkowo łatwy do zrozumienia, nawet jeśli nigdy wcześniej nie widziałeś lexera, po prostu dlatego, że rozbicie strumienia postaci (w tym przypadku String
) na strumień tokenów (w tym przypadku List<Token>
) nie jest ciężko. Jeśli masz pytania, mogę spróbować wyjaśnić dokładniej.
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);
}
}
}
Przykład użycia:
~/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
Po wpisaniu jeden lub dwa proste lexers tak, można uzyskać całkiem dobry pomysł, jak ten problem rozkłada. W takim razie warto odkryć, jak korzystać z automatycznych narzędzi, takich jak Lex. Teoria stojąca za odpowiednikami wyrażeń regularnych nie jest zbyt trudna, ale pełne zrozumienie zajmuje trochę czasu. Myślę, że pisanie lexers ręcznie motywuje to badanie i pomaga lepiej poradzić sobie z problemem, niż zagłębiać się w teorię konwersji wyrażeń regularnych w skończoną automatyzację (pierwsze NFA, potem NFAs w DFA), itd ... brnąc w tę teorię być dużo do wzięcia na raz, i łatwo jest uzyskać przytłoczony.
Osobiście, podczas gdy książka smok jest dobra i bardzo dokładny, zasięg może nie być najłatwiejsze do zrozumienia, ponieważ ma być kompletna, niekoniecznie dostępne. Przed otwarciem książki Smoka możesz wypróbować inne teksty kompilatora.Oto kilka darmowe książki, które mają dość dobre pokrycie wprowadzającym IMHO:
http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
http://www.diku.dk/~torbenm/Basics/
Niektóre artykuły dotyczące realizacji wyrażeń regularnych (zautomatyzowana analiza leksykalna zwykle używa wyrażeń regularnych)
http://swtch.com/~rsc/regexp/
Mam nadzieję, że to pomaga. Powodzenia.
DZIĘKUJEMY BARDZO DUŻY SIR. Bardzo mi to pomogło. Chciałbym zapytać, czy muszę studiować te rzeczy jako student informatyki. Jakie ma to znaczenie dla mojego majora? – KLoverated
Analiza leksykalna jest pierwszym krokiem, który zrobi kompilator lub interpreter, przed analizą składni. Kompilatory (i interpretery) są bardzo przydatne, a bez nich musielibyśmy napisać cały kod maszynowy. Nie będę komentował, czy uczeń CS powinien, czy nie powinien uczyć się kompilatorów. Myślę, że są one interesujące same w sobie, a jeśli jesteś ciekawym programistą, możesz być ciekawy, jak działają. W CS jest wiele tematów, a zrozumienie kompilacji może nie być dla ciebie interesujące. To też jest w porządku. Powiedział, że kompilatory są z pewnością istotne dla CS w ogóle. – spacemanaki
Dziękuję bardzo za podzielenie się swoimi przemyśleniami. Interesuje mnie studiowanie procesu kompilacji/kompilacji, ponieważ marzyłem o zaprojektowaniu pewnego dnia. Obawiam się, że może nie rozumiem tego bardzo dobrze. Jak już powiedziałem, wciąż jestem początkującym. Zacząłem studiować informatykę bez żadnego zaplecza na temat programowania komputerów. Zawsze zastanawiam się, od czego zacząć. – KLoverated