fu.htm.bak

建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术

<br>      
要恢复正常状态，用语句<br>       
<br>      
BEGIN 0<br>       
<br>      
它将 Lex恢复到 Lex解释器的初始条件<br>       
<br>      
一条规则也可以在几个开始条件下都起作用，如<br>       
<br>      
&lt;name1 ，name2，name3&gt; rule<br>      
<br>       
使rule在三个不同的开始条件下都起作用。要使一条规则在所有开始条件下都起作用，就不在它前面附加任何开始条件。<br>       
<br>      
例：解决1）中的问题，这次用开始条件，Lex源程序如下：<br>       
<br>      
％start AA BB CC<br>       
％％<br>       
∧a {ECHO； BEGIN AA；}<br>      
∧b {ECHO； BEGIN BB；}<br>      
∧c {ECHO； BEGIN CC；}<br>      
\n {ECHO； BEGIN 0；｝<br>       
＜AA＞magic printf （“first”） ;<br>       
＜BB＞magic Printf（“second”）；<br>       
＜CC＞magic Printf（“third”）i<br>       
<br>      
1.10 Lex源程序格式总结<br>       
<br>      
为使用方便起见，将Lex源程序的格式，Lex的正规式的格式等总录于此．<br>       
<br>      
Lex源程序的一般格式为：<br>       
<br>      
｛definitions｝<br>       
<br>      
％％<br>       
<br>      
｛rules｝<br>       
<br>      
％％<br>       
<br>      
｛user subroutines｝<br>       
<br>      
辅助定义部分包括以下项目；<br>       
<br>      
1）辅助定义，格式为：<br>       
<br>      
name translation<br>       
<br>      
2）直接按照抄的代码，格式为：<br>       
<br>      
空格 代码<br>       
<br>      
3）直接照抄的代码，格式为：<br>       
<br>      
％{<br>      
代码<br>      
％｝<br>      
<br>     
4）开始条件，格式为：<br>      
<br>     
％S namel name2…<br>       
<br>      
还有几个其他项目，不常使用故略去。<br>       
<br>      
识别规则部分的格式是<br>       
<br>      
expression action<br>       
<br>      
其中expression必须与action用空格分开，动作如果多于一行，要用花括号括起来。<br>       
<br>      
Lex用的正规式用的运算符有以下一些：<br>       
<br>      
x 字符x<br>      
<br>     
“x”字符x，若为运算符，则不起运算符作用<br>      
<br>     
\x 同上<br>       
<br>      
［xy］ 字符x或y<br>       
<br>      
[x-z] 字符x，或y，或z<br>       
<br>      
[∧x] 除x以外的所有字符<br>       
<br>      
&nbsp;. 除回车换行外的所有字符<br>      
<br>     
∧x 出现在一行开始处的x<br>       
<br>      
＜y＞x 当 Lex处于开始条件 y时， x<br>       
<br>      
X＄ 出现在一行末尾处的x<br>       
<br>      
x？ 可有可无的 X<br>       
<br>      
x* 0个或多个x<br>       
<br>      
x+ 1个或多个x<br>       
<br>      
x|y X或y<br>       
<br>      
（x）字符x<br>       
<br>      
x/y 字符x但仅当其后紧随y<br>       
<br>      
{xx} 辅助定义XX的展开<br>       
<br>      
x（m,n）m到n个x<br>       
<br>      
二、语法分析程序自动产生器yacc的使用方法<b><br>     
</b><br>      
2.l yacc概述<br>       
<br>      
&nbsp;&nbsp;&nbsp;      
形式语言都有严格定义的语法结构，我们对它们进行处理时首先要分析其语法结构。yace是一个语法分析程序的自动产生器，严格地说Lex也是一个形式语言的语法分析程序的自动产生器。不过Lex所能处理的语言仅限于正规语言，而高级语言的词法结构恰好可用正规式表示，因此Lex只是一个词法分析程序的产生器。yace可以处理能用LALR（1）文法表示的上下文无关语言。而且我们将会看到yace具有一定的解决语法的二义性的功能。<br>       
<br>      
&nbsp;&nbsp;&nbsp;      
yacc的用途很广，但主要用于程序设计语言的编译程序的自动构造上。例如可移植的C语言的编译程序就是用yacc来写的。还有许多数据库查询语言是用yacc实现的。因此，yacc又叫做“编译程序的编译程序（&quot;A Compiler ComPiler&quot;）。<br>       
<br>      
&nbsp;&nbsp;&nbsp;&nbsp;      
yacc的工作示意图如下；</font></p>  
<p align="center"><font size="2">       
<img border="0" src="f2.gif" tppabs="http://162.105.30.75/materialroot/ug3/compiler_project/f2.gif" width="367" height="176"><br>
图2.1 yacc示意图 </font></p>  
<p><font size="2">      
<br>      
<br>      
&nbsp;&nbsp;&nbsp;      
在图2.1中，“yacc源程序”是用户用yacc提供的一种类似BNF的语言写的要处理的语言的语法描述。yacc会自动地将这个源程序转换成用LR方法进行语法分析的语法分析程序yyparse，同Lex一样，yacc的宿主语言也是C，因此yyParse是一个C语言的程序，用户在主程序中通过调用yyparse进行语法分析。<br>      
<br>     
&nbsp;&nbsp;&nbsp;     
语法分析必须建立在词法分析的基础之上，所以生成的语法分析程序还需要有一个词法分析程序与它配合工作。yyparse要求这个词法分析程序的名字为yylex。用户写yylex时可以借助于Lex。因为Lex产生的词法分析程序的名字正好是yylex，所以 Lex与yacc配合使用是很方便的，这将在2.5的2.5.3中详细介绍，请注意词法分析程序也是可以包含在yacc源程序中的。<br>      
<br>     
&nbsp;&nbsp;&nbsp;     
在yacc源程序中除了语法规则外，还要包括当这些语法规则被识别出来时，即用它们进行归约时要完成的语义动作，语义动作是用C语言写的程序段。语法分析的输出可能是一棵语法树，或生成的目标代码，或者就是关于输入串是否符合语法的信息。需要什么样的输出都是由语义动作和程序部分的程序段来实现的。<br>      
<br>     
&nbsp;&nbsp;&nbsp;     
下面分节介绍yacc源程序的写法以及在Unix系统中使用yacc的有关命令。<br>      
<br>     
2.2 yacc源程序的一般格式<br>       
<br>      
&nbsp;&nbsp;&nbsp;      
一个yacc源程序一般包括三部分：说明部分；语法规则部分；程序段部分，这三部分内容依次按下面的格式组织在一起：<br>       
<br>      
<center>
	<table border=0>
		<tr>
			<td>
				说明部分<br>       
				<br>      
				％％<br>       
				<br>      
				语法规则部分<br>       
				<br>      
				％％<br>       
				<br>      
				程序段部分<br>       
				<br>      
			</td>
		</tr>
	</table>
</center>
上述三部分中说明部分和程序段部分不必要时可省去，当没有程序段部分时，第二<br>       
<br>      
个％％也可以省去。但是第一个％％是必须有的。下面详细介绍各部分的组成及写法。<br>       
<br>      
2.3 yacc源程序说明部分的写法<br>       
<br>      
yacc源程序的说明部分定义语法规则中要用的终结符号，语义动作中使用的数据类<br>       
<br>      
型、变量、语义值的联合类型以及语法规则中运算符的优先级等。这些内容的组织方式如<br>       
<br>      
下：<br>       
<br>      
％｛<br>       
头文件表<br>       
宏定义<br>       
数据类型定义<br>       
全局变量定义<br>       
％｝<br>       
语法开始符定义<br>       
语义值类型定义<br>       
终结符定义<br>       
运算符优先级及结合性定义<br>       
<br>      
2.3.1 头文件表<br>       
<br>      
yacc直接把这部分定义抄到所生成的C语言程序y.tab.c中去的，所以要按C语言<br>      
<br>     
的语法规定来写。头文件表是一系列C语言的＃include语句，要从每行的第一列开始写，<br>      
<br>     
例如：<br>      
<br>     
<center>
	<table border=0>
		<tr>	
			<td>			
				％｛<br>      
				＃include＜stdio.h＞<br>      
				＃include ＜math.h＞<br>       
				＃include＜ctype.h＞<br>      
				＄include “header.h”<br>       
				％｝<br>       
				.<br>
				.<br>
				.<br>
				％｝<br>
				<br>     
			</td>
		</tr>
	</table>
</center>

2.3.2 宏定义<br>       
<br>      
&nbsp;&nbsp;&nbsp;      
这部分用C语言的 ＃ define语句定义程序中要用的宏。例如<br>       
<br>      
<center>
	<table border=0>
		<tr>
			<td>
				％｛<br>       
				.<br>     
				.<br>     
				.      
				<br>      
				＃define EOF O<br>       
				＃dffine max（x,y）（（x＞y）？x:y）<br>       
				.<br>
				.<br>
				.      
				<br>      
				％｝<br>      
			</td>
		</tr>
	</table>
</center>
<br>     
2.3.3 数据类型定义<br>       
<br>      
&nbsp;&nbsp;&nbsp;      
这部分定义语义动作中或程序段部分中要用到的数据类型，例如：<br>       
<br>      
<center>
	<table border=0>
		<tr>
			<td>
				％｛<br>       
				.<br>     
				.<br>     
				.      
				<br>      
				typedef struct interval｛<br>       
				double lo， hi；<br>       
				｝INTERVAL；<br>       
				.<br>     
				.<br>     
				.<br>     
				％｝<br>      
			</td>
		</tr>
	</table>
</center>
<br>     
2.3.4 全局变量定义<br>       
<br>      
外部变量（external variable）和yacc源程序中要用到的全局变量都在这部分定义，例如：<br>       
<br>      
<center>