📄 2.4.1.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>

<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.3.3c.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.4.1b.htm'"></img></td>
</tr>
</table>
<br><br>

<font class="title2"><b>2.4 形式语言概观</b></font><br><br> 
<font class="title2"><b>2.4.1 形式语言分类</b></font><br> 
<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td> 
<td class="content"> 
<p> 
1956年，著名的语言学家Noam Chomsky首先对形式语言进行了描述。他定义了四类文法和相应的四种形式语言类。 
</p> 
<p> 
Noam Chomsky把文法分成四种类型，即0型、1型、2型和3型。0型强于1型 ，1型强于2型，2型强于3型。这几类文法的差别在于对产生式施加不同的限制。 
</p> 
<p> 
我们说一个<font class="definition2">0型文法G</font>是一个四元组(V<sub>T</sub>，V<sub>N</sub>，S,P)，其中：<br> 
&nbsp&nbsp&nbsp&nbsp V<sub>T</sub>是一个非空有穷集合，它的每个元素是终结符号。<br> 
&nbsp&nbsp&nbsp&nbsp V<sub>N</sub>是一个非空有穷集合，它的每个元素是非终结符号，V<sub>T</sub>∩V<sub>N</sub>=Φ。<br> 
&nbsp&nbsp&nbsp&nbsp S是一个非终结符号，称为开始符号。 <br> 
&nbsp&nbsp&nbsp&nbsp P是一个产生式的非空有穷集合，每个产生式的形式是：<br> 
<center> α→β </center> 
&nbsp&nbsp&nbsp&nbsp其中α，β∈(V<sub>T</sub>∪V<sub>N</sub>)<sup>*</sup>，而α≠ε。 请注意，这里α和β都是文法的终结符号和非终结符号组成的符号串，只是α≠ε。 
</p> 
<p> 
推广定义2.2，可以定义直接推导。我们说<br> 
<center> γαδ <img src="IMG/equal.gif"></img> γβδ </center> 
仅当α→β是一个产生式。类似可以定义推导和语言。由0型文法产生的语言称为O型语言。 
</p> 
<p> 
若对文法G＝(V<sub>T</sub>，V<sub>N</sub>，S,P )中的每一个产生式α→β,有|α|≤|β|，其中|α|和|β|分别为α和β的长度，则G是<font class="definition2">1型文法</font>。1型文法也称作<font class="definition2">上下文有关文法</font>。这是因为可以证明：每一个1型文法所产生的语言可由这样的一个文法产生，在此文法中的所有产生式都具有如下的形式：<br> 
<center> ζAη→ζγη </center> 
</p> 
<p> 
其中A∈V<sub>N</sub>,ζ，η,γ∈(V<sub>T</sub>∪V<sub>N</sub>)<sup>*</sup>，而γ≠ε。也就是说，对于这种文法而言，当对非终结符号进行替换时务必考虑上下文环境。在上述产生式的形式下，即只有在上下文ζ和η中，才允许我们把A替换为γ。    
</p> 
<p> 
1型文法所产生的语言称作<font class="definition2">1型语言</font>，也称作<font class="definition2">上下文有关语言</font>。 
</p> 

</td></tr></table> 
 
<br> 
<table align=right width=300> 
<tr> 
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.3.3c.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.4.1b.htm'"></img></td>
</tr> 
</table> 
 
</BODY> 
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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