Русские вычислители

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Русские вычислители » Вычислители по-русски » Прозрачное преобразование EBNF->BNF


Прозрачное преобразование EBNF->BNF

Сообщений 1 страница 3 из 3

1

Всем хорош алгоритм Эрли, да только работает он с 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;

0

2

ВежливыйЛис

да только работает он с BNF. А описывать грамматику удобнее в EBNF.

Это семейства языков. Тут лучше уточнять диалекты.

Под прозрачностью здесь понимается сокрытие этого процесса от пользователя.

Кхе-кхе. Это всё равно что солёный сахар.
Под прозрачностью тут надо понимать ссылку на исходную грамматику. Или как вы выразились наличие артефакта. А вообще это давно зовётся таблицей символов.

0

3

Павиа написал(а):

Это семейства языков. Тут лучше уточнять диалекты


Есть два англоязычных термина:
1) EBNF
      (The International Organization for Standardization has adopted an EBNF standard (ISO/IEC 14977))
2) EBNF family
      (то есть, кроме EBNF ещё есть ABNF, описанная в RFC 5234)

Я имею в виду первый.

Павиа написал(а):

вообще это давно зовётся таблицей символов


Таблицей символов зовётся другое (а именно - список идентификаторов на следующей стадии разбора)

Отредактировано ВежливыйЛис (05.04.2016 17:46:47)

0


Вы здесь » Русские вычислители » Вычислители по-русски » Прозрачное преобразование EBNF->BNF


форум на 24bb Создать форум бесплатно