📄 4.7.2.0.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='4.7.1.1b.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.2.0b.htm'"></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>4.7.2 SLR分析表的构造 </b></font>
<table><tr><td>    </td>
<td class="content">
<p>SLR分析方法的中心思想是首先从给定的文法去构造一个识别该文法所有活前缀的确定的有限自动机(DFA)，然后根据DFA去构造它的分析表。</p>
<p>在活前缀的定义中我们已经知道一个规范句型的活前缀中决不含句柄右边的任何符号，因此活前缀与句柄的关系不外下述三种情况：<br>
1．活前缀已含有句柄的全部符号。<br>
2．活前缀只含有句柄的一部分符号。<br>
3．活前缀不含有句柄的任何符号。
</p>
<p>LR分析过程中，分析栈中出现的活前缀(即栈中文法符号序列)，若是第1种情况，表明此时某一产生式A→β的右部符号串β已出现在栈顶，因此相应的分析动作应当是用此产生式进行归约。若是第2种情况表明此时某产生式A→β<sub>1</sub>β<sub>2</sub>的右端的左部子串β<sub>1</sub>已出现在栈顶，正期待从剩余输入串中能看到由β<sub>2</sub>推出的符号串。若是第3种情况表明此时期望从剩余输入串中能看到由某产生式A→α的右部α所推出的符号串。为了刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别(出现在栈顶)，我们在该产生式的某处加上一圆点“·”来指示位置。对上述三种情况，标有圆点的产生式分别为 <br>
A→β·
A→β<sub>1</sub>·β<sub>2</sub> A→·α
</p>
<p>在文法G的右部某个位置上标有圆点的产生式称为文法G的一个LR(0)项目。例如产生式A→XYZ对应有四个项目</p>
<table align=center width=450 class="content">
<tr><td>A→·XYZ</td></tr>
<tr><td>A→X·YZ</td></tr>
<tr><td>A→XY·Z </td></tr>
<tr><td>A→XYZ·</td></tr>
</table>
<p>但产生式A→ε，只对应一个LR(0)项目为A→·。 </p>
<p>为了叙述方便，凡圆点在产生式最右端的项目，称为归约项目，如A→XYZ·。但对文法开始符号的归约项目，称为接受项目，如S→α·。形如A→α·Bβ的项目，称为待约项目。形如A→α·aβ的项目称为移进项目。上述A→·XYZ，A→X·YZ，A→XY·Z都是移进- 待约项目。究竟是移进还是待约项目视圆点之后第一个符号是终结符号还是非终结符号而定。我们对任何文法G,在G中加进一个新的符号S'和一个产生式S'→S，并以S'代替S作为文法的开始符号，这样得到一个与G等价的文法G' ，它称为G的拓广文法。拓广文法G'的文法开始符号S'仅在一个产生式右部出现，并且它的接受项目是唯一的。
</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='4.7.1.1b.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.2.0b.htm'"></img></td>
</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -