源代码文本经过词法分析后，变成一串token。语法分析就是处理这串token，使之变成树状的token。这个树状的token就是AST。比如源代码文本1 + 2 * 3经过语法分析，变为后序遍历这颗树就可以求出这个表达式的值。怎么构造这颗树呢?使用自顶向下算法。首先构造第一个表达式节点，然后遇到1构造一个1节点，作为第一个表达式的子节点。然后遇到+构造+号节点，也作为第一个表达式的子节点。后面要么是一个表达式，要么是一个数字，所以也构造一个表达式节点作为第一个表达式节点的子节点。然后遇到2，构造一个2节点，作为第二个表达式节点的子节点，然后遇到*号，构造一个*节点作为第二个表达式的子节点，然后遇到3，构造一个3节点，作为第二个表达式的子节点。什么是表达式呢?假设expr表示表达式，并且expr只有加法和乘法，则有如下定义：expr -> add add -> mul ｜ add + mul mul -> literal | mul * literal literal -> 0｜1｜2｜3｜4｜5｜6｜7｜8｜9上面的式子叫产生式，可以读作expr由add组成。a

 什么是词法分析?就是把字符串流根据词语组成的法则，切分成一个个有效的词。以c语言为例，词法分析的任务是把形如"int a = 1; int b = 2; int c = a + b;"这样的字符串切分成int,a,=,1,;,int,b,=,2,;,int,c=,a,+,b,;这样的一个个词，编译原理中一般叫token。 那怎么切呢？从左到右看，第一个字母i，以i打头的词语有几种可能，第一种可能是关键字int，第二种可能是关键字if，第三种可能是变量名i或者ints或者ias之类,所以还要继续往右看，如果第二个字母是空格，则i确定了，就是变量名i。如果第二个字母是n,则in有可能是int或者变量名，如果是f，则if有可能是关键字if或者变量名，如果既不是n不是f也不是空格，则是变量名。还需要继续往下看。就这样一个一个字符从左往右看，根据词法规则，来切分token。 词法规则可以用正则表达式来表示。比如变量名是以字母开头后面可以跟字母或数字，可以表示成a-zA-z*。从左往右扫描时根据正则表达式来匹配token。匹配的过程可以用有限自动机来表示。如下图&e