Всем хорош алгоритм Эрли, да только работает он с BNF. А описывать грамматику удобнее в EBNF.
И поэтому возникает задача обеспечения прозрачного двухстороннего преобразования внешней грамматики во внутреннюю (производную) грамматику.
Под прозрачностью здесь понимается сокрытие этого процесса от пользователя.
Под двухстороннестью понимается возможность получения артефакта оригинальной грамматики при возникновении ошибки парсинга с использованием внутренней грамматики.
В итоге, сначала нужно написать:
1) представление внешней грамматики в памяти;
2) представление внутренней грамматики в памяти;
3) примитивы для отображения грамматик друг на друга;
4) парсер грамматики EBNF из текстового вида во внешнее представление в памяти;
5) код для преобразования ссылок на внутренную грамматику в термины текстового вида исходной EBNF.
Правила преобразования EBNF в BNF просты:
EBNF have 3 additional constructs:
- repetitions
- optional parts
- alternatives
Repetitions
Can be replaced with additional recursive rule
A := B, { C }, D ; (* repetition of C *)
can be replaced with
A0 := ;
A0 := C, A0; // supplementary rule, which express repetition through tail recursion
A1 := B, A0, D; (* final rule = A *)
I don't know the reason, why { } mean 0 to many repetitions instead of 1 to many.
Optional parts
A := B, [ C ], D ; (* C is optional *)
replaced with 2 rules
A1 := B, D ;
A1 := B, C, D ;
What if there N optional parts (and 2N variants of their presence)?
A := B, [ C ], [ D ], [ E ], [ F ], G ;
A0 := ;
A0 := C;
A1 := ;
A1 := D;
A2 := ;
A2 := E;
A3 := ;
A3 := F;
A4 := B, A0, A1, A2, A3, G; (* final rule = A *)
Alternatives
A := B | C;
replaced with N rules - one for each alternative branch:
A1 := B;
A1 := C;