Вам не нужно ни АНТЛР, ни книга Дракона написать простой лексический анализатор вручную. Даже лексические анализаторы для более полных языков (например, Java) сложнее не писать вручную. Очевидно, что если у вас есть промышленная задача, вы можете подумать о промышленных силовых инструментах, таких как ANTLR или какой-нибудь лексический вариант, но для того, чтобы узнать, как работает лексический анализ, письмо, написанное вручную, вероятно, окажется полезным упражнением. Я предполагаю, что это так, поскольку вы сказали, что все еще новичок.
Вот простой лексический анализатор, написанный на Java, для подмножества языка типа Scheme, который я написал после просмотра этого вопроса. Я думаю, что код относительно легко понять, даже если вы никогда раньше не видели lexer, просто потому, что разбивая поток символов (в данном случае String
) в поток токенов (в данном случае List<Token>
), это не так жесткий. Если у вас есть вопросы, я могу попытаться объяснить более подробно.
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);
}
}
}
Пример использования:
~/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
После того, как вы написали один или два простых лексеры, как это, вы получите довольно хорошее представление о том, как эта проблема распадается. Тогда было бы интересно изучить, как использовать автоматизированные инструменты, такие как lex. Теория подходов, основанных на регулярных выражениях, не слишком сложна, но для полного понимания требуется некоторое время. Я думаю, что писать лексеры вручную мотивирует это изучение и помогает вам справиться с проблемой лучше, чем погрузиться в теорию преобразования регулярных выражений в конечную автоматизацию (первые NFA, затем NFAs для DFA) и т. Д. ... wading в эту теорию может быть много, чтобы принять сразу, и легко получить перегружены.
Лично, в то время как книга Дракона хорошая и очень тщательная, освещение может быть не самым простым для понимания, потому что оно имеет целью быть полным, не обязательно доступным. Возможно, вы захотите попробовать другие тексты компиляторов, прежде чем открывать книгу Дракона.Вот несколько бесплатных книг, которые имеют очень хорошее вводное покрытие, ИМХО:
http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
http://www.diku.dk/~torbenm/Basics/
Некоторые статьи об осуществлении регулярных выражений (автоматизированный лексический анализ обычно использует регулярные выражения)
http://swtch.com/~rsc/regexp/
Я надеюсь, что это поможет. Удачи.
СПАСИБО ВАМ ОЧЕНЬ СЮР. Это мне очень помогло. Я просто хотел бы спросить, нужно ли мне изучать эти вещи как студент-информатик. Что это касается моего майора? – KLoverated
Лексический анализ - это первый шаг, который сделает компилятор или интерпретатор, прежде чем разбираться. Компиляторы (и переводчики) очень полезны, и без них нам пришлось бы писать машинный код весь день. Я не буду комментировать, должен ли студент CS учиться или не должен изучать компиляторы. Я думаю, что они интересны сами по себе, и если вы любопытный программист, вы можете быть заинтересованы в том, как они работают. В CS есть много тем, и понимание компиляции может быть вам неинтересно. Тоже норм. Тем не менее, компиляторы, безусловно, имеют отношение к CS в целом. – spacemanaki
Большое спасибо за то, что вы делитесь своими мыслями. Мне интересно изучить процесс компиляции/компиляции, потому что я когда-нибудь мечтал о разработке. Чего я боюсь, так это то, что я не могу понять это очень хорошо. Как я уже сказал, я все еще новичок. Я начал изучать компьютерную науку без каких-либо предпосылок о программировании. Мне всегда интересно, с чего начать. – KLoverated