Применение искинов - шоссе империализма (Стенгазета русификаторов ИТ)

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

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

Как вообще обрабатывается грамматика

Страница: 1

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

1

  • Автор: ВежливыйЛис
  • Администратор
  • Зарегистрирован: 2017-03-25
  • Приглашений: 0
  • Сообщений: 1116
  • Уважение: [+2/-1]
  • Позитив: [+4/-1]
  • Провел на форуме:
    7 дней 12 часов
  • Последний визит:
    2025-01-15 19:35:45

1) Сначала мы пишем грамматику в EBNF (потому что это самый свежий стандарт, и потому что это вообще стандарт. Не писать же в каком-то непонятном DSL? )
2) Затем мы автоматическим способом преобразуем EBNF в BNF (тут надо думать, как сохранять историю преобразований, чтобы отследить исходные позиции в тексте для выдачи сообщений об ошибках)
3) затем выполняем устранение пустых правил
4) затем преобразуем леворекурсивне дерево в праворекурсивное (это может раздуть грамматику)
5) затем пытаемся выделить регулярные части (автоматизированным способом) и для них генерируем ДКА
6) для всего остального применяем алгоритм ЭРЛИ с модификациями, который даёт линейную сложность (а не кубическую, и не квадратичную, как думают умники, которые не в теме)

Отредактировано Лис (2017-04-14 08:49:46)

0

2

  • Автор: Лис [М]
  • Участник
  • Лис [М]
  • Зарегистрирован: 2023-03-10
  • Приглашений: 0
  • Сообщений: 1119
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    6 дней 1 час
  • Последний визит:
    2024-11-27 23:25:17

В этой теме неправильно следующее:
1) BNF и EBNF имеют множество разных синтаксисов каждая.

Сравнение синтаксисов
ISO/IEC 14977:1996
EBNF от W3C
ABNF - RFC5234 (https://www.rfc-editor.org/rfc/rfc5234)

Какая-то грамматика:
https://github.com/ArsenShnurkov/rus_gr … ntax2.ebnf

Не по теме:
упоминание ABNF
NuShaman разбирается в теме BNF

2) у грамматик есть более-менее математические определения, в которых грамматика состоит из частей, например:

Контекстно-свободная грамматика (КС-грамматика) - это четвёрка:
G = (N, Σ, P, S), где:
N - конечное множество нетерминальных символов
Σ - конечное множество терминальных символов (токенов).
P - конечное множество правил вывода, т.е. правил формирования нетерминальных символов из токенов и нетерминальных символов.
S - начальный символ грамматики (скорее всего нетерминальный символ).
Правило переписывания (production)
Состоит из левой и правой части. В левой части находится нетерминальный символ
(Для терминальные символов не может существовать правил переписывания, потому что терминальные символы - это символы алфавита входной строки)
Правая часть - это цепочка из терминалов, нетерминалов и, возможно, дополнительного синтаксиса.

3) ну так вот, нужно писать библиотеку с объектами для каждой части и функциями, соответствующими операциям с этими объектами (добавить правило в грамматику, добавить терминал в правило, добавить нетерминал в правило)

4) на основе этой библиотеки делать работу с абстрактным синтаксическим деревом в действиях парсера грамматики

ну и обеспечивать взаимодействие - GObject Introspection

Отредактировано Лис (2023-04-01 16:43:42)

0

Страница: 1