Преобразование BNF в EBNF смущает разница между левой и правой рекурсией - PullRequest
Новая
       99

Преобразование BNF в EBNF смущает разница между левой и правой рекурсией

0 голосов
/ 27 апреля 2020

У меня есть это правило 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+

1 Ответ

0 голосов
/ 01 мая 2020

Они будут такими же. Например, <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 не делает express, как выражение анализируется При переходе от BNF к EBNF вы теряете выразительность. Однако вы можете сделать это явно, избегая +: 

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

. Конечно, тот факт, что оба сокращаются до E+, означает, что вы можете анализировать их как леворекурсивные или праворекурсивные, и результат не имеет значения. Это не всегда так - (2-3)-4 &ne; 2-(3-4), но у вас есть возможность конвертировать <C> в правильно-рекурсивное производство, и результат будет таким же.

...