📄 3.4.1a.htm

📁 建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术
💻 HTM
字号:
<html>

<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>

<BODY bgColor=Lavender>

<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.2c.htm'" src="../images/previous.gif"></IMG></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.1b.htm'" src="../images/next.gif"></IMG></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td colspan=2>
			<font class="title2"><b>3.4正规表达式与有限自动机</b></font>
		</td>
	</tr>
	<tr>
		<td width=5></td>
		<td>
			<br>
			<b>3.4.1 正规表达式与单词</b><br><br>
		</td>
	</tr>
	<tr>
		<td width=10></td>
		<td>
			<p>我们知道，在Pascal等语言中，一个标识符是一个字母开头的“字母|数字”串。问题是如何表示这种结构呢？本节中我们将要介绍一种表示法，称作<font class="definition2">正规表达式</font>，简称<font class="definition2">正规式</font>。用这种表示法可以详细说明单词符号的结构，可以精确地定义集合，所谓<font class="definition2">正规集</font>。</p> 
			<p>如果用letter和digit分别表示字母和数字，采用这种表示法，则Pascal的标识符可表示为：  	  <br> 
			  <center><font color=blue>letter (letter|digit)<sup>*</sup></font></center><br>
			其中“|”的含义是“或”，括号用来组成子表达式，星号“<font size="4">*</font>”意味着“零次或多于零次地引用”括号中的表达式，letter与表达式的其余部分的并置意味着连接。 	  <br>
			&nbsp;&nbsp;&nbsp;&nbsp;一个正规表达式是按照一组定义规则由一些较简单的正规表达式所组成的。下面我们还将看到，每一个正规表达式r表示一个语言L(r)。而且定义规则将指明L(r)是如何由r的子表达式所表示的语言用不同的方式结合而成的。</p>
			<p>在字母表Σ上的正规表达式可用如下规则来定义，其中与每一个规则相联系的是有关正规表达式所表示的语言的详细说明。</p>
			<table>
				<tr>
					<td width=70></td>
					<td>
						<b>1.</b>ε和Φ都是Σ上的正规表达式，它们所表示的语言分别是｛ε｝(即只含空符号串的集合)和Φ(即空集｛｝)。   <br>
						<b>2.</b>如果ａ是Σ内的一个符号，则ａ是一个正规表达式，它表示的语言是｛a｝，即包含符号串a的集合。虽然这里的符号、正规表达式和符号串都用a来表示，但正规表达式a不同于符号串a或符号ａ。然而我们可以从上下文中清楚地看出正在讨论的a究竟是什么。 			  <br>
						<b>3.</b>如果r和s分别是表示语言L(r)和L(s)的正规表达式，那么 <br>
					</td>
				</tr>
			</table>
			<table	>
				<tr>
					<td width=100></td>
					<td>
						(a) (r)|(s)是一个表示L(r)∪L(s)的正规表达式。 <br> 
						(b) (r)(s)是一个表示L(r)L(s)的正规表达式。 <br> 
						(c) (r)<sup>*</sup>是一个表示(L(r))<sup>*</sup>的正规表达式。  <br> 
						(d) (r)也是一个表示L(r)的正规表达式。</p> 
					</td>
				</tr>
			</table>
			<p>一个由正规表达式表示的语言称为一个正规集。</p> 
		</td>
	<tr>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.2c.htm'" src="../images/previous.gif"></IMG></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.1b.htm'" src="../images/next.gif"></IMG></td>
	</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -