编译原理例题与习题解答.ppt

例题与习题解答第二章 回顾 程序语言的定义 一个程序语言是一个记号系统,它主要由以下方面定义： 语法 语义 语法={词法规则+语法规则} 词法规则：单词符号的形成规则。 单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。 描述工具：正规式和有限自动机理论 语法规则：语法单位的形成规则。 语法单位通常包括：表达式、语句、子程序、过程、函数、程序等; 描述工具：上下文无关文法 标识符与名字 标识符：以字母开头的，由字母数字组成的字符串。 标识符与名字两者有本质区别： 标识符是语法概念 名字有确切的意义和属性 上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT ? VN=? S：文法的开始符号，S?VN P：产生式集合(有限)，每个产生式形式为 P??， P?VN， ? ? (VT ? VN)* 开始符S至少必须在某个产生式的左部出现一次。 文法产生语言 假定G是一个文法，S是它的开始符号。如果S ? ?，则称?是一个句型。仅含终结符号的句型是一个句子。 文法G所产生的句子的全体是一个语言，将它记为L(G) L(G) =｛ ? | S ? ? ? ∈VT*｝ 文法和语言的二义性 定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。 语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。 可能存在G和G’，一个为二义的，一个为无二义的。但L(G)=L(G’) 例题2.1：有一个文法 G=({S,A,B},{a,b},P,S),其中P: S ? aB|bA A ?a|aS|bAA B ?b|bS|aBB 采用最左推导产生句子aabbab 并画出相应的语法树。 S ?aB?aaBB? aabSB ?aabbAB?aabbaB ?aabbab 例题2.2 试构造生成语言L={anbnci|n?1, i ?0}的文法 分析：要求a和b的个数一样多，并至少为一个，而c的个数为0个以上即可，所以可以用一个终结符去生成anbn串，用另一个非终结符去生成ci 。 G(Z): Z?AB A ?aAb|ab B ?cB|? 例题2.3 请证实文法G(E): E ? EiT | T T ? T+F | iF | F F ? E* | ( 是一个二义文法。 注意：1)步骤，?和 ?的区别；2) ?不能写为→ 解：0127的最左推导：N?ND?NDD?NDDD?DDDD ?0DDD?01DD?012D?0127 0127的最右推导：N?ND?N7?ND7?N27?ND27 ?N127?D127?0127 8. 令文法为 E → T|E+T|E-T T → F|T*F|T/F F → (E)|i 8. 令文法为 E → T|E+T|E-T T → F|T*F|T/F F → (E)|i 10. 把下面文法改写成无二义性的文法 S-SS | (S) | ( ) 解答： S- TS | T T-(S) | ( ) 例题与习题解答第三章 1. 假定NFA M=S, ?, ?, S0, F，我们对M的状态转换图进行以下改造： 1) 引进新的初态结点X和终态结点Y，X,Y?S， 从X到S0中任意状态结点连一条?箭弧， 从F中任意状态结点连一条?箭弧到Y。 2) 对M的状态转换图进一步施行替换，其中k是新引入的状态。 确定有限自动机的确定化 ——采用子集法 设a是?中的一个字符，定义 Ia= ?-closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。 对一个DFA M最少化的基本思想: 把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。 具体做法: 对M的状态集进行划分 首先，把S划分为终态和非终态两个子集，形成基本划分?。 假定到某个时候，?已含m个子集，记为?={I(1)，I(2)，?，I(m)}，检查?中的每个子集看是否能进一步