计算机是无法对程序语言的产生人一样的“理解”的，对于计算机一个程序只是一个字符串。因此要在计算机上运行一段程序就需要把程序语言转化为机器语言，这个过程就是“编译”。编译的第一步（通常称为前端）就是对程序语言做词法分析和语法分析 。
词法分析
词法分析的任务是把一整串程序代码切分成一个一个的token，token就是数字、变量名、关键字、函数名这些程序语言中的基本单位。我们在这里考虑最简单的While语言，它包括以下token：运算符（+,-,*,/,...）、赋值符号（=）、间隔符（(,),{,}）、自然数（0,23,...）、变量名（x1,yyy,__x,...）、关键字（if,while,var,...）、函数名（read,write）。例如，对于表达式(1+x)*y ，我们期待词法分析结果为TOK_LEFT_PAREN TOK_NAT(1) TOK_PLUS TOK_IDENT(x) TOK_RIGHT_PAREN TOK_MUL TOK_IDENT(y)
因此，词法分析本质上是做字符串匹配——用token匹配程序代码。我们可以用“正则表达式”这一语言来描述字符串（token），正则表达式\(r\)递归定义如下：\(r=\epsilon\)表示空串；\(r=c\)表示单个字符\(c\)；\(r=r_1|r_2\)表示\(r_1\)或\(r_2\)；\(r=r_1r_2\)表示\(r_1\)和\(r_2\)首位连接；\(r^*\)表示空或\(r\)或\(rr\)或\(rrr\cdots\)。通常我们有一些惯用的简写，用[a-cA-C]表示a|b|c|A|B|C；用r?表示r|ε。于是变量名的正则表达式写作[_a-zA-Z][_a-zA-Z0-9]*，自然数的正则表达式写作0|[1-9][0-9]* 。
匹配字符串的最常用办法就是转化为在自动机上做状态转移（走路）。我们很容易把正则表达式转化为一个非确定性有限状态自动机(NFA，Nondeterministic Finite Automata)，在这种自动机上状态转移的字符可以是ASCII码或\(\epsilon\)（空），同时从一个状态出发一个字符有多种转移方式。我们在自动机上选出起点状态和若干终点状态，期待从起点出发能到达终点当且仅当走过的所有状态转移字符一起串成的字符串落在正则表达式内。为此，对于单个字符\(c\)只需要一个起点和终点中间连接\(c\)这一条状态转移边；空字符\(\epsilon\)只需要一个起点和终点以及一条\(\epsilon\)边；\(r_1|r_2\)我们从一个起点出发连两条\(\epsilon\)边连向\(r_1,r_2\)的自动机的起点，再让它们的终点以\(\epsilon\)边连向一个终点；\(r_1r_2\)只需把\(r_1\)的终点用\(\epsilon\)边连向\(r_2\)的起点；对于\(r^*\)，我们从\(r\)的终点连一条\(\epsilon\)边向\(r\)的起点，再从起点用一条\(\epsilon\)边连向\(r\)的起点。至此，我们已经能把一切正则表达式转化为NFA了。
然而在实践中我们是不可能用NFA来匹配字符串的，因为从一个状态出发我们并不知道应当选择哪条路径。而接下来我们说明，我们可以高效地把NFA转化为DFA（有限状态自动机，Deterministic Finite Automata），这种自动机的转移边只有ASCII码而没有\(\epsilon\)边，从一个状态出发一个字符只有一种转移方式。方法是：DFA的每个状态是NFA状态的集合。从起点出发，把所有只经过\(\epsilon\)边能到达的状态集合作为DFA的起始状态。对于每个DFA的状态，它经过字符\(c\)能到达的状态是，把NFA中这些状态对应的状态只经过\(\epsilon\)边或\(c\)边能到达的新状态收集起来作为一个新的状态集合。可以证明这样构建得到的一定是正确的DFA。
语法分析
在词法分析以后，我们希望能够得到表达式和程序语句的抽象语法树。例如对于(1+x)*y，我们希望根节点为*，左儿子为+，右儿子为y，+的儿子分别是1和x。