#> RESTKHZ _

休止千鹤 | 我依旧是一名平凡的学生

EBNF转换BNF的规则和例子(巴科斯范式)

  休止千鹤  |    09/03/2021

废话不多说,能看到这篇文章的相信已经学了BNF的内容.至于这个东西和上下文无关文法的关系,和Algol的关系,在这里就不赘述.

首先我们知道EBNF是BNF的扩展.添加了一些符号.而这些符号规则和正则表达式又有关系.

由于md编辑器的问题, “竖线”为| ,双竖线为||, ε 为空

EBNF 含义 等价BNF
X::=u(v)w 括号,优先级 X::=uYw Y::=v
X::=u(v1竖线v2)w Alternative X::=uYw Y::=v1 Y::v2
X::=u[v]w 可选,可有可无 X::=uYw Y::=v Y::= ε
X::=u v? w 可选,可有可无 X::=uYw Y::=v Y::= ε
X::=uv*w 重复 X::=uYw Y::=vY Y::= ε
X::=uv+w 重复,v至少出现一次 X::=uYw Y::=vY Y::= v
X::= u(v双竖线s)w 分隔 X::=uYw Y::=vsY Y::=v

表格来自某个大学讲义

那么我们来看一个例子

S ::= ((word +) || ',') ('.' | '?')

这是一个EBNF, 我们如何把它转化成BNF?
不难看出,这是说一个句子的组成结构.
我们应该如何转换呢?

  1. 我们可以根据括号从大到小一步一步的分开.比如这里的S显然是由两大部分组成的.((word +) || ‘,’) 和 (‘.’ | ‘?’)那么我们就可以自己创造两个非终结符来表示这两个部分:做如下BNF: S::= sub_s symbol.
  2. 由此递归的处理我们已经转换的每一个非终结符.比如上面我们已经得到的sub_s可以自己继续根据规则转换成sub_s::= words ‘,’ sub_s
  3. 直到拆到最后一个括号比如(word+) 按照规则就可以转化为 words::= word words, words::=word. 那么就算是完成了.
S ::= sub_s symbol
sub_s ::= words ',' sub_s
words::=word words
words::=word
symbol ::= '.' | '?'

 views:34

 Comments


(no comments...maybe you can be the first?)