-
第三章
N=>D=> {0,1,2,3,4,5,6,7,8,9}
N=>ND=>NDD
L={a
|a(0|1|3..|9)
n
且
n>=1}
(0|1|3..|9)
n
且
n>=1
{ab,}
a
n
b
n
n>=1
第
6
题
.
(1) <
表达式
> =>
<
项
> =>
<
因子
> => i
(2)
<
表达式
> =>
<
项
> =>
<
因子
> =>
(<
表达式
>) =>
(<
项
>)
=>
(<
因子
>)=>(i)
(3)
<
表达式
> =>
<
项
> => <
项
< br>>*<
因子
> => <
因子<
/p>
>*<
因子
> =i*i
(4) <
表达式
> =>
<
表达式
> +
<
项
> => <
项
< br>>+<
项
> => <
项
>*<
因子
>+<
项
>
=> <
因子
< br>>*<
因子
>+<
项
> => <
因子
>*<
因子
>+<
因子
> = i*i+i
(5) <
表达式
> => <
表达式
>+<
项
>=
><
项
>+<
项
> => <
因子
>+<
项<
/p>
>=i+<
项
>
=>
i+<
因子
> =>
i+(<
表达式
>) => i+(<
表达式
>+<
项
>)
=> i+(<
因子
>+<
因子
>)
=>
i+(i+i)
(6) <
表达式
>
=> <
表达式
>+<
项
> => <
项
>+<
项<
/p>
> => <
因子
>+<
项
> => i+<
项
>
=> i+<
项
>*<
因子
> => i+<
因子
>*<
因子
> = i+i*i
第
7
题
<
表达式
>
<
表达式
>
<
运算符
>
<
表达式
>
<
表达式
>
<
运算符
>
<
表
达式
>
*
i
i
+
i
1
<
表达式
>
<
表达式
>
<
运算符
>
<
表
达式
>
i
+
<
表达式
>
<
运
算符
>
<
表达式
>
i
*
第
9
题
语法树
s
s
s
*
s<
/p>
s
+
a
a
a
推导
: S=>SS*=>SS+S*=>aa+a*
11.
推导
:E=>E+T=>E+T*F
语法树
:
E
E
+
T
T
*<
/p>
F
短语
:
T*F E+T*F
直接短语
: T*F
句柄
: T*F
12
．
i
2
短语：
直接短语：
句柄：
13.(1)
最左推导：
S =>
ABS => aBS =>aSBBS => aBBS
=> abBS =>
abbS => abbAa => abbaa
最右推导：
S => ABS => ABAa =>
ABaa => ASBBaa
=> ASBbaa =>
ASbbaa => Abbaa => a1b1b2a2a3
(2)
文法：
S
?
ABS
S
?
Aa
S
?
ε
A
?
a
B
?
b
(3)
短语：
a1 , b1 , b2, a2 , , bb ,
aa , abbaa,
直接短语：
a1 , b1
, b2, a2 , ,
句柄：
a1
14 (1)
S
?
AB
A
?
aAb |
ε
B
?
aBb |
ε
(2)
S
?
1S0
S
?
A
A
?
0A1
|
ε
第四章
1.
1.
构造下列正规式相应的
DFA
(1)
1(0|1)*101
NFA
0
1
1
1
2
0
3<
/p>
1
4
0,1
(2) 1(1010*|1(010)*1)*0
NFA
3
0<
/p>
0
1
1
1
0
1
0
ε
0
0
0
1
4
0
0
1
0
2
0
(3)NFA
b
(4)NFA
a
2
< br>a
0
a
1
b
4
2
b
0
b
1
ε
3
ε
b
a
5
b
6
ε
3
ε
a,b
a
b
4
2.
解：构造
DFA
矩阵表示
{X}
{Z
}
{X,Z}
{Y}
*
*
0
0
{Z}
{X,Z}
{X,Z}
{X,Y}
1
{X}
{Y}
{X,Y}
4
{X,Y}
{X,Y,Z}
{X}
{X,Y,Z}
*
{X,Y,Z}
{X,Y}
其中
0
表示初态，
< br>*
表示终态
用
0
，
1
，
2
，
3
，
4
，
5
分别代替
{
X}
{Z} {X,Z}
{Y} {X,Y} {X,Y,Z}
得
DFA
状态图为：
1
1<
/p>
1
3
0
0
0
0
0
0
5
0
1
2
4
1
1
3
．解：构造
DFA
矩阵表示
构造
DFA
的矩
阵表示
0
1
{S}
0
{V,Q}
{Q,U}
{V,Q}
{Z,V}
{Q,U}
{Q,U}
{V}
{Q,U,Z}
{Z,V}
*
{Z}
{Z}
{V}
{Z}
{Q,U,Z}
*
{V,Z}
{Q,U,Z}
{Z}
{Z}
{Z}
其中
0
表示初态，
*
表示终态
替换后的矩阵
0
1
0
0
1
2
1
3
2
2
4
5
3
*
6
6
4
6
5*
3
5
6
6
6
构造
DFA
状态转换图（略）
4
．
（
1
）解
构造状态转换矩阵：
5
a
b
{0}
0*
{0,1}
{1}
{0,1}
*
{0,1}
{1}
{1}
{0}
转换为
a
b
0
*
1
2
1
*
1
2
2
0
{2
，
3}
{0
，
1}
{2
，
3}a={0,3}
{2},{3},{0,1}
{0,1}a={1,1}
{0,1}b={2,2}
（<
/p>
2
）
解：
首先把
M
的状态分为两组：
终态组
{0}
，
和非终态组
{1
，
2
，
3
，
4,5}
{1,2,3,4,5}<
/p>
a
={1,3,0,5}
{1,2,3
,4,5}
b
={4,3,2,5}
由于
{4}
a
={0}
{1,2,3,5}
a
={1,3,5}
因此应将
{1,2,3,4,5}
划分为
< br>{4},{1,2,3,5}
G=({0}{4}{1,2,3,5})
{1,2,3,5}
a
={1,3,5}
{1,2,3,5}
b
={4,3,2
}
因为
{1,5}
b
={4} {23}
b
={2,3}
所以应将
{1,2,3,5}
划分为
{1,5}{2,3}
G=({0}{1,5}{2,3}{4})
{1,5}
a
={1,5}
{1,5}
b
={4}
所以
{1,5}
不用再划分
{2,3}
a
={1,3}
{2,3}
b
={3,2}
因为
{2}
a
={1}
{3}
a
={3}
所以
{2,3}
应划分为
{2}{3}
所以化简后为
G
＝（
{0},{2},{3},{4},{1,5}
）
7.
去除
多余产生式后，构造
NFA
如下
a
A
D
a
b
b
b
S
Z
b
b
b
< br>b
B
Q
a
a
此时
G=(
{0},{1,2,3,4,5}
)
6
确定化，构造
< br>DFA
矩阵
a
b
S
A
Q
A
A
B,Z
B,Z
Q
D
Q
Q
D,Z
D
A
B
D,Z
A
D
B
Q
D
变换为
a
b
0
0
1
3
1
1
2
2
*
3
4
3
3
5
4
1
6
5
*
1
4
6
3
4
化简：
G={(0,1,3,4,6),(2,5)}
{0,1,3,4,6}a={1,3}
{0,1,3,4,6}b={2,3,4,5,6}
所以将
{0,1,3,4,6}
划分为
{0,4,6}{1,3}
G={(0,4,6),(1,3),(2,5)}
{0,4,6}b={3,6,4}
所以
划分为
{0},{4,6}
G={(0),(4,6),(1,3),(2,5)}
不能再划分，分别用
0
，
4
，
1
，
2
代表各状态，构造
DFA
状
态转换图如下；
a
0
a,b
1
a
4
b
b
a
b
2
8
．代入得
S = 0(1S|1)| 1(0S|0)
=
01(S|
ε
) |
10(S|
ε
)
=
(01|10)(S|
ε
)
= (01|10)S | (01|10)
7
=
(01|10)
*
(01|10)
构造
NFA
0
A
1
1
S
Z
0
1
B
0
由
NFA
可得正
规式为
(01|10)
*
(01|10
)=(01|10)
+
9.
状态转换函数不是全函数
,
< br>增加死状态
8,
G={(1,2,3,4,5,8),(6,7)}
(1,2,3,4,5,8)
a
=(3,4,8)
(3,4)
应分出
(1,2,3,4
,5,8)
b
=(2,6,7,8)
(1,2,3,4,5,8)
c
=(3,8)
(1,2,3,4,5,8)
d
=(3,8)
所以应将
(1,2,3,4,5,8)
分为
(1,2,5,8), (3,4)
G={(1,2,5,8),(3,4),(6,7)}
(1,2,5,8)a=(3,4,8)
8
应分出
(1,2,5,8)b=(2,8)
(1,2,5,8)c=(8)
(1,2,5,8)d=(8)
G={(1,2,5),(8),(3,4),(6,7)}
(1,2,5)a=(3,4,8)
5
应分出
G={(1,2),
(3,4),5, (6,7) ,(8) }
去掉死状态
8,
最终结果为
(1,2) (3,4) 5,(6,7)
以
1,3,5,6
代替
,
最简
DFA
为
b
c
1
< br>a
3
b
6
b
d
a
5
正规式
:b
*
a(da|c)
*
bb
*
第五章
1.
8
S->a | ^ |( T )
T -> T , S | S
(a,(a,a))
S => ( T ) => ( T , S ) => ( S , S ) =>
( a , S) => ( a, ( T )) =>(a , ( T , S ) ) => (a ,
( S , S )) => (a , ( a , a ) )
S=>(T)
=> (T,S) => (S,S) => ( ( T ) , S ) => ( ( T , S )
, S ) => ( ( T , S , S ) , S ) =>
( ( S , S , S ) , S )
=> ( ( ( T ) , S , S ) , S )
=> ( ( ( T , S ) , S , S )
, S ) =>( ( ( S , S ) , S , S ) , S ) => ( ( ( a ,
S ) , S , S ) , S )
=> ( ( ( a , a ) ,
S , S ) , S ) => ( ( ( a , a ) , ^ , S ) , S ) =>
( ( ( a , a ) , ^ , ( T ) ) , S )
=> (
( ( a , a ) , ^ , ( S ) ) , S )
=> ( ( ( a , a ) , ^ , ( a ) ) , S ) =>
( ( ( a , a ) , ^ , ( a ) ) , a )
S->a | ^ |( T )
T -> T , S
T -> S
消除直接左递归：
S->a | ^ |( T )
T -> S
T
’
T
’
-> , S
T
’
|
ξ
SELECT ( S->a) = {a}
SELECT ( S->^) = {^}
SELECT
( S->( T ) ) = { (
}
SELECT ( T -> S
T
’
) = { a , ^ , (
}
SELECT ( T
’
-> ,
S T
’
) = { ,
}
SELECT (
T
’
->
ξ
) = FOLLOW (
T
’
) = FOLLOW ( T ) = {
）
}
构造预测分析表
S
T
T
’
a
->
a
-> S T
’
^
-> ^
-> S T
’
(
-> ( T )
-> S
T
’
)
->
ξ
,
-> , S
T
’
#
分析符号串
（
a , a
）
#
分析栈
剩余输入串
所用产生式
#S
( a ,
a) #
S
-> ( T )
# ) T (
( a ,
a) #
(
匹配
# ) T
a ,
a ) #
T -> S
T
’
# )
T
’
S
a ,
a ) #
S -> a
# )
T
’
a
a ,
a ) #
a
匹配
#
) T
’
，
a) #
T
’
-> , S
T
’
# )
T
’
S ,
,
a ) #
,
匹配
# ) T
’
S
a ) #
S->a
# )
T
’
a
a ) #
a
匹配
#
) T
’
) #
T
’
->
ξ
#
)
) #
)
匹配
#
#
接受
9
2.
E->TE
’
E
’
->+E
E
’
->
ξ
T->FT
’
T
’
->T
T
’
-><
/p>
ξ
F->PF
’
F
’
->*F
’
F
’
-><
/p>
ξ
P->(E)
P->a
P->b
P->
∧
非终结符名
E
E
’
T
T
’
F
F
’
P
是否＝
>
ε
否
是
否
是
否
是
否
FIRST
集
{
（，
a
，
b
，
^}
{+,
ε
}
{
（，
a
，
b
，
^}
{
ε
,
（，
a
，
b
，
^}
{
（，
a<
/p>
，
b
，
^}
{*,
ε
}
{
（，
a
，
b
，
^}
FOLLOW
集
{#
，
）
}
{#
，
）
}
{
＋，
#
，<
/p>
）
}
{
＋，<
/p>
#
，
）
}
{
（，
a
，
b
，
^
，＋，
#
，
）
}
{
（，
a
，
b
，
^
，＋，
#
，
）
}
{*
，
（，
a
，
b
，
^
< br>，
#
，
）
}
SELECT
（
E
－
>TE’
）
=FIRST
(TE’)=FIRST(T)= {
（，
a
< br>，
b
，
^
）
SELECT
（
E
’
－
>+E
）
={+}
SELECT
（
E
’
－
>
ε
）
=FOLLOW(E’)=
{#
，
)}
SELECT
（
T
－
>FT
’
）
=FIRST
（
F
）
= {
（，<
/p>
a
，
b
，
^}
SELECT
（
T
’
—
>T
）
=FIRST
（
T
）
= {
（，
a
，
b
，
^
< br>）
SELECT(T’
－
>
ε
)=FOLLOW(T’)= {
＋，
#
，
)}
SELECT(F
－
>PF’)=FIRST(F)= {
（，
a
，
b
，
^}
SELECT(F’
－
>*F’)={*}
SELECT(F’<
/p>
－
>
ε
)=FO
LLOW(F’)= {
（，
a
，
b
，
^
，＋，
#
，
）
}
3.
S->MH
S->a
H->Lso
H->
ξ
K->dML
K->
ξ
L->eHf
M->K
M->bLM
FIRST ( S ) =FIRST(MH)=
FIRST ( M )
∪
FIRST ( H )
∪
{
ξ
}
∪
{a}= {a, d , b
, e ,
ξ
}
FIRST( H ) = FIRST ( L )
∪
{
ξ
}= { e ,
ξ
}
FIRST( K ) = { d ,
ξ
}
FIRST( M ) = FIRST ( K )
∪
{ b } =
{ d , b
,
ξ
}
FOLLOW ( S ) = { # , o }
FOLLOW ( H ) =
FOLLOW ( S )
∪
{
f } = { f , # , o }
FOLLOW ( K ) =
FOLLOW ( M ) =
{ e , # , o
}
FOLLOW ( L )
={ FIRST ( S )
–
{
ξ
} }
∪
{o}
∪
FOLLOW ( K )
∪
{ FIRST ( M )
–
{
ξ
} }
∪
FOLLOW ( M )
=
{a,
d , b , e , # , o }
FOLLOW ( M ) ={ FIRST ( H )
–
{
ξ
} }
∪
FOLLOW ( S )
∪
{ FIRST ( L )
–
{
ξ
} }
= { e , # , o }
SELECT ( S-> M H) = ( FIRST ( M H)
–
{
ξ
} )
∪
FOLLOW ( S )
= ( FIRST( M )
∪
FIRST ( H )
–
{
ξ
} )
∪
FOLLOW ( S )
= { d , b , e , # , o }
SELECT ( S-> a ) = { a }
SELECT ( H->L S o ) = FIRST(L S o) = {
e }
10
SELECT ( H ->
ξ
) = FOLLOW ( H ) = { f , # , o }
SELECT ( K-> d M L ) = { d }
SELECT ( K->
ξ
) = FOLLOW ( K )
= { e , # , o }
SELECT ( L->
e H f ) = { e }
SELECT ( M->K ) = (
FIRST( K )
–
{
ξ
} )
∪
FOLLOW ( M )
= {d
，
e , # , o }
SELECT ( M -> b
L M )= { b }
构造
LL( 1 )
分析表
S
H
K
L
M
a
-> a
b
-> M H
-> b L M
e
-> M H
->L S o
->
ξ
->
e H f
->K
d
-> M
H
-> d M L
->K
f
->
ξ
o
->
M H
->
ξ
->
ξ
->K
#
-> M H
->
ξ
->
ξ
->K
4 .
文法含有左公因式，变为
S->C $$
{ b, a }
C-> b A
{ b }
C->
a B
{ a
}
A -> b A A
{ b }
A-
> a A’
{ a }
A’
->
ξ
{ $$ , a, b }
A’
-> C
{ a , b }
B->a B
B
{ a }
B -
> b B’
{ b }
B’
->
ξ
{ $$
, a , b }
B’
-> C
{ a, b }
5.
<
程序
>
---
S
<
语句表
>
――<
/p>
A
<
语句
>
――
B
<
无条件语句
>
――
C
<
条件语句
>
――
< br>D
<
如果语句
>
――
E
<
如果子句
> --F
S->begin A end
S->begin A end
{
begin }
A-> B
A-
>
B A’
{ a , if }
A-
> A B
A’
-
> B A’
{
}
A’
->
ξ
{ end }
B-> C
B-> C
{ a }
B-> D
B->
D
{
if }
C-> a
C-> a
{ a }
D->
E
D-
>
E D’
{ if
}
D-> E else B
D’
-> else B
{ else }
D’
->
ξ
{; , end
}
E->
FC
E-> FC
{
if }
F-> if b then
F-> if b then
{ if }
非终结符是否为空
S
－否
A
－否
A
’
－是
B
－否
C
－否
D
－否
D
’
－是
E
－否
F
－否
11
FIRST(S) = { begin }
FIRST(A) = FIRST(B)
∪
FIRST(A
’
)
∪
{
ξ
} = {a , if ,
,
ξ
}
FIRST(A
’
) ={ ,
ξ
}
FIRST(B) =
FIRST(C)
∪
FIRST(D) ={ a , if }
FIRST(C) = {a}
FIRST(D) = FI
RST
（
E
）
=
{ if }
FIRSR(D
’
) = {else
,
ξ
}
FIRST(E) =
FIRST(F) = { if }
FIRST(F) = { if }
FOLLOW(S) = {# }
FOLLOW(A) = {end}
FOLLOW(A
’
) = {
end }
FOLLOW(B) = {; , end }
FOLLOW (C) = {; , end , else }
FOLLOW(D) = {; , end }
FOLLOW( D
’
) = {
; , end }
FOLLOW(E) = { else , end }
FOLLOW(F) = { a }
S A
A
’
B C D
D
’
E F
if then else
begin end
a b
S
A
A
’
B
C
D
D
’
E
F
if
-
> B A’
-> D
-
> E D’
->FC
->if b then
then
else
begin
end
->
ξ
->
ξ
a
-
> B A’
-> C
-> a
b
;
#
->begin A end
->
;
B
A’
->
ξ
->
else
B
D’
6.
1.
(1) S -> A | B
(2) A -> aA|a
(3)B -> bB |b
提取
（
2<
/p>
）
，
（
3
）左公因子
(1) S -> A | B
(2) A -> aA
’
(3) A
’
->
A|
ξ
(4) B ->
bB
’
12
(5)
B
’
-> B
|
ξ
2.
(1) S->AB
(2)
A->Ba|
ξ
(3)
B->Db|D
(4) D->
d|
ξ
提取（
3
）左公因子
(1) S->AB
(2) A->Ba|
ξ
(3) B->DB
’
(4) B
’
->b|
ξ
(5) D->
d|
ξ
3.
(1) S->aAaB | bAbB
(2) A->
S| db
(3) B->bB|a
4
(1)
S->i|(E)
(2)
E->E+S|E-S|S
提取（
2
）左公因子
(1)
S->i|(E)
(2)
E->SE
’
(3)
E
’
->+SE
’
|-SE
’
|
ξ
5
(1)
S->SaA | bB
(2)
A->aB|c
(3)
B->Bb|d
消除（
1
）
(3)
直接左递归
(1)
S->bBS
’
(2)
S
’
->aAS
’
|
ξ
(3)
A->aB | c
(4)
B -> dB
’
(5)
B
’
->bB
’
|
ξ
6.
(1) M->MaH | H
(2) H->b(M) |
(M) |b
消除（
1
）直接左递归
，提取（
2
）左公因子
(1)
M->
HM
’
(2)
M
’
->
aHM
’
|
ξ
(3)
H->bH
’
| ( M )
(4)
H
’
->(M)
|
ξ
7.
(1)
13
1)
A->baB
2)
A->
ξ
3)
B->Abb
4)
B->a
将
1
）
、
2)
式代入
3
）式
1)
A->baB
2)
A->
ξ
3)
B->baBbb
4)
B->bb
5)
B->a
提取
3
）
、
4
）式左公因子
1)
A->baB
2)
A->
ξ
3)
B->bB
’
4)
B
’
->aBbb | b
5)
B->a
(3)
1)
S->Aa
2)
S->b
3)
A->SB
4)
B->ab
< br>将
3
）式代入
1
）式
1)
S->SBa
2)
S->b
3)
A->SB
4)
B->ab
消除
1
< br>）式直接左递归
1)
S->bS
’
2)
S
’<
/p>
->BaS
’
|
ξ
3)
S->b
4)
A->SB
5)
B->ab
删除多余产生式
4
）
1)
S->bS
’
2)
S
’<
/p>
->BaS
’
|
ξ
3)
S->b
4)
B->ab
（
5
）
1)
S->Ab
2)
S->Ba
3)
A->aA
4)
A->a
5)
B->a
提取
3
）
4
）左公因子
14
1)
S->Ab
2)
S->Ba
3)
A->aA
’
4)
A
’
-> A
|
ξ
5)
B->a
将
3
）代入
1
）
5
）代入
2
1)
S->aA
’
b
2)
S->aa
3)
A->aA
’
4)
A
’
-> A
|
ξ
5)
B->a
提取
1
）
2
）
左公因子
1)
S->
aS
’
2)
S
’
->A
’
b | a
3)
A->aA
’
4)
A
’
-> A
|
ξ
5)
B->a
删除多余产生式
5
）
1)
S-> aS
’
2)
S
’<
/p>
->A
’
b | a
3)
A->aA
’
4)
A
’
-> A
|
ξ
A
A
’
S
’
S
将
3
）代
入
4
）
1)
S->
aS
’
2)
S
’
->A
’
b | a
3)
A->aA
’
4)
A
’
->
aA
’
|
ξ
将
4
）代入
2
）
1)
S-> aS
’
2)
S
’<
/p>
->aA
’
b
3)
S
’
->a
4)
S
’
->b
5)
A->aA
’
6)
A
’
->
aA
’
|
ξ
对
2
）
3)<
/p>
提取左公因子
1)
S->aS
’
2)
S
’<
/p>
->aS
’’
3)
S
’’
->A
’
b|
ξ
4)
S
’
->b
5)
A->aA
’
6)
A
’
->
aA
’
|
ξ
删除多余产生式
5
）
< br>
1)
S->aS
’
2)
S
’<
/p>
->aS
’’
3)
S
’’
->A
’
b|
ξ
15
4)
S
’
->b
5)
A
’
->
aA
’
|
ξ
第六章
1
S
?
a |
∧
| ( T )
T
?
T , S | S
解：
(1)
增加辅助产生式
S
’
?
＃
S
＃
< br>
求
FIRSTVT
集
FIRSTVT<
/p>
（
S
’
）＝
{#}
FIRSTVT
（
S
）＝
{a
∧
(
}
＝
{ a
∧
( }
FIRSTVT
(T)
＝
{,}
∪
FIRSTVT( S ) = { , a
∧
( }
求
LASTVT
集
LASTVT
（
S
’
）＝
{ # }
LASTVT
（
S
）＝
{ a
∧
)}
LASTVT (T)
＝
{ ,
a
∧
)}
(2)
算符优先关系表
a
∧
(
)
,
#
a
·
>
·
>
·
>
∧
·
>
·
>
·
>
(
<
·
<
·
<
·
=
·
<
·
)
·
>
·
>
·
>
,
<
·
<
·
<
·
·
>
·
>
#
<
·
<
·
<
·
=
·
因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法
(3)
a
∧
(
)
,
F
1
1
1
1
1
1
g
1
1
1
1
1
1
f
2
2
1
3
2
1
g
2
2
2
1
2
1
f
3
3
1
3
3
1
g
4
4
4
1
2
1
f
3
3
1
3
3
1
g
4
4
4
1
2
1
(4)
栈
优先关系
当前符号
剩余输入串
移进或规约
＃
<
·
(
a,a)#
移进
16
#
＃
(
<
·
a
,a)#
移进
#
(a
·
>
,
a)#
规约
＃
(T
<
·
,
a)#
移进
＃
(T
，
<
·
a
)#
移进
＃
(T,a
·
>
)
#
规约
＃
(T,T
·
>
)
#
规约
＃
(T
=
·
)
#
移进
＃
(T)
·
>
＃
规约
＃
T
=
·
＃
接受
4.
扩展后的文法
S
’
?
#S#
S
?
S;G
S
?
G
G
?
G(T)
G
?
H
H
?
a
H
?
(S)
T
?
T+S
T
?
S
（
1
）
FIRSTVT(S)={;}
∪
FIRS
TVT(G) = {; , a , ( }
FIRSTVT(G)={ (
}
∪
FIRSTVT(H) = {a , ( }
FIRSTCT(H)={a , ( }
FIRSTVT(T) = {+}
∪
FIRSTVT(S) = {+ , , a , (
}
LASTVT(S) = {;}
∪
LASTVT(G) = { , a , )}
LASTVT(G) = { )}
∪
LASTVT(H) = { a
, )}
LASTVT(H) = {a, )}
LASTVT(T) = {+ }
∪
LASTVT(S) = {+ , , a , )
}
构造算符优先关系表
；
(
)
a
+
#
;
·
>
<
·
·
>
·
>
<
·
<
·
(
<
·
<
·
·
>
·
>
<
·
<
·
)
·
>
＝·
·
>
·
>
·
>
a
<
·
<
·
<
·
<
·
+
·
>
<
·
·
>
·
>
·
>
#
·
>
·
>
·
>
＝·
<
/p>
因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法
< br>
（
2
）
句型
a(T+S);H;(S)
的
短语有：
a(T+S);H;(S)
a(T+S);H
a(T+S)
a
T+S
(S)
H
直接短语有
: a
T+S
H
(S)
句柄：
a
素短语：
a
T+S
(S)
最左素短语：
a
(3)
分析
a
；
（
a
＋
a
）
< br>
栈
优先关系
当前符号
剩余输入串
移进或规约
17
＃
＃
a
＃
T
＃
T
；
＃
T
；
（
＃
T
；
（
a
＃
T
；
（
T
＃
T
；
（
T
＋
＃
T<
/p>
；
（
T
＋
a
＃
T
；
（
T
＋
T
＃
T
；
< br>（
T
＃
T
；
（
T
）
＃
T
；
T
＃
T
分析
a
；
（
a
＋
a
）
栈
＃
＃（
＃（
a
＃（
T
＃（
T
＋
<
/p>
＃（
T
＋
a
＃（
T
＋
T
＃（
T
＃（
T
）
＃
T
<
·
·
>
<
·
<
·
<
·
·
>
<
·
<
·
·
>
·
>
＝
·
·
>
·
>
＝
·
a
；
；
（
a
＋
＋
a
）
）
）
＃
＃
＃
；
（
a
＋
a
）＃
（
a
＋
a
）＃
（
a
＋
a
< br>）＃
a
＋
a
）＃
＋
a
）＃
a
）＃
a
）＃
）＃
＃
＃
＃
移进
规约
移进
移进
移进
规约
移进
移进
规约
规约
移进
规约
规约
接受
优先关系
<
·
<
·
·
>
<
·
<
·
·
>
·
>
＝
·
·
>
＝
·
当前符号
(
a
＋
＋
a
）
）
）
＃
＃
剩余输入串
a
＋
a
）＃
＋
a
）＃
a
）＃
a
）＃
）＃
＃
＃
＃
移进或规约
移进
移进
规约
移进
移进
规约
规约
移进
规约
接受
（
4
）
不能用最右推导推导出上面的两个句子。
第七章
1
、已知文法：
A
→
aAd|aAb|
ξ
判断该文法是否
是
SLR
（
1
）文法，若是构造相应分析表，并对输入串
ab#
给出分析过程
。
解：
(0)
A
’→
A
(1)
A
→
aAd
(2) A
→
aAb
(3) A
→
ξ
构造该文法的活前缀
DFA
：
18
-
-
-
-
-
-
-
-
-
上一篇：拳击术语2
下一篇：中医英语术语翻译重点