作业三——语法书、短语、直接短语、句柄

1.已知文法：

S->a|^|(T)

T->T,S|S

分析句型（T,(^,a))，求全部的短语、直接短语和句柄。

推导：S->(T)->(T,S)->(T,(T))->(T,(T,S))->(T,(S,S))->(T,(^,S))->(T,(^,a))

语法树：

 

全部短语

(T,(^a))   T,(^,a)      (^,a)      ^,a    ^    a

直接短语

a   ^

句柄

^

2.构造上下文无关文法，描述语言：

｛aⁿbⁿ|n>=0｝

｛a^mbⁿ|m>=n>=0｝

｛(ab)ⁿ|n>=0｝

｛a^mbⁿ|m,n>=1｝

(1)设文法：G(S)：S->aSb|ab|ε

n=0时，S->ε

S->aSb->aaSbb->aaaSbbb->……->aⁿbⁿ

(2)文法：G(S)：S->ab|aaSb|ε

n=0时，S->ε

S->aaSb->aaaSbb->……->a^mbⁿ

(3)文法：G(S)：S->(ab)|(ab)S|ε

n=0时，S->ε

S->(ab)S->(ab)(ab)S->(ab)(ab)(ab)S->……->(ab)ⁿ

(4)文法：

S->AB

A->aA|a

B->bB|b

或者

S->ACB

A->aA|a

B->bB|b

C->aCb|ab

3.如果if语句的方法：

stmt->if expr then stmt

     | if expr then stmt else stmt

     | other

句子if E1 then if E2 then S1 else S2是否有两棵不同的语法树？说明了什么？

 

 由此可得：句子有两颗不同的语法树，语法具有二义性。