废话不多说,能看到这篇文章的相信已经学了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?
不难看出,这是说一个句子的组成结构.
我们应该如何转换呢?
- 我们可以根据括号从大到小一步一步的分开.比如这里的S显然是由两大部分组成的.((word +) || ‘,’) 和 (‘.’ | ‘?’)那么我们就可以自己创造两个非终结符来表示这两个部分:做如下BNF: S::= sub_s symbol.
- 由此递归的处理我们已经转换的每一个非终结符.比如上面我们已经得到的sub_s可以自己继续根据规则转换成sub_s::= words ‘,’ sub_s
- 直到拆到最后一个括号比如(word+) 按照规则就可以转化为 words::= word words, words::=word. 那么就算是完成了.
S ::= sub_s symbol
sub_s ::= words ',' sub_s
words::=word words
words::=word
symbol ::= '.' | '?'
Comments
(no comments...maybe you can be the first?)