英文含义资料

1、英文含义：机器语言：Machine language 汇编语言：Assembly language高级语言：High-level language 源语言：Source language目标语言：Target language 翻译程序：Translator编译程序：Compiler 交叉编译程序：Cross compiler预处理程序：Preprocessor 解释程序：Interpreter中间代码：Intermediate code 词法分析器：scanner语法分析器：Parser 前端：Front end后端：back end 遍：pase文法：Grammar 正规文法：Regula

2、r grammar正则式：Regular expression 有穷自动机：Finite automata术语解释：推导: 连续使用产生式右部去替换左部某个非终结符的过程,得到的连续序列称为一个推导。直接推导：又称一步推导(用 符号=>表示),就是用某条规则的右部去替换该规则的左部最左推导：如果整个推导中，每一步都是替换句型中最左边的非终结符。最右推导：在推导的每一步都替换最右边的非终结符。规范推导：又称最右推导句型：设(s)是一文法，如果符号串x是从开始符号推导出来的，即有s=>x,则称x是文法G(s)的一个句型。句子：若x仅由终结符号组成，则称x为G(S)的句子。语言：一个文法

3、G可以推导出的所有句子构成的一个集合, 就确定了一个语言。非确定有限自动机：（NFA）M是一个五元组：M=（S，s0，F）。确定有限自动机：一个确定的有穷自动机（DFA）M是一个五元组：M=（S，s0，F）。 LL(1)分析：文法不含左递归，对文法中的任一个非终结符A的各个候选式的首终结符集两两不相交，对文法中的每个非终结符A,若它的某个首终结符集含有短语：如果有S=>xAy, 且有A=>,则是句型xy相对于非终结符A的短语直接短语：如果有S=>xAy, 且有A->,则是句型xy相对于A->的直接短语句柄：位于一个句型最左边的直接短语称为句柄.素短语：是一个短语，

4、至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。算符优先文法：根据优先性“低于”来识别句柄的头，根据优先性“高于”来识别句柄的尾。各种优先关系已经存于优先关系表中。LR（0）项目：是在G的某个产生式右部的某个位置添加一个圆点。归约项目：后继符号为空：即圆点在最右边A®· 接受项目：归约项目的左边是文法开始符号S®·移进项目：后继符号为终结符： A®· a待约项目：后继符号为非终结符：A®· B1.编译工程划分为词法分析，语法分析，语义分析与中间代码生成，代码优化，目标代码生成。同时还伴有表格管理和错误

5、处理。2LL(1)分析中，第一个L的含义是从左到右的扫描，第二个L的含义是分析过程采用最左推导，1的含义是需要向右查看一个符号便可决定如何推导。3.LR（0）分析中“L”的含义是从左到右的扫描，“R”的含义是分析过程采用最右推导的逆过程最右规约，0的含义是向后查看0个符号决定分析动作。1.考虑文法GS:S®aSbS|bSaS|(1) 句子abab有如下两个不同的最左推导：S => aSbS => abS =>abaSbS => ababS => abab    S => aSbS => abSaSbS => abaS

6、bS => ababS => abab    所以此文法是二义性的。(2) 句子abab的两个相应的最右推导：    S => aSbS => aSbaSbS => aSbaSb => aSbab => abab    S => aSbS => aSb => abSaSb => abSab => abab(3) 句子abab的两棵分析树： (a)(b)(4) 此文法产生的语言是：在a，b上由相同个数的a和b组成的字符串。2. 求正规式(a|b)*a(a|b)的NF

7、A、DFA 求出NFA M:确定化，得到DFA M:化简: 在第步中求出的DFA M中没有等价状态，因此它就是最小化的DFA M。3.有一台自动售货机，接受1元和5角的硬币。其中a代表1元硬币，b代表5角硬币4.设计一个状态数量少的DFA，其输入字母表是0,1，它能接受以00或01结尾的所有序列，并给出相应的正规文法。解答：正规式为：(0|1)*(00|01) 化简：(0|1)*0(0|1)不确定的有穷自动机为：确定化，并最小化得到：正规文法为：S1S | 0AA0B | 0 | 1C | 1B0B | 0 | 1C | 1C1S | 0A 5.求下列文法GE中各个非终结符符号和各个

8、候选式的Frist集，Follow集，预测分析表，对输入串i+i*i # 进行分析。 ETE' E+TE'| TFT' T'*FT '| F(E)|i解：First(F) = ( ，i First(T') = *， First(E) = +， First(T) = First(F) = ( ，i First(E) = First(T) = ( ，i follow(E) =#，) follow(E') = follow(E) = #，) follow(T) = (first(E')-) follow(E') =#,),+ f

9、ollow(T') =follow(T) =#，)，+ follow(F) =(first(T')-)follow(T) =*,#,),+ i+*()#E®TE'  ®TE'  E' ®+TE'  ® ee®T®FT'  ®FT '  T' ® e®*FT ' ® ee®

10、;F®i  ®(E)  6已知文法GS,其产生式如下：S® (L)|a L®-L,S|S解答：消除所给文法的左递归，得G'：        S(L)|a         LSL'        L',SL' |e 实现预测分析器的不含递归调用的一种

11、有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法G'有：First(S) = ( , a )Follow(S) = ) , , , #First(L) = ( , a )Follow(L) = ) First(L') = ,Follow(L') = ) 按以上结果，构造预测分析表M如下：文法G'是LL(1)的，因为它的LL(1)分析表不含多重定义入口。预测分析器对输入符号串(a,(a,a)做出的分析动作如下：步骤栈剩余输入串输出1#S(a,(a,a)#2#)L(a,(a,a)#S (L)3#)La,(a,a)#4#)L'Sa,(

12、a,a)#L SL'5#)L'aa,(a,a)#S a6#)L',(a,a)#7#)L'S,(a,a)#L' ,SL'8#)L'S(a,a)#9#)L')L(a,a)#S (L)10#)L')La,a)#11#)L')L'Sa,a)#L SL'12#)L')L'aa,a)#S a13#)L')L',a)#14#)L')L'S,a)#L' ,SL'15#)L')L'Sa)#16#)L')L'aa)#S a1

13、7#)L')L')#18#)L')#L'e19#)L')#20#)#L'e21#7对下面的文法G:ETE'E'+E|eTFT'T'T|eFPF'F'*F'|eP(E)|a|b| 解答：(1) 求First和Follow集 First(E)=First(T)=(,a,b, First(E')=+, e First(T)=First(F)=(,a,b, First(T')=(,a,b, , e First(F)=First(P)=(,a,b, First(F')=*，e

14、First(P)=(,a,b, （计算顺序）Follow(E)= #, ) Follow(E')= Follow(E)=#，) (1)（使用的产生式）Follow(T) = First(E')eFollow(T') (1,2) = +),#=+,),#Follow(T')= Follow(T)=+,# (3)Follow(F)= First(T')eFollow(T) (3,4) = (,a,b,+ ,),#Follow(F')= Follow(F) (5) = (,a,b,+ ,),#Follow(P)= First(F')eFollo

15、w(F) (5,6) =*,(,a,b,+ ,),# (2) 证明: a. 文法不含左递归；b. 每个非终结符的各个侯选式的First集不相交；c. First(E')Follow(E')=+, e#,),=FFirst(T')Follow(T')=(,a,b, e+,)=FFirst(F')Follow(F')=*, e,a,( ,+,#= F改造后的文法满足LL(1)文法的三个条件，是LL(1)文法。(3) 预测分析表如下所示。ab*+()#EETE'ETE'ETE'E'E'+EE'eE'

16、;eTTFT'TFT'TFT'TFT'T'T'TT'TT'TT'TT'eT'eFFPF'FPF'FPF'FPF'F'F'eF'eF'*F'F'eF'eF'eF'eF'ePPaPbPP(E)8.已知文法GE:ET|E+TTF|T*FE(E)|i解答： 最右推导：E=>T=>F=>(E)=>(ET)=>(EF)=>(Ei)=> (Ti)=>(T*Fi)语

17、法树：图4.1 句型(T*Fi)的语法树 短语：(T*Fi)，T*Fi，T*F，i 素短语：T*F，i最左素短语：T*F 由于E =>E+T =>E+T*F，故E+T*F为该文法的句型 短语：T*F、E+T*F 直接短语： T*F 句柄： T*F9求给出下列GE的算符优先关系表。表达式i+i*i的算符优先过程EE+T | TTT*F | FFPF|PF(E) | i解: (1)求firstVT和lastVT集firstVT(E')=#firstVT(E)=+,*, ( , i )firstVT(T)=*, ( , i )firstVT(F)=, ( , i )firstVT

18、(P)= ( , i )lastVT(E)=#lastVT(E)=+,*, ) , i lastVT(T)=*, ) , i lastVT(F)= ) , i lastVT(P)= i , ) (2) 求=关系 ><关系略E' #E# # = #P(E) ( = )(3)算符优先表10 给定文法GS，其产生式如下：S(T)|a TT,S|S解答：最左推导：S=> (T) => (T,S) => (S,S) => (a,S) => (a,(T) => (a,(T,S) => (a,(S,S) => (a,(a,S) =>

19、(a,(a,a)最右推导：S=> (T) => (T,S) => (T,(T) => (T,(T,S) => (T,(T,a) => (T,(T,a) => (T,(a,a) => (S,(a,a) => (a,(a,a)文法中S和T的FirstVT和LastVT集为：FirstVT(S)=a,( FirstVT(T)=,a, ( lastVT(S)=a, ） lastVT(T)=,a,)  文法GS的算符优先关系表： 根据优先关系表，对每个终结符或#建立符号f与g，把f(和g)分成一组。根据GS的算符优先关系表，画出如

20、下的有向图。优先函数如下：用算符优先分析法分析句子(a,(a,a)是否是文法的一个句子。11.设文法G为：SA ABA| e BaB|b解答：(1) 构造其拓广文法G'的产生式为 0S' S1S A2A BA3A e4B aB5B b构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0 = S'·S, #, S·A, #, A·BA, #, A·, #,         B·aB, a/b/#, B·b, a/b/# I1 = S'