编译器设计中的乔姆斯基层次结构是什么？

  • Z时代
  • 2024-01-10
  • 分类：综合

乔姆斯基层次结构是各种形式语法的集合。通过使用这种形式语法，它可以生成一些形式语言。它们可以由可以识别这些语言的多种类型的设备定义，例如分别为有限状态自动机、下推自动机、线性有界自动机和图灵机。

乔姆斯基提出了四种不同类别的短语结构语法如下 -

  • Type-0 Grammar (Unrestricted Grammar) - Type-0 语法的构造对替换规则没有限制。非终结符必须出现在左侧的字符串中。生成的语言称为递归可枚举语言。

    因此，类型 0 文法是

    • 终端符号的字母∑。

    • 包含开始符号的非终结符的字母 ∀。$\sum\cup V,'α'$至少包含一个非终结符，对'β'没有限制。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 语法或上下文敏感语法 -

    • 每个α→β形式的产生式，α的长度小于或等于β的长度，即没有空产生式，右边是空串∈的产生式。

    • 形式为α 1 Aα 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-2 Grammar (Context Free Grammar) − 如果产生式为 A→α 形式，则称该文法为上下文无关文法/2 型文法，其中 A 是非终结符，α 是感伤形式即，α∈(V∪T)∗ie，α可以是∈。产生式的左侧必须只包含一个非终结符。

下推自动机可以识别类型 2 语法。令文法G(V,T,P,S)=({S},{a,b},P,S) 并且其中 P 由 S→aSa|bSb|a|b 组成是上下文无关文法的一个例子。

  • Type-3 Grammar (Regular Grammar) − 如果产生式为 A→a 或 A→aB 形式，即每个产生式的左侧应仅包含一个非终结符，则称该文法为 type-3 文法或右侧的第一个符号必须是终结符，并且可以跟一个非终结符。

这种文法生成的语言被有限状态机识别。这些正则语言也可以用更简单的表达式来表示，称为正则表达式。

以上是 编译器设计中的乔姆斯基层次结构是什么？ 的全部内容， 来源链接： utcz.com/z/343674.html

回到顶部