1．1 Lex概述

    程序设计语言从机器语言发展到今天的象pascal, C等这样的高级语言，使人们可以摆脱与机器有关的细节进行程序设计。但是用高级语言写程序时程序员必须在程序中详尽地告诉计算机系统怎样去解决某个问题，这在某种程度上说也是一件很复杂的工作。

    人们希望有新的语言——非常高级的语言，用这种语言程序员仅仅需要告诉计算机系统要解决什么问题，计算机系统能自动地从这个问题的描述去寻求解决问题的途径，或者说将这个问题的描述自动地转换成用某种高级语言如C、FORTRAN表示的程序。这个程序就可以解决给定的问题，这种希望虽然还没有能够完全变成现实，但是在某些具体的问题领域里已经部分地实现了。

   这里要介绍的Lex和下章要介绍的Yacc就是在编译程序设计这个领域里的两种非常高级的语言。用它们可以很方便的描述词法分析器和语法分析器，并自动产生出相应的高级语言（C）的程序。

    Lex是一个词法分析器（扫描器）的自动产生系统，它的示意图如图1.1。

    Lex源程序是用一种面向问题的语言写成的。这个语言的核心是正规表达式（正规式），用它描述输入串的词法结构。在这个语言中用户还可以描述当某一个词形被识别出来时要完成的动作，例如在高级语言的词法分析器中，当识别出一个关键字时，它应该向语法分析器返回该关键字的内部编码。Lex并不是一个完整的语言，它只是某种高级语言（称为lex的宿主语言）的扩充，因此lex没有为描述动作设计新的语言，而是借助其宿主语言来描述动作。我们只介绍C作为lex的宿主语言时的使用方法，在Unix系统中，FORTRAN语言的一种改进形式Ratfor也可以做lex的宿主语言。 

    Lex自动地表示把输入串词法结构的正规式及相应的动作转换成一个宿主语言的程序，即词法分析程序，它有一个固定的名字yyler，在这里yyler是一个C语言的程序。

    Yylex将识别出输入串中的词形，并且在识别出某词形时完成指定的动作。

    看一个简单的例子：写一个lex源程序，将输入串中的小写字母转换成相应的大定字母。

    程序如下：

    %%
    
    [a-z]printf(“%c”.yytext[0]+'A'-'a')；

    上述程序中的第一行%%是一个分界符，表示识别规则的开始。第二行就是识别规则。左边是识别小写字母的正规式。右边就是识别出小写字母时采取的动作:将小写字母转换成相应的大写字母。

    Lex的工作原理是将源程序中的正规式转换成相应的确定有限自动机，而相应的动作则插入到yylox中适当的地方，控制流由该确定有限自动机的解释器掌握，不同的源程序，这个解释器是相同的。关于lex工作原理的详细情况请参考[3]，这里不多介绍。

1．2 lex源程序的格式

    lex源程序的一般格式是：

    {辅助定义的部分}

    %%

    {识别规则部分}

    %% 

    {用户子程序部分}

    其中用花括号起来的各部分都不是必须有的。当没有“用户子程序部分”时，第二个%%也可以省去。第一个%%是必须的，因为它标志着识别规则部分的开始，最短的合法的lex源程序是：
   
    %%

    它的作用是将输入串照原样抄到输出文件中。

    识别规则都分是Lex源程序的核心。它是一张表，左边一列是正规式，右边一列是相应的动作。下面是一条典型的识别规则：

    integer printf（"found keywcrd INT"）;

    这条规则的意思是在输入串中寻找词形“integer”，每当与之匹配成功时，就打印出“foundkeyword INT”这句话。

    注意在识别规则中，正规式与动作之间必须用空格分隔开。动作部分如果只是一个简单的C表达式，则可以写在正规式右边同一行中，如果动作需要占两行以上，则须用花括号括起来，否则会出错。上倒也可以写成：

    integer {printf（"found keyword INT"）;}

    下面先介绍识别规则部分的写法，再介绍其余部分。

1.3 Lex用的正规式

    一个正规式表示一个字符串的集合。正规式由正文字符与正规式运算符组成．正文字符组成基本的正规式，表示某一个符号串；

正规式运算符则将基本的正规式组合成为复杂的正规式，表示字符串的集合。

    例如：

                ab 
    
    仅表示字符串ab，而

               （a b）+

    表示字符串的集合：

               ｛ab，abab，ababab，…）。

    Lex中的正规式运算符有下列十六种：

    ”\[ ]∧ -？•*+| （）/${} %<> 

    上述运算符需要作为正文字符出现在正规式中时，必须借助于双引号”或反斜线＼，具体用法是；

    xyz“++”或xyz＼+＼+

    表示字符串xyz++

    为避免死记上述十多个运算符，建议在使用非数字或字母字符时都用双引号或反斜线。

    要表示双引号本身可用＼”，要表示反外线用”＼”或\\

    前面说过，在识别规则中空格表示正规式的结束，因此要在正规式中引进空格必须借助双引号或反斜线，但出现在方括号[]之内的空格是例外。

几个特殊符号：

＼n是回车换行（newline）

＼t是tab

\b是退格（back space）

下面按照运算符的功能分别介绍上述正规式运算符。

1．字符的集合

用方括号对可以表示字符的集合。正规式

[a b c]

与单个字符a或b或c匹配

在方括号中大多数的运算符都不起作用，只有＼-和∧例外。

运算符----表示字符的范围，例如

［a-z 0-9 ＜＞-]

表示由所有小写字母，所有数字、尖括号及下划线组成的字符集合。

如果某字符集合中包括-在内，则必须把它写在第一个或最后一个位置上，如

[-+0-9]

与所有数字和正负号匹配

在字符集合中，运算符∧必须写在第一个位置即紧接在左方括号之后，它的作用是求方括号中除∧之外的字符组成的字符集合相对于计算机的字符集的补集，例如 [∧abc]与除去a、b和c以外的任何符号匹配。

运算符＼在方括号中同样发挥解除运算符作用的功能。

2．与任意字符匹配的正规式

运算符。形成的正规式与除回车换行符以外的任意字符匹配。

在lex的正规式中，也可以用八进制数字与＼一起表示字符，如

[＼40-＼176]

与ASCII字符集中所有在八进制 40（空格）到八进制176（～）之间的可打印字符匹配。

3．可有可无的表达式

运算得？指出正规式中可有可无的子式，例如

ab?c

与ac或abc匹配，即b是可有可无的。

4．闭包运算

    运算符*和十是 Lex正规式中的闭包运算符，它们表示正规式中某子式的重复，例如"a*"表示由0个或多个a组成的字符串的集合，而"a+"表示由1个或多个a组成的字符串的集合，下面两个正规式是常用的：
[a-z]+

[A-Za-z][A-Za-z 0-9]*

第一个是所有由小写字母组成的字符串的集合，第二个是由字母开头的字母数字串组成的集合。

5、选择和字符组

运算符|表示选择：

（ab|cd）

与ab或cd匹配

运算符（）表示一组字符，注意（）与[ ]的区别。（ab）表示字符串ab，而[ab]则表示单个字符a或b。

圆括号（）用于表示复杂的正规式，例如：

（ab|cd+）？（ef）*

与abefef, efef, cdef, cddd匹配，但不与abc, abcd或abcdef匹配。

6、上下文相关性

    lex可以识别一定范围的上下文，因此可在一定程度上表示上下文相关性。

     若某正规式的第一个字符是∧，则仅当该正规出现在一行的开始处时才被匹配，一行的开始处是指整个输入串的开始或者紧接在一个回车换行之后，注意∧还有另一个作作即求补，∧的这两种用法不可能发生矛盾。

    若某正规式的最后一个字符是$，则仅当该表达式出现在一行的结尾处时才被匹配，一行的结尾处是指该表达式之后紧接一个回车换行。

    运算符/指出某正规式是否被匹配取决于它的后文，例如: ab/cd，仅在ab之后紧接cd的情况下才与ab匹配。$其实是/的一个特殊情形，例如下面两个正规式等价：ab$,ab/\ n

    某正规式是否被匹配，或者匹配后执行什么样的动作也可能取决于该表达式的前文，前文相关性的处理方法在后面专门讨论，将用到运算符"<>"

7、重复和辅助定义

    当被{}括起来的是数字对时，{}表示重复；当它括起来的是一个名字时，则表示辅助定义的展开。例如：a{1，5} ，表示集合{a.aa.aaa.aaaa.aaaaa}.{digit}则与预先定义的名叫dight的串匹配，并将有定义插入到它在正规式中出现的位置上，辅助定义在后面专门讨论。

    最后，符号%的作用是作为lex源程序的段间分隔符。

1．4 Lex源程序中的动作

    前面说过当Lex识别出一个词形时，要完成相应的动作。这一节叙述Lex为描述动作提供的帮助。

    首先应指出，输入串中那些不与任何识别规则中的正规式匹配的字符串将被原样照望抄到输出文件中去。因此如果用户不仅仅是希望照抄输出，就必须为每一个可能的词形提供识别规则，并在其中提供相应的动作。用lex为工具写程序语言的词法分析器时尤其要注意。最简单的一种动作是滤掉输入中的某些字符串，这种动作用C的空语句“；”来实现。

例：滤掉输入申中所有空格、tab和回车换行符，相应的识别规则如下：

［\t\n]；

如果相邻的几条规则的动作都相同，则可以用|表示动作部分，它指出该规则的动作与下一条规则的动作相同。例如上倒也可以写成： 

“ ”| 

“\t”|

“\n”；

注意\t和\n中的双引号可以去掉。

   外部字符数组yytext的内容是当前被某规则匹配的字符串，例如正规式[a-z]+与所有由小写字母组成的字符串匹配，要想知道与它匹配的具体字符串是什么，可用下述规则：

[a－z]＋ printf（“％ s”， yytext）;

动作printf（“％s”，yytext）就是将字符数组yytext的内容打印出来，这个动作用得很频繁，Lex提供了一个宏ECHO来表示它，因此上述识别规则可以写成：

［a－z]+ECHO；

请注意，上面说过缺省的动作就是将输入串原样抄到输出文件中，那么上述规则起什么作用呢？这一点将在“规则的二义性”一节中解释。

    有时有必要知道被匹配的字符串中的字符个数，外部变量yyleng就表示当前yytext中字符的个数。例如要对输入串中单词的个数和字符的个数进行计数（单词假定是由大写或小写字母组成的字符串），可用下述规则：
[a-zA－Z]+ {words++；

Chars+=yyleng；}

注意被匹配的字符串的第一个字符和最后一个字符分别是

yytext[0]和yytext[yyleng-1]

    下面介绍三个Lex提供的在写动作时可能用到的C函数

l．yymore（）

     当需下一次被匹配的字符串被添加在当前识别出的字符串后面，即不使下一次的输入替换yytext中已有的内容而是接在它的内容之后，必须在当前的动作中调用yymore( )

例：假设一个语言规定它的字符串括在两个双引号之间，如果某字符串中含有双引号，则在它前面加上反斜线＼。用一个正规式来表达该字符串的定义很不容易，不如用下面较简明的正规式与yymore（）配合来识别：

\" [∧"]*{ 
if（yytext[yyleng－1]
= =’\\’yymore( );
else
…normal user processing
｝

当输入串为”abc＼"def”时，上述规则首先与前五个字符”abc＼匹配，然后调用yymore（ ）使余下部分”def被添加在前一部分之后，注意作为字符串结尾标志的那个双引号由”normal user proessing”部分负责处理

2．yyless（n）

    如果当前匹配的字符串的末尾部分需要重新处理，那么可以调用 yyless（n）将这部分子串“退回”给输入串，下次再匹配处理。yyless(n）中的n是不退回的字符个数，即退回的字符个数是yyleng-n。

例；在C语言中串“=-a”具有二义性，假定要把它解释为“=-a”同时给出信息，可用下面的识别规则：

=-［a-zA-Z]{
printf（“Operator（=-）
ambiguous\n”）；
yyless（yyleng-1）;
…action for＝-…
｝

上面的规则先打印出一条说明出现二义性的信息，将运算符后面的字母返回给输入串，最后将运算符按“=－”处理．另外，如果希望把“=- a”解释为”＝- a”，这只需要把负号与字母一起退回给输入串等候下次处理，用下面的规则即可：

=-[a-zA-Z］｛
printf（“Operator（=-）
ambiguous\n”）；
yyless (yyleng-1);
…action for = …
} 
3. yywrap ( )

    当Lex处理到输入串的文件尾时，自动地调用yywrap（），如果 yywrap（）返回值是 1，那么Lex就认为对输入的处理完全结束，如果yywrap（）返回的值是0,Lex就认为有新的输入串等待处理。

    Lex自动提供一个yywrap（），它总是返回1，如果用户希望有一个返回0的yywrap（ ），那么就可以在”用户子程序部分”自己写一个 yywrap（），它将取代Lex自动提供的那个yywrap（），在用户自己写的ywrap（）中，用户还可以作其他的一些希望在输入文件结束处要作的动作，如打印表格、输出统计结果等，使用yywrap（）的例子在后面举出。

1. 5识别规则的二义性

    有时Lex的程序中可能有多于一条规则与同一个字符串匹配，这就是规则的二义性，在这种情况下，Lex有两个处理原则：

1）能匹配最多字符的规则优先

2）在能匹配相同数目的字符的规则中，先给出的规则优先

例：设有两规则按下面次序给出：

integer kegword action…
[a-z]+ identifier action…

如果输入是integers，则它将被当成标识符处理，因为规则integer只能匹配7个字符，而[a-z]+能匹配8个字符；如果输入串是integer，那么它将被当作关键字处理，因为两条规则都能与之匹配，但规则integer先给出。


1.6 lex源程序中的辅助定义部分

    Lex源程序的第一部分是辅助定义，到目前为止我们只涉及到怎样写第二部分，即识别规则部分的写法，现在来看第一部分的写法。在Lex源程序中，用户为方便起见，需要一些辅助定义，如用一个名字代表一个复杂的正规式。辅助定义必须在第一个％％之前结出，并且必须从第一列开始写，辅助定义的语法是：

name translation

例如用名字IDENT来代表标识符的正规式的辅助定义为

IDENT [a-zA-Z][a-zA-Z0-9]*

辅助定义在识别规则中的使用方式是用运算符｛ ｝将 name括起来，Lex自动地用 translation去替换它，例如上述标识符的辅助定义的使用为：

{IDENT｝action for identifer…

下面我们用辅助定义的手段来写一段识别FORTRAN语言中整数和实数的Lex源程序：

D    [0一9]
E    [DEde]［-+]？｛ D｝+
％％
{D}+ printf（“integer”）；
{D}+"."{D}*({E})?   |
{D}*"."{D}+({E})?   |
{D}+{E} printf( "real" );

    请注意在辅助定义部分中可以使用前面的辅助定义。例如：定义E时使用了D，但所用的辅助定义必须是事先已定义过的，不能出现循环定义。上面的规则只是说明辅助定义的用法，并不是识别FORTRAN中数的全部规则，因为它不能处理类似35.EQ．I这样的问题，即会把35.EQ．I中的35.E当作实数，怎么解决这种问题请读者思考。

    除了上面介绍的辅助定义之外，用户还需要在Lex源程序中使用变量，还需要有一些自己写的子程序。前面已经见过两个常用的变量即yytext和yylong，也介绍过几个Lex提供的子程序yymore,yyless和yywrap,现在介绍用户如何自己定义变量和写子程序。

    Lex是把用户写的Lex源程序转换成一个C语言的程序yylex，在转换过程中，Lex是把用户自己的变量定义和子程序照抄到yylex中去,lex规定属于下面三种情况之一的内容就照抄过去；

1）以一个空格或tab起头的行，若不是 Lex的识别规则的一部分，则被照抄到 Lex产生的程序中去。如果这样的行出现在第一个％％之前，它所含的定义就是全局的，即Lex产生的程序中的所有函数都可使用它。如果这样的行紧接在第一个％％之后但在所有识别规则之前，它们就是局部的，将被抄到涉及它的动作相应的代码中去。注意这些行必须符合C语言的语法，并且必须出现在所有识别规则之前。

    这一规定的一个附带的作用是使用户可以为Lex源程序或Lex产生的词法分析器提供住解，当然注解必须符合C语言文法。

2）所有被界于两行％{和％}之间的行，无论出现在哪里也无论是什么内容都被照抄过去，要注意 ％｛和％｝必须分别单独占据一行．例如；

％｛

# defineENDOFFILE 0
#include “head.h”
int flag
％｝

提供上面的措施主要因为在C语言中有一些行如上例中的宏定义或文件蕴含行必须从第一列开始写。

3）出现在第二个％％之后的任何内容，不论其格式如何，均被照抄过去。

1.7 怎样在Unix系统中使用Lex假定已经写好了一个Lex源程序。怎样在Unix系统中从它得到一个词法分析器呢？

    Lex自动地把Lex源程序转换成一个C语言的可运行的程序，这个可运行的程序放在叫Lex.yy.c的文件中，这个C语言程序再经过C编译，即可运行。

例，有一名叫source的Lex源程序，第一步用下面的命令将它转换成lex.yy.c：

$ lex source

（$是 Unix的提示符）。Lex.yy.c再用下面的命令编译即得到可运行的目标代码 a．

out：

$cc lex.yy.c－ll

上面的命令行中的一11是调用Lex的库，是必须使用的，请参看[1]。

这一节内容请读者参看[4]中的lex（1）

Lex可以很方便地与Yacc配合使用，这将在下一章中介绍。

$1.8例子

这一节举两个例子看看Lex源程序的写法

1．将输入串中所有能被7整除的整数加3，其余部分照原样输出，先看下面的Lex源程序：

％％
int k；
［0-9］+{
scanf（-1， yytext，“％d”，＆k）;
if（k ％ 7 = =0）
printf（“％d”，k+3）；
else
printf（“ ％ d”, k）;
｝

上面的程序还有不足的地方，如对负整数，只是将其绝对值加上3，而且象X7,49.63这样

的项也做了修改，下面对上面的源程序稍作修改就避免了这些问题。

％％
int k; 
-?[0-9]+{
scanf（－1，yytext，“％d”，&k）；
printf（“％d”，k％7= =0？k+3;k）;
｝
-?[0-9]+ ECHO;
[A-Za-z][A-Za-z0-9]+ ECHO;

2．下一个例子统计输人串中各种不同长度的单词的个数，统计结果在数组lengs中，单词定义为由字母组成的串，源程序如下；

int lengs [100];
％％
[a-z]+ lengs[yyleng]++;
•|
\n ;
％％
yywrap ( )
｛
int i ；
printf（“Length No.words \n”） ;
for（i＝0；i＜100；i++)
if（lengs［i］＞0）
ptintf（“％5d ％ 10d＼n”，i， lengs[i];
return (1);
｝

在上面的流程序中，当Lex读入输入串时，它只统计而不输出，到输入串读入完毕后，才在调用 yywrap（）时输出统计结果，为此用户自己提供了yywrap（），注意yywrap（）的最后一个语句是返回值1。

1.9 再谈上下文相关性的处理

    在$3中介绍Lex用的正规式时提到了上下文相关性的表示，这里再详细介绍Lex提供的处理上下文相关的措施。要处理的问题是某些规则在不同的上下文中要采取不同的动作，或者说同样的字符串在不同的上下文中有不同的解释。例如在程序设计语言中，同一个等号“=”，在说明部分表示为变量赋初值，这时的动作应是修改符号表内容；而在语句部分等号就是赋值语句的赋值号，这时又应该产生相应于赋值语句的代码。因此要依据等号所处的上下文来判断它的含义。Lex提供了两种主要的方法，

1）使用标志来区分不同的上下文。

    标志是用户定义的变量，用户在不同的上下文中为它置不同的值，以区分它在哪个上下文中，这样识别规则就可以根据标志当前值决定在哪个上下文中并采取相应的动作。

例：将输入串照原样输出，但对magic这个词，当它出现在以字母a开头的行中，将其改为first，出现在以b开头的行中将其改为second，出现在以c开头的行中则改为third。

使用标志flag的Lex源程序如下；

int flag ;

％％
∧a {flag='a';ECHO;}
∧b {flag='b'; ECHO;}
∧c {flag='c'; ECHO;}
\n {flag=o; ECHO;}
magic{
switch (flag)
{ 
case 'a' : printf (“first”); break;
case 'b': printf (“second”); break;
case 'c' : printf (“third”); break;
default; ECHO; break;
} 
}

2）使用开始条件来区分不同上下文

    在Lex源程序中用户可以用名字定义不同的开始条件。当把某个开始条件立置于某条识别规则之前时，只有在Lex处于这个开始条件下这条规则才起使用，否则等于没有这条规则。Lex当前所处的开始条件可以随时由用户程序（即Lex动作）改变。

开始条件由用户在Lex源程序的“辅助定义部分”定义，语法是

％Start name1 name2 name3…

其中Start可以缩写成S或s。开始条件名字的顺序可以任意给出，有很多开始条件时也可以由多个％Start行来定义它们。

开始条件在识别规则中的使用方法是把它用尖括号括起来放在识别规则的正规式左边:
＜name1＞expression

要进入开始条件如Name1，在动作中用语句

BEGIN name1

它将Lex所处的当前开始条件改成 name1

要恢复正常状态，用语句

BEGIN 0

它将 Lex恢复到 Lex解释器的初始条件

一条规则也可以在几个开始条件下都起作用，如

rule

使rule在三个不同的开始条件下都起作用。要使一条规则在所有开始条件下都起作用，就不在它前面附加任何开始条件。

例：解决1）中的问题，这次用开始条件，Lex源程序如下：

％start AA BB CC
％％
∧a {ECHO； BEGIN AA；}
∧b {ECHO； BEGIN BB；}
∧c {ECHO； BEGIN CC；}
\n {ECHO； BEGIN 0；｝
＜AA＞magic printf （“first”） ;
＜BB＞magic Printf（“second”）；
＜CC＞magic Printf（“third”）i

1.10 Lex源程序格式总结

为使用方便起见，将Lex源程序的格式，Lex的正规式的格式等总录于此．

Lex源程序的一般格式为：

｛definitions｝

％％

｛rules｝

％％

｛user subroutines｝

辅助定义部分包括以下项目；

1）辅助定义，格式为：

name translation

2）直接按照抄的代码，格式为：

空格 代码

3）直接照抄的代码，格式为：

％{
代码
％｝

4）开始条件，格式为：

％S namel name2…

还有几个其他项目，不常使用故略去。

识别规则部分的格式是

expression action

其中expression必须与action用空格分开，动作如果多于一行，要用花括号括起来。

Lex用的正规式用的运算符有以下一些：

x 字符x

“x”字符x，若为运算符，则不起运算符作用

\x 同上

［xy］ 字符x或y

[x-z] 字符x，或y，或z

[∧x] 除x以外的所有字符

 . 除回车换行外的所有字符

∧x 出现在一行开始处的x

＜y＞x 当 Lex处于开始条件 y时， x

X＄ 出现在一行末尾处的x

x？ 可有可无的 X

x* 0个或多个x

x+ 1个或多个x

x|y X或y

（x）字符x

x/y 字符x但仅当其后紧随y

{xx} 辅助定义XX的展开

x（m,n）m到n个x

二、语法分析程序自动产生器yacc的使用方法

2.l yacc概述

    形式语言都有严格定义的语法结构，我们对它们进行处理时首先要分析其语法结构。yace是一个语法分析程序的自动产生器，严格地说Lex也是一个形式语言的语法分析程序的自动产生器。不过Lex所能处理的语言仅限于正规语言，而高级语言的词法结构恰好可用正规式表示，因此Lex只是一个词法分析程序的产生器。yace可以处理能用LALR（1）文法表示的上下文无关语言。而且我们将会看到yace具有一定的解决语法的二义性的功能。

    yacc的用途很广，但主要用于程序设计语言的编译程序的自动构造上。例如可移植的C语言的编译程序就是用yacc来写的。还有许多数据库查询语言是用yacc实现的。因此，yacc又叫做“编译程序的编译程序（"A Compiler ComPiler"）。

   ，“yacc源程序”是用户用yacc提供的一种类似BNF的语言写的要处理的语言的语法描述。yacc会自动地将这个源程序转换成用LR方法进行语法分析的语法分析程序yyparse，同Lex一样，yacc的宿主语言也是C，因此yyParse是一个C语言的程序，用户在主程序中通过调用yyparse进行语法分析。

    语法分析必须建立在词法分析的基础之上，所以生成的语法分析程序还需要有一个词法分析程序与它配合工作。yyparse要求这个词法分析程序的名字为yylex。用户写yylex时可以借助于Lex。因为Lex产生的词法分析程序的名字正好是yylex，所以 Lex与yacc配合使用是很方便的，这将在2.5的2.5.3中详细介绍，请注意词法分析程序也是可以包含在yacc源程序中的。

    在yacc源程序中除了语法规则外，还要包括当这些语法规则被识别出来时，即用它们进行归约时要完成的语义动作，语义动作是用C语言写的程序段。语法分析的输出可能是一棵语法树，或生成的目标代码，或者就是关于输入串是否符合语法的信息。需要什么样的输出都是由语义动作和程序部分的程序段来实现的。

    下面分节介绍yacc源程序的写法以及在Unix系统中使用yacc的有关命令。

2.2 yacc源程序的一般格式

    一个yacc源程序一般包括三部分：说明部分；语法规则部分；程序段部分，这三部分内容依次按下面的格式组织在一起：



说明部分

％％

语法规则部分

％％

程序段部分

 

上述三部分中说明部分和程序段部分不必要时可省去，当没有程序段部分时，第二

个％％也可以省去。但是第一个％％是必须有的。下面详细介绍各部分的组成及写法。

2.3 yacc源程序说明部分的写法

yacc源程序的说明部分定义语法规则中要用的终结符号，语义动作中使用的数据类

型、变量、语义值的联合类型以及语法规则中运算符的优先级等。这些内容的组织方式如

下：

％｛
头文件表
宏定义
数据类型定义
全局变量定义
％｝
语法开始符定义
语义值类型定义
终结符定义
运算符优先级及结合性定义

2.3.1 头文件表

yacc直接把这部分定义抄到所生成的C语言程序y.tab.c中去的，所以要按C语言

的语法规定来写。头文件表是一系列C语言的＃include语句，要从每行的第一列开始写，

例如：


％｛
＃include＜stdio.h＞
＃include ＜math.h＞
＃include＜ctype.h＞
＄include “header.h”
％｝
.
.
.
％｝

 

2.3.2 宏定义

    这部分用C语言的 ＃ define语句定义程序中要用的宏。例如


％｛
.
.
. 
＃define EOF O
＃dffine max（x,y）（（x＞y）？x:y）
.
.
. 
％｝
 


2.3.3 数据类型定义

    这部分定义语义动作中或程序段部分中要用到的数据类型，例如：


％｛
.
.
. 
typedef struct interval｛
double lo， hi；
｝INTERVAL；
.
.
.
％｝
 


2.3.4 全局变量定义

外部变量（external variable）和yacc源程序中要用到的全局变量都在这部分定义，例如：


％{
.
.
.
extern int nfg;
douhle dreg[ 26]；
INTERVAL Vreg[26]；
.
.
.
％｝
 


   另外非整型函数的类型声明也包含在这部分中，请参看2.6例2。

    重申一遍，上述四部分括在 ％{和％}之间的内容是由yacc原样照抄到y.tab.c中去，所以必须完全符合C语言文法，另外，界符％｛和％｝最好各自独占一行，即最好不写成 
%{ int x; %}

2.3.5 语法开始符定义

    上下文无关文法的开始符号是一个特殊的非终结符，所有的推导都从这个非终结符开始，在yacc中，语法开始符定义语句是：

% start 非终结符……

如果没有上面的说明，yacc自动将语法规则部分中第一条语法规则左部的非终结符作为语法开始符。

2.3.6语义值类型定义

    yycc生成的语法分析程序yyparse用的是LR分析方法，它在作语法分析时除了有一个状态钱外，还有一个语义值钱，存放它所分析到的非经结符和终结符的语义值，这些语义值有的是从词法分析程序传回的，有的是在语义动作中赋与的，这些在介绍语义动作时再详细说明。如果没有对语义值的类型做定义，那么yacc认为它是整型（int）的，即所有语法符号如果赋与了语义值，则必须是整型的，否则会出类型错，但是用户经常会希望语义值的类型比较复杂，如双精度浮点数，字符串或树结点的指针．这时就可以用语义值类型定义进行说明。因为不同的语法符号的语义值类型可能不同，所以语义值类型说明就是将语义值的类型定义为一个联合（Union），这个联合包括所有可能用到的类型（各自对应一个成员名），为了使用户不必在存取语义值时每次都指出成员名，在语义值类型定义部分还要求用户说明每一个语法符号（终结符和非终结符）的语义值是哪一个联合成员类型。下面举例说明并请参看2.6例2。



％ union｛
int ival
double dval
INTERVAL VVal;
｝
％token ＜ival＞ DREG VREG
％token ＜dval＞ CONST
％type  ＜dyal＞dexp
％type  ＜vval＞vexP
．．．
 


    在上述定义中，以％union开始的行定义了语义值的联合类型，共有三个成员类型分别取名为ival, dval, vval。

    以％token开始的行定义的是终结符（见2.3.7）所以DREG,VREG和CONST都是终结符，尖括号中的名字就是这些终结符的语义值的具体类型。如DREG和VREG这两个终结符的语义值将是整型（int）的，成员名是ival。

    以％tyPe开始的行是说明非终结符语义值的类型。如非终结符dexP的语义值将是双精度浮点类型，请注意，在yacc中非终结符不必特别声明，但是当说明部分有对语义值类型的定义，而且某非终结符的语义值将被存取，就必须用上面的方法定义它的类型。

2.3.7 终结符定义

    在yacc源程序语法规则部分出现的所有终结符（文字字符literal除外）必须在这部分定义，定义方法如下例：

％ token DIGIT LETTER

    每个终结符定义行以％token开头，注意％与token之间没有空格，一行中可以定义多个终结符，它们之间用空格分开，终结符名可以由字母，数字，下划线组成，但必须用字母于头。非终结符名的组成规则与此相同。终结符定义行可多于一个。

    yacc规定每个终结符都有一个唯一的编号（token number）。当我们用上面的方式定义经结符时，终结符的编号由yacc内部决定，其编号规则是从257开始依次递增，每次加1。但这个规则不适用于文字字符（literal）的终结符。例如在下面的语法规则中，’＋’，’；'就是文字字符终结符:

stats： stats'；' stat；
expr: expr'+’ expr;

    文字字符终结符在规则中出现时用单引号括起来。它们不需要用％token语句定义，yacc对它们的编号就采用该字符在其字符集（如ASCII）中的值。注意上面两条语法规则末尾的分号是yacc元语言的标点符号，不是文字字符终结符。

    yacc也允许用户自己定义终结符的编号。如果这样，那么终结符定义的格式就是：

％token终结符名 整数

    其中“终结符名”就是要定义的终结符，“整数”就是该终结符的编号，每一个这样的行定义一个终结符。特别注意不同终结符的编号不能相同。例如


%token BEGIN 100
％token END 101
%token IF 105
％token THEN 200
...
 


在3.6中我们说过如果用户定义了语义值的类型，那么那些具有有意义的语义值的终结符其语义值的类型要用Union中的成员名来说明，除了在3.6段中介绍的定义方法外，还可以把对终结符的定义和其语义值的类型说明分开，例如：


%token DREG VREG CONST
％type ＜ival＞ DREG VREG
％type ＜dval＞ CONST
 


2.3.8运算符优先级及结合性定义

    请看下面的关于表达式的文法：


%token NAME
expr: expr'+' expr
|expr '–' expr
|expr'*'expr
|NAME
;
 


     这个文法有二义性，例如句子：a＋b－c ，可以解释成（a＋ b）一 c也可以解译成 a＋（b－ c），虽然这两种解释都合理但造成了二义性，如果将句子

a＋b*C

解释为（a＋b）*c就在语义上错了。

    yacc允许用户规定运算符的优先级和结合性，这样就可以消除上述文法的二义性。例如规定’＋”－'具有相同的优先级，而且都是左结合的，这样。a＋b－c就唯一地解释为( a＋ b)一 c。再规定'*'的优先级大于’＋”－’，则 a＋ b* c就正确地解释为 a＋（b*c） 了，因此上述文法的正确形式应是：


％token NAME
％left '+''-’
％left '*' 
％％
expr：expr'+’ expr
|expr'-’ exPr
|expr'*’ expr
|NAME
;
 


    在说明部分中以％left开头的行就是定义算符的结合性的行。％left表示其后的算符是遵循左结合的；％right表示右结合性，而％nonassoc则表示其后的算符没有结合性。优先级是隐含的，在说明部分中，排在前面行的算符较后面行的算符的优先级低；排在同一行的算符优先级相同，因此在上述文法中，’＋’和’一’优先级相同，而它们的优先级都小于'*’，三个其符都是左结合的。

    在表达式中有时要用到一元运算符，而且它可能与某个二元运算符是同一个符号，例如一元运算符负号“-”就与减号’-’相同，显然一元运算符的优先级应该比相应的二元运算符的优先级高。至少应该与’*'的优先级相同，这可以用yacc的％Prec子句来定义，请看下面的文法：


％token NAME
％left '-''+’
％left '*''／'
％％
expr；expr'+' expr
|expr'+' expr
|expr'-’expr
|expr'*' expr
|expr'／’ expr
|'-'expr ％prec'*'
|NAME
;
 

    在上述文法中，为使一元’－’的优先级与’*’相同，我们使用了子句

             ％prec’*’

    它说明它所在的语法规则中最右边的运算符或终结符的优先级与％Prec后面的符号的优先级相同，注意％Prec子句必须出现在某语法规则结尾处分号之前，％prec子句并不改变’－’作为二元运算符时的优先级。

    上面介绍的八项定义，没有必要的部分都可以省去。

2.4. yacc源程序中语法规则部分的写法

    语法规则部分是yacc源程序的核心部分，这一部分定义了要处理的语言的语法及要采用的语义动作。下面介绍语法规则的书写格式、语义动作的写法以及yacc解决二义性和冲突的具体措施。最后介绍错误处理。

2.4.1语法规则的书写格式

    每条语法规则包括一个左部和一个右部，左右部之间用冒号’:’来分隔，规则结尾处要用分号”;”标记，所以一条语法规则的格式如下：

            nonterminal : BODY；

          或

             nonterminal：BODY

    其中nonterminal是一个非终结符，右部的BODY是一个由终结符和非终结符组成的串、可以为空，请看几个例子：

stat: WHILE bexp DO Stat
;
stat: IF bexp THEN stat
;
stat：/* empty*／
;

上面的第三条语法规则的右部为空，用’／*’和‘*／’括起来的部分是注解．可以把左部非终结符相同的语法规则集中在一起，规则间用短线’|’分隔，最后一条规则之后才用分号，例如：

stat： WHILE bexp DO stat
| IF bexp THEN stat
|／* empty*／
;

对语法规则部分的书写有几条建议；

1. 用小写字母串表示非终结符，用大写字母串表示终结符。

2．将左部相同的产生式集中在一起，象上例一样。

3．各条规则的右部尽量对齐，例如都从第一个tab处开始。按这样的风格写yacc源程序清晰可读性强而且易修改和检查错误。

4．如果产生式（语法规则）需要递归，尽可能使用左递闭方式．例如：

seq: item
| seq',’ item
;

因为用左速归方式可以使语法分析器尽可能早地进行归约，不致使状态栈溢出。

2.4.2 语义动作

    当语法分析程序识别出某个句型时，它即用相应的语法规则进行归约，yscc在进行归约之前，先完成用户提供的语义动作，这些语义动作可以是返回语法符号的语义值，也可以是求某些语法符号的语义值，或者是其他适当的动作如建立语法树，产生目标代玛，打印有关信息等。终结符的语义值是通过词法分析程序返回的，这个值由全局变量（yacc自动定义的） yylval带回，如果用户在词法分析程序识别出某终结符时，给yylval赋与相应的值，这个值就自动地作为该终结符的语义值。当语义值的类型不是int时，要注意yylval的值的类型须与相应的终结符的语义值类型一致。语义动作是用C语言的语句写成的，跟在相应的语法规则后面，用花括号括起来．例如：

A：'('B')'
{hello（l，“abc”）；｝
XXX：YYY ZZZ
{printf（“a message＼n”）；
flag＝25；
｝
:
 


    要存取语法符号的语义值，用户要在语义动作中使用以＄开头的伪变量，这些伪变量是yacc内部提供的，用户不用定义。伪变量＄＄代表产生式左部非终结符的语义值，产生式右部各语法符号的语义值按从左到右的次序为＄1，＄ 2，…  例如在下面的产生式中：

        A :B C D
;

A的语义值为＄＄，B、C、D的语义值依次为＄ 1，＄2，＄3。 
    为说明伪变量的作用，请看下例：有产生式

expr:'('expr')'
;

左的边的exPr的值应该等于右连的expr的值，表示这个要求的语义动作为，
expr: '('expr')'
{$$=$2;}
; 

如果在产生式后面的语义动作中没有为伪变量＄＄赋值， yaCC自动把它置为产生式右部第一个语法符号的值（即＄1）有较复杂的应用中，往往需要在产生式右部的语法符号之间插入语义动作．这意味着使语法分析器在识别出句型的一部分时就完成这些动作。请看下例：

A：B

｛＄＄＝1；｝

C
{X=$2; y=$3;}

    例中x 的值最后为1而y的值量为符号C的语义值，注意B后面的语义动作＄＄＝1并非将符号A的语义值置为1，这是因为上面的例子是按下面的方式实现的。

＄ACT：／*empty。／
｛＄＄＝1；｝
;
A：B＄ACTC
{X＝＄2；y=$3；｝
；

即 yacc自动设置一个非终结符＄ ACT及一个空产生式用以完成上述语义动作。关于语义动作的实例请读者详细阅读6中的两个例子。

2.4.3 yacc解决二义性和冲突的方法

    在2.3.8中已涉及到二义性和冲突的问题，这里再集中介绍一下，这在写Yacc源程序时会经常碰到。二义性会带来冲突。在2.3.8中我们介绍了yacc可以用为算符确定优先级和结合规则解决由二义性造成的冲突，但是有一些由二义性造成的冲突不易通过优先级方法解决，

如有名的例子：

stat：IF bexp THEN stat

|IF bexp THEN stat ELSE
stat
;

    对于这样的二义性造成的冲突和一些不是由二义性造成的冲突，Yacc提供了下面两条消除二义性的规则：

A1．出现移进／归约冲突时，进行移进；

A2. 出现归约／归约冲突时，按照产生式在yacc源程序中出现的次序，用先出现的产生式归约。

    我们可以看出用这两条规则解决上面的IF语句二义性问题是合乎我们需要的。所以用户不必将上述文法改造成无二义性的。当Yacc用上述两条规则消除了二义性，它将给出相应信息。

    下面再稍微严格地介绍一下Yacc如何利用优先级和结合性来解决冲突的。

    Yacc源程序中的产生式也有一个优先级和结合性．这个优先级和结合性就是该产生式右部最后一个终结符或文字字符的优先级和结合性，当使用了％Prec子句时，该产生式的优先级和结合性由％Prec子句决定。当然如果产生式右部最后一个终结符或文字字符没有优先级或结合性，则该产生式也没有优先级或结合性。

    根据终结符（或文字字符）和产生式的优先级和结合性，Yacc又有两个解决冲突的规则：

P1. 当出现移进/归约冲突或归约／归约冲突，而当时输入符号和语法规则（产生式）均没有优先级和结合性，就用 AI和A2来解决这些冲突。

P2．当出现移进／归约冲突时，如果输入符号和语法规则（产生式）都有优先级和结合性，那么如果输入符号的优先级大于产生式的优先级就移进如果输入符号的优先级小于产生式的优先级就归约。如果二者优先级相等，则由结合性决定动作，左结合则归约，右结合则移进，无结合性则出错。

    用优先级和结合性能解决的冲突，yacc不报告给用户。

2.4.4 语法分析中的错误处理

    当进行语法分析时发现输入串有语法错误，最好能在报告出错信息以后继续进行语法分析，以便发现更多的错误。

    yacc处理错误的方法是：当发现语法错误时，yacc丢掉那些导致错误的符号适当调整状态栈。然后从出错处的后一个符号处或跳过若干符号直到遇到用户指定的某个符号时开始继续分析。

    Yacc内部有一个保留的终结符error，把它写在某个产生式的右部，则Yacc就认为这个地方可能发生错误，当语法分析的确在这里发生错误时，Yacc就用上面介绍的方法处理，如果没有用到 error的产生式，则 Yacc打印出“Syntax error”，就终止语法分析。

下面看两个使用error的简单例子：

1．下面的产生式

stat: error
;

使yacc在分析stat推导出的句型时，遇到语法错误时跳过出错的部分，继续分析（也会打

印语法错信息）

2．下面的产生式

stat: error ';'
;

使yacc碰到语法错时，跳过输入串直到碰到下一个分号才继续开始语法分析。

如果语法分析的输入串是从键盘上输入的（即交互式），那么某一行出错后，希望重新

输入这一行，并使yacc立即开始继续分析，这只要在语义动作中使用语句yyerror即可，如下例：



input: error‘\n’
{yyerror;
printf (“Reenter last line:”);}
input
{＄＄＝＄4；}
;
 


关于错误处理请参看[2]和6的例子。

2.5 程序段部分

    程序段部分主要包括以下内容：主程序 main（）；错误信息执行程序 yyerror（s）；词法分析程序yylex（）；用户在语义动作中用到的子程序，下面分别介绍。

2.5.l主程序

    主程序的主要作用是调用语法分析程序yyparse（），yyparse（）是yacc 从用户写的yacc源程序自动生成的，在调用语法分析程序yyparse（）之前或之后用户往往需要做一些其他处理，这些也在main（）中完成，如果用户只需要在main()中调用yyparse（），则也可以使用Unix的yacc库（一ly）中提供的main（）而不必自己写。库里的main（）如下：


main（） ｛
return（yyparse（））；
｝
 


2.5.2 错误信息报告程序

    yacc的库也提供了一个错误信息报告程序，其源程序如下:


＃include yyerror (s) char * s{
fprintf (stderr, “%s\n”,s);
｝
 


    如果用户觉得这个yyerror（s）太简单。也可以自己提供一个，如在其中记住输入串的行号并当yyerror（s）被调用时，可以报告出错行号。

2.5.3 词法分析程序

    词法分析程序必须由用户提供，其名字必须是yylex，调法分析程序向语法分析程序提供当前输入的单词符号。yylex提供给yyparse的不是终结符本身，而是终结符的编号，即token number,如果当前的终结符有语义值，yylex必须把它赋给yylval。

    下面是一个词法分析程序例子的一部分。


yylex（）｛
extern int yylval
int c；
…
c＝ getchar（）；
…
switch（c）{
…
case ‘0’：
case ‘1’：
...
case “9”
yylval=c-'0'
return (DIGIT);
…
} 
…
 


    上述词法分析程序碰到数字时将与其相应的数值赋给yylval,并返回DIGIT的终结符编号，注意DIGIT代表它的编号（如可以通过宏来定义）。

    用户也可以用Lex为工具编写记号词法分析程序，如果这样，在yacc源程序的程序段部分就只需要用下面的语句来代替词法分析程序：

#include "lex.yy.c"

    
    在Unix系统中，假设lex源程序名叫plo.l.yace源程序名叫plo.y,则从这些源程序得到可用的词分析程序中语法分析程序依次使用下述三个命令：



Lex plo.l

yacc plo,y

cc y,tab,c -ly-ll
 


    第一条命令从lex源程序plo.l产生词法分析程序，文件名为lex.yy.c第二命令从yacc源程序plo.y产生语法分析程序，文件名为y.tab.c;第三条命令将y.tab.c这个c语言的程序进行编译得到可运行的目标程序。

    第三条命令中-11是调用lex库，-ly是调用yacc库，如果用户在yacc源程序的程序段部分自己提供了main（）和yyerror（s）这两个程序，则不必使用-ly．另外如果在第二条命令中使用选择项-v，例如：

yacc －v plo.y

    则yacc除产生y.tab.c外，还产生一个名叫y.output的文件，其内容是被处理语言的LR状态转换表,这个文件对检查语法分析器的工作过程很有用。”

    请参看[4]的 Lex（1）和 yacc（1）

2.5.4 其他程序段

    语义动作部分可能需要使用一些子程序，这些子程序都必须遵守C语言的语法规定，这里不多讲了。

2.6 yacc源程序例子说明

    例1．用yacc描述一个交互式的计算器，该计算器有26个寄存器，分别用小写字母a到z表示，它能接受由运算符+、-、*、／、％（取模）、&（按位求与）、|（按位求或）组成的表达式，能为寄存器赋值，如果计算器接受的是一个赋值语句，就不打印出结果，其他情况下都给出结果，操作数为整数，若以0（零）开头，则作为八进制数处理。

    例 1的yacc源程序见附录F 

    读者从例1中可以看出用优先关系和二义性文法能使源程序简洁，还可看到错误处理方法，但例1不足之处是它的词法分析程序太简单，还有对八进制与十进制数的区分也最好在词法分析中处理.

    例2．这个例子是例1的改进，读者能看到语义值联合类型的定义及使用方法和如何模拟语法错误并进行处理，该树也是描述一个交互式的计算器，比例1的计算器功能强，它可以处理浮点数和浮点数的区间的运算，它接受浮点常数，以及+、-、*、/、一元-和=（赋值）组成的表达式，它有26个浮点变量，用小写字母a到z表示，浮点数区间用一对浮点数表示：(x,y)

    其中x小于或等于y，该计算器有26个浮点数区间变量，用大写字母A到Z表示。和例1相似，赋值语句不打印出结果，其他表达式均打印出结果，当发生错误时给出相应的信息。 

    下面简单总结一个例2的一些特点。

1．语义值联合类型的定义

    区间用一个结构表示，其成员给出区间的左右边界点，该结构用c语言的typedef语 句定义，并赋与类型名INTERVAL。 yacc的语义值经过％union定义后，可以存放整型，浮点及区间变量的值，还有一些函数（如 hil,vmul,vdiv）都返回结构类型的值。

2．yacc的出错处理

    源程序中用到了YYERROR来处理除数区间中含有0或除数区间端点次序倒置的错误，当碰到上述错误时，YYERROR使yacc调用其错误处理机构，丢掉出错的输入行，继续处理。

3．使用有冲突的文法

    如果读者在机器上试试这个例子，就会发现它包含18个移进／归约冲突，26个归约／归约冲突，请看下面两个输入行：

2.5+(3.5-4.0)

2.5+(3.5,4.0)

    在第二行中，2.5用在区间表达式中，所以应把它当作区间处理，即要把它的类型由标量转换成区间量，但yacc只有当读到后面的’,'时才知道是否应该进行类型转换，此时改变主意为时已晚，当然也可以在读到2.5时再向前看几个符号来决定2.5的类型，但这样实现较困难，因为yacc本身不支持，该例是通过增加语法规则和充分利用yacc内部的二义性消除机构来解决问题的。在上述文法中，每一个区间二元运算都对应两条规则，其中一条左操作数是区间，另一条左操作数是标量，yacc可以根据上下文自动地进行类型转换。除了这种情况外，还存在着其他要求决定是否进行类型转换的情形，本例将标量表达式的语法规则放在区间表达式语法规则的前面，使运算量的类型先为标量。直到必要时再转换成区间，这样就导致了那些冲突。有兴趣的读者不妨仔细看一看这个源程序和yacc处理它时产生的y.output文件分析一下yacc解决冲突的具体方法。要注意上述解决类型问题的方法带有很强的技巧性，对更复杂的问题就难以施展了。

（1）解释程序
    任何一种高级语言（如C）都精确规定了数据结构和程序的执行顺序，即定义了一台计算机（称作A）。 A的存储结构是C的数据结构，A的控制器控制C程序的执行，A的运算器完成C的语句操作，A的机器语言即是C，每个C程序都规定了计算机A从初始状态到终止状态的转换规则。我们用一台通用计算机B来模拟计算机A的执行，为达到这个目的，必须用计算机B的机器语言构造一组程序以支持用A的机器语言C编写的程序的执行。换句话说，我们在一台通用计算机B上用软件构造了一台高级语言计算机A。这个过程称为软件模拟（或软件解释）。

（2）编译方式和解释方式的主要区别
    解释程序由总控程序和各类指令或语句的解释函数组成，它按照源程序的逻辑流程，直接解释执行源程序或源程序的内部形式。对于循环中的语句，每次循环执行要进行相当复杂的分析过程，因此，用解释方式执行是低效的；而用编译方式（参见2.1.4）仅在产生目标代码时分析一遍，最后执行目标代码，这是它们之间的主要区别。
（1） 解释程序基本原理
    模拟程序的解释算法如图2.6，它按输入程序的执行顺序解释执行，产生程序规定的输. 



（2） 程序语言的通常实现方式
    纯碎的解释和纯碎的编译是两个极端情况，很少使用它们。例如，在处理汇编语言时才使用纯碎的编译方式；在处理操作系统的控制语言和交互语言时才使用纯碎的解释方式。程序语言的通常实现方式如图2.7所示，是编译技术和解释技术的结合。


    采用哪一种处理方式，是由被实现的语言和实现环境（在什么计算机系统上实现）两者决定的，而被实现的语言，它的数据结构和控制结构更起着重要作用。程序语言被分为编译型和解释型，为了提高效率并尽早检查出源程序中的错误，尽量采用编译方式,既使采用解释方式，也尽量生成接进目标代码的中间代码。
C、C++、FORTRAN、PASCAL和ADA通常采用编译方式实现，称为编译型语言。编译器把源程序翻译成目标计算机语言程序，解释器只提供一个运行库，以支持目标语言程序中计算机语言没有提供的操作。一般来说，编译器比较复杂庞大，它的侧重点是产生尽可能高效运行的目标语言程序。
     LISP、ML、Prolog和Smalltalk通常采用解释方式实现,称为解释型语言。在实现中，编译器仅产生易于解释的中间代码，中间代码不能在硬件机上直接执行，而由解释器解释执行。这种实现的编译器相对简单，实现的复杂工作在于构造解释器。
    Java不象LISP，而更象C++，但由于Java运行在网络环境上，Java通常被当作解释型语言，编译器产生一种字节码的中间语言，被各个终端上的浏览器创建的解释器解释执行。