📄 4.7.2.2b.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.2.2.htm'" width="24" height="24" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.2.2c.htm'" width="26" height="24"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>    </td>
<td class="content">
没有从I<sub>6</sub>，I<sub>10</sub>,I<sub>7</sub>及I<sub>11</sub>出发的转移。从I<sub>4</sub>及I<sub>5</sub>出发的有: <br>
I<sub>8</sub>＝go(I<sub>4</sub>，A)=closure({A→cA·})={A→cA·} <br>
I<sub>4</sub>=go(I<sub>4</sub>,c)＝closure({A→c·A})={A→c·A,A→·cA,A→·d} <br>
I<sub>10</sub>＝go(I<sub>4</sub>,d)=closure({A→d·})={A→d·} <br>
I<sub>9</sub>＝go(I<sub>5</sub>，B)=closure({B→cB·})={B→cB·} <br>
I<sub>5</sub>=go(I<sub>5</sub>,c)＝closure({B→c·B})={B→c·B,B→·cB,B→·d} <br>
I<sub>11</sub>＝go(I<sub>5</sub>,d)=closure({B→d·})={B→d·} <br>
它们分别是活前缀acA，acc ，acd，bcB，bcc，bcd的有效项目集。注意到I4经过箭弧c，I<sub>5</sub> 经过箭弧c引向自身的转移可以任意多次重复，其余I<sub>8</sub>，I<sub>10</sub>，I<sub>9</sub>及I<sub>11</sub>都没有引向其他有效项目集的转移。此地Ik既代表项目集又代表状态，在不同的地方有不同的含义。</p>
<p>上述文法(4.15)的LR(0)项目集规范族及识别活前缀的DFA如图4.17所示。显然这个DFA识别文法G的所有活前缀。图4.17中每一个状态都是终态，为了减少画图的麻烦，本章我们省略掉用双圆圈表示终态结的规定。</p>
<p>从上面的讨论,我们已经看到:对于拓广文法G'的每一个活前缀γ,它的有效项目集恰好是从它的识别活前缀的DFA的初态出发经过γ道路所到达的那个状态所代表的项目集。这是LR分析理论中的一条基本定理。事实上，在任何时候分析栈中的活前缀X<sub>1</sub>X<sub>2</sub>…X<sub>m</sub>的有效项目集恰恰是栈顶状态S<sub>m</sub>所代表的那个集合。这也表示栈顶状态体现了栈里一切有用的信息。然而我们不再进行严格的形式化证明。</p>
<p>在图4.17中，I<sub>6</sub>，I<sub>7</sub>，…，I<sub>11</sub>所含的项目都是归约项目。I<sub>1</sub>所含的项目是接受项目，其余的I<sub>k</sub>所含项目都是移进或待约项目，若归约项目A→β<sub>1</sub>·对活前缀αβ<sub>1</sub>是有效的，则它告诉我们应把符号串β<sub>1</sub>归约为A。若移进项目A→β<sub>1</sub>·β<sub>2</sub>对活前缀αβ<sub>1</sub>是有效的，则它告诉我们句柄尚未形成，下步动作应该是移进。一般而言，对同一个活前缀存在若干不同的项目对它是有效的，而且它告诉我们应做的事情可能各不相同，互相冲突。这种冲突通过向前看几个输入符号或许能够解决。本节的SLR及LR(1)分析器分别是通过简单的向前看和向前看一个输入符号来解决的。</p>
</td></tr></table>
</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.2.2.htm'" width="24" height="24" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='4.7.2.2c.htm'" width="26" height="24"></img></td>
</tr>
</table>
</BODY>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -