精华内容
下载资源
问答
  • Chomsky文法类型的判断
  • Chomsky papers

    2010-05-26 12:13:32
    Chomsky 近年来在生物语言学方面的理论文章,非常有价值
  • chomsky文法分类

    千次阅读 2018-10-30 13:01:44
    chomsky文法分类0123型 乔姆斯基把文法法分成四种类型,即0型、1型、2型和3型。这几种文法类型的概念一定要掌握,是一个非常重要的考点 0型文法 设G=(VN,VT,P,S)G=(V_N,V_T,P,S)G=(VN​,VT​,P,S),如果它的每个产生...

    chomsky文法分类0123型

    乔姆斯基把文法法分成四种类型,即0型、1型、2型和3型。这几种文法类型的概念一定要掌握,是一个非常重要的考点

    0型文法

    G=(VN,VT,P,S)G=(V_N,V_T,P,S),如果它的每个产生式α→β是这样一种结构:α∈(VNV_NVTV_T)*且至少含有一个非终结符,而 β∈(VNV_NVTV_T)*则G是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是:0型文法的能力相当于图灵机(Turing)。或者说,任 何0型文语言都是递归可枚举的,反之,递归可枚举集必定是一个0型语言。0型文法是这几类文法中,限制最少的一个,所以我们在试题中见到的,至少是0型文法

    1型文法

    1型文法也叫上下文有关文法,此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。

    注意:虽然要求|β|>=|α|,但有一特例:α→ε也满足1型文法

    如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a,则不符合1型文法

    2型文法

    2型文法也叫上下文无关文法,它对应于下推自动机。2型文法是在1型文法的基础上,再满足:每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。

    如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求,因为其α=Ab,而Ab不是一个非终结符。

    3型文法

    3型文法也叫正规文法,它对应于有限状态自动机。它是在2型文法的基础上满足:A→α|αB(右线性)或A→α|Bα(左线性)。

    如有:A->a,A->aB,B->a,B->cB,则符合3型文法的要求。但如果推导 为:A->ab,A->aB,B->a,B->cB或推导为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。具体的说,例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定义,如果把后面的ab,改成“一个非终结 符+一个终结符”的形式(即为aB)就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为B->Bc的形式就对了,因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法

    注意:上面例子中的大写字母表示的是非终结符,而小写字母表示的是终结符。

    展开全文
  • chomsky经典论文

    2012-12-11 20:21:48
    经典的chomsky论文。计算语言学必读书籍。
  • On Phases by chomsky

    2014-03-01 01:24:24
    On Phases by chomsky
  • Chomsky文法分类

    千次阅读 2019-01-16 20:24:49
    Chomsky文法分类体系 文章目录Chomsky文法分类体系0型文法(Type-0 Grammar)1型文法(Type-1 Grammar)2型文法(Type-2 Grammar)3型文法(Type-3 Grammar)四种文法之间的关系 0型文法(Type-0 Grammar) α→β \alpha \...

    Chomsky文法分类体系

    0型文法(Type-0 Grammar)

    αβ \alpha \rightarrow{\beta}
    无限制文法/短语结构文法

    αβP\forall \alpha \rightarrow \beta \in Pα\alpha中至少包含1个非终结符。

    0型文法生成的语言称为0型语言

    1型文法(Type-1 Grammar)

    αβ \alpha \rightarrow{\beta}

    上下文有关文法(Context-Sensitive Grammar)
    7

    • αβP,αβ\forall \alpha \rightarrow{\beta} \in P,|\alpha| \le |\beta|
    • 产生式的一般形式:α1Aα2α1βα2(βϵ)\alpha_1 A\alpha_2 \rightarrow{\alpha_1\beta \alpha_2} (\beta \ne \epsilon)
    • 由上下文有关文法(1型文法)G产生的语言L(G),称为1型语言(上下文有关语言)。

    2型文法(Type-2 Grammar)

    αβ \alpha \rightarrow{\beta}

    上下文无关文法(Context-Free Grammar)

    • αβP,aVN\forall \alpha \rightarrow{\beta} \in P, a \in V_N(产生式的左部一定要是非终结符)
    • 产生式的一般形式:AβA \rightarrow{\beta}

    例如:

    1. SLLTS \rightarrow{L | LT}
    2. TLDTLTDT \rightarrow{L | D | TL | TD}
    3. Labc...zL \rightarrow{a|b|c|...|z}
    4. D012..9D \rightarrow{0|1|2|..|9}

    由上下文无关文法生成的语言称为上下文无关语言(2型语言)

    3型文法(Type-3 Grammar)

    3型文法又称正则文法(Regular Grammar):

    • 右线性文法AωBA \rightarrow{\omega B}AωA \rightarrow{\omega}
    • 左线性文法ABωA \rightarrow{B \omega}AωA \rightarrow{\omega}

    左线性文法和右线性文法都称为正则文法。

    由于左部一定是非终结符,所以3型文法满足2型文法

    正则文法能描述程序设计语言的多数单词

    四种文法之间的关系

    • 逐级限制
      • 0型文法:α\alpha中至少包含1个非终结符
      • 1型文法:αβ|\alpha| \le |\beta|
      • 2型文法:αVN\alpha \in V_N
      • 3型文法:AωBA \rightarrow{\omega B}AωA \rightarrow{\omega}(右线性)。ABωA \rightarrow{B \omega}AωA \rightarrow{\omega}(左线性)
    展开全文
  • Chomsky文法类型判断

    2014-06-05 17:55:01
    Chomsky文法类型判断,以及原理和源程序!
  • 在形式语言中通过Chomsky范式“标准化”上下文无关文法,从而构造性地证明了:给定一上下文无关文法G=(V,∑,R,S)和一字符串x,必存在多项式算法确定是否x∈L(G)。本文指出了Harry R Lewis,Christos H ...
  • Chomsky文法分类体系

    2021-05-06 10:32:34
    Chomsky 文法分类体系 四种文法: 0型文法 (Type-0 Grammar) 1型文法 (Type-1 Grammar) 2型文法 (Type-2 Grammar) 3型文法 (Type-3 Grammar) 0型文法,无限制文法,α → β,α中至少包含1个非终结符 1型文法,上...


    参考哈工大课件

    四种文法

    • 0型文法,无限制文法,α → β,α中至少包含1个非终结符
    • 1型文法,上下文有关文法,∀α → β∈P,|α|≤|β|
      产生式的一般形式: α1Aα2 → α1βα2( β≠ε ),不包含空产生式(|β|不能为0)
    • 2型文法,上下文无关文法,∀α → β∈P,α ∈ VN,产生式左部是非终结符
      产生式的一般形式:A→β
    • 3型文法 ,正则文法,A→wB产生式右部至多只有一个非终结符,并且非终结符在同侧
      右线性(Right Linear)文法: A→wB 或 A→w
      左线性(Left Linear) 文法: A→Bw 或 A→w

    四种文法之间的关系

    逐级限制
    0型文法:α中至少包含1个非终结符
    1型文法(CSG) :|α|≤|β|,右部长度不得少于左部
    2型文法(CFG) :α ∈ VN,左部必须为非终结符
    3型文法(RG):A→wB 或 A→w (A→Bw 或A→w)
    逐级包含(不考虑空产生式)
    0型文法集合 ⊇ 1型文法集合(右部不得空) ⊇ 2型文法集合 ⊇ 3型文法集合

    二型文法的分析树

    1. (句型的)短语,分析树中的每一棵子树的边缘
    2. 直接短语,子树只有父子两代结点(高度为2)的边缘
      直接短语一定是某产生式的右部,但产生式的右部不一定是给定句型的直接短语
    3. 句柄:一个句型的最左直接短语(可能不只一片叶子,但是是最左的高度为2的子树边缘)
    4. 二义性文法:如果一个文法可以为某个句子生成多棵分析树,则称这个文法是二义性的
      只要能够对一个文法的句型画出两棵不同的分析树,则证明文法是二义性的。
    展开全文
  • 这是Chomsky,它是《纽约时报》刊头样式的报纸刊头字体。 该字体是根据SIL Open Font License版本1.1发布的。 该字体不是《纽约时报》刊头的确切副本。 相反,它的目的是也适合运行文本,因此我使用了较大的词干。 ...
  • Chomsky文法体系分类

    2017-11-15 12:48:00
    文法是用来定义语言的一个模型,常用的文法体系为Chomsky文法体系。 文法定义 文法G(Grammar)是一个四原组,G=(N,T,P,S),N(Non-terminator)是非终结符集合,T(Terminator)是终结符集合,P(Production)是产生式集合...

    文法是用来定义语言的一个模型,常用的文法体系为Chomsky文法体系。

    文法定义

    文法G(Grammar)是一个四原组,G=(N,T,P,S),N(Non-terminator)是非终结符集合,T(Terminator)是终结符集合,P(Production)是产生式集合,S(Start)是起始符

    其中:

    N 交 T = 空集

    P 是形式为 α -> β 的产生式

       α ∈  (N∪T)*N+(N∪T)*,也就是说α中必须有一个非终结符

       β ∈  (N∪T)* ,也就是说β可以是空串

    S∈N

     

    分类

    1型文法 又称上下文有关文法。生成式形式为 α->β, 且 |α| < |β| 并且不存在 A->ε

    2型文法 又称上下文无关文法。生成式形式为 A->α,即左边必须只有一个非终结符

    3型文法 又称正则文法。

                 生成式 A->wB或A->w,称为右线性文法

                 生成式 A->Bw或A->w,称为左线性文法

    0型文法 对生成式没有任何限制的文法称为0型文法。从0到3都是包含的关系,但是有特例,包含  A->ε 产生式的2,3型文法不属于1型文法。

    四种文法产生的语言分别称为 上下文有关语言,上下文无关语言,正则语言,无限制性语言。

     

    2型语言的表示法

    2型语言是很重要的一种语言,除了用四元组的方法表示,此处再介绍两种表示方法。

    当人们要解释或者讨论程序设计语言本身时,经常又需要一种语言,被讨论的语言叫做对象语言,即某种程序设计语言,讨论对象语言的语言称为元语言,即元语言是描述语言的语言。BNF范式通常被作为讨论某种程序设计语言语法的元语言,而语法图是与BNF范式的描述能力等价的另一种文法表示形式,因其直观性而经常采用。

    (1)巴科斯范式(Backus Normal Form,BNF)

    2型文法生成式左端只有一个非终结符,所以可以把左端相同的生成式合并在一起,右端用|隔开,用::=代替->,所有非终结符用<>括起来,这是Backus为了描述AIGOL语言首次提出并使用的。

    用BNF描述十进制整数的生成语法:

    <无符号整数> ::= <数字>|<数字><无符号整数>

    <数字> ::= 0|1|2|3|4|5|6|7|8|9

    (2)语法图

    语法图有四种基本形式

    (3)推导树

    2型文法还经常用推导树表示

     


    本文转自nxlhero 51CTO博客,原文链接:http://blog.51cto.com/nxlhero/695660,如需转载请自行联系原作者

    展开全文
  • I . 上下文无关语法 设计 示例 II . 上下文无关语法 的歧义性 III . Chomsky 范式 IV . 上下文无关语法 转为 Chomsky 范式 V . 上下文无关语法 转为 Chomsky 范式 示例
  • 编译原理实验一:生成Chomsky文法,zip文件里包含实验报告和源代码两部分。
  • 论文研究-模糊上下文无关文法的Chomsky范式和Greibach范式.pdf, 模糊上下文无关文法的提出和研究成果,极大地丰富了形式语言理论.模糊上下文无关文法的规范化问题是其...
  • 编译原理实验 chomsky文法类型判断

    热门讨论 2011-11-25 10:57:14
    编译实验 输入一组任意的规则,输出相应的Chomsky 文法的类型
  • Chomsky句法理论的最新动向.pdf Chomsky句法理论的最新动向.pdf
  • Chomsky文法类型判断及文法化简 Chomsky文法类型判断及文法化简
  • 这个是编译原理的Chomsky文法的判断,没有采用手动输入,只是将终结符和非终结符固定在代码中了,使用者可以根据使用,适当改变,不难的.
  • Java版编译原理Chomsky文法判断Java版

    千次阅读 2017-03-24 17:59:06
    输出:相应的Chomsky 文法的类型 import java.util.Scanner; public class Chomsky { /** * @param args */ public static void main(String[] args) { int n; Scanner scanner = new Scanner(Sys
  •   在这一部分中,我们介绍完全句法分析的基础——Chomsky形式文法。   句法分析的任务是确定句子的句法结构或句子中词汇之间的依存关系,主要包括三种:完全句法分析、局部句法分析、依存关系分析。   其中,...
  • 冯志伟先生:“《语言描写的三个模型》是Chomsky 的早期著作,后来Chomsky 在1957 年发表的《句法结构》实际上是这篇文章的通俗解释。”
  • SPIR-V 研究:编译器基本原理(三) - Chomsky文法分类标签(空格分隔): SPIR-V Vulkan Grammar上一篇说过语法分为四类;这一篇来介绍Chomsky Hierarchy。首先,我们简单看看type-0和type-1的语法。Type-0 - ...
  •  而chomsky的文法定义则是很好的工具。  从形式上文法是一个四元式(VN,VT,P,S)  VN为非终结符的集合 如:动词  VT为终结符的集合 如:动词->eat(eat不可分解,则为终结符)  P文法规则的集合  ...
  • Chomsky hierarchy

    2010-01-12 20:40:00
     Chomsky hierarchy   The Chomsky hierarchy consists of the following levels:   Type-3 grammars ( regular grammars ) generate the  regular languages . Such a grammar restricts its ...
  • Chomsky_hierarchy

    2014-10-20 18:34:00
    Grammar Languages Automaton Production rules (constraints) Type-0 Recursively enumerable Turing machine   (no restrictions) ...http://en.wikipedia.org/wiki/Chomsky_hierarchy

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 190
精华内容 76
关键字:

chomsky