精华内容
下载资源
问答
  • 形式文法和形式语言

    2011-09-09 15:15:00
    形式文法和形式语言 摘自维基百科 http://en.wikipedia.org/wiki/ 【形式文法】 在计算机科学中,形式语言是:某个字母表上,一些有限长字串的集合,而形式文法是描述这个集合的一...

    形式文法和形式语言

    摘自维基百科 http://en.wikipedia.org/wiki/


    【形式文法】

    计算机科学中,形式语言是:某个字母表上,一些有限长字串的集合,而形式文法是描述这个集合的一种方法。形式文法之所以这样命名,是因为它与人类自然语言中的文法相似的缘故。

    形式文法描述形式语言的基本想法是,从一个特殊的初始符合出发,不断的应用一些产生式规则,从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。

    一个形式文法 G 是下述元素构成的一个四元组(N, Σ, P, S):

    • 非终结符号”集合 N
    • 终结符号”集合 Σ ,Σ 与 N 无交。
    • 取如下形式的一组“产生式规则P
    (Σ ∪ N)*中的字符串 → (Σ ∪ N)* 中的字符串,并且产生式左侧的字符串中必须至少包括一个非终结符号。
    • 起始符号SS 属于 N

    一个由形式文法 G = (N, Σ, P, S) 产生的语言是所有如下形式的字符串集合,这些字符串全部由“终结符号”集 Σ 中符号构成,并且可以从“初始符号”S 出发,不断应用 P 中的“产生式规则”而得到。

    考虑如下的文法 G ,其中 N = {S, B}, Σ = {a, b, c}, P 包含下述规则

    1. S -> aBSc
    2. S -> abc
    3. Ba -> aB
    4. Bb -> bb

    非终结符号 S 作为初始符号。下面给出字串推导的例子:(推导使用的产生规则用括号标出,替换的字串用黑体标出)

    • S -> (2) abc
    • S -> (1) aBSc -> (2) aBabcc -> (3) aaBbcc -> (4) aabbcc
    • S -> (1) aBSc -> (1) aBaBScc -> (2) aBaBabccc -> (3) aaBBabccc -> (3) aaBaBbccc -> (3) aaaBBbccc -> (4) aaaBbbccc -> (4) aaabbbccc

    很清楚这个文法定义了语言 { anbncn | n > 0 } ,这里 an 表示含有 n 个 a 的字串。

    形式文法与 Lindenmayer 系统(L-系统)类似, 但有几点不同:L-系统不区分终结符号非终结符号;L-系统限制规则的应用顺序;L-系统能不停地运行,产生一个无限长的字串列。通常情况下,每一个字符串同空间中的一个点集联系起来,而L-系统的输出就是这个点集列的极限。L-系统可以用于模拟细胞的生长,所以又被称为发展系统


    【乔姆斯基体系】

    乔姆斯基体系是刻画形式文法表达能力的一个分类谱系,是由诺姆·乔姆斯基1956年提出的。它包括四个层次:

    • 0-型文法(无限制文法或短语结构文法)包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串,这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别,后者是前者的一个真子集,是能够被一个总停机的图灵机判定的语言。
    • 1-型文法(上下文相关文法)生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号,而 α, β 和 γ 是包含非终结符号与终结符号的字串;α, β 可以是空串,但 γ 必须不能是空串;这种文法也可以包含规则 S->ε ,但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
    • 2-型文法生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号,γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
    • 3-型文法(正规文法)生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号;如果所有产生式的右侧都不含初始符号 S ,规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受,也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。

    正规语言类包含于上下文无关语言类,上下文无关语言类包含于上下文相关语言类,上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系,也就是说:存在递归可枚举语言不属于上下文相关语言类,存在上下文相关语言不属于上下文无关语言类,存在上下文无关语言不属于正规语言类。

    下表总结了上述四种类型的文法的主要特点:

    文法 语言 自动机 产生式规则
    0-型 递归可枚举语言 图灵机 无限制
    1-型 上下文相关语言 线性有界非确定图灵机 αAβ -> αγβ
    2-型 上下文无关语言 非确定下推自动机 A -> γ
    3-型 正规语言 有限状态自动机 A -> aB

    A -> a


    这个分类谱系把所有的文法分成四种类型:无限制文法上下文相关文法上下文无关文法正规文法。四类文法对应的语言类分别是递归可枚举语言上下文相关语言上下文无关语言正规语言。这四种文法类型依次拥有越来越严格的产生式规则,同时文法所能表达的语言也越来越少。尽管表达能力比无限制文法和上下文相关文法要弱,但由于能高效率的实现,四类文法中最重要的是上下文无关文法和正规文法。例如对上下文无关语言存在算法可以生成高效率的LL 分析器LR 分析器


    上下文无关文法
    上下文无关文法要求产生式左侧只能包含一个非终结符号。上例定义的语言并不是一个上下文无关语言,但 { anbn | n > 0 }是一个上下文无关语言。具体如下,文法G2 包括 N={S}, Σ={a,b}, S 是起始符号,产生式规则有:

    1. S -> aSb
    2. S -> ab

    正规文法
    正规文法有多种等价的定义,我们可以用左线性文法或者右线性文法来等价地定义正规文法。左线性文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号。右线性文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个终结符号后随一个非终结符号。

    上例定义的语言 { anbn | n > 0 } 不是一个正规语言。下面给出一个正规语言的例子,语言 { anbm | m,n > 0 } 是一个正规语言。文法G3 包括 N={S,A,B}, Σ={a,b}, S 是起始符号,产生式规则有:

    1. S -> aA
    2. A -> aA
    3. A -> bB
    4. B -> bB
    5. B -> ε

    【形式语言】

    数学逻辑计算机科学中,形式语言是用精确的数学或机器可处理的公式定义的语言。

    语言学中语言一样,形式语言一般有两个方面: 语法语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论,它只研究语言的语法而不致力于它的语义。在形式语言理论中,形式语言是一个字母表上的某些有限长字符串集合。一个形式语言可以包含无限多个字符串。

    语言的形式定义

    字母表 Σ 为任意有限集合,ε 表示空串, 记 Σ0 为{ε},全体长度为 n 的字串为 Σn , Σ* 为 Σ0∪Σ1∪…∪Σn∪…, 语言 L 定义为 Σ* 的任意子集。

    注记:Σ*空子集 ∅ 与 {ε} 是两个不同的语言。


    语言间的运算

    语言间的运算就是 Σ*幂集上的运算。

    • 字符串集合的等运算。
    • 连接运算:L1L2 = { xy | x 属于L1并且 y 属于L2 }。
    • 幂运算:Ln = L … L (共 n 个 L 连接在一起),L0 = {ε}。
    • 闭包运算:L* = L0∪L1∪…∪Ln∪…。
    • 右商运算:L1/L2 = {x | 存在 y 属于L2使得 xy 属于L1}。
    • S ⊆ Σ* 是一个语言,S 的补语言定义为集合 {ω | ω ∈ Σ* 且 ω ∉ S}

    语言的表示方法

    一个形式语言可以通过多种方法来限定自身,比如:


    展开全文
  • 形式文法和形式语言 本章主要阐述了一些基本的概念,为后续部分的编译进行了基础的准备: 符号 符号串及其运算(闭包运算,关注星闭包和正闭包) 推导和规约 文法,句型,句子,语言 语法分析树:句型,短语,直接...

    形式文法和形式语言

    本章主要阐述了一些基本的概念,为后续部分的编译进行了基础的准备:

    • 符号
    • 符号串及其运算(闭包运算,关注星闭包和正闭包)
    • 推导和规约
    • 文法,句型,句子,语言
    • 语法分析树:句型,短语,直接短语,句柄,素短语,最左素短语
    • 二义性
    • 乔姆斯基文法

    2.1 符号串和语言:

    • 人工语言:必须是明确的,不能有歧义。
    • 字母表:符号的有限集合。
    • 符号:可以互相区分的记号或元素。
    • 符号串:字母表上符号的一个有穷序列(特殊:空符号串ℰ)
    • 语言=符号串+运算逻辑

    2.2 符号串运算:

    • 连接
    • 子串
    • 前、后缀
    • 幂:自己连自己
    • 绝对值:符号个数

    2.3 符号串集合运算

    • 并集:在两个集合中存在的串
    • 交集:从两个集合中分别取串连接
    • 幂运算:多次并运算,自己并自己
    • 星闭包Σ*(Kleene):集合不同幂次的并集,就是字母表中所有任意组合的组合,可以空;全集【语言:存在一定的逻辑,规范】,Σ+字符串至少为1,没有空。
    • 空集∅有一个的,空串{ℰ}是有一个的

    2.4 语言描述

    • 有穷:枚举
    • 无穷:找出有穷表示
      (1)生成(文法):利用某种规则生成合法句子
      (2)识别(自动机):将串输入模型,模型进行判别

    2.5 文法

    • 语言是语法产生的所有句子的全体
    • 组成(终结符号集合VT,非终结符号集合VN,开始符号S,产生式规则P)
      (1)终结:句子中可以出现的符号,可以看到(没有特殊说明,在右部的都是终结符号)
      (2)非终结:语法单位(主语,谓语。。),看不到,用于辅助分析
      (3)开始:最大的非终结(可以代表句子)
      (4)P:α→β α至少有一个非终结符号,上下文无关文法α只有一个
    • 从开始符号形成的串开始,对子串,用终结符号替代,直到完成推导过程
      α→β1 α→β2 α→β3 = α→β1|β2|β3

    2.6 推导

    • 右部代替左部
    • 直接推导:A→γ 则 aAb→aγb
    • 推导(0步或多步):在这里插入图片描述
    • 在这里插入图片描述
    • 中间所有的推导过程都称为句型,最后得到的全部都是终结符号的表示称为句子
    • 最左推导和最右推导(规范推导):在哪边加(左句型,右句型)
    • 最左推导:任何一步α => β都是对阿尔法中的最左非终结符进行替换
      左右推导:任何一步α => β都是对阿尔法中的最右非终结符进行替换

    2.7 规约(推导逆过程)

    • 用产生式的左部来代替右部
      -
      可以采用树状图说明

    2.8 语言

    语言是文法产生表达式的集合,一个文法 一个语言

    2.9 分析树

    • 利用树状结构得到推导过程

    在这里插入图片描述

    • 遍历方式不同得到序列不同,但是一棵树只对应一个最左最右推导
    • BD

    在这里插入图片描述

    • 短语:以非终结符号为子树根节点的所有叶节点(终结符号)
      在这里插入图片描述
      在这里插入图片描述
    • 直接短语:包含父子两代的短语(只能有一步)
    • 句柄:直接短语中,最左边的那个
    • 素短语:
      (1)至少含有一个终结符
      (2)除自身外不含更小的带终结符的短语
      在这里插入图片描述

    2.10 二义性

    • 句子二义性:一个文法的句子存在两颗分析树
    • 文法二义性:一个文法中某个句子存在二义性
    • 语言二义性:所有生成该语言的文法都是二义的
    • 判断二义性方法:若产生式集合中,存在某个非终结符号,既存在左递归,又存在右递归
    • 解决:
      (1)改写文法,要求新文法与初始的文法等价
      (2)在使用过程中增加一些限制

    2.11 乔姆斯基文法

    • 0型,短语结构文法(PSG):至少包括一个非终结符号,图灵机
    • 1型,上下文有关文法(CSG):F→α会受到前后a,b的影响(aFb),线性有界自动机
    • 2型,上下文无关文法(CFG):只要有一个即可产生(语法分析),下推自动机
    • 3型,正规文法(RG):正则表达式(词法分析)右部全是终结符号,要么只有一个且位于最做或最右,有限自动机
    展开全文
  • 基于符号形式文法的三维建模是一种新颖的建模方法,该方法从现实世界抽象出模型的文法产生式规则,通过产生式规则的叠加演算,提供一种从基础几何形状迭代生成目标模型的过程。实现产生式规则的模型生成器允许用户采用...
  • 形式文法概述

    千次阅读 2008-02-22 09:37:00
    形式文法在计算机科学中,形式语言是某个字母表上一些有限长字串的集合,而形式文法是描述这个集合的一种方法。形式文法之所以这样命名,是因为它与人类自然语言中的文法相似的缘故。 形式文法描述形式语言的基本...

    形式文法

    在计算机科学中,形式语言是某个字母表上一些有限长字串的集合,而形式文法是描述这个集合的一种方法。形式文法之所以这样命名,是因为它与人类自然语言中的文法相似的缘故。

    形式文法描述形式语言的基本想法是,从一个特殊的初始符合出发,不断的应用一些产生式规则,从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。举例来说,假设字母表只包含 'a' 和 'b' 两个字符,初始符号是 'S' ,我们应用下述规则:

    1. S -> aSb
    2. S -> ba
    于是我们可以通过把 "S" 重写为 "aSb"(规则1),我们还可以继续应用这条规则把 "aSb" 重写为 "aaSbb"。这个重写的过程不断重复,直到结果中只包含字母表中的字母为止。在例子中,我们可以得到 S -> aSb -> aaSbb -> aababb 这样的结果。由文法刻画的语言包含了所有可以这样产生的字串,比如 ba, abab, aababb, aaababbb 等等。


    形式定义
    一个形式文法 G 是下述元素构成的一个元组(N, Σ, P, S):----有些书上也写成(V,T,S,P)

    非终结符号集合 N。
    终结符号集合 Σ ,Σ 与 N 无交。
    取如下形式的一组产生式规则 P,
    (Σ ∪ N)*中的字串 -> (Σ ∪ N)* 中的字串字串,并且产生式左侧的字串中必须至少包括一个非终结符号。
    起始符号 S,S 属于 N。
    一个由形式文法 G = (N, Σ, P, S) 产生的语言是所有如下形式字串的集合,这些字串全部由终结符号集 Σ 中符号构成,并且可以从初始符号 S 出发,不断应用 P 中的产生式规则而得到。


    例子
    考虑如下的文法 G ,其中 N = {S, B}, Σ = {a, b, c}, P 包含下述规则

    1. S -> aBSc
    2. S -> abc
    3. Ba -> aB
    4. Bb -> bb
    非终结符号 S 作为初始符号。下面给出字串推导的例子:(推导使用的产生规则用括号标出,替换的字串用黑体标出)

    S -> (2) abc
    S -> (1) aBSc -> (2) aBabcc -> (3) aaBbcc -> (4) aabbcc
    S -> (1) aBSc -> (1) aBaBScc -> (2) aBaBabccc -> (3) aaBBabccc -> (3) aaBaBbccc -> (3) aaaBBbccc -> (4) aaaBbbccc -> (4) aaabbbccc
    很清楚这个文法定义了语言 { anbncn | n > 0 } ,这里 an 表示含有 n 个 a 的字串。

    形式文法与 Lindenmayer 系统(L-系统)类似, 但有几点不同:L-系统不区分终结符号和非终结符号;L-系统限制规则的应用顺序;L-系统能不停地运行,产生一个无限长的字串行。通常情况下,每一个字串同空间中的一个点集联系起来,而L-系统的输出就是这个点集列的极限。L-系统可以用于模拟细胞的生长,所以又被称为发展系统。

    文法的分类
    某些类型的文法及其产生的语言得到了细致的研究并被单独命名。最常见的文法的分类系统是诺姆·乔姆斯基于1950年发展的乔姆斯基谱系,这个分类谱系把所有的文法分成四种类型:无限制文法、上下文相关文法、上下文无关文法和正规文法。任何语言都可以由无限制文法来表达,馀下的三类文法对应的语言类分别是递归可枚举语言、上下文无关语言和正规语言。这四种文法类型依次拥有越来越严格的产生式规则,同时文法所能表达的语言也越来越少。尽管表达能力比无限制文法和上下文相关文法要弱,但由于能高效率的实现,四类文法中最重要的是上下文无关文法和正规文法。例如对上下文无关语言存在算法可以生成高效率的LL 分析器和LR 分析器。

    上下文无关文法
    上下文无关文法要求产生式左侧只能包含一个非终结符号。上例定义的语言 { anbn | n > 0 } 并不是一个上下文无关语言,但它却可以用一个上下文无关文法来表达。具体如下,文法G2 包括 N=, Σ={a,b}, S 是起始符号,产生式规则有:

    1. S -> aSb
    2. S -> ab


    正规文法
    正规文法有多种等价的定义,我们可以用左线性文法或者右线性文法来等价地定义正规文法。左线性文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个非终结符号後随一个终结符号。右线性文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个终结符号後随一个非终结符号。

    上例定义的语言 { anbn | n > 0 } 不是一个正规语言。下面给出一个正规语言的例子,语言 { anbm | m,n > 0 } 是一个正规语言。文法G3 包括 N={S,A,B}, Σ={a,b}, S 是起始符号,产生式规则有:

    1. S -> aA
    2. A -> aA
    3. A -> bB
    4. B -> bB 

    形式语言理论◇(formal language theory
       
    用数学方法研究自然语言(如英语)和人工语言(如程序设计语言)的产生方式、一般性质和规则的理论。形式语言是模拟这些语言的一类数学语言,它采用数学符号,按照严格的语法规则构成。从广义上说,形式语言是符号取自某个字母表的字符串的集合。
       
    如同自然语言具有语法规则一样,形式语言也是由形式文法生成的。一个形式文法是一个有穷变元集合,这些变元也称为非终结符或语法范畴。每个变元都可以用来定义语言,定义方式可以是递归的,即通过一些称为终结符的原始符号,加上变元自身,递归地加以定义。和变元有关的规则称为生成式,生成式决定了语言是如何构造出来的。一个典型的生成式表示:给定变元所代表的语言包含这样一些字符串,它们是通过连结运算,将另外某些变元语言中的字符串和若干终结符连结起来而得到的。

    形式文法被严格地定义为四元组G=(V,T,P,S),其中V和T分别是变元和终结符的有穷集合,并且V和T分别是变元和终结符的有穷集合,并且V和T没有公共元素,即V∩T=Æ。S是一个特殊变元,称为开始符号。P是生成式的有穷集合,生成式的基本形式是:a→β,这里a和β,这里a和β都是(V∪T)*中的元素,即它们都是由变元和终结符组成的符号串,但要求a至少含有一个非终结符。在形式文法定义中,生成式集合P是至关重要的 。 在对使用符号的惯例作某些约定后,仅仅考查生成式,就能推断出一个文法的变元、终结符和开始符号,故可以友爱过列出生成式来定义一个形式文法。
       
    同形式文法G=(V,T,P,S)产生的形式语言记为L(G)。L(G)中的字符串ω都具有如下特点:①该字符串仅由终结符组成,即ω∈T*;②该字符串能由开始符号S派生出来,即从S出发,通过应用零个或多个P中的生成式,由S可以推导出ω。 


    根据P中生成式a→β的特点,可以将形式文法及其产生的形式语言分类,构成所谓的形式语言谱系。形式语言理论中重点研究四类文法和语言:①0型文法。又称为无限制文法。这种文法对生成式a→β不作特殊限制,a和β可以是任意的文法符号串,当然a不能是空字符串。0型文法是形式语言谱系中最大的文法类。由0型文法产生的形式语言恰是图灵机所识别的语言类,即递归可枚举语言。②1型文法。又称为上下文有关文法。这种文法要求生成式a→β满足|a|≤|β|,即β要至少和a一样长。 由1型文法产生的语言称为1型语言或上下文有关语言。1型语言恰是非确定型线性有界自动机所识别的语言类。③2型文法。又称为上下文无关文法。这种文法要求生成式a→β中的a必须是变元。由2型文法产生的语言称为2型语言或上下文无关语言。2型语言恰是由下推自动机所识别的语言类。④3型文法。又称为正则文法。这种文法分为两种类型:第一类要求生成式的形式必须是A→ωB或A→ω,其中A,B都是变元,ω是终结符串(可以是空串),这种特殊的正则文法称为右线性文法。第二类正则文法称为左线性文法,它要求生成式必须是A→Bω,或A→ω的形式。由正则文法生成的语言称为正则语言,它恰是有穷自动机所识别的语言类。
       
    上述定义的4种语言类具有依次包含关系,即对于i=0,1,2,在不考虑空字符串时,i型语言都真包含i+1型语言 。  

    展开全文
  •   在这一部分中,我们介绍完全句法分析的基础——Chomsky形式文法。   句法分析的任务是确定句子的句法结构或句子中词汇之间的依存关系,主要包括三种:完全句法分析、局部句法分析、依存关系分析。   其中,...

      在上一部分中,我们介绍了NLP领域最基本的问题:词法分析,现阶段解决该问题最常用的方法就是将其转化为序列标注问题,根据解决序列标注问题的方法对其进行解决。
      词的问题解决了,那么下一步,就是句法分析。
      在这一部分中,我们介绍完全句法分析的基础——Chomsky形式文法。

      句法分析的任务是确定句子的句法结构或句子中词汇之间的依存关系,主要包括三种:完全句法分析、局部句法分析、依存关系分析。
      其中,前两种句法分析是对句子的句法结构进行分析(也称为短语结构分析),而后一种是对句子中词汇间的依存关系进行分析,我们在后文中将有所介绍。

    1.完全句法分析

      在完全句法分析任务中,我们手中已经得到了曾进行过词法分析的句子,目的是得到句子的句法结构,通常用短语结构树来表示。
      对词法分析不熟悉的朋友们可以参看博客:NLP入门概览(6) ——词法分析
      也就是说,完全句法分析的任务可以描述如下:
    在这里插入图片描述

      解决该任务的方法依然是我们曾经提到过的三种方法:规则法、概率统计法、深度学习法(多数NLP问题的解决方法都是这三种)。

      那么,在上图中,我们通过一个叫做“层次分析法”的方法将已经进行过词法分析的句子处理为一棵短语结构树。

    2.层次分析法

      那么,什么是层次分析法呢?
      层次分析法就是利用语言学,从句子结构层面对句子进行分析:

    1. 将句子分为主语、谓语、宾语、定语、状语、补语六个成分;
    2. 以词或词组作为划分成分的基本单位;
    3. 根据六个成分的搭配排列按层次顺序确定句子的格局。

      一般来说,以树结构表示结果,我们将其称为句法分析树(也就是上文提到的短语结构树)。
      分析的时候,往往找出主语和谓语作为句子的主干,以其他成分作为枝叶,描述整个句子的结构。

      举个例子:“我弟弟已经准备好了一切用品。”
    在这里插入图片描述

      由此我们可以得到一棵句法分析树:
    在这里插入图片描述

      由此可见,层次分析法枝干分明,便于归纳句型。然而,这种方法会遇到大量的歧义,比如对于“新桌子和椅子”,它会产生如下歧义:
    在这里插入图片描述

      此外,层次分析法还面临着很多困难:
      1.在汉语中,词类跟句法成分之间的关系比较复杂,除了副词只能作状语(一对一)之外,其余的都是一对多,即一种词类可以作多种句法成分:
    在这里插入图片描述

      图中黑线表示词类的主要功能,蓝线表示次要功能,红线表示局部功能。
      2.词存在兼类
      例如:“每次他都会在会上制造新闻。”
      其中第一个“会”是名词,表示会议;而第二个“会”是动词,表示能够。
      3.短语存在多义
      例如:
    在这里插入图片描述

    3.Chomsky形式文法

      在完全句法分析中,Chomsky形式文法是极为重要的理论。

      Chomsky形式语言自诞生之日起至今,历经古典理论、标准理论、扩充式标准理论、管辖约束理论和最简理论五个阶段的发展变化。它在语言学界产生了重大影响,被誉为一场Chomsky式的革命。其影响力波及到语言学之外的心理学、哲学、教育学、逻辑学、翻译理论、通讯技术、计算机科学等领域。

    3.1 Chomsky文法

      Chomsky文法用 G GG 表示形式语法,将其表示为四元组:
    G=(Vn,Vt,S,P)G = (V_n,V_t,S,P)
      其中各变量定义如下:
      VnV_n:非终结符的有限集合,不能处于生成过程的终点,即在实际句子中不出现。在推导中起变量作用,相当于语言中的语法范畴;
      VtV_t:终结符的有限集合,只处于生成过程的终点,是句子中实际出现的符号,相当于单词表。
      SSVnV_n中的初始符号,相当于语法范畴中的句子。
      PP:重写规则,也成为生成规则,一般形式为αβα\rightarrowβ,其中αβα、β都是符号串,αα至少含有一个VnV_n中的符号。

      语法GG 的不含非终结符的句子形式称为GG生成的句子;
      由语法GG生成的语言,记做L(G)L(G),指GG生成的所有句子的集合。

      举个例子:
      假设有一种语言{ab,aab,aaab,aaaab...}\{ab,aab,aaab,aaaab...\},如何用Chomsky形式文法表示?

      从语言句子集合中我们可以看出,只有$ a、b$两种字符出现在句子集中,所以,终结符集合 Vt={a,b}V_t=\{a,b\}
      我们有非终结初始符SS,假设非终结符集合Vn={S,A}V_n=\{S,A\}VnV_n中的元素个数、表示方法可以自己定义),我们可以将上述句子描述为:
    SAb,AaA,AaS\rightarrow Ab, \quad A\rightarrow aA, \quad A\rightarrow a
      也就是重写规则PP
      于是我们有语法:
    G={Vn,Vt,S,P}G=\{V_n,V_t,S,P\}
      其中,
    Vn={S,A}V_n = \{S,A\}

    Vt={a,b}V_t=\{a,b\}

    P:SAb,AaAaP:S\rightarrow Ab, \quad A\rightarrow aA|a
      (| 表示或)
      于是,我们可以用有限的规则生成无限的语句。

      值得注意的是,GG的表示方法可能不唯一,以上例为例,将重写规则$ P$ 改为:
    P:SaA,AaA,AbP:S\rightarrow aA, \quad A\rightarrow aA, \quad A\rightarrow b
      这种语法也可以对该语言进行表示,大家可以自己推推看。

      Chomsky根据重写规则的形式,将形式文法分为4级:
    在这里插入图片描述

      在这里,先加深一下集合的闭包这个概念:
      VV^*表示符号串集合VV的闭包,定义为:V=V0V1V2...V^*=V^0∪V^1∪V^2∪...

      举个例子:假设V={a,b}V=\{a,b\},那么
    V0={ϵ},V1=V,V2={aa,ab,ba,bb},V={ϵ,a,b,aa,ab,ba,bb,aaa,...}V^0=\{\epsilon\},V^1=V,V^2=\{aa,ab,ba,bb\},V^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,...\}

      了解了这个概念之后,我们来介绍各级文法。

    3.2 0型文法(无约束文法)

       0型文法(无约束文法): 重写规则为αβα\rightarrowβ,其中,α,β(VnVt)α,β∈(V_n∪V_t)^*。该文法对规则形式没有任何限制,因此也称为无约束文法或无限制重写文法。

    3.3 1型文法(上下文相关文法)

       1型文法(上下文相关文法): 重写规则为αAβαγβαAβ\rightarrowαγβ,其中,AVn,α,β,γ(VnVt)A∈V_n,\quadα,β,γ∈(V_n∪V_t)^*,且 γγ非空。在上下文α...βα...β中,单个非终结符AA被重写为符号串γγ, 因此是上下文相关的。

      举个例子:
    G={Vn,Vt,S,P}G=\{V_n,V_t,S,P\}Vn={S,A,B,C},Vt={a,b,c} V_n=\{S,A,B,C\},\quad V_t=\{a,b,c\}P:SABC,AaAa,BbBb,BCBccP:S\rightarrow ABC,\quad A\rightarrow aA|a,\quad B\rightarrow bB|b,\quad BC\rightarrow Bcc

      容易判断,该文法属于1型文法,且 L(G)={anbmc2},n,m1L(G) = \{a^nb^mc^2\},\quad n,m\ge1

    3.4 2型文法(上下文无关文法CFG)

       2型文法(上下文无关文法CFG): 重写规则为AαA\rightarrowα,其中,AVn,α(VnVt)A∈V_n,\quadα∈(V_n∪V_t)^*AA重写为 αα时没有上下文限制。
      举个例子:
    G={Vn,Vt,S,P}G=\{V_n,V_t,S,P\}Vn={S,A,B,C},Vt={a,b,c} V_n=\{S,A,B,C\},\quad V_t=\{a,b,c\}P:SABC,AaAa,BbBb,CBAcP:S\rightarrow ABC,\quad A\rightarrow aA|a,\quad B\rightarrow bB|b,\quad C\rightarrow BA|c

      容易判断,该文法属于2型文法,且L(G)={anbmapcq},n,m1,p0,q{0,1}L(G) = \{a^nb^ma^pc^q\},\quad n,m\ge1,\quad p\ge0,\quad q∈\{0,1\},若p=0p=0,则q=1q=1;若p>0p>0,则q=0q=0

    3.5 3型文法(正则文法RG)

       3型文法(正则文法RG): 重写规则为 ABxA\rightarrow BxAxA\rightarrow x,其中,A,BVn,xVtA,B∈V_n,\quad x∈V_tAxA\rightarrow x是将ABxA\rightarrow Bx中的BB看作空符号的一种特殊情况。如果把A,BA,B看作不同的状态,那么由重写规则可知,由状态AA转入状态BB时,可生成一个终结符xx,因此正则文法也称作有限状态文法。
       上述定义的是左线性正则文法,如果AxBA\rightarrow xB,则是右线性正则文法。

       举个例子:
    G={Vn,Vt,S,P}G=\{V_n,V_t,S,P\}

    Vn={S,A,B,C},Vt={a,b}V_n=\{S,A,B,C\},\quad V_t=\{a,b\}

    P:SaA,AaA,AbB,BbC,CbCbP:S\rightarrow aA,\quad A\rightarrow aA,\quad A\rightarrow bB,\quad B\rightarrow bC ,\quad C\rightarrow bC|b

       容易判断,该文法属于3型文法,且 $ L(G) = {anbm},\quad n\ge1,\quad m\ge3$

       对上述4级文法有疑问的朋友可以私信给我,一同进行交流讨论~

       此外,4级文法之间还有如图所示的关系:
    在这里插入图片描述

    L(G3)L(G2)(G1)(G0) L(G_3)\subseteq L(G_2)\subseteq (G_1)\subseteq (G_0)
       即,每一个正则文法都是上下文无关文法,每一个上下文无关文法都是上下文有关文法,每一个上下文有关文法都是0型文法。
       Chomsky把0型文法生成的语言叫0型语言,把由上下文有关文法、上下文无关文法、正则文法生成的语言分别叫作上下文有关语言、上下文无关语言、正则语言(或有限状态语言)。

       一般来说,如果一种语言能由几种文法所产生,则把这种语言称为在这几种文法中受限制最多的那种文法所产生的语言。

    4.自然语言形式文法

      在NLP领域中,采用Chomsky形式文法作为刻画语言规律、表示语言的形式文法。
      那么问题来了:用几型文法对自然语言进行刻画比较合适呢?
      从描述能力上来说,正则文法描述能力太弱,上下文无关文法也不足以表述自然语言,因为自然语言中上下文相关情况非常常见。
      然而,上下文有关文法的计算复杂度为NP完全,而上下文无关文法的复杂度为多项式复杂度,可以接受。
      因此,用上下文无关文法来描述自然语言最为普遍,此外需要用一些其它手段来增强其描述能力。

      上下文无关文法会产生二义性问题。
      我们一定还记得这样一张歧义图:
    在这里插入图片描述

      对一个文法GG,如果存在某个句子有不只一棵分析树与其对应,那么称这个文法是二义的。
      很明显,上下文无关文法处理语言会产生二义性。

      Chomsky证明,任何由上下文无关文法生成的语言,均可由重写规则为ABCA\rightarrow BC或者 AxA\rightarrow x的文法生成,其中A,B,CVn,xVtA,B,C∈V_n,\quad x∈V_t
      具有这样重写规则的上下文无关文法,它的推导树均可简化为二元形式,这样就可以用二分法来分析自然语言,采用二叉树来表示自然语言的句子结构。
      上述重写规则就称为 Chomsky范式 。

      之前我们提到过,Chomsky形式语言可以形式化表示为四元组:
    G=(Vn,Vt,S,P)G = (V_n,V_t,S,P)
      那么,用它来表示自然语言,各部分究竟对应着什么呢?
      VnV_n:非终结符的有限集合,对应语言语法单位(一般为“词” 戒“词组”的词性)。
      VtV_t:终结符的有限集合,对应语言基本组成单位 (一般为“词” )
      VnV_n中的初始符号,相当于语法范畴中的句子。
      PP:生成规则,对应语法结构规则(不同的语言有不同的规则),一般情况下由人工编写。

      举个例子:
      假设有如下语句:
      {我吃饭,我洗衣,我喝水,我看书,
      你吃饭,你洗衣,你喝水,你看书,
      他吃饭,他洗衣,他喝水,他看书}

      如何用形式文法表示?
    Vt={}V_t =\{我,你,他,吃,洗,喝,看,饭,衣,书,水\}

    Vn={S,IP,PR,VV,NN}V_n=\{S,IP,PR,VV,NN\}

    PSIP,IPPRVVNNP:S\rightarrow IP,\quad IP\rightarrow PR \quad VV \quad NN

    PR,VV,NNPR\rightarrow 我|你|他,\quad VV\rightarrow 吃|洗|喝|看,\quad NN\rightarrow 饭|衣|书|水

    G={Vn,Vt,S,P}G = \{V_n,V_t,S,P\}

      很明显,这是一个2型文法。

      由此文法生成句子的过程图如下:
    在这里插入图片描述

      句子分析过程是生成过程的逆过程,由于形式文法中的生成规则是根据语法规则制定,所以在分析句子是否由某文法产生的同时就等同于对句子进行语法结构分析。

      但是很明显的是,该种方法有很大的局限性:它局限于规则。
    有很多句子无法由规则集生成(例如,我看你喝水),也有很多不合逻辑的句子可以由规则集生成(例如,我吃衣)。

      在这一部分中,我们主要介绍了Chomsky形式文法,了解了如何利用它对自然语言进行表示;此外,我们还简单介绍了完全句法分析的概念。
      在下一部分的内容中,我们将会对完全句法分析进行详细介绍,包括其所面临的问题和解决方法。

    参考文献

    [1] https://blog.csdn.net/echoKangYL/article/details/88106893

    展开全文
  • 的基础——Chomsky形式文法。 句法分析的任务是确定句子的句法结构或句子中词汇之间的依存关系,主要包括三种: 完全句法分析、局部句法分析、依存关系分析 。 其中,前两种句法分析是对句子的句法结构进行分析...
  • 形式语言自动机课程笔记 学到编译原理的时候用到了文法相关概念,复习自动机正好把以前的笔记整理...文法也可以用严格的规则形式描述,比如C语言文法,这种文法称为形式文法 二、形式文法和形式语言 (1)形式...
  • 文法形式一般有很多种,只要能正确的描述出终结符非终结符约定、以及开始符号就行 第一种 ②第二种: 二、句型和句子 只要是在整个推到过程的所有符号都是句型; 句子是只含有终结符。 三、四种文法 0型文法...
  • 形式语言——文法

    2014-03-16 18:38:08
    讲解了文法的构造方法,及应用,是学习汇编语言的必备知识
  • 语义规则形式: 左部 右部 文法符号综合属性 产生式右部任意属性 产生式右部非终结符继承属性 产生式右部符号和文法符号任意属性 也就是说,左部只能是关于非终结的属性。 例子: 这里说一下a...
  • 形式语言——四类文法

    千次阅读 2016-06-20 16:20:38
    参考:形式语言文法定义G=(N,∑,P,S),其中N为终止符集合,∑为终止符集合,P为产生式集合,S为起始语句G=(N,\sum,P,S),其中N为终止符集合,\sum 为终止符集合,P为产生式集合,S为起始语句 0-型文法(无限制文法或...
  • 编译原理2文法形式语言 编译原理2文法形式语言 编译原理2文法形式语言 编译原理2文法形式语言 编译原理2文法形式语言
  • 文法形式化定义

    千次阅读 2019-01-16 20:21:33
    文章目录句子的构成规则自然语言的例子文法形式化定义产生式的简写符号的约定 句子的构成规则 自然语言的例子 <句子>→\rightarrow→<名词短语><动词短语> <...
  • 编译原理学习-形式语言 乔姆斯基文法 四种文法 我觉得讲课的老师都不一定能搞清楚这些文法到底是什么东西 0型文法 1型文法 2型文法-上下文无关文法 3型文法 直接推出的严格定义 可以理解成字符...
  • 文法

    2019-10-08 14:42:25
    文章目录文法基本概念文法形式定义 文法 基本概念 符号:字母、数字、标点… 字母表∑:一个有穷符号集合*(比如ASCII码就是一个字母表)* 字母表的乘积 ∑1∑2 = { ab | a∈∑1,b∈∑2} 字母表的n次幂 ∑0...
  • 高级程序设计语言的三个基本因素: 语法:描述语言成分的构成规则(包括词法规则和语法规则) 语义:描述语法成分的含义 语用:描述语法成分的使用方法形式语言理论(formal language theory)是用数学方法研究自然...
  • 文法形式定义 1.处理文法的语法分析器大体上可以分为三种类型:通用的,自顶向下的和自顶向上的。 2.文法:一种用于描述程序设计语言语法的表示方法——“上下文无关文法”,简称“文法”。 3.一个上下文无关...
  • 一,定义语言模型什么是语言模型,简单讲就是描述语言规律的数学模型。语言模型的任务就是寻找困惑度...二,Chomsky形式文法对语言形式定义后,还需要对语言进行形式化描述,形式语言学中,采用形式文法对语言进行...
  • 一、文法之间的关系 1、文法=语法。 词法规则:描述单词符号的构成规则。 标识符,常数,符号运算。 工具:正规文法(正规式,有限自动机) 语法规则:描述语法单位构成规则。 表达式,语句,函数,过程。 ...
  • 以下内容主要来自维基百科 形式科学是指主要研究对象为抽象形态的科学,如逻辑、数学、计算理论、信息论、统计学等。 专门研究语言的语法的...形式文法之所以这样命名,是因为它与人类自然语言中的文法相似的缘故
  • byyl - 文法及语言

    2020-05-08 11:51:52
    文法的表示形式 文法的分类 BB...BBC类型文法 ABB...BBC类型文法 语言是什么? 语言的表示 等价文法 已知文法求语言 <一> 文法 1> 文法为什么出现? 使用文法作为工具,可以严格定义句子的结构...
  • 文法和语言的形式定义
  • 文章目录前面的话一、 语言及文法1.1 文法形式概念 前面的话 第一章 文法形式化描述方法之一) 第二章 自动机和文法和正规表达式(形式化描述方法的三种方法) 第三章 图灵机(更高级的形式化手法) 一、 语言及...
  • 可视化语言文法形式化描述.pdf
  • 文章目录1 文法的概念2 符号和符号串的定义3 文法形式化定义3.1 终结符3.2 非终结符3.3 P&&S 1 文法的概念 每一种自然语言或者是编程语言都需要文法来描述,文法相当于语言学的语义分析,即分析每一句话所...
  • 基础回顾 根据Chomsky文法体系划分为四类,0,1,2,3型。 由文法G产生的语言记为L(G) L(G)中的一个字符串,必是由终结符组成的,并且是从起始符S推导出来的 ...1型 ,不允许A→ε形式。 思考 那么如何利用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 945
精华内容 378
关键字:

形式文法