《编译原理》练习题
发布时间：2023-02-25 15:00:46 来源：文档文库
小
中
大
字号：
《编译原理》练习题一
一、填空题（每空1分）
1．设G［S］是一个文法，我们把能由文法的 （1） 推导出来的符号串α称为G的一个句型。当句型α仅由 （2） 组成时 (即α∈VT，则将它称为G产生的句子。
2．从某一给定的状态q出发，仅经过若干条 (3 的矢线所能达到的状态所组成的集合称为ε-CLOSURE(q。
3．设G=(VN,VT,P,S是一文法，我们说G中的一个符号X∈VN∪VT是有用的，是指X至少出现在 （4） 的推导过程中，否则，就说X是无用的。我们将不含形如A→A的产生式和不含无用符号及无用产生式的文法称为 （5） 。
4．我们常采用形如 (class, value的二元式作为一个单词的 (6 。其中,class是一个整数，用来指示该单词的 (7 ，value则是单词之值。
;*
5．一个文法G[S]可表示成形如 （8） 的四元式。其中VN,VT,P均为非空的有限集，分别称为非终结符号集、终结符号集和产生式集， S∈VN为文法的开始符号。此外，将出现在各产生式左部和右部的一切符号所组成的集合称为 （9） ，记作V。显然，V=VN∪VT,VN∩VT=。
6．通常，可通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义，用 (10 构造词法分析程序；另外一种途径是所谓词法分析程序的 (11 。
7．设G为一文法，A→α是G的一个产生式，如果α具有υAδ的形式，其中υ，δ不同时为ε，则称产生式A→α是 （12） 。若存在推导A称产生式A→α是 （13） 。
8．设M=(K,Σ,f,S0,Z为一DFA，并设s和t是M的两个不同状态，我们说状态s,t为某一输入串w (14 ，是指从s,t中之一出发，当扫视完w之后到达M的终态，但从其中的另一个状态出发，当扫视完同一个w后而进入 (15 。
9．把最右推导称为 （16） ，而把右句型称为 （17） 。
A*，则
10．如果从状态转换图的初态出发，分别沿着一切可能的路径到达 (18 ，并将每条路径各矢线上的 (19 