编译器设计中的乔姆斯基层次结构是什么？
乔姆斯基层次结构是各种形式语法的集合。通过使用这种形式语法，它可以生成一些形式语言。它们可以由可以识别这些语言的多种类型的设备定义，例如分别为有限状态自动机、下推自动机、线性有界自动机和图灵机。
乔姆斯基提出了四种不同类别的短语结构语法如下-
Type-0Grammar(UnrestrictedGrammar)-Type-0语法的构造对替换规则没有限制。非终结符必须出现在左侧的字符串中。生成的语言称为递归可枚举语言。
因此，类型0文法是
终端符号的字母∑。
包含开始符号的非终结符的字母∀。$\sum\cupV,'α'$至少包含一个非终结符，对'β'没有限制。0型文法由图灵机识别。让我们考虑一个例子，语法G可以表示如下-
G=(V,T,P,S)
V=set of non−terminals={A,B,C}
T=set of terminals={a}
S=start symbol={A}和生产P如下-
A→AB
AB→BC
乙→α
类型1语法（上下文敏感语法）-如果符合以下条件，则称语法为类型1语法或上下文敏感语法-
每个α→β形式的产生式，α的长度小于或等于β的长度，即没有空产生式，右边是空串∈的产生式。
形式为α1Aα2→α1βα2的每个产生式，其中$β≠∈$。可以构造图灵机来识别由上下文敏感语法(CSG)生成的上下文敏感语言。令文法G(V,T,P,S)是上下文敏感语言的一个例子，其中
V={A,B,C}
T={a,b}
S={A}
和生产由
A→AB
AB→BC
C→ab
Type-2Grammar(ContextFreeGrammar)−如果产生式为A→α形式，则称该文法为上下文无关文法/2型文法，其中A是非终结符，α是感伤形式即，α∈(V∪T)∗ie，α可以是∈。产生式的左侧必须只包含一个非终结符。
下推自动机可以识别类型2语法。令文法G(V,T,P,S)=({S},{a,b},P,S)并且其中P由S→aSa|bSb|a|b组成是上下文无关文法的一个例子。
Type-3Grammar(RegularGrammar)−如果产生式为A→a或A→aB形式，即每个产生式的左侧应仅包含一个非终结符，则称该文法为type-3文法或右侧的第一个符号必须是终结符，并且可以跟一个非终结符。
这种文法生成的语言被有限状态机识别。这些正则语言也可以用更简单的表达式来表示，称为正则表达式。