Search code examples
regexbnfebnf

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

I have this BNF rule: 

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

i want to turn it into EBNF rule however i am confused about the left and right recursion in the <A> and <C>, how will it differs in EBNF or they will be the same?

Here is what i did:

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+
Solution

  • They'll be the same. For example, <C> will match all of the following:

    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

    And <A> will match all of the following:

    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

    As a result, the EBNF for both will match. In general, if the left recursion is at the very beginning and the right recursion is at the very end, they will look similar:

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

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

    What this EBNF grammar doesn't express is how the expression is parsed. In converting from BNF to EBNF, you lose the expressiveness. However, you can make it explicit by avoiding +:

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

    Of course, the fact that both reduce to E+ means you can parse them as left-recursive or right-recursive, and the result won't matter. That's not always true—(2-3)-4 ≠ 2-(3-4)—but you do have the option of converting <C> to a right-recursive production, and the result will be the same.