BNF转EBNF 混淆左右递归的区别

Question

我有这个 BNF 规则：

<S> ->  <A> b | <A> b <C>
<A> ->  a | a <A>
<C> ->  c | <C> c

我想把它变成 EBNF 规则，但是我对 <A> and <C> 中的左右递归感到困惑，它在 EBNF 中有何不同或相同？

这是我所做的：

To convert: <S> -> <A> b | <A> b <C> to EBNF
1.   <S> -> <A> b | <A> b <C>
2.   <S> -> <A> b [<C>]
3.   <S> -> <A> b (<C>)?
To convert: <A> - >  a | a<A>  to EBNF
1.  <A> - >  a | a<A>  
2.  < A> - >  a | a{a}
3.  < A> - >  a | a{a}+    
4.  <A>  - > a+
To convert: <C> -> c | <C> c to EBNF
1.  <C> -> c | <C> c
2.  <C> -> c | {c} c
3.  <C> -> c | {c}+ c
4.  <C> -> c+

Answer 1

他们会是一样的。例如，<C> 将匹配以下所有内容：

c
c c
c c c
c c c c c c c c c c c c c c c c c c c c c

并且 <A> 将匹配以下所有内容：

a
a a
a a a
a a a a a a a a a a a a a a a a a a a a a

因此，两者的 EBNF 将匹配。一般来说，如果左递归在最开始，右递归在最后，它们看起来会很相似：

<A> -> a | a <A>
<C> -> c | <L> c

EBNF:
<A> -> a | a a*
<A> -> a+
<C> -> c | c* c
<C> -> c+

这个 EBNF 文法没有表达的是表达式是如何被解析的。在从 BNF 转换为 EBNF 时，您失去了表达能力。但是，您可以通过避免 +:

来使其明确

<A> -> a a*
<C> -> c* c

当然，两者都归约到 E+ 的事实意味着您可以将它们解析为左递归或右递归，结果并不重要。这并不总是正确的——(2-3)-4 ≠ 2-(3-4)——但你确实可以选择将 <C> 转换为右递归产生式，结果将是相同的。

BNF转EBNF 混淆左右递归的区别

Converting BNF to EBNF confused about the difference between left and right recursion

regex

bnf

ebnf