精华内容
下载资源
问答
  • BNF范式

    千次阅读 2018-12-17 14:36:39
    BNF范式

    在这里插入图片描述

    1.概念

    巴科斯范式 以美国人巴科斯(Backus)和丹麦人诺尔(Naur)的名字命名的一种形式化的语法表示方法,用来描述语法的一种形式体系,是一种典型的元语言。又称巴科斯-诺尔形式(Backus-Naur form)。它不仅能严格地表示语法规则,而且所描述的语法是与上下文无关的。它具有语法简单,表示明确,便于语法分析和编译的特点。BNF表示语法规则的方式为:非终结符用尖括号括起。每条规则的左部是一个非终结符,右部是由非终结符和终结符组成的一个符号串,中间一般以“::=”分开。具有相同左部的规则可以共用一个左部,各右部之间以直竖“|”隔开

    2. 格式

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

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

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

    3.基本原理

    BNF类似一种数学游戏:从一个符号开始(叫做起始标志,实例中常用S表示),然后给出替换前面符号的规则。BNF语法定义的语言只不过是一个字符串集合,你可以按照下述规则书写,这些规则叫做书写规范(生产式规则),形式如下:

        symbol := alternative1 | alternative2 ...
    

    每条规则申明:=左侧的符号必须被右侧的某一个可选项代替。替换项用“|”分割(有时用“::=”替换“:=”,但意思是一样的)。替换项通常有两个符号和终结符构成。之所以叫做终结符是因为没有针对他们的书写规范,他们是书写过程的终止(符号通常被叫做非终止符,也有人叫非终端)。

    4. 语法

    1. 在双引号中的字("word")代表着这些字符本身。而double_quote用来代表双引号。
    2. 在双引号外的字(有可能有下划线)代表着语法部分。
    3. 尖括号( < > )内包含的为必选项。
    4 方括号( [ ] )内包含的为可选项。
    5 大括号( { } )内包含的为可重复0至无数次的项。
    6 竖线( | )表示在其左右两边任选一项,相当于"OR"。
    7 ::= 是“被定义为”。
    8 "..." : 术语符号 
    9 [...] : 选项,最多出现一次 
    10 {...} : 重复项,任意次数,包括 0 次 
    11 (...) : 分组 
    12 |   : 并列选项,只能选一个 
    13 斜体字: 参数,在其它地方有解释 
    
    展开全文
  • BNF范式查看器

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

    2019-07-08 17:37:40
    1、什么是BNF范式,什么又是EBNF范式?(在学习中经常会碰到用BNF范式描述的规则,老是忘记每个符号确切的作用,现在把他们一一罗列如下,亲手记录的东西应该能记住吧。。。-__-|||)  答:巴科斯范式及其扩展(BNF &...

     1、什么是BNF范式,什么又是EBNF范式?(在学习中经常会碰到用BNF范式描述的规则,老是忘记每个符号确切的作用,现在把他们一一罗列如下,亲手记录的东西应该能记住吧。。。-__-|||) 

      答:巴科斯范式及其扩展(BNF & Augmented BNF) 

      1)巴科斯范式巴科斯范式(BNF: Backus-Naur Form 的缩写)是由 John Backus 和 Peter Naur 首先引入的用来描述计算机语言语法的符号集。现在,几乎每一位新编程语言书籍的作者都使用巴科斯范式来定义编程语言的语法规则。 

      2)巴科斯范式的内容: 

      在双引号中的字("word")代表着这些字符本身。而double_quote用来代表双引号。 

      在双引号外的字(有可能有下划线)代表着语法部分。 

      < > : 内包含的为必选项。 

      [ ] : 内包含的为可选项。 

      { } : 内包含的为可重复0至无数次的项。 

      | : 表示在其左右两边任选一项,相当于"OR"的意思。 

      ::= : 是“被定义为”的意思 


      3)扩展的巴科斯范式(Augmented BNF):RFC2234 定义了扩展的巴科斯范式(ABNF)。近年来在Internet的定义中ABNF被广泛使用。ABNF做了更多的改进,比如说,在ABNF中,尖括号不再需要。 

      4)EBNF的基本内容: 

      "..." : 术语符号 

      [...] : 选项:最多出现一次 

      {...} : 重复项: 任意次数,包括 0 次 

      (...) : 分组 

      | : 并列选项,只能选一个
     

      斜体字: 参数,在其它地方有解释 

      例子BNF应用较多,以下给出一个简单例子,这是用BNF来定义的Java语言中的For语句的实例: 

      FOR_STATEMENT ::= 

      "for" "(" ( variable_declaration | 

      ( expression ";" ) | ";" ) 

      [ expression ] ";" 

      [ expression ] ";" 

      ")" statement 

      什么是BNF? 

      
     Backus-Naur符号(就是众所周知的BNF或Backus-Naur Form)是描述语言的形式化的数学方法,由John Backus (也许是Peter Naur)开发,用于描述Algol 60编程语言的语法。 

      最初的时候是许多标记(图例),是John Backus 在数学家Emil Post早期工作的基础上开发的,Peter Naur 在Algol 60中采用了它,并进行了稍许改进,从而使其出名,因此Naur把BNF叫做Backus Normal Form,而其他人则把它叫成Backus-Naur Form。 

      BNF被用来形式化定义语言的语法,以使其规则没有歧义。事实上,BNF非常精确,围绕这些语法有很多数学理论,使得人们竟然可以机械地为基于BNF语法的语言构造解析器。(有些语法不能实现,但通常可以手工地通过转换成其他形式来实现)。 

      实现这个功能的程序叫做编译器,最有名的是YACC,当然,还有很多很多。 

      工作原理 

      基本原理 

      BNF类似一种数学游戏:从一个符号开始(叫做起始标志,实例中常用S表示),然后给出替换前面符号的规则。BNF语法定义的语言只不过是一个字符串集合,你可以按照下述规则书写,这些规则叫做书写规范(生产式规则),形式如下: 

      symbol := alternative1 | alternative2 ... 

      每条规则申明:=左侧的符号必须被右侧的某一个可选项代替。替换项用“|”分割(有时用“::=”替换“:=”,但意思是一样的)。替换项通常有两个符号和终结符构成。之所以叫做终结符是因为没有针对他们的书写规范,他们是书写过程的终止(符号通常被叫做非终止符,也有人叫非终端)。 

      BNF语法的另一个变化是把终止符(终端)放在引号中,把他们与符号区别开来。有些BNF语法用符号明确地标明允许使用空格的地方,而有的语法则把它留给读者推测。 

      BNF中有一个特殊符号“@”,表示符号可以去掉。如果用@替换符号,只需要将符号去掉。这非常有用,因为如果不利用这个技巧,有时很难终止替换过程。 

      因此,一个语法描述的语言就是用书写规则(生产式规则)写的字符串的集合。如果一个字符串无法用这些规则写出,那么,该字符串在这个语言中就被禁用。 

      一个实例 

      下面是BNF语法的一个实例: 

      S := '-' FN | FN 

      FN := DL | DL '.' DL 

      DL := D | D DL 

      D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 

      这里的各种符号都是缩写的:S是开始符,FN产生一个分数,DL是一串数字列表,D是各个数字。 

      该语法描述的语言的有效句子都是数字,可能是分数,也可能是负数。要写一个数字,首先以S符号开头: 

      S 

      然后,用S的结果替换它。上例中,我们可以选择在数字前面不加“-”号而仅仅使用FN,并用FN替换S: 

      FN 

      接着用FN的结果替换FN。我们想写一个分数,所以选择产生两个中间带“.”的十进制数的列表,然后,我们接着在每一行用一个符号的结果替换一个符号,像下面的例子: 

      DL . DL 

      D . DL 

      3 . DL 

      3 . D DL 

      3 . D D 

      3 . 1 D 

      3 . 1 4 

      这里我们写了一个分数3.14。如何写-5,读者可自己练习。要彻底搞明白,还需要研究语法,知道您弄明白为什么按照上述规则不能写出3..14。 

      EBNF及其用途 

      在DL中,我们已经用到了递归(如DL能产生新的DL)来表达许多数字D的情况。这有点不太灵活,使BNF难以阅读。扩展BNF(EBNF)通过引入下列操作符解决了这个问题: 

      l ?:意思是操作符左边的符号(或括号中的一组符号)是可选项(可以出现0到多次)。 

      l *:是指可以重复多次。 

      l +:是指可以出现多次。 

      一个EBNF语法实例 

      上面的例子用EBNF可以写成: 

      S := '-'? D+ ('.' D+)? 

      D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 

      提示:EBNF在定义语言方面并不比BNF更强大,只是更方便。凡是用EBNF写的东西都可以转换成BNF的形式。 

      BNF和EBNF的使用 

      一般用法 

      
     多数编程语言标准都使用一些EBNF变量来定义语言的语法。这有两个好处:一是在语言的语法上没有争议,而是易于编译器的编写,因为编译器的解析器可以用类似YACC这样的“编译器编译器”自动产生。 

      EBNF也用于许多其他标准,如定义协议格式,数据格式和XML,SGML这样的标记语言。(HTML没有按照语法定义,而是用SGML DTD这样的高级语法定义的。) 

      在BNF web club(http://cuiwww.unige.ch/db-research/Enseignement/analyseinfo/BNFweb.html )上可以查到BNF的一个语法集。 

      如何使用形式语法 

      现在,我们已经了解什么是BNF和EBNF以及它们的用途了,但还不知道为什么它们很有用以及如何利用它们。 

      形式语法最明显的用法已经提到过了:一旦为语言制定了形式语法,就完全定义了这个语言。对于那些东西可以用于语言,那些东西不可以就不会有歧义了。这非常有用因为用普通语言描述的语法不仅冗长,而且会产生对不同的解释。 

      另一个好处是:形式语法是数学产物,可以被计算机理解。实际上有许多程序可以用(E)BNF语法输入,并自动为给定语法的解析器提供处理代码。实际上,这是设计编译器的常见做法:用带有语法输入的所谓“编译器编译器”产生编程语言的解析器代码。 

      当然,编译器除了做语法检查之外还做许多其他检查,他们也产生代码。这些都没有在(E)BNF中描述,因此编译器编译器通常有针对一种语法中不同代码的代码块连接(也叫做操作)的特殊语法。 

      最有名的编译器编译器是YACC(Yet Another Complier Complier),产生C代码,其他的编译器还有针对C++,JAVA,Python等等其他语言的。 

      解析 

      最简单的方法 

      自上而下的解析(LL) 

      
     按照现有语法解析代码的最简单方法是叫做LL解析(自上而下解析)。它是这样工作的:对每一段代码找出代码开始的非终端标记(叫做初始集)。 

      然后,在解析时只需要从起始符开始比较不同代码段(符号)初始集和第一个输入的符号,判断代码段用的是哪个起始符作为开始的(用到了那些符号)。只有不存在一个符号的两个初始集含有相同的终止符时才可以这样。否则,就不能通过输入的第一个终止符选择哪个开始符(符号)了。 http://www.ce91.com/forum-63-1.html

      LL语法通常按数字分类,比如LL(1), LL(0)等等。括号中的数字是在语法中的任何一点选择适当符号时需要同时考虑的最大终端数。因此 LL(0)根本不需要检查终端(终止符),总能够选择适当的终止符。这种情况只发生在所有符号只有一个替换符的情形,而如果只有一个替换符意味着语言只有一个字符串。也就是说LL(0)没有意义。 

      最常有也是做有用的LL语法是联络LL(1),通过检查输入的第一个终止符总能够选择适当的替换符。而LL(2)需要检查两个符号,以此类推。 

      一个LL分析实例 

      为了说明,我们就实例语法做一个初始集分析。对符号D这非常容易:所有的替换符号跟它们的初始集(它们产生的)一样是一个数字,D符号把由10个数字组成的集合作为初始集。这意味着至少有一个LL(1)语法,因为这时我们需要一个终端来选择适当的替换符。 

      对DL就会有些麻烦。两个替换符都以D开头,因此都有相同的初始机。这意味着不能够通过检查输入的第一个终止符来选择适当的替换符。但我们可以通过欺骗轻松地克服这个困难:如果输入的第二个终止符不是数字,我们就用第一个替换符,如果两个都是数字,就用第二个替换符。也就是说,这至少是LL(2)语法。 

      这里其实把事情简化了。DL的替换符并没有告诉我们D @的替换符中的第一个终止符后哪个终止符是被允许的,因为我们需要知道在DL后面哪个终止符被允许。这个终止符集叫做符号的后续集(follow set of the symbol),这里是“.”,是输入的结尾。 

      FN符号更糟糕,因为两个替换符都是以数字作为其初始集。检查第二个也终止符没有用,因为在数字列表(DL)中的最后一个数字的后面需要查看第一个终止符,而我们需要读取所有的数字后才能知道有多少数字。由于有多少数字并无限制,这就不是一个对于任意k的LL(k)语法。 

      或许有些奇怪,S符号很简单。第一个替换项“-”是它的初始集,第二个全部是数字。也就是说,解析时从S符号开始查看输入项来决定使用哪个替换项。如果第一个终端是“-”,就用第一个替换项“-”;否则就用第二个。只有FN和DL替换想会引起麻烦。 

      一个LL转换实例 

      其实也没有必要失望。多数非LL(k)语法可以容易地转换成了LL(1)语法。这样我们需要转换两个符号:FN和DL。 

      FN的问题是两个替换项都以DL开头,但第二个后接一个“.”和另外一个初始DL后面的DL。这很好解决:我们把FN变成只有以一个DL开头的替换项后跟一个FP(分数部分),FP可以是空或是”.”后跟一个DL。变成下面这样: 

      FN := DL FP 

      FP := @ | '.' DL 

      现在FN没有问题了,因为只有一个替换项,FP也没有问题,因为两个替换项有不同的初设集。分别是输入的结尾和“.”。 

      DL是块硬骨头,因为主要问题出在递归,而且是复合的,需要从DL中得到一个D。解决方案是给DL一个单独的替换项,一个D后接一个 DR(其余的数字)。这时DR就有两个替换项:D和DR或@。第一个替换项以所有的数字为初始集,第二个含有“.”和输入的结尾作为其初始集,从而解决问题。 

      这样就彻底转换成LL(1)语法了: 

      S := '-' FN | FN 

      FN := DL FP 

      FP := @ | '.' DL 

      DL := D DR 

      DR := D DR | @ 

      D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 

      稍难的方法 

      自底而上的解析(LR)
     

      一个稍难的方法是移动替换法或叫自底而上解析。这个技术采集所有输入直道发现能够还原成符号的输入。这听起来好像很困难,所以需要给个例子加以说明。我们解析“3.14”看看如何从该语法中产生。我们从读取输入“3”开始: 

      3 

      然后,我们查看能否还原成产生它的符号。实际上我们能,它是从符号D产生的,我们用D替换3。这时我们注意到D可以从DL产生,所以用DL替换D。(这个语法有不确定性,我们可以一直还原到FN,但是是错误的。简单起见我们这里跳过错误的步骤,但清晰的语法将不会允许这样的错误发生),之后我们从输入中读取“.”并试图还原它,但是失败了。 

      D 

      DL 

      DL . 

      他不能还原成其它的东西,所以我们继续读取其它输入“1”,并把它还原成D,在读取下一个输入“4”, “4”也可以还原成D,再还原成DL,然后,“D DL”序列可以进一步还原成DL。 

      DL . 

      DL . 1 

      DL . D 

      DL . D 4 

      DL . D D 

      DL . D DL 

      DL . DL 

      看一下语法就会发现FN恰好能够还原“DL.DL”序列,于是将其还原。FN是从S产生的,所以FN可以还原成S,到此为止就完成了解析。 

      DL . DL 

      FN 

      S 

      也许你注意到我们可以先在做还原,也可以等到有多个符号在做不同的还原。这种移位还原解析算法有许多复杂变化,按照复杂程度和功能分为LR(0)、 SLR、LALR和LR(1)。LR(1)需要太大的解析表,所以LALR是最常用的算法,而SR(0)和SLR对多数编成语言都不够强大。 

      LALR 和LR(1)实在太复杂了,这里没法讨论,但你已经了解了其基本思想。 

      LL还是LR? 

      这个问题已经被人回答了,这里引用他的新消息: 

      希望不要引发争议,首先,当Frank看到这个时不要打我(我老板就是Frank DeRmer,LALR解析的创始人…)。 

      (借用一下Fischer&LeBlanc's "Crafting a Compiler"的摘要) 

      简单性Simplicity - - LL 

      通用性Generality - - LALR 

      操作Actions - - LL 

      错误恢复Error repair - - LL 

      表大小Table sizes - - LL 

      解析速度Parsing speed - - comparable (me: and tool-dependent) 

      简单性- - LL 占优 

      ========== 

      LL解析器更简单,如果要调试一个解析器,考虑递归下降解析器(编写LL解析器的常用方法)要比LALR解析器的表简单多了。 

      通用性 - - LALR 占优 

      ========== 

      在规范定义的简易性,LALR轻松取胜。LL和LALR的最大不同是LL语法必须用左因子法则和消除左递归。 

      提取左因子是必须的,因为LL解析器需要基于固定的输入数选择替换。 

      左回归是有问题的,因为规则前导标记总是统一规则的前导标记。这将导致无穷递归。 

      参考以下连接了解LALR转换成LL语法的方法: 

      http://www.jguru.com/thetick/articles/lalrtoll.html 

      许多语言已经有了LALR语法,但还需要翻译。如果语言没有这样的语法,写一个LL语法也不是什么难事。 

      操作性 - - LL 占优 

      ======= 

      在LL解析器中可以把操作放在任何地方而不会引起冲突。 

      错误修复 - - LL 占优 

      ============ 

      LL解析器具有丰富的环境信息(上下文信息),对修复错误很有帮助而非报告所无。 

      表大小 - - LL 

      =========== 

      假设你编写一个表驱动LL解析器,它的表只有其他的一半大小。(平心而论,有很多方法优化LALR表,使其变小) 

      解析速度 – 比较(我的观点:视工具而定) 

      --Scott Stanchfield in article <http://www.ietf.org/rfc/rfc2234.txt )中可以找到,the ISO 14977 standard中也有。更多信息 

      John Aycock用Python开发了一个非常好而且简单易用的解析框架叫做SPARK ,用可读性非常强的论文描述。 

      编译器和解析器方面权威工作是'The Dragon Book',也叫Compilers : Principles, Techniques, and Tools,作者Aho, Sethi and Ullman。请注意这是一本高级的数学书。 

      在线的免费资料较好的是这本:http://www.cs.vu.nl/~dick/PTAPG.html ,http://www.web006.com/bbs/forum.php。 

      Frank Boumphrey的another EBNF tutorial,(http://www.hypermedic.com/style/xml/ebnf.htm ) 

      Henry Baker的an article about parsing in Common Lisp(http://home.pipeline.com/~hbaker1/Prag-Parse.html )呈现的是一个简单、高效而且十分方便的解析框架。方法类似于编译器编译器,但它依赖于一个十分强大的Common Lisp宏系统。 

      定义BNF语法的句法规则在RFC 2234(http://www.ietf.org/rfc/rfc2234.txt )中可以找到,the ISO 14977 standard中也有。

    展开全文
  • C语言BNF范式

    千次阅读 2015-02-09 20:51:07
    C89,bnf范式

    终结符号:
    所有‘ ‘内的符号以及
    int_const char_const float_const id string enumeration_const

    translation_unit    : external_decl
                | translation_unit external_decl
                ;
    external_decl       : function_definition
                | decl
                ;
    function_definition : decl_specs declarator decl_list compound_stat
                |       declarator decl_list compound_stat
                | decl_specs declarator     compound_stat
                |       declarator  compound_stat
                ;
    decl            : decl_specs init_declarator_list ';'
                | decl_specs            ';'
                ;
    decl_list       : decl
                | decl_list decl
                ;
    decl_specs      : storage_class_spec decl_specs
                | storage_class_spec
                | type_spec decl_specs
                | type_spec
                | type_qualifier decl_specs
                | type_qualifier
                ;
    storage_class_spec  : 'auto' | 'register' | 'static' | 'extern' | 'typedef'
                ;
    type_spec       : 'void' | 'char' | 'short' | 'int' | 'long' | 'float'
                | 'double' | 'signed' | 'unsigned'
                | struct_or_union_spec
                | enum_spec
                | typedef_name
                ;
    type_qualifier      : 'const' | 'volatile'
                ;
    struct_or_union_spec    : struct_or_union id '{' struct_decl_list '}'
                | struct_or_union   '{' struct_decl_list '}'
                | struct_or_union id
                ;
    struct_or_union     : 'struct' | 'union'
                ;
    struct_decl_list    : struct_decl
                | struct_decl_list struct_decl
                ;
    init_declarator_list    : init_declarator
                | init_declarator_list ',' init_declarator
                ;
    init_declarator     : declarator
                | declarator '=' initializer
                ;
    struct_decl     : spec_qualifier_list struct_declarator_list ';'
                ;
    spec_qualifier_list : type_spec spec_qualifier_list
                | type_spec
                | type_qualifier spec_qualifier_list
                | type_qualifier
                ;
    struct_declarator_list  : struct_declarator
                | struct_declarator_list ',' struct_declarator
                ;
    struct_declarator   : declarator
                | declarator ':' const_exp
                |       ':' const_exp
                ;
    enum_spec       : 'enum' id '{' enumerator_list '}'
                | 'enum'    '{' enumerator_list '}'
                | 'enum' id
                ;
    enumerator_list     : enumerator
                | enumerator_list ',' enumerator
                ;
    enumerator      : id
                | id '=' const_exp
                ;
    declarator      : pointer direct_declarator
                |   direct_declarator
                ;
    direct_declarator   : id
                | '(' declarator ')'
                | direct_declarator '[' const_exp ']'
                | direct_declarator '['     ']'
                | direct_declarator '(' param_type_list ')'
                | direct_declarator '(' id_list ')'
                | direct_declarator '('     ')'
                ;
    pointer         : '*' type_qualifier_list
                | '*'
                | '*' type_qualifier_list pointer
                | '*'           pointer
                ;
    type_qualifier_list : type_qualifier
                | type_qualifier_list type_qualifier
                ;
    param_type_list     : param_list
                | param_list ',' '...'
                ;
    param_list      : param_decl
                | param_list ',' param_decl
                ;
    param_decl      : decl_specs declarator
                | decl_specs abstract_declarator
                | decl_specs
                ;
    id_list         : id
                | id_list ',' id
                ;
    initializer     : assignment_exp
                | '{' initializer_list '}'
                | '{' initializer_list ',' '}'
                ;
    initializer_list    : initializer
                | initializer_list ',' initializer
                ;
    type_name       : spec_qualifier_list abstract_declarator
                | spec_qualifier_list
                ;
    abstract_declarator : pointer
                | pointer direct_abstract_declarator
                |   direct_abstract_declarator
                ;
    direct_abstract_declarator: '(' abstract_declarator ')'
                | direct_abstract_declarator '[' const_exp ']'
                |               '[' const_exp ']'
                | direct_abstract_declarator '['    ']'
                |               '[' ']'
                | direct_abstract_declarator '(' param_type_list ')'
                |               '(' param_type_list ')'
                | direct_abstract_declarator '('        ')'
                |               '('     ')'
                ;
    typedef_name        : id
                ;
    stat            : labeled_stat
                | exp_stat
                | compound_stat
                | selection_stat
                | iteration_stat
                | jump_stat
                ;
    labeled_stat        : id ':' stat
                | 'case' const_exp ':' stat
                | 'default' ':' stat
                ;
    exp_stat        : exp ';'
                |   ';'
                ;
    compound_stat       : '{' decl_list stat_list '}'
                | '{'       stat_list '}'
                | '{' decl_list     '}'
                | '{'           '}'
                ;
    stat_list       : stat
                | stat_list stat
                ;
    selection_stat      : 'if' '(' exp ')' stat
                | 'if' '(' exp ')' stat 'else' stat
                | 'switch' '(' exp ')' stat
                ;
    iteration_stat      : 'while' '(' exp ')' stat
                | 'do' stat 'while' '(' exp ')' ';'
                | 'for' '(' exp ';' exp ';' exp ')' stat
                | 'for' '(' exp ';' exp ';' ')' stat
                | 'for' '(' exp ';' ';' exp ')' stat
                | 'for' '(' exp ';' ';' ')' stat
                | 'for' '(' ';' exp ';' exp ')' stat
                | 'for' '(' ';' exp ';' ')' stat
                | 'for' '(' ';' ';' exp ')' stat
                | 'for' '(' ';' ';' ')' stat
                ;
    jump_stat       : 'goto' id ';'
                | 'continue' ';'
                | 'break' ';'
                | 'return' exp ';'
                | 'return'  ';'
                ;
    exp         : assignment_exp
                | exp ',' assignment_exp
                ;
    assignment_exp      : conditional_exp
                | unary_exp assignment_operator assignment_exp
                ;
    assignment_operator : '=' | '*=' | '/=' | '%=' | '+=' | '-=' | '<<='
                | '>>=' | '&=' | '^=' | '|='
                ;
    conditional_exp     : logical_or_exp
                | logical_or_exp '?' exp ':' conditional_exp
                ;
    const_exp       : conditional_exp
                ;
    logical_or_exp      : logical_and_exp
                | logical_or_exp '||' logical_and_exp
                ;
    logical_and_exp     : inclusive_or_exp
                | logical_and_exp '&&' inclusive_or_exp
                ;
    inclusive_or_exp    : exclusive_or_exp
                | inclusive_or_exp '|' exclusive_or_exp
                ;
    exclusive_or_exp    : and_exp
                | exclusive_or_exp '^' and_exp
                ;
    and_exp         : equality_exp
                | and_exp '&' equality_exp
                ;
    equality_exp        : relational_exp
                | equality_exp '==' relational_exp
                | equality_exp '!=' relational_exp
                ;
    relational_exp      : shift_expression
                | relational_exp '<' shift_expression
                | relational_exp '>' shift_expression
                | relational_exp '<=' shift_expression
                | relational_exp '>=' shift_expression
                ;
    shift_expression    : additive_exp
                | shift_expression '<<' additive_exp
                | shift_expression '>>' additive_exp
                ;
    additive_exp        : mult_exp
                | additive_exp '+' mult_exp
                | additive_exp '-' mult_exp
                ;
    mult_exp        : cast_exp
                | mult_exp '*' cast_exp
                | mult_exp '/' cast_exp
                | mult_exp '%' cast_exp
                ;
    cast_exp        : unary_exp
                | '(' type_name ')' cast_exp
                ;
    unary_exp       : postfix_exp
                | '++' unary_exp
                | '--' unary_exp
                | unary_operator cast_exp
                | 'sizeof' unary_exp
                | 'sizeof' '(' type_name ')'
                ;
    unary_operator      : '&' | '*' | '+' | '-' | '~' | '!'
                ;
    postfix_exp     : primary_exp
                | postfix_exp '[' exp ']'
                | postfix_exp '(' argument_exp_list ')'
                | postfix_exp '('           ')'
                | postfix_exp '.' id
                | postfix_exp '->' id
                | postfix_exp '++'
                | postfix_exp '--'
                ;
    primary_exp     : id
                | const
                | string
                | '(' exp ')'
                ;
    argument_exp_list   : assignment_exp
                | argument_exp_list ',' assignment_exp
                ;
    const           : int_const
                | char_const
                | float_const
                | enumeration_const
                ;
    

    BNF范式百度百科

    展开全文
  • 「编程语言」课程的配套资源,包含了C、Java和Python的BNF范式生成规则。
  • 大家,过年好; 考虑到自身需求,需要自定义一种操作语言;... 问下大家:我已经定义了指令集,那么写出对应BNF范式的难度有多大呢? 设计完BNF范式后,是手写还是利用已知的工具进行词法、语法、语义分析呢?
  • 前言 BNF范式是一种描述编程语言的数学方法,可读性接近自然语言。 ...

    前言

    上个月买了本《两周自制脚本语言》,虽然我是不信这种鬼话的。买了后也不信,两周的时间是假的,但是知识还是有的。这一篇不会实现任何匹配,而是如何用数学点的方法定义自己要求的语言。

    BNF范式是一种描述编程语言的数学方法,可读性接近自然语言。


    BNF规则

    • ::= 左边是非终结符或元变量,右边是终结符——一些事先规定好的符号,这些符号可能是简单的单词或者在其他BNF式子中作为非终结符。有些BNF式子中是用冒号代替 ::=
    • 双引号中的内容表示符号本身的意思,之所以用双引号包上是因为部分符号在BNF中表达特定的意思。看BNF需要把双引号拿掉再看。有些BNF式子中是用的引号代替双引号
    • 双引号外的内容表示语法部分
    • 括号中的内容是必选项。有些BNF式子是用的尖括号
    • 方括号中的内容是可选项
    • 花括号中的内容可以是零次或者许多次
    • 竖线表示左右任选一项
    • 有的单词加引号表示原本的意思,有的不用引号也表示原本的意思(好不严谨的样子)

    变量var

    这里指变量的命名,即标识符!
    变量开头不能是数字,可以是字母和下划线。变量其他字符可以是数字、字母、下划线。
    (letter、digit、underline这类简单的单词表达的意思就不用解释了!)

    var          ::= prechar[otherchar]          
    prechar      ::= letter|underline
    otherchar    ::= (letter|digit|underline)[otherchar]
    

    表达式

    表达式可以指数据,变量存放的数据!
    二元表达式和一元表达式,判断式,四则运算式。
    无效值nil和用两个点连接字符串都是LUA语法,在进行设计的时候尽量考虑的简单点,所以使用一些LUA、python、C等语言的语法。

    exp           ::= nil|false|true|unop exp|exp binop exp|NUMBER|STRING|var
    unop          ::= "+"|"-"|"~"|not
    binop         ::= "+"|"-"|"*"|"/"|"//"|"%"|"^"|"&"|and|"|"|or|
    			      ">"|"<"|"=="|"<="|">="|".."
    NUMBER        ::= digit { digit } [ "." digit { digit } ]
    STRING        ::= """ everyletter """ { ".." STRING } 
    

    语句

    每个语句块用花括号包起来。每句话可以以分号或者换行结束, } 左边的第一条语句可以不用分号和换行结束。
    语句块内可以嵌套语句块。
    赋值语句左边可以是一个变量,或者用逗号分隔的几个变量。
    当型循环用while关键字,满足条件就进入循环。
    直到型循环用until关键字,满足条件就跳出循环。
    区分局部变量和全局变量,如果是类或者函数内的,就是默认局部变量。
    凡是可以用赋值式的地方,等于号都能用is关键字代替。

    block          ::= "{" { stat endstat } [ stat ] "}" | "{" block "}"
    varlist        ::= var { "," var }
    explist        ::= exp { "," exp }
    stat           ::= [ local ] varlist ( "=" | is ) explist |
    			       if exp block { elif block } [ else block ] |
    			       for var ( "=" is ) exp "," exp [ "," exp ] block |
    			       while exp block |
    			       do block until exp |
    			       break |
    			       continue 			   
    endstat        ::= ";"|newline
    

    函数

    • 在增加功能的时候,把新增的BNF式子到之前的有过的非终结符式子里面。下面的式子都是对已有的补充(高级数组代替类有修改的内容)

    三个连续的点表示任意数量、任意类型的参数。
    参数内可传递变量、函数名、表达式。
    因为没有设计运行这么自定义语言可以嵌套定义函数,所以函数体不涵盖在block里了。
    返回参数可以为零,可以是一串参数。

    funcname       ::= var
    args           ::= ( var | funcname | exp ) [ "," args ]
    arglist        ::= args [ "," "..." ] | "..."
    paramlist      ::= "(" [ arglist ] ")"
    functiondef    ::= def funcname paramlist block 
    stat           ::= return [explist] | functioncall
    functioncall   ::= funcname "(" [ args ] ")"
    

    对象

    这里点操作符只能用在实例对象或者包(package/module)的相关使用上。现在暂时就不管包了。
    语句stat增加了创建实例对象这一句!直接用类名赋值就是创建了,简单易懂。
    增加this关键字,指向本身。

    classname      ::= var
    classdef       ::= class classname [ extends classname ] classbody
    classbody      ::= "{" {  
    						(functiondef | 
    						varlist ( "=" | is ) explist)
    					} "}"
    exp            ::= classname 
    var            ::= var { "." ( var | functioncall ) }
    this           ::= classname
    

    数组

    数组内部可以嵌套数组!元素间用逗号分开。元素可以是表达式不能是赋值式子。
    增加了in关键字。
    数组的使用可以递归?就是不止一维数组,可以有许多维度。

    括号后面可以跟方括号,但是方括号后面不能跟括号,因为这里没有设计数组中可以存放变量——现在数组中只能放置常量。

    arrayname      ::= var
    elements       ::= NUMBER | STRING
    arraydef       ::= "[" { elements } "]" | "[" arraydef "]"
    exp            ::= var in arrayname | arraydef
    var            ::= var { "[" var "]" }
    

    高级数组代替类

    在LUA里只有表这个数据结构,但是也能通过setmetatable方法实现面向对象。
    因为数组和类的功能有重叠,都能存放数据,所以可以把二者合二为一。让数组可以存放函数,并且可以拥有继承和多态!!
    下面的数组允许多继承,存放变量、赋值式、函数。

    访问数组元素可通过索引[2]点操作符.a加引号的元素名"a",函数 .fun() 必须用点操作符来调用!

    elements       ::= var | 
    				   functiondef | 
    				   varlist ( "=" | is ) explist 
    arraynamelist  ::= arrayname { "," arrayname }
    arraydef       ::= [ extends arraynamelist with ] ( "[" { elements } "]" | "[" arraydef "]" ) 
    var            ::= var { "[" 
    						( var | 
    						""" elements """ ) 
    						"]" }
    this           ::= arrayname
    

    没有包就不能灵魂,鸡蛋都放在一个篮子里是不对的!
    可以通过一个变量来接收这个包,用这个变量来访问包内的元素,当然也可以直接访问。引用时可以引用整个包,或者包内的某个元素——为了使其他包内未引用的元素不被访问到,需要屏蔽。

    %import        ::= import """ dir/packname [ "." var ] """
    exp            ::= %import
    var            ::= [ packname "." ] var 
    functioncall   ::= [ packname "." ] funcname "(" [ args ] ")"
    

    实现不实现暂时不管了,就做个梦吧(笑)

    参考:《两周自制脚本语言》
    B站up的视频编程范式02BNF

    展开全文
  • 1、什么是BNF范式,什么又是EBNF范式?(在学习中经常会碰到用BNF范式描述的规则,老是忘记每个符号确切的作用,现在把他们一一罗列如下,亲手记录的东西应该能记住吧。。。-__-|||) 答:巴科斯范式及其扩展(BNF &...
  • HTTP协议: BNF范式

    千次阅读 2012-05-08 15:34:57
    BNF范式简析: 1. BNF范式结构: a. 命名规则 name = definition 以=字符分开 b. 标题 literal用引号包住,默认小写 eg: "hello" c. rule1 | rule2 分隔符,说明多规则的或关系 eg: yes | no d. (rule1 ...
  • Linux的命令格式其实也是依据BNF范式(巴科斯范式)的,BNF规定的是推导规则的集合,可简单的写为 &lt;符号&gt; ::= &lt;使用符号的表达式&gt; 或 symbol := alternative1 | alternative2 ... ...
  • 0.如何用BNF范式写优先级语法 1.关于一个数组的数学解析:数组就是一个函数,index->value的映射 2.BNF范式与正则表达式是不同的,之前一直搞混乱了。正则表达式是用来描述词法,BNF范式是用来描述语法的。 --------...
  • BNF就是巴科特·瑙尔式的缩写, 在计算机的史前时代(1950s),曾有一位大师,他奠定了现代计算机的基础,在他老人家的诸多成就之中,包括了对形式语言的研究,和发明了高级语言:FORTRAN。 为了纪念他老人家,我们把...
  • C语言的BNF范式表示

    千次阅读 2011-09-25 16:53:10
    bison 的规则中,对文法的描述,使用的是BNF范式,这是一种上下文无关文法。 用BNF来描述C语言,比自然语言简练多了,当然,逻辑上会有点复杂,不过平时可以研究研究。 以下代码来自 http://www.cs.man.ac.uk/~...
  • RFC2234(SIP遵循的BNF范式) 语法规范的扩展巴科斯范式:ABNF (RFC2234——Augmented BNF for Syntax Specifications: ABNF) 本备忘录的状态 本文档讲述了一种Internet社区的Internet标准跟踪协议,它需要...
  • 什么是BNF范式

    千次阅读 2007-11-22 09:26:00
    from:...838BE88BC5E4CDA3!778.entry什么是BNF范式,什么又是EBNF范式?巴科斯范式及其扩展BNF & Augmented BNF 什么是巴科斯范式? 巴科斯范式(BNF: Backus-Naur Form 的缩写)是由 Jo
  • BNF范式学习

    千次阅读 2017-02-20 16:00:42
    BNF 规定是推导规则(产生式)的集合,写为: ::= 这里的 符号> 是非终结符,而表达式由一个符号序列,或用指示选择的竖杠'|' 分隔的多个符号序列构成,每个符号序列整体都是左端的符号的一种可能的替代。从未...
  • BNF范式简介

    千次阅读 2015-04-24 21:23:11
    巴科斯范式(英语:Backus Normal Form,缩写为 BNF),又称为巴科斯-诺尔范式(英语:Backus-Naur Form,也译为巴科斯-瑙尔范式、巴克斯-诺尔范式),是一种用于表示上下文无关文法的语言,上下文无关文法描述了...
  • BNF 规定是推导规则(产生式)的集合,写为: <符号> ::= <使用符号的表达式> 这里的 <符号> 是非终结符,而表达式由一个符号序列,或用指示选择的竖杠'|' 分隔的多个符号序列构成,每个符号...
  • BNF 规定是推导规则(产生式)的集合,写为: &lt;符号&gt; ::= &lt;使用符号的表达式&gt; 这里的 &lt;符号&gt; 是非终结符,而表达式由一个符号序列,或用指示选择的竖杠'|' 分隔的多个...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 273
精华内容 109
关键字:

bnf范式