перепишет рекурсивное правило BNF с итерационным

Question

Посмотрите на следующий рекурсивного правиле BNF

(1) X = Xa | b 

Это создает предложения типа

X = b 
X = ba 
X = baa 
X = baaa 
... 

Это можно записать в виде

(2) X = b a* 

где правая рука сторона не является рекурсивной

Теперь посмотрим на следующем рекурсивном правило BNF

(3) X = { X } | b 

Это производит предложения, как

X = b 
X = {b} 
X = {{b}} 
X = {{{b}}} 
... 

Есть ли способ переписать правила (3) в не рекурсивным образом, аналогично, как мы делали когда мы переписали правило (1) на правило (2).

Обратите внимание, что X = {* b} * не подходит, поскольку скобки необходимо сбалансировать.

Answer 1

Не знаю, можно ли ответить на указанный выше вопрос. Причина вышеизложенного заключалась в том, что я хотел избежать бесконечного цикла в своем парсере (написанном на Java). Один из способов заключался в том, чтобы гарантировать, что правила BNF не являются рекурсивными, поэтому мой вопрос. Но другой способ - использовать рекурсивное правило, но избегать бесконечного цикла внутри моей (Java) программы. Оказывается, вы можете избежать циклов ленивым инстанцированием.

Например рассмотрим следующие правила:

expression = term ('+' term)*; 
term  = factor ('*' factor)*; 
factor  = '(' expression ')' | Num; 

выражение() вызывает термин(), который вызывает фактор(), который вызывает выражение(), таким образом, мы можем в конечном итоге с бесконечным циклом. Чтобы избежать этого, мы можем использовать ленивую экземпляра, поэтому вместо того, чтобы писать что-то вроде:

public Parser expression() { 
    expression = new ... 
    return expression; 
} 

мы вместо того, чтобы написать:

public Parser expression() { 
    if (expression == null) { 
     expression = new ... 
    } 
    return expression; 
} 

Заметим, что вы должны объявить выражение в качестве переменной экземпляра, чтобы получить эту работу.