给定文法G[S]：下图分别是输入串（a，（a))的语法分析树和对应的带标注语法树，但其属性值没有标出，

1. 文法G＝({A,B,S},{a,b,c},P,S), 其中P 为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 2. 文法G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？ 3. 考虑下面上下文无关文法： S→SS*|SS+|a (1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。 (2)G[S]的语言是什么？ 4. 给出生成下述语言的二型文法： (1) {anbn | n >=0 } (2) { ambn | m≥n ≥0 } (3) {uawb | u,w ∈{a,b}*∧|u|=|w| } (4) { anbm | n≥2m ≥0 } (5) { anbm | n ≥ 0, m ≥ 0,3n≥m≥2n } (6) {wwR|w∈{a,b}*，wR 表示w的逆} (7) {uvwvR|u,v,w∈{a,b}+=1 } 5. 给出生成下述语言的三型文法： (1) {an | n >=0 } (2) { anbm | n,m>=1 } (3) {anbmck | n,m,k>=0 }

设有文法G(S)：S→SS*｜SS＋｜a (1)G(S)的语言L(G(S))是什么? (2)下列字符串哪些是该文法的句子? $1：aa＋aa*＋a $2：aa＋aaa*＋＋ $3：aS＋a* (3)对属于该文法的句子$i，画出其分析树。

考虑下面上下文无关文法： S→SS*|SS＋|a 为串aa＋a*构造语法树。  

设文法G(S)的BNF描述为 S→S，E｜E E→E＋T｜T T→T*F｜F F→a｜(E)｜a[S] (1)给出G(S)的元语言符号集、文法符号集、终结符号集和非终结符号集。 (2)G(S)属于哪类文法?写出L(G(S))集合。 (3)判断符号串 $1：a，a＋a[a[S]] $2：a*a，a＋a[a] 是否为文法G(S)的句子，对是L(G(S))的句子给出对应的分析树。

A.短语

B.句型

C.句柄

D.素短语

设有下列文法： S→S，E｜E E→E＋T｜T T→T*F｜F F→a｜(E)｜a[S] (1)指出下列字符串哪些是该文法的句子： $1：a＋a[aa＋[a]] $2：a*a，a＋a[a] $3：a，a＋a[a[S]] (2)对属于该文法的句子$i画出自上而下分析树。

下面是一个符合短语结构语法定义的受限英语子集的语法： P：S→NP VP (a) NP→the NPl (b) NP→NP1 (c) NP1→ADJS N (d) ADJS→￠｜ADJ ADJS (e) VP→V (f) VP→V NP (g) N→boy｜Johnson｜blackball (h) ADJ→little｜dig (i) V→play｜run (j) 其中，大写的是非终结符，而小写的是终结符，￠表示空字符串。请依据该语法对句子 the boy plays the blackball 进行自顶向下的句法分析，并建立相应的句法分析树。

σ),其中,P₂:σ→λ,σ→σcσ,σ→c。

a)描述L(G)(i=1,2)。

b)对每一语言,给出一个长度为5的终结符串的派生,并构造派生树。

给定输入文件：101，48，19，65，3，74，33，17，2l，20，99，53，21，并设记录缓冲区个数k=-4，写出基于败者树的外排序顺串生成算法runs输出的顺串。【东南大学1996一、6(6分)】

已知4个字符A，E C，D的哈夫曼编码分别是1，01，000,001。下列01串是由以上4个字母构 成的一段文本的哈夫曼编码： 1001000011011010011010011 请将上述01串还原为编码前的文本。以字符在文本中出现的次数为权值，求出这棵树 的带权路径长度。【电子科技大学2013三、1(5分)】