📄 4.7.2.2.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.1b.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.2b.htm'" width="26" height="24"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>    </td>
<td class="content">
<p>下面我们来构造文法(4.15)的LR(0)项目集规范族。</p>
<p>显然项目S'→·S是活前缀ε 的有效项目(因为只要在定义4.7中取γ= ε，β<sub>1</sub>= ε,β<sub>2</sub>=S,
A=S'即可)，我们把包含S'→·S的有效项目集记为I<sub>0</sub>。因为此项目的圆点后紧跟S ，故项目S→·aA及S→·bB也都属于I<sub>0</sub>。由于这两个列入I<sub>0</sub>的项目在圆点之后紧跟终结符号，故I<sub>0</sub>已“封闭”。就是说不可能还有其他项目属于I<sub>0</sub>。构造有效项目集I<sub>0</sub>的工作宣告结束，这样初态项目集是 <br>
I<sub>0</sub>＝｛S'→·S，S→·aA，S→·bB｝ </p>
<p>上述从项目S'→·S出发构造有效项目集I<sub>0</sub>的过程，可用一个对其基本项目集{S'→·S}的闭包运算来表示。即 <br>
I<sub>0</sub>＝closure({ S'→·S}) </p>
<p>有了初态项目集I<sub>0</sub>之后，我们来说明如何从I<sub>0</sub>出发转到下一个有效项目集的构造。我们已知，若I<sub>0</sub>中有圆点后紧跟文法符号X的项目A→α·Xβ(实际上，这里A=S或S'，α=ε)，则项目A→αX·β是对活前缀X 的有效项目(因I<sub>0</sub>中项目的活前缀是ε)，所以从I<sub>0</sub>出发的转移有: <br>
I<sub>1</sub>＝go(I<sub>0</sub>，S)=closure({S'→S·})={S'→ S·｝<br>
I<sub>2</sub>=go(I<sub>0</sub>,a)＝closure({S→a·A
})={S→a·A，A→·cA，A→·d} <br>
I<sub>3</sub>＝go(I<sub>0</sub>,b)=closure({S→b·B})={S→b·B,B→·cB，B→·d} <br>
I<sub>1</sub>，I<sub>2</sub>，I<sub>3</sub>分别是对活前缀S,a，b的有效项目集。<p>因为集合I<sub>1</sub>中唯一元素S'→ S·的圆点后已没有文法符号，故没有从I<sub>1</sub>出发的转移。从I<sub>2</sub>出发的转移有: <br>
I<sub>6</sub>＝go(I<sub>2</sub>，A)=closure({S→aA·})={S→aA·} <br>
I<sub>4</sub>=go(I<sub>2</sub>,c)＝closure({A→c·A})={A→c·A,A→·cA，A→·d} <br>
I<sub>10</sub>＝go(I<sub>2</sub>,d)=closure({A→d·})={A→d·} <br>
它们分别是活前缀aA ，ac，ad的有效项目集。从I<sub>3</sub>出发的转移有:<br>
I<sub>7</sub>＝go(I<sub>3</sub>，B)=closure({S→bB·})={S→bB·} <br>
I<sub>5</sub>=go(I<sub>3</sub>,c)＝closure({B→c·B})={B→c·B，B→·cB,B→·d} <br>
I<sub>11</sub>＝go(I<sub>3</sub>,d)=closure({B→d·})={ B→d·} <br>
它们分别是活前缀bB，bc及bd的有效项目集。<br>
</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.1b.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.2b.htm'" width="26" height="24"></img></td>
</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -