1、觊皱筠桡Chomsky把文法分为几种类型？什么是文法的二义性？1）分成四种类型，即0型、1型、2型和3型。（1）0型文法：设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而 β∈(VN∪VT)*，则G是一个0型文法。（2）1型文法：若P中的每一个产生式α→β均满足|β|>=|α|，仅仅S->ε除外，则文法G是1型。（3）若P中的每一个产生式α→β满足：α是非终结符，β∈(VN∪VT)*，则此文法称为2型的。（4）若P中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a∈VT*，则G是3型文法。2）如果文法G中的某个句子存在不只一棵语法树，则称该句子是二义性的。如果文法含有二义性的句子，则称该文法是二义性的
2、简啄醴荇侧述DFA与NFA的区别(1)DFA对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应吹涡皋陕用广泛，当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。(2)只有NFA才支持lazy和backreference等特性；(3)NFA急于邀功请赏，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；DFA则是“最长的左子正则式优先匹配成功”。(4)NFA缺省采用greedy量词（见item 4）；(5)NFA可能会陷入递归调用的陷阱而表现得性能极差。两种引擎的工作方式完全不同，一个(NFA)以表达式为主导，一个(DFA)以文本为主导！一般而论，DFA引擎则搜索更快一些！但是NFA以表达式为主导，反而更容易操纵，因此一般程序员更偏爱NFA引擎
3、什么是算符文法？并举例说明设有文法G，如果G中没有形如A->…BC…的产生式，其中B,C为非终结符，则称G为算符文法。例如：对于表达式的二义性文法E->E|E-E|E*E|E/E|E↑E|(E)|i其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法为算符文法。
4、什么是3型文法？什么是文法的语言？（1）若P中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a∈VT*，则G是3型文法。（2）文法的语言：文法是用于描述语言的语法结构的形式规则。文法描述的语言是该文法一切句子的集合。一个文法所描述的语言是唯一的。
5、什么是文法的二义性？给出一个二义性文法实例（1）如果文法G中的某个句子存在不只一棵语法树，则称该句子是二义性的。如果文法含有二义性的句子，则称该文法是二义性的书上：若一个文法中存在某个句子，有两个不同的最左（最右）推导，则该文法是二义的。（2）文法G=（{E},{+, * , i , (,) }, P, E），其中P为：E->i ; E->E+E ; E->E*E ; E->(E) ;这里的非终结符E表示一类算术表达式，i表示程序设计语言中的变量。该文法定义了由变量，+，*，（和）组成的算术表达式的语法结构。
6、常见的代码优化技术有哪些？依据优化所涉及的范围分为那些级别？删除多余运算、代码外提、强度削弱、变换控制条件、合并已知量和复写传播、删除无用赋值。局部优化、循环优化、全局优化
