文档章节

BNF Grammars 描述编程语言的语法

Freewheel
 Freewheel
发布于 2017/04/28 21:51
字数 668
阅读 68
收藏 0
  • 几个基础概念

    1. A sentence 句子 is a string of characters over some alphabet
    2. A language is a set of sentences 语言是一些句子的集合
    3. A lexeme is the lowest level syntactic unit of a language (e.g., *, sum, begin) 最小语法单位
    4. A token is a category of lexemes (e.g., identifier) 标识符
  • BNF 基础

    • In BNF, abstractions 抽象 are used to represent classes of syntactic structures--they act like
      syntactic variables 变量 (also called nonterminal symbols, or just nonterminals)
    • Terminals are lexemes or tokens
    • A rule 规则 has a left-hand side (LHS) 左侧, which is a nonterminal, and a right-hand side (RHS) 右侧, which is a string of terminals and/or nonterminals 左侧是nonterminal,右侧是terminals序列或者nonterminal
  • Nonterminals are often enclosed in angle brackets 角括号 Examples of BNF rules:
    <ident_list> -> identifier | identifier, <ident_list>
    <if_stmt> -> if <logic_expr> then <stmt>

  • Grammar: a finite non-empty set of rules 有限的非空规则集合

  • A start symbol is a special element of the nonterminals of a grammar 起始标志是特殊nonterminal

  • BNF规则

    • An abstraction (or nonterminal symbol) can have more than one RHS 右侧可以有多种规则
      e.g. <stmt> -> <single_stmt> | begin <stmt_list> end (一个语句可以是单个句子或者一些句子)
    • Syntactic lists are described using recursion 如何描述一个list
      <ident_list> -> ident| ident, <ident_list>
    • A derivation is a repeated application of rules, starting with the start symbol and ending with a
      sentence (all terminal symbols) 一次衍生指不断运用规则直到最后只剩一个全是terminal的语句
      e.g. 假设一个语言的语法如下
      输入图片说明
      那么以下就是一种衍生
      输入图片说明
  • Derivations 具体了解衍生

    • Every string of symbols in a derivation is a sentential form 衍生中每一行都是语句的形式
    • sentence is a sentential form that has only terminal symbols 语句只包含terminal
    • leftmost derivation is one in which the leftmost nonterminal in each sentential form is the one
      that is expanded 左侧衍生是被展开的对象总是以左侧优先(比如上述的例子),以此类推可知右侧
      衍生的定义
    • derivation may be neither leftmost nor rightmost 衍生可以既不是左侧衍生也不是右侧衍生(顺序
      不重要)
  • Parse Tree 解析树

    • A hierarchical representation of a derivation 用来表现衍生的一种树状表达方式
      e.g.
      输入图片说明
  • Ambiguity in Grammars 语法的含糊性

    • A grammar is ambiguous if and only if it generates a sentential form that has two or more distinct
      parse trees 如果一个语句可以用两个不同parse tree解析树表示,则说明这个语言的语法是含糊的
      e.g. 下面的语法是含糊的
      输入图片说明

    • 如何避免语法的含糊性?
      答: 不让两个以上的同名 nonterminals 出现在一个语句的右侧一个表达式里,比如上述的<expr>
      现在将上面的语法稍微修改,就是非含糊的
      输入图片说明

  • EBNF 是BNF的一个扩展版本,增加了一些更便利的语法(如 可选,重复等) 有兴趣可以参考
    Wikipedia EBNF

© 著作权归作者所有

Freewheel
粉丝 8
博文 83
码字总数 48265
作品 0
普陀
程序员
私信 提问
巴科斯范式(BNF)

什么是 巴科斯范式(BNF) , 是一种用形式化符号来描述给定语言的语法。 现在,几乎每一位新编程语言书籍的作者都使用巴科斯范式来定义编程语言的语法规则。 ------------------------------...

曾赛
2010/04/27
465
0
扩展巴科斯范式

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

曾赛
2010/05/14
196
0
我为什么要学 Common Lisp

我喜欢文本处理,以前热衷于使用数据库技术。现在用 Vim 和 Perl。我可以不假思索的用 Vim 写 Perl 代码。像聊天一样。Perl 语言的所有特性我都熟悉,几乎不用查询帮助文档。其他语言中关于文...

沙枣
2013/08/31
0
1
2017-12-24 为新语言编写Visual Studio Code语法高亮插件

本文源码库: program-in-chinese/quan4-highlighter 语法高亮是一个开发环境的基本功能. 此文尝试为之前的"圈4"语言(详见编程语言试验之Antlr4+JavaScript实现"圈4")编写一个高亮插件, 仅为演...

吴烜
03/06
0
0
前端要以正确的姿势学习编译原理(上篇)

前端要以正确的姿势学习编译原理(上篇) 发布于 02:05 文章被以下专栏收录

brambles
2018/05/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

AOP的学习(1)

AOP 理解AOP编程思想(面向方法、面向切面) spring AOP的概念 方面 -- 功能 目标 -- 原有方法 通知 -- 对原有方法增强的方法 连接点 -- 可以用来连接通知的地方(方法) 切入点 -- 将用来插入...

太猪-YJ
9分钟前
0
0
一张图看懂亮度、明度、光度、光亮度、明亮度

亮度、明度、光亮度,Luminance和Brightness、lightness其实都是一个意思,只是起名字太难了。 提出一个颜色模型后,由于明度的取值与别人的不同,为了表示区别所以就另想一个词而已。 因此在...

linsk1998
昨天
0
0
Python应用:python链表示例

前言 python链表应用源码示例,需要用到python os模块方法、函数和类的应用。 首先,先简单的来了解下什么是链表?链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是...

python小白1
昨天
2
0
Source Insight加载源码

Source Insight是一个图形化的源代码查看工具(当然也可以作为编译工具)。如果一个项目的源代码较多,此工具可以很方便地查找到源代码自建的依赖关系。 1.创建工程 下图为Snort源代码的文件...

天王盖地虎626
昨天
2
0
nginx-rtmp-module的缺陷分析(二)

nginx-rtmp-module使用指令push和pull来relay媒体流数据,以便分布式部署服务。 当nginx-rtmp-module作为边缘服务器(一般不会向边缘服务器推流)时,使用pull从源服务器获取媒体流数据,俗称...

YoungSagit
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部