ПО, ЭВМ и АСУ из Таможенного Союза

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

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


Вы здесь » ПО, ЭВМ и АСУ из Таможенного Союза » контекстно-свободные грамматики » О склеивании выхода парсера со входом сканера


О склеивании выхода парсера со входом сканера

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

1

В некоторых языках есть возможность передавать компилятору длинные строки, записывая их кусками в нескольких строках текстового редактора.
Для того, чтобы компилятору было ясно, что это не несколько разных строк, а одна длинная, перед переводами строки ставят знак "обратный слеш" - \

Как это обрабатывать. Во первых, есть разница - встречается обратный слеш в символьной строке или в основном тексте (например у budden специальные строки, из которых удаляются начальные пробелы). Эта разница заключается в том, что содержимое строки и код описывают разные правила грамматики. Значит описание слеша попадёт в граматику минимум два раза. Во-вторых, есть ещё комментарии, которые тоже могут обрабатываться особо.

Почему надо вносить обработку склеиваний в грамматику комиплятора, а не сделать препроцессор, который всё просклеивает заранее и передаст обработанный текст на вход компилятора? Потому что в первом случае информация об исходных номерах строк доступна, а во-втором потеряется.
Почему потеряется? Потому что директива #line должна располагаться на отдельной строке. Это значит, что нельзя указать разные номера исходных строк для разных частей длинной "логической" строки.

Как задача передачи информации об исходных положениях токенов решается в компиляторе C++? Неизвестно.
preprocessor macro __LINE__ and __FILE__. They are predefined macros and part of the C/C++ standard. During preprocessing, they are replaced respectively by a constant string holding an integer representing the current line number and by the current file name.
The #line directive tells the preprocessor ( почему не tells to the compiler??? ) to change the compiler's internally stored line number and filename to a given line number and filename.
The C preprocessor informs the C compiler of the location in your source code where each token came from.
#line digit-sequence ["filename"]
#line preprocessing_expression
http://www.complete-concrete-concise.co … -directive
# must be the first character on the line or the first character on the line following optional white space.
Spaces or tabs are permitted between the # and line, but not escape characters or other symbols or macros.
The preprocessor removes white space and concatenates the # and line together.
If anything follows the #line directive (other than white space) then the program is malformed.
https://gcc.gnu.org/onlinedocs/cpp/Line-Control.html
#line do not have any effect on ‘#include’’s idea of the directory containing the current file.

Если бы от препроцессора компилятору передавался бы не отпрепроцешшеный текст, а набор фрагментов текста с позициями и именами исходных файлов, то можно было бы обработку склеивания разместить в препроцессоре.
Для того, чтобы передавать набор фрагментов текста и позиции нужно определить API (и ABI ?).
Похожее API есть у сканнера (он же лексер), там дополнительно передаётся "код токена".

Собственно, надо придумать, как к парсеру прикрутить похожий интерфейс, чтобы состыковать выход парсера предыдущей стадии разбора с входом сканера следующей стадии. В случае использования scannerless-парсеров задача их последовательной состыковки всё равно остаётся.

Схожая задача разбиения грамматики на уровни возникает так же при раскрашивании текста (синтаксической подсветке). Есть грамматика для раскрашивания (попроще), а есть для анализа (посложнее). Хорошо бы, чтобы вторая пользовалась полуфабрикатами, произведёнными первой.

Отредактировано Лис (2018-01-03 12:34:08)

0

2

Ещё две мысли:
1) для обработки конкретно строк, комментариев и "склеивания" не нужен парсер. Хватит и сканера. Тогда надо соединить выход сканера со входом следующего сканера, чтобы были переданы исходные позиции символов.
2) сами позиции (разметка отрезков текста) - это паттерн flyweight. "Логически" позиция есть у каждого символа, но создавать столько объектов позиций было бы слишком накладно, поэтому смежные символы описываются группой.

Однако в общем случае соединения сканеров недостаточно.
Например в файле конфигурации может быть директива, у которой параметр - строка. А в строке - регулярное выражение.
Хотелось бы общий синтаксис описать в одной грамматике, синтаксис регулярных выражений в другой. Где две грамматики, там два парсера.
Как в тексте первой грамматики указать, что в фрагменте используется вторая?

Должна быть какая-то директива, подключающая вторую грамматику, и какой-то синтаксис, позволяющий в правиле использовать ссылку на вторую грамматику...

В семантической части правила первой грамматики нужно иметь возможность упоминать/производить какие-либо действия с элементами второй грамматики. Два варианта:
1) как-то отсечь корень (и возможно несколько смежных улов) дерева для второй грамматики. а оставшиеся узлы интегрировать в дерево первой грамматики;
Например указать, что в подключаемой грамматике может быть много стартовых правил (там есть уже директива %start), а так же, сколько вхождений может быть (0, 1, много). Тогда для грамматики препроцессора стартовыми можно было бы сделать "строку", "комментарий", и всё, что она бы вернула как сканер. А в первой грамматике указать, что они встречаются в любом порядке в произвольном количестве.
2) вместо отсекания ссылаться на нетерминальные символы по именам, выражениями типа XPath

Отредактировано Лис (2017-05-16 15:04:04)

0

3

В некоторых языках есть возможность передавать компилятору длинные строки, записывая их кусками в нескольких строках текстового редактора.
Для того, чтобы компилятору было ясно, что это не несколько разных строк, а одна длинная, перед переводами строки ставят знак "обратный слеш" - \

В питоне вроде как все что выровнено табуляцией между маркерами есть сплошной текст. То есть немного по-другому.

Значит описание слеша попадёт в граматику минимум два раза.

Ну и что?

Почему надо вносить обработку склеиваний в грамматику комиплятора, а не сделать препроцессор, который всё просклеивает заранее и передаст обработанный текст на вход компилятора? Потому что в первом случае информация об исходных номерах строк доступна, а во-втором потеряется.
Почему потеряется? Потому что директива #line должна располагаться на отдельной строке. Это значит, что нельзя указать разные номера исходных строк для разных частей длинной "логической" строки.

Нет, потому что препроцессор это нагородить непонятный огород, а склеивать строки по ходу их разбора вполне логично и легко реализуется. Только поэтому. Лис, помимо научных изысканий есть еще всегда экономика. Она гласит, что любое действие следует рассматривать в первую очередь с точки зрения максимизации прибыли. Иными словами препроцессор это сложно, долго и нафиг не надо в данном случае, когда есть естественный и понятный путь решения задачи.

Как задача передачи информации об исходных положениях токенов решается в компиляторе C++? Неизвестно.
preprocessor macro __LINE__ and __FILE__.

Весьма огорчает, что Вас периодически начинает тошнить буржуйскими текстами. Желание вникать в проблему сразу же отпадает.

Если бы от препроцессора компилятору передавался бы не отпрепроцешшеный текст, а набор фрагментов текста с позициями и именами исходных файлов, то можно было бы обработку склеивания разместить в препроцессоре.

О, уже давно придумали ответ на этот вопрос - в Лиспе. Разбирайте дерево, а не поток символов и будет Вам счастье.

Схожая задача разбиения грамматики на уровни возникает так же при раскрашивании текста (синтаксической подсветке). Есть грамматика для раскрашивания (попроще), а есть для анализа (посложнее). Хорошо бы, чтобы вторая пользовалась полуфабрикатами, произведёнными первой.

Именно так и было в В-1 и так будет в В-2. Для раскрашивания текста будет использоваться все тот же парсер.

Как в тексте первой грамматики указать, что в фрагменте используется вторая?

Без проблем. Эта фигня называется контекст. Ну и дальше высокая философия пошла уже. Давайте пример проблемы (не абстрактный), будем разбирать.

0

4

ВежливыйЛис написал(а):

Почему надо вносить обработку склеиваний в грамматику комиплятора, а не сделать препроцессор, который всё просклеивает заранее и передаст обработанный текст на вход компилятора? Потому что в первом случае информация об исходных номерах строк доступна, а во-втором потеряется.

Ну и пускай она потеряется, кому она после лексического разбора уже будет нужна то? На уровне грамматики это уже атомарный объект - токен, про которого разве что только позицию где он начинается и нужно знать.
Обработка склеивания должна происходить перед фазой лексического анализа или как первый этап этой фазы, в этом случае лексер встретив символ склеивания просто продолжит работу с начала новой строки или пропускает также еще и пробелы в ее начале для определенных типов токенов. При этом требуется только обновить информацию об текущей позиции обрабатываемого символа.

0

5

А по хорошему стоит вообще убрать возможность склеивания строк, это вредный и маловостребованный в современных языках механизм.
Он затрудняет работу с кодом и служит причиной возникновения трудно обнаруживаемых ошибок.
Грамматика языка должна быть устроена так что бы в подобном склеивании не было необходимости.
Возможность записи строковых литералов в несколько строк и для всех правил грамматики перенос строки должен обрабатываться таким же способом как и пробел. Вот все что нужно что бы в склеивании отпал смысл!

0

6

А по хорошему стоит вообще убрать возможность склеивания строк, это вредный и маловостребованный в современных языках механизм.

Не сказать, что вредный, но пользоваться действительно приходится не часто.

Отредактировано utkin (2018-04-24 07:14:25)

0

7

rst256 написал(а):

Ну и пускай она потеряется, кому она после лексического разбора уже будет нужна то? На уровне грамматики это уже атомарный объект - токен, про которого разве что только позицию где он начинается и нужно знать.Обработка склеивания должна происходить перед фазой лексического анализа или как первый этап этой фазы, в этом случае лексер встретив символ склеивания просто продолжит работу с начала новой строки или пропускает также еще и пробелы в ее начале для определенных типов токенов. При этом требуется только обновить информацию об текущей позиции обрабатываемого символа.

Номера строк нужны отладчику для пошаговой отладки. Поэтому их после лексического анализа помещают в токены и приходится их тянуть через весь код. А после лексического анализа в дело вступает прерпоцессор который склеивает строки. ДА и не только строки у меня так же склеиваются шестнадцатеричные числа (знак пунктуации $ и число ), символьные константы (знак пунктуации # и число), а в Си++ ещё и длинные строки - префикс L. 

На уровень грамматики нет смысла выносить. Так как после склейки надо выполнить макроподстановки. И только потом приступать к грамматике.

0

8

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

А после лексического анализа в дело вступает прерпоцессор который склеивает строки.

Интересно как же у вас тогда лексический анализатор сможет обработать еще не склеенные строки,
И даже если он сможет их правильно обработать тогда какой уже будет смысл в препроцессоре? Разве лексер не должен был преобразовать текст исходного кода в последовательность токенов? Значит никаких строк после лексера уже нет, что же тогда тут склеивать препроцессору?!
Что бы было возможно успешное выполнение лексического анализа, лексер у вас должен быть способен правильно распознавать все токены, в т.ч. и те что будут разделены на несколько склеенных строк. Тогда почему же тогда склейку должен делать не лексер, для которого это будет проще всего, а какой то "пришлый" препроцессор?
Неужели у программных модулей тоже бывает "блат", т.к. иных причин для применения тут особого препроцессора я не вижу.

0

9

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

Номера строк нужны отладчику для пошаговой отладки. Поэтому их после лексического анализа помещают в токены и приходится их тянуть через весь код.

Но так ведь никаких отличий для токенов склеенных из нескольких строк от обычных нет. И там и там нужно хранить позицию начала токена, а сам токен для отладчика есть монолитный и не делимый объект кода.
Про случаи же подобные подстановке фрагментов кода макросами препроцессоров с/с++ лучше вообще даже не думать, так как там делать просто нельзя!

0

10

Абстракция_Уровня_Н
Разновидность_Абстракции_Уровня_Н
Позиционная_Привязка_Уровня_Н

Уровень_Байтов
Абстракция - Байт
Разновидности - 256 штук
Позиционная привязка - индекс в файле

Уровень_Юникода
Абстракция - Кодовая_Позиция
Разновидности - под миллион
Позиционная привязка - номера байтов в файле

Уровень_Символов
Абстракция - Символ
Разновидности - с ударением, без ударения, варианты одного и того же символа (например 'ё')
Позиционная привязка - номера кодовых позиций

Уровень_Слов (Лексем)
Абстракция - лексемы, как они определяются в конфигурации сканера
Разновидности - все разные конкретные слова (лексемы) входного файла
Позиционная привязка - номера символов

Уровень_Правила_П
Абстракция - правило вывода
Разновидности - как правило было использовано
Позиционная привязка - лексемы, составляющие правило, или правила предыдущего уровня
(таких уровней много - столько же, сколько правил)

Всё вместе это образует одно дерево (а может и не только дерево), только разные уровни строятся разными механизмами
(просто автоматами или автоматами с магазинной памятью
И если добавить после МП-автомата какой-нибудь хитрый искатель зависимостей, то можно наверное впихнуть модель Смысл-Текст в ту же структуру.)

Что делать, если нужно вставить препроцессор?

делаем уровени:
- лексемы препроцссора
- грамматика препроцессора
и вставляем уровни препроцессора между уровнем символов и уровнем лексем,

Уровень препроцессора похож на уровень раскладки текста на листе (для анализа отступов как в питоне).

Зачем это нужно:
при наличии унифицированных интерфейсов
трассируемость от ошибки до исходника должна по-идее сохраниться.

Отредактировано Лис (2018-05-05 20:29:26)

0

11

а может и не только дерево

Все деревья являются графами.

просто автоматами или автоматами с магазинной памятью

Поэтому и нет в РФ развития ИТ, что у нас до сих пор такие анахроизмы. Чего бы нормально не сказать, автомат с использованием стека? Обязательно надо как-то извернуться.

делаем уровени:
- лексемы препроцссора
- грамматика препроцессора
и вставляем уровни препроцессора между уровнем символов и уровнем лексем,

Препроцессор это то что обрабатывает программу до начала основной обработки, когда еще нет никаких уровней лексем. Именно поэтому он и не нужен. Опять же символьная обработка - 19 век еще.  Уже давно есть возможность рассматривать строки, но Вы что! Это же ересь! Земля по-прежнему должна быть плоской...

Отредактировано utkin (2018-05-05 22:54:51)

0

12

Лис написал(а):

трассируемость от ошибки до исходника должна по-идее сохраниться.

А ведь для этого можно просто запускать в режиме интерпретации.

Лис написал(а):

можно наверное впихнуть модель Смысл-Текст в ту же структуру.)

Поскольку несколько томов её, скорее всего, почти никто не читал, то было бы неплохо уточнить что именно (или, например) от русского языка предполагается впихнуть.

Отредактировано MihalNik (2018-05-06 11:43:00)

0

13

ВежливыйЛис написал(а):

Потому что директива #line должна располагаться на отдельной строке. Это значит, что нельзя указать разные номера исходных строк для разных частей длинной "логической" строки.

А если директива стала такой?

#line digit-sequence ["filename"] {digit-sequence}

#line 21 "file1.c"
1234567890
file1.c:21: "1234567890"

#line 21 "file1.c" 7
1234567890
file1.c:21: "1234567"
file1.c:22: "890"

#line 21 "file1.c" 4 7
1234567890
file1.c:21: "1234"
file1.c:22: "567"
file1.c:23: "890"

0

14

rst256 написал(а):

А если директива стала такой?

Да, это интересная идея.

Код:
Т.е. раньше у нас были строки \
  с продолжениями.
А после препроцессинга \
  станут с директивами.
Код:
#line 1 "file.c" 41
Т.е. раньше у нас были строки   с продолжениями.
#line 2 "file.c" 33
А после препроцессинга   станут с директивами.

Q: Много ли работы удалось перенести на препроцессор?
Да, теперь кроме директивы line других директив нет
Q: Легче ли стало компилятору? Сильно ли упросталась граматика?
Ну, по крайней мере, теперь в текстах нет "склеиваний", а интервалы токенов задаются "магически", не через грамматику

Кстати, если склеивание не проводить заранее, то тогда становится более понятно, как мог бы работать препроцессор C:

Код:
#line 1 "file.c"
Т.е. раньше у нас были строки \
  с продолжениями.
#line 2 "file.c"
А после препроцессинга \
  станут с директивами.

понятно, что тут директивы line излишни, это просто для примера, как переносы строк могли бы быть включены в исходник для компилятора.

Однако, если мы всё равно делаем передачу интервалов токенов "магическим" способом, то почему бы всё равно не сделать как предлагается в первом сообщении - передавать информацию не через поток текста, а через API.

0

15

надо соединить выход сканера со входом следующего сканера

Нельзя просто так сделать склеить выход lex со входом другого lex, потому что yytext состоит из char или из wchar_t.

А должен быть произвольным типом.
Сделать переменную произвольным типом можно либо при помощи макросов,
либо при помощи шаблонизированных классов (templates).

При передаче из flex в bison можно макросом переопределить тип YYSTYPE.
Но внутри утилиты flex тип символов не переопределяется (если бы это делалось, тогда надо было бы ещё определять правила,
по которым символьные литералы из грамматики .l преобразуются в объекты этого типа (или этих типов))

Можно попробовать предпринять такой финт:
flex занимается преобразовыванием входных байтов в какой-то тип,
а дальше применяется несколько слоёв .y-грамматик, которые используются
как автоматные грамматики (автомат с магазинной памятью это ДКА если не использовать стек),
но у них более чётко определён интерфейс для вызова нижележащего уровня.

По-моему бизону можно дать директиву
%define api.prefix {lev02_}
и тогда yyparse превратится в lev02_parse
а в заголовке файла определять макроподстановку YY_DECL, чтобы вместо yylex вызывалась какая-нибудь ещё функция.

Задачей лексера второго уровня будет обход синтаксического дерева предыдущего уровня и выдача в типе токенов второго уровня.

Надо будет когда-нибудь попробовать.

Отредактировано Лис (2023-04-10 22:16:37)

0

16

%option bison-bridge
или ключ командной строки --bison-bridge при запуске flex из командной строки.
становится доступной переменная yylval и тип YYSTYPE (надо ещё подключить mygrammar.tab.h, сгенерированный bison-ом)

https://westes.github.io/flex/manual/Bison-Bridge.html

[[:digit:]]+  { yylval->num = atoi(yytext);   return NUMBER;}
[[:alnum:]]+  { yylval->str = strdup(yytext); return STRING;}
"="|";"       { return yytext[0];}

https://www.gnu.org/software/bison/manu … -Decl.html
While POSIX Yacc allows %type only for nonterminals,
Bison accepts that this directive be also applied to terminal symbols.

Отредактировано Лис (2023-04-13 03:12:15)

0


Вы здесь » ПО, ЭВМ и АСУ из Таможенного Союза » контекстно-свободные грамматики » О склеивании выхода парсера со входом сканера