`
deng131
  • 浏览: 660073 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

巴科斯范式和扩展巴科斯范式

阅读更多
巴科斯范式

巴科斯范式(也称为巴科斯-瑙尔范式、巴克斯-诺尔范式)即 BNF 是一种用于表示上下文无关文法的语言,上下文无关文法描述了一类形式语言。尽管巴科斯范式也能表示一部分自然语言的语法,它还是更广泛地使用于程序设计语言、指令集、通信协议的语法表示中。大多数程序设计语言或者形式语义方面的教科书都采用巴科斯范式。在各种文献中还存在巴科斯范式的一些变体,如扩展巴科斯范式EBNF或扩充巴科斯范式 ABNF。

BNF 规定是推导规则(产生式)的集合,写为:

<code><符号> ::= <使用符号的表达式>

这里的<符号> 是非终结符,而表达式由一个符号序列,或用指示选择的竖杠 ‘|’ 分隔的多个符号序列构成,每个符号序列整体都是左端的符号的一种可能的替代。从未在左端出现的符号叫做终结符。
扩展巴科斯范式

扩展巴科斯-瑙尔范式(EBNF)是表达作为描述计算机编程语言和形式语言的正规方式的上下文无关文法的元语法符号表示法。它是基本巴科斯范式 (BNF)元语法符号表示法的一种扩展。

它最初由尼古拉斯·沃斯开发,最常用的 EBNF 变体由标准,特别是 ISO-14977 所定义。
基本

代码,如由终结符即可视字符、数字、标点符号、空白字符等组成的计算机程序的源代码。

EBNF 定义了把各符号序列分别指派到非终结符的产生规则:

digit excluding zero = "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9" ;
digit = "0" | digit excluding zero ;

这个产生规则定义了在这个指派的左端的非终结符 digit。竖杠表示可供选择,而终结符被引号包围,最后跟着分号作为终止字符。所以 digit 是一个 0 或可以是 1 或 2 或 3 直到 9 的一个 digit excluding zero。

产生规则还可以包括由逗号分隔的一序列终结符或非终结符:

twelve = "1" , "2" ;
two hundred one = "2" , "0" , "1" ;
three hundred twelve = "3" , twelve ;
twelve thousand two hundred one = twelve , two hundred one ;

可以省略或重复的表达式可以通过花括号 { … } 表示:

natural number = digit excluding zero , { digit } ;

在这种情况下,字符串 1, 2, …,10,…,12345,… 都是正确的表达式。要表示这种情况,于花括号内设立的所有东西可以重复任何次,包括根本不出现。

可选项可以通过方括号 [ ... ] 表示:

integer = "0" | [ "-" ] , natural number ;

所以 integer 是一个零(0)或可能前导可选的负号的一个自然数。

EBNF 还包括描述指定次数的重复,和排除产生式的某部分或向 EBNF 文法插入注释的语法。
依据 ISO 的扩展

依据 ISO 14977 标准,提供了两个设施来扩展 EBNF。其一是在 EBNF 文法部分的特殊序列,它是在问号包围内的任意文本,其解释超出了 EBNF 标准的范围。例如,空格字符可以用如下规则定义:

space = ? US-ASCII character 32 ?;

其二利用圆括号在 EBNF 中不能放置到紧随标识符之后的事实。下列不是有效的 EBNF:

something = foo ( bar );

所以 EBNF 的扩展可以使用这种表示法。例如,在 Lisp 文法中,函数应用可以用如下规则定义:

function application = list( symbol , [ { expression } ] );

扩展 BNF 的动机

BNF 有着可选项和重复不能直接表达的问题。作为替代,它们需要利用中介规则或两选一规则,对于可选项,定义要么是空的要么是可选的产生式的规则,对于重复,递归的定义要么是被重复的产生式要么是自身的规则。同样的构造仍可用在 EBNF 中。

可选项:

signed number = [ sign , ] number ;

可按 BNF-风格定义为:

signed number = sign , number | number ;



signed number = optional sign , number ;
optional sign = ε | sign ; (* 使用 ε 来更清晰的指示空产生式 *)

重复:

number = { digit } ;

可按 BNF-风格定义为:

number = digit | number digit;

其他增加和修改

EBNF 排除了 BNF 的一些缺陷:

   1. BNF 为自身使用了符号 (<, >, |, ::=)。当它们出现在要定义的语言中的时候,BNF 不能不加以修改或解释的使用。
   2. BNF-语法在一行中只表示一个规则。

EBNF 解决了这些问题:

   1. 终结符被严格的包围在引号 (“…” 或 ‘…’) 中。给非终结符的尖括号 (“<…>”)可以省略。
   2. 通常使用终止字符分号结束一个规则。

进一步还提供了定义重复次数,排除法选择(比如除了引号的所有字符)和注释等的增强机制。

不管所有这些增强,EBNF 在能定义的语言的意义上不比 BNF 更强大。在原理上用 EBNF 定义的任何文法都可以用 BNF 表达。但是经常导致可观的更多规则的表示。

EBNF 已经被ISO用代码 ISO/IEC 14977:1996(E) 标准化了。

在某些场合任何扩展的 BNF 都被称为 EBNF。例如 W3C 使用 one EBNF 来规定 XML。
另一个例子

只允许赋值的简单编程语言可以用 EBNF 定义为:

(* a simple program in EBNF − Wikipedia *)
program = 'PROGRAM' , white space , identifier , white space ,
           'BEGIN' , white space ,
           { assignment , ";" , white space } ,
           'END.' ;
identifier = alphabetic character , [ { alphabetic character | digit } ] ;
number = [ "-" ] , digit , [ { digit } ] ;
string = '"' , { all characters − '"' } , '"' ;
assignment = identifier , ":=" , ( number | identifier | string ) ;
alphabetic character = "A"|"B"|"C"|"D"|"E"|"F"|"G"
             |"H"|"I"|"J"|"K"|"L"|"M"|"N"
             |"O"|"P"|"Q"|"R"|"S"|"T"|"U"
             |"V"|"W"|"X"|"Y"|"Z" ;
digit = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9" ;

white space = ? white space characters ? ;
all characters = ? all visible characters ? ;

一个语法上正确的程序:

PROGRAM DEMO1
BEGIN
  A0:=3;
  B:=45;
  H:=-100023;
  C:=A;
  D123:=B34A;
  BABOON:=GIRAFFE;
  TEXT:="Hello world!";
END.

这个语言可以轻易的扩展上控制流,算术表达式和输入/输出指令。就可以开发出一个小的、可用的编程语言了。

使用了在标准中提议为正规表示的下列字符:
用途 符号表示
定义 =
串接 ,
终止 ;
分隔 |
可选 [ ... ]
重复 { … }
分组 ( … )
双引号 ” … “
单引号 ‘ … ‘
注释 (* … *)
特殊序列 ? … ?
除外 -
约定

   1. 使用了如下约定:
         1. 扩展 BNF 每个元标识符都被写为用连字号连接起来的一个或多个字;
         2. 结束于“-symbol” 的元标识符是扩展 BNF 的终结符的名字。
   2. 表示扩展 BNF 的每个操作符的正常字符和它所蕴涵的优先级(顶部为最高优先级)为:

      * repetition-symbol
      - except-symbol
      , concatenate-symbol
      | definition-separator-symbol
      = defining-symbol
      ; terminator-symbol

   3. 下列括号对超越正常优先级:

      '  first-quote-symbol            first-quote-symbol  '
      "  second-quote-symbol          second-quote-symbol  "
      (* start-comment-symbol          end-comment-symbol *)
      (  start-group-symbol              end-group-symbol  )
      [  start-option-symbol            end-option-symbol  ]
      {  start-repeat-symbol            end-repeat-symbol  }
      ?  special-sequence-symbol   special-sequence-symbol ?

作为例子,下列语法规则展示了表达重复的设施:

aa = "A";
bb = 3 * aa, "B";
cc = 3 * [aa], "C";
dd = {aa}, "D";
ee = aa, {aa}, "E";
ff = 3 * aa, 3 * [aa], "F";
gg = {3 * aa}, "D";

这些规则定义的终结字符串如下:

aa: A
bb: AAAB
cc: C AC AAC AAAC
dd: D AD AAD AAAD AAAAD etc.
ee: AE AAE AAAE AAAAE AAAAAE etc.
ff: AAAF AAAAF AAAAAF AAAAAAF
gg: D AAAD AAAAAAD etc.

有关工作

   1. W3C 使用一种不同的 EBNF 来指定 XML 语法。
   2. British Standards Institute 在1981年出版了一个 EBNF 标准: BS 6154。
   3. IETF 使用在 RFC 4234 中规定的扩充 BNF (ABNF)。

ps,由于中文维基百科尚不可访问,所以就原文转载了其中关于巴科斯范式和扩展巴科斯范式的词条。
分享到:
评论

相关推荐

    扩展巴科斯范式.pdf

    常用的语法描述语言,某些情况下(例如:boost/sprit),可以用于编写语法解析器 例如:自己写一个c++函数识别程序,自动匹配函数名以及参数,用于写单元测试程序有可能会用到语法识别。

    ISO_IEC_14977_1996(E) 信息技术 语法元语言 扩展的BNF标准(EBNF) .pdf

    信息技术 语法元语言 扩展的BNF标准(EBNF) 巴科斯范式(BNF: Backus-Naur Form 的缩写)是由 John Backus 和 Peter Naur 首先引入的用来描述计算机语言语法的符号集。现在,几乎每一位新编程语言书籍的作者都使用...

    论文研究-面向供需网协同管理的企业知识建模研究.pdf

    为了在供需网环境下实现企业知识的协同管理,提出了供需网企业知识本体...为表达供需网的协同知识语义,阐述了SDNKO概念框架的巴科斯范式和文档类型定义。最后,给出了供需网企业产品订单生成的知识协同管理实例。

    RFC2234(SIP遵循的BNF范式)

    语法规范的扩展巴科斯范式:ABNF (RFC2234——Augmented BNF for Syntax Specifications: ABNF) 本备忘录的状态 本文档讲述了一种Internet社区的Internet标准跟踪协议,它需要进一步进行讨论和建 议以得到改进。...

    论文研究-基于范式语法的工控协议Fuzzing测试技术.pdf

    首先以改进的扩展巴科斯范式(modified augmented Backus-Naur form,MABNF)来描述工控协议;然后根据范式语法模型,将报文样本解析为范式语法变异树,进而生成范式语法变异树的描述脚本;提出了基于MABNF变异树的...

    BNF范式查看器

    巴科斯范式(BNF)查看器,可查看BNF范式生成的First集,Follow集,Select集和预测分析表,是学习编译原理的好工具。 附带标准c的bnf范式文件。

    基于范式语法的工控协议Fuzzing测试技术 (2016年)

    首先以改进的扩展巴科斯范式(modified augmented Backus-Naur form,MABNF)来描述工控协议;然后根据范式语法模型,将报文样本解析为范式语法变异树,进而生成范式语法变异树的描述脚本;提出了基于MABNF变异树的...

    plo编译的实现

    掌握语言的形式化描述:语法描述图与巴科斯范式EBNF。以PL/0为例学习编译程序实现的基本步骤和相关技术,熟悉并理解编译程序的基本原理和概念。对于一段给定的程序,给出其形式化描述

    基于EBNF和二次爬取策略的XSS漏洞检测技术

    针对传统基于渗透测试技术的漏洞检测方法中攻击向量复杂度低易被过滤、整体检测流程繁琐等问题,提出了一种基于扩展的巴科斯范式(EBNF)的攻击向量自动生成方法和XSS漏洞二次爬取策略。通过定义EBNF规则生成规则...

    cache_server:缓存系统

    1 *数字内容= * OCTET 键值=长度SP长度SP内容内容响应=错误| 字节数组错\u8bef='-'字节数组注意: DIGIT是ABNF的基本规则,取值范围是0〜9 OCTET是ABNF的基本规则,取值范围是0x00〜0xFF扩展巴科斯范式(ABNF,增强...

    lex_yacc简明教程

    Lex 是一种生成扫描器的工具。扫描器是一种识别文本中的词汇模式的程序。 这些词汇模式(或者常规表达式)在一种特殊的句子结构中定义;Yacc 代表 Yet Another Compiler ...它用巴科斯范式(BNF, Backus Naur Form)来书写

    Python中用Spark模块的使用教程

    在日常的编程中,我经常需要标识存在于文本文档中的部件和结构,这些文档包括:日志文件、配置文件、定界的数据以及格式更自由的(但还是半结构化的)报表...大多数正式的解析器都使用扩展巴科斯范式(Extended Backus

    javacc源代码

    相一致 JavaCC还提供JJTree工具来帮助我们建立语法树 JJDoc工具为我们的源文件生成BNF范式 巴科斯 诺尔范式 文档 Html "&gt;JavaCC JavaCompilerCompiler 是一个用JAVA开发的最受欢迎的语法分析生成器 这个分析生成器...

    论文研究-钢铁企业在制品成本追溯模型研究.pdf

    该模型通过作业中心维、属性维和成本中心维对在制品进行描述,并采用巴科斯—诺尔范式对其进行数学规范,给出了在制品成本追溯规则和算法流程。通过在钢铁企业的应用实例,验证了该模型的可行性,能够实现钢铁企业...

    论文研究-建模语言中的文本表面语法分析方法研究.pdf

    通过分析三种常见文法的利弊,采用了扩展的BNF文法进行文本语法规则的描述,并通过准引用(quasiquote)和语法糖方法对该文法进行了改进和扩充,增强了文本语法的描述能力和易用性。通过准引用方法,已经被建立好...

    HTTP协议详解

    2.1 扩充的BNF(扩充的 巴科斯-诺尔范式) 2.2基本规则 (basic rule) 3 协议参数 3.1 HTTP版本 3.2 统一资源标识符(URI) 3.2.1一般语法 3.2.2 http URL 3.2.3 URI 比较 3.3 日期/时间格式(Date/Time Formats)...

    温州医学院《儿科》期末考试试卷(含答案).pdf

    温州医学院《儿科》期末考试试卷(含答案

    大学生《儿科》期末考试复习知识点总结及题库.pdf

    大学生《儿科》期末考试复习知识点总结及题库.

    大学生《内科学I》期末复习知识点总结.pdf

    大学生《内科学I》期末复习知识点总结

    大学生《儿科学》期末复习知识点总结.pdf

    大学生《儿科学》期末复习知识点总结

Global site tag (gtag.js) - Google Analytics