📄 4.10.16.htm
字号:
<html>
<head>
<title>4.16的解答</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>
<body background="../images/background2.gif">
<center>
<center><font class="title2"><b>练习4.16</b></font></center><br>
</center>
<table><tr><td> </td>
<td class="content">
解：(1)<br>
其拓广文法G'：
<table align=center width=450 class="content">
<tr><td>(0) S' → S</td><td>(1) S → AS</td></tr>
<tr><td>(2) S → b</td><td>(3) A → SA</td></tr>
<tr><td>(4) A → a</td><td></td></tr>
</table>
构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:<br>
I<sub>0</sub> = {S'→·S, S→·AS, S→·b, A→·SA, A→·a} <br>
I<sub>1</sub> = {S'→S·, A→S·A, A→·SA, A→·a, S→·AS, S→·b }<br>
I<sub>2</sub> = {S→A·S, S→·AS, S→·b, A→·SA, A→·a }<br>
I<sub>3</sub> = {A →a·}<br>
I<sub>4</sub> = {S→b·}<br>
I<sub>5</sub> = {A→SA·, S→A·S, S→·AS, S→·b, A→·SA, A→·a }<br>
I<sub>6</sub> = {A→S·A, A→·SA, A→·a, S→·AS, S→·b}<br>
I<sub>7</sub> = {S→AS·, A→S·A, A→·SA, A→·a, S→·AS, S→·b}<br>
<center><img src="images/ex4.161.gif"></center><br>
<br>
(2) 文法G[S]的LR(0)项目如下：
<table align=center width=450 class="content">
<tr><td>(0) S' → ·S</td><td>(1) S' → S·</td></tr>
<tr><td>(2) S → ·AS</td><td>(3) S → A·S</td></tr>
<tr><td>(4) S → AS·</td><td>(5) S → ·b</td></tr>
<tr><td>(6) S → b·</td><td>(7) A → ·SA</td></tr>
<tr><td>(8) A → S·A</td><td>(9) A → SA·</td></tr>
<tr><td>(10)A → ·a</td><td>(11)A → a·</td></tr>
</table>
<center><img src="images/ex4.162.gif"></center><br>
对上面的NFA通过求ε-cloasure确定化，得到与(1)相同的识别文法G[S]活前缀的DFA。因此，此NFA与(1)的DFA等价。<br>
<br>
(3) 求<b>FOLLOW</b>集：<br>
<b>FOLLOW</b>(S) = { a, b, ＄ }<br>
<b>FOLLOW</b>(A) = { a, b }<br>
G[S]的SLR分析表：<br>
<center><img src="images/ex4.163.gif" width="553" height="231"></center><br>
<br>
(4)
<center><img src="images/ex4.164.gif" width="553" height="252"></center><br>
注：G[S]的SLR分析表中有移进－归约冲突，因此它不是一个SLR文法。其实，G[S]是一个二义性文法，对于句子abab有下面两棵不同的分析树。因此，G[S]不是任何LR文法。<br>
<center><img src="images/ex4.165.gif" width="394" height="235"></center><br>
<br>
(5) 文法G[S]的LR(1)项目集规范族及转移函数为：<br>
I<sub>0</sub> = {[S'→·S, $], [S→·AS, $/a], [S→·b, $/a], [A→·SA, a/b], [A→·a, a/b]}<br>
I<sub>1</sub> = {[S'→S·, $], [A→S·A, a/b], [A→·SA,a/b], [A→·a, a/b], [S→·AS, a/b], [S→·b, a/b]}<br>
I<sub>2</sub> = {[S→A·S, $/a/b], [S→·AS, $/a/b], [S→·b, $/a/b], [A→·SA, a/b], [A→·a, a/b],}<br>
I<sub>3</sub> = {[A→a·, a/b]}<br>
I<sub>4</sub> = {[S→b·, a/b/$]}<br>
I<sub>5</sub> = {[A→S·A, a/b], [A→·SA, a/b], [A→·a, a/b], [S→·AS, a/b], [S→·b, a/b]}<br>
I<sub>6</sub> = {[A→SA·, a/b], [S→A·S, a/b], [S→·AS, a/b], [S→·b, a/b], [A→·SA, a/b], [A→·a, a/b]}<br>
I<sub>7</sub> = {[S→AS·, a/b/$], [A→S·A, a/b], [A→·SA, a/b], [A→·a, a/b], [S→·AS, a/b], [S→·b, a/b]}<br>
I<sub>8</sub> = {[S→A·S, a/b], [S→·AS, a/b], [S→·b, a/b], [A→·SA, a/b], [a→·a, a/b]}<br>
I<sub>9</sub> = {[S→AS·, a/b/$], [A→S·A, a/b], [A→·SA, a/b], [A→·a, a/b], [S→·AS, a/b], [S→·b, a/b], }<br>
I<sub>10</sub> = {[S→b·, a/b]}<br>
<center><img src="images/ex4.166.gif" width="429" height="366"></center><br>
合并同心项目集(I<sub>2</sub>和I<sub>8</sub>，I<sub>7</sub>和I<sub>9</sub>，I<sub>4</sub>和I<sub>10</sub>)：<br>
I<sub>0</sub> = {[S'→·S, $], [S→·AS, $/a], [S→·b, $/a], [A→·SA, a/b], [A→·a, a/b]}<br>
I<sub>1</sub> = {[S'→S·, $], [A→S·A, a/b], [A→·SA,a/b], [A→·a, a/b], [S→·AS, a/b], [S→·b, a/b]}<br>
I<sub>2,8</sub> = {[S→A·S, $/a/b], [S→·AS, $/a/b], [S→·b, $/a/b], [A→·SA, a/b], [A→·a, a/b],}<br>
I<sub>3</sub> = {[A→a·, a/b]}<br>
I<sub>4,10</sub> = {[S→b·, a/b/$]}<br>
I<sub>5</sub> = {[A→SA·, a/b], [S→A·S, a/b], [S→·AS, a/b], [S→·b, a/b], [A→·SA, a/b], [A→·a, a/b]}<br>
I<sub>6</sub> = {[A→S·A, a/b], [A→·SA, a/b], [A→·a, a/b], [S→·AS, a/b], [S→·b, a/b]}<br>
I<sub>7,9</sub> = {[S→AS·, a/b/$], [A→S·A, a/b], [A→·SA, a/b], [A→·a, a/b], [S→·AS, a/b], [S→·b, a/b]}<br>
<center><img src="images/ex4.167.gif" width="400" height="370"></center><br>
LR(1)和LALR分析表从略。<br>
</td></tr></table>
</body>
</html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -