📄 2.4.1b.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.4.1.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.4.2.htm'"></img></td>
</tr>
</table>
<br><br>

<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td> 
<td class="content"> 
<p> 
如果文法G=(V<sub>T</sub>，V<sub>N</sub>，S,P )中的每一个产生式的形式为：<br> 
<center> A→β </center> 
&nbsp&nbsp&nbsp&nbsp其中A∈V<sub>N</sub>，β∈(V<sub>T</sub>∪V<sub>N</sub>)<sup>*</sup>，则称G是<font class="definition2">2型文法</font>，也称为<font class="definition2">上下文无关文法</font>。2型文法所产生的语言称作<font class="definition2">2型语言</font>，也称作<font class="definition2">上下文无关语言</font>。 
</p> 
<p> 
如果文法G＝(V<sub>T</sub>，V<sub>N</sub>，S,P )中的每一个产生式的形式为：<br> 
<center> A→aB或A→a </center> 
&nbsp&nbsp&nbsp&nbsp其中，A,B∈V<sub>N</sub>，a∈V<sub>T</sub>∪{ε} ，则称G是<font class="definition2">右线性文法</font>。     
</p> 
<p> 
如果文法G中的每一个产生式的形式为：<br> 
<center> A→Ba或A→a </center> 
&nbsp&nbsp&nbsp&nbsp则称G是<font class="definition2">左线性文法</font>。 
</p> 
<p> 
右线性文法和左线性文法都称为<font class="definition2">3型文法</font>。3型文法也称为<font class="definition2">正规文法</font>。它所产生的语言称为<font class="definition2">3型语言</font>或<font class="definition2">正规语言</font>。     
</p>
<p> 
另外，正规文法也可以按如下方式定义：<br> 
&nbsp&nbsp&nbsp&nbsp如果文法G＝(V<sub>T</sub>，V<sub>N</sub>，S,P)中的每一个产生式的形式为：<br> 
<center> A→αB或A→α </center> 
&nbsp&nbsp&nbsp&nbsp其中A,B∈V<sub>N</sub>，α∈V<sub>T</sub><sup>*</sup>，则称G为右线性文法。<br> 
&nbsp&nbsp&nbsp&nbsp如果文法G中的每一个产生式的形式为：<br> 
<center> A→Bα或A→α </center> 
&nbsp&nbsp&nbsp&nbsp则称G是左线性的。 
</p> 
<p> 
这两种正规文法的定义的不同之处在于：前一种定义中的a是一个终结符号或ε，后一种定义中的α是属于V<sub>T</sub><sup>*</sup>的终结符号串，自然也可以是ε。然而这两种定义是等价的。 
</p> 
<p> 
由此可知，上面所定义的四个文法类是逐渐增加限制的。如表2.1所示，在0型文法的定义的基础上增加表中列出的限制1，成为1型文法；再进一步增加限制2，成为2型文法；再进一步增加限制3，成为3型文法。这就是说，依次有不是上下文有关的0型语言、不是上下文无关的上下文有关语言以及不是正规语言的上下文无关语言。有关形式语言理论之中所做的大量工作是在上下文无关语言、正规语言方面。本书只限于讨论这些语言。  
</p> 
<p align=center> 
表2.1 文法的类型<br> 
<table align=center border=1 cellpadding=5>
<tr align=center>
<td>文法类型</td>
<td>产生式形式的限制</td>
<td>文法产生的语言</td>
<tr align=center>
<td>0</td>
<td>α->β，其中α,β∈(V<sub>N</sub>∪V<sub>T</sub>)<sup>*</sup><br>|α|≠0</td>
<td>0型语言</td>
<tr align=center>
<td>1</td>
<td>α->β，其中α,β∈(V<sub>N</sub>∪V<sub>T</sub>)<sup>*</sup><br>但需|α|≤|β|</td>
<td>1型语言<br>即上下文有关语言</td>
<tr align=center>
<td>2</td>
<td>A->β，其中A∈V<sub>N</sub><br>β∈(V<sub>N</sub>∪V<sub>T</sub>)<sup>*</sup></td>
<td>2型语言<br>即上下文无关语言</td>
<tr align=center>
<td>3</td>
<td>A->α或A->αB(右线性)<br>或<br>A->α或A->Bα(左线性)<br>其中A,B∈V<sub>N</sub>,α∈V<sub>T</sub>∪{ε}</td>
<td>3型语言<br>即正规语言</td>
</tr>
</table>

</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.4.1.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.4.2.htm'"></img></td>
</tr> 
</table> 
 
</BODY> 
</html>
⌨️ 快捷键说明

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