詞法分析是編譯器實現的第一步。主要是分析輸入的源程序（字符串），輸出該字符串中出現的所有的合法的單詞。例如：int a = 3 + 5;經過詞法分析會輸出 int,a,=,3,+,5和;這七個單詞。實現詞法分析器的官方做法是：
1.寫出各個單詞的正規式（正則表達式）；
2.根據正規式構造NFA（不確定的有限自動機）；
3.將NFA轉換DFA（確定的有限自動機）；
4.根據DFA就可以實現詞法分析器，寫出程序。
下面用實例來說明上面的各個步驟：
假設我們要實現一個很簡單的腳本，該腳本中只有兩種類型的單詞，一種就是變量，變量名的規則就是以字母開頭后面緊跟0個或多個字母或數字的的字符串，如 a 和 a12d3 等；另一種就是操作符，很簡單只有 &,|,~,(,),==,!= 這幾個。給出幾個腳本的實例：result1 & result2，rst1&(rst2|rst3)，answer1 | (~answer2)。
按照上面的步驟，讓我們來看一下如何實現這個詞法分析器：
第一步：寫出正規式
變量的正規式是：letter(letter|digit)
*
操作符的正規式：&,|,~,(,)。由于操作符都是固定字符的，所以正規式就是它本身。
第二步：根據正規式構造NFA
正規式構造NFA的基礎是先構造正規式中每個字符的NFA，如變量的正規式中只有兩個字符 letter 和 digit,他們的正規式分別是：
根據構造|形式的NFA的公式可以構造 letter|digit 的NFA如下圖：
(letter|digit)
*的NFA為：
letter(letter|digit)
*的NFA為：
第三步：將NFA轉換為DFA
先是將所有通過
ε可以到達的狀態合并，由上圖NFA可以看出1,2,3,4,6,9都是通過ε可以直接用箭頭連接的，以此類推5,8,9,3,4,6和7,8,9,3,4,6都是可以合并稱一個狀態的，如下圖：
此圖用新的DFA表示如下：
由于生成的DFA的狀態過多，需要將上面的DFA最小化，生成狀態數最少的DFA，最小化DFA的過程就是將那些無論怎樣轉換都仍然轉換到本組合內部的狀態組合合并，如上圖{B,C,D}這三個狀態組合稱狀態組無論經過letter還是digit轉換都仍然轉換到該組合，那么就可以將這三個狀態合并，如下圖：
用新狀態表示為： 
腳本中變量的DFA已經構造好了。
由于操作符都是固定字符，所以DFA比較簡單，下面給出幾個的圖示例子：
現在我們將各個單詞的DFA組合在一起，大致類似下圖：
實際上，由于這種很簡單的例子不必套用這種正規的步驟來得到DFA，可以直接把圖畫出來。首先畫一個開始狀態(Start)和一個結束狀態(Done),然后再考慮各個單詞之間的關系將其分類，這種分類的過程就看你的經驗了，依據各個單詞挨個字符被識別的過程即可畫出類似上圖的DFA，然后再根據這個DFA寫出詞法分析的程序來就非常的簡單了。
下面給出根據這個DFA的寫出的大概程序，這段代碼可執行，但是沒有考慮各種意外、出錯以及相關優化處理等，所以僅供參考，請斟酌使用：
1
2 public class ScriptScanner
3 {
4 private String scriptInput = null;
5
6 /**
7 * @param scriptInput
8 */
9 public ScriptScanner(String scriptInput)
10 {
11 this.scriptInput = scriptInput;
12 }
13
14 /** 標記當前讀取段的開始位置 */
15 private int start_read_pos = 0;
16
17 /** 當前位置 */
18 private int current_pos = 0;
19
20 private char readChar()
21 {
22 if (scriptInput == null || current_pos >= scriptInput.length())
23 return EOF;
24
25 return scriptInput.charAt(current_pos);
26 }
27
28 public Token getNextToken()
29 {
30 Token currentToken = null;
31
32 int state = STATE_START;
33
34 start_read_pos = current_pos;
35
36 while (state != STATE_DONE)
37 {
38 char ch = readChar();
39
40 switch (state)
41 {
42 case STATE_START:
43 {
44 if (Character.isLetter(ch))
45 {
46 state = STATE_IN_VAR;
47 }
48 else if (ch == '=')
49 {
50 state = STATE_IN_EQUAL;
51 }
52 else if (ch == '<')
53 {
54 state = STATE_IN_NOTEQUAL;
55 }
56 else
57 {
58 state = STATE_DONE;
59
60 switch (ch)
61 {
62 case EOF:
63 currentToken = new Token(TokenType.EOF);
64 break;
65
66 case '&':
67 currentToken = new Token(TokenType.AND);
68 break;
69
70 case '|':
71 currentToken = new Token(TokenType.OR);
72 break;
73
74 case '~':
75 currentToken = new Token(TokenType.NOT);
76 break;
77
78 case '(':
79 currentToken = new Token(TokenType.LPAREN);
80 break;
81
82 case ')':
83 currentToken = new Token(TokenType.RPAREN);
84 break;
85
86 default:
87 currentToken = new Token(TokenType.ERROR, "無法識別的字符");
88 break;
89 }
90
91 } // End: else
92
93 current_pos ++; // 開始狀態下除 EOF 外都需要將位置后移
94
95 break;
96
97 } // End: case STATE_START
98
99 case STATE_IN_EQUAL:
100 {
101 state = STATE_DONE;
102
103 if (ch == '=')
104 {
105 currentToken = new Token(TokenType.EQUAL);
106 }
107 else
108 {
109 currentToken = new Token(TokenType.ERROR, "錯誤的運算符");
110 }
111
112 current_pos ++;
113
114 break;
115
116 } // End: case STATE_IN_EQUAL
117
118 case STATE_IN_NOTEQUAL:
119 {
120 state = STATE_DONE;
121
122 if (ch == '>')
123 {
124 currentToken = new Token(TokenType.NOTEQUAL);
125 }
126 else
127 {
128 currentToken = new Token(TokenType.ERROR, "錯誤的運算符");
129 }
130
131 current_pos ++;
132
133 break;
134
135 } // End: case STATE_IN_NOTEQUAL
136
137 case STATE_IN_VAR:
138 {
139 if (! Character.isLetterOrDigit(ch))
140 {
141 state = STATE_DONE;
142
143 String value = scriptInput.substring(start_read_pos, current_pos);
144
145 currentToken = new Token(TokenType.ID, value);
146 }
147 else
148 {
149 current_pos ++;
150 }
151
152 break;
153
154 } // End: case STATE_IN_VAR
155
156 default:
157 {
158 state = STATE_DONE;
159
160 currentToken = new Token(TokenType.ERROR);
161 }
162 } // End: switch (state)
163 }
164
165 return currentToken;
166 }
167
168 public final static char EOF = '\0';
169
170 /*
171 * 定義 DFA 的狀態。
172 */
173
174 /** 開始狀態 */
175 public final static int STATE_START = 0;
176
177 /** 當前 Token 是變量 */
178 public final static int STATE_IN_VAR = 1;
179
180 /** 當前 Token 是 "==" */
181 public final static int STATE_IN_EQUAL = 2;
182
183 /** 當前 Token 是 "<>" */
184 public final static int STATE_IN_NOTEQUAL = 3;
185
186 /** 當前 Token 結束 */
187 public final static int STATE_DONE = 4;
188 }
189
從代碼中可以看出，預先根據DFA定義了5個狀態：STATE_START，STATE_IN_VAR，STATE_IN_EQUAL，STATE_IN_NOTEQUAL，STATE_DONE，然后每個記號（Token）都是從STATE_START開始到STATE_DONE結束，中間根據輸入字符的不同在各個狀態中不斷的轉換，直到識別出記號或者錯誤為止。由此可見只要畫好DFA寫代碼就簡單多了。
有興趣的朋友可以研究一下語法分析，生成語法樹，根據語法樹求值；也可以研究一下利用中綴表達式求值。
http://www.tkk7.com/qujinlong123/