Сообщение Re[16]: Опциональные типы от 25.02.2017 11:42
Изменено 25.02.2017 12:02 vdimas
Re[16]: Опциональные типы
Здравствуйте, WolfHound, Вы писали:
WH>Но похоже ничего кроме трёпа от него так и не будет. Видимо показывать просто нечего.
Показываю.
Вот есть таблица переходов лексера. Она однозначна, в том смысле, что по каждому входному символу из этой таблицы есть ровно один переход.
Алгоритм парсинга по такой таблице, уверен, тебе понятен.
А теперь представим, что есть неоднозначность, которую можно разресолвить лишь "когда-нибудь потом". Из таблицы для такого разборщика по данному символу идёт список следующих состояний. На каждую альтернативу ты заводишь по новой "копии" текущего состояния парсера. Всё копировать не надо — цепочка предыдущего разбора будет общая для всех новых альтернатив. В какой-то момент по текущему символу есть переходы не у всех альтернативных веток. У кого нет перехода (переход в ошибку) — те ветки отмирают. Если отмерли все ветки — это ошибка во входной цепочке. Всё.
Далее.
Известно, что для класса регулярных грамматик (которые растут только справа или только слева) такую недетерминированную таблицу можно привести через известные несколько алгоритмов к детерминированной. Для случая леволинейной грамматики (а грамматики для лексера записывают почти всегда именно в этой форме) получим эдакий LR(0) разбор. 0 — потому что нет альтернатив, т.е. нет рекурсий/иерархий/дерева разбора, вернее дерево разбора имеет всегда константную вложенность — ровно 1, т.н. любая LR-"свертка" — это уже и есть конечный допустимый символ, это и есть выход лексера. Поэтому, если ты понимаешь, как работает автоматный лексер, то ты уже почти понимаешь как работает LR-разбор — в его случае "свернутая" цепочка нетерминалов заменяется другим нетерминалом и идёт разбор уже от него. Т.е. лексер выплёвывает нетерминал "куда-то наверх", а LR-парсер — себе же.
Итого, LR-разбор — это иерархия банальных тупейших лексеров, именно так. Т.е. каждая вложенность — это вызов эдакого "низлежащего лексера".
Например, в C#
Кстате, именно поэтому часто можно встретить scanerless GLR-парсер, бо а смысл выделять какой-то специальный уровень под автоматную грамматику, если у нас и так на каждом уровне иерархии зачастую идёт исключительно автоматная грамматика?
А если грамматика растёт как справа, так и слева и даже одновременно, то она уже не относится к классу регулярных — это контекстно-свободные грамматики и привести в общем случае подобную недетерминированную таблицу к детерминированной нельзя. Но можно же по такой таблице парсить! Но когда на длительном участке входных цепочек на каждом шаге будет однозначный переход, то на таких участках будет в точности повторение алгоритма лексера по затратности. Вот и всё кино, собсно.
Большинство языков, даже С+, на более 90% своих цепочках однозначны, т.е. участки параллельного протягивания нескольких вариантов обычно весьма и весьма коротки.
==============
Дальше наблюдения насчёт применимости алгоритма.
Я приводил сравнения — док-ты EDI бывают слишком неоднозначны, в сравнении с языками программирования. Например, конкретный прикладной идентификатор т.н. "цикла" (или что это именно цикл, а не альтернативная ветка, где идут несколько фиксированных полей, таких же как в одной из альтернатив в нефиксированном цикле) можно распознать только спустя несколько мегабайт данных. Именно поэтому любые алгоритмы с откатами и мемоизациями показывали себя именно в этом сценарии не плохо, а очень плохо.
А когда в случае EDI обычно идёт протягивание в среднем не более 2-х одновременных альтернативных веток парсера на такие "далекие расстояния", то параллельный алгоритм парсинга напрашивается сам собой.
В итоге, по результатам исследования своей предметной области я ВСЕГДА протягивал две непосредственные альтернативы + список дополнительных. Изначально шел сразу список, но это давало косвенность +1 на каждом шаге, к тому же на каждом участке получается цикл по списку, даже если у нас всего одна альтернатива. Затем я ввел одну непосредственную альтернативу + список остальных — стало лучше. В итоге лучший результат получил на двух непосредственных альтернативах + список остальных.
В итоге, в случае однозначных цепочек (т.е. когда работает лишь первая альтенатива) у меня всё отличие от алгоритма работы лексера по детерминированной таблице было в одном if на каждый входной НЕТЕРМИНАЛ.
Тут уже стоит вспомнить ту фишку современных процессоров, что если они правильно предсказали ветвление, то if будет бесплатен. А ветвление "предсказывается" по предыдущему его результату. Итого, уже на второй if в мегабайтной их последовательности (когда долго протягивается только одна или только две альтернативы) — совершенно бесплатен.
Ну а если больше альтернатив — то тут уже всего больше, появляется косвенность, получается проход for() по списку, получается заметное снижение скорости парсинга. Но я уже напоминал, что трафик нетерминалов резко меньше трафика терминалов. В моей предметной области — в десяток с лишним раз, отсюда такие низкие цифры разницы:
Плюс участки с неоднозначностями довольно коротки, опять повторюсь.
=========
А твои "быстрее лексера" — это спекуляция и нечистоплотность.
Дословно было сказано "на уровне лексера".
WH>Но похоже ничего кроме трёпа от него так и не будет. Видимо показывать просто нечего.
Показываю.
Вот есть таблица переходов лексера. Она однозначна, в том смысле, что по каждому входному символу из этой таблицы есть ровно один переход.
Алгоритм парсинга по такой таблице, уверен, тебе понятен.
А теперь представим, что есть неоднозначность, которую можно разресолвить лишь "когда-нибудь потом". Из таблицы для такого разборщика по данному символу идёт список следующих состояний. На каждую альтернативу ты заводишь по новой "копии" текущего состояния парсера. Всё копировать не надо — цепочка предыдущего разбора будет общая для всех новых альтернатив. В какой-то момент по текущему символу есть переходы не у всех альтернативных веток. У кого нет перехода (переход в ошибку) — те ветки отмирают. Если отмерли все ветки — это ошибка во входной цепочке. Всё.
Далее.
Известно, что для класса регулярных грамматик (которые растут только справа или только слева) такую недетерминированную таблицу можно привести через известные несколько алгоритмов к детерминированной. Для случая леволинейной грамматики (а грамматики для лексера записывают почти всегда именно в этой форме) получим эдакий LR(0) разбор. 0 — потому что нет альтернатив, т.е. нет рекурсий/иерархий/дерева разбора, вернее дерево разбора имеет всегда константную вложенность — ровно 1, т.н. любая LR-"свертка" — это уже и есть конечный допустимый символ, это и есть выход лексера. Поэтому, если ты понимаешь, как работает автоматный лексер, то ты уже почти понимаешь как работает LR-разбор — в его случае "свернутая" цепочка нетерминалов заменяется другим нетерминалом и идёт разбор уже от него. Т.е. лексер выплёвывает нетерминал "куда-то наверх", а LR-парсер — себе же.
Итого, LR-разбор — это иерархия банальных тупейших лексеров, именно так. Т.е. каждая вложенность — это вызов эдакого "низлежащего лексера".
Например, в C#
Вот эта изолированная цепочка относится к классу регулярных грамматик и соответственно её LR-парсинг столь же эффективен, да еще по точно такому же алгоритму по такой же таблице. На входе будет 8 символов-нетерминалов, полученных от лексера, на выходе — нетерминал, означающий заголовок описания класса.public class MyClass : Base1, Base2 {
Кстате, именно поэтому часто можно встретить scanerless GLR-парсер, бо а смысл выделять какой-то специальный уровень под автоматную грамматику, если у нас и так на каждом уровне иерархии зачастую идёт исключительно автоматная грамматика?
А если грамматика растёт как справа, так и слева и даже одновременно, то она уже не относится к классу регулярных — это контекстно-свободные грамматики и привести в общем случае подобную недетерминированную таблицу к детерминированной нельзя. Но можно же по такой таблице парсить! Но когда на длительном участке входных цепочек на каждом шаге будет однозначный переход, то на таких участках будет в точности повторение алгоритма лексера по затратности. Вот и всё кино, собсно.
Большинство языков, даже С+, на более 90% своих цепочках однозначны, т.е. участки параллельного протягивания нескольких вариантов обычно весьма и весьма коротки.
==============
Дальше наблюдения насчёт применимости алгоритма.
Я приводил сравнения — док-ты EDI бывают слишком неоднозначны, в сравнении с языками программирования. Например, конкретный прикладной идентификатор т.н. "цикла" (или что это именно цикл, а не альтернативная ветка, где идут несколько фиксированных полей, таких же как в одной из альтернатив в нефиксированном цикле) можно распознать только спустя несколько мегабайт данных. Именно поэтому любые алгоритмы с откатами и мемоизациями показывали себя именно в этом сценарии не плохо, а очень плохо.
А когда в случае EDI обычно идёт протягивание в среднем не более 2-х одновременных альтернативных веток парсера на такие "далекие расстояния", то параллельный алгоритм парсинга напрашивается сам собой.
В итоге, по результатам исследования своей предметной области я ВСЕГДА протягивал две непосредственные альтернативы + список дополнительных. Изначально шел сразу список, но это давало косвенность +1 на каждом шаге, к тому же на каждом участке получается цикл по списку, даже если у нас всего одна альтернатива. Затем я ввел одну непосредственную альтернативу + список остальных — стало лучше. В итоге лучший результат получил на двух непосредственных альтернативах + список остальных.
В итоге, в случае однозначных цепочек (т.е. когда работает лишь первая альтенатива) у меня всё отличие от алгоритма работы лексера по детерминированной таблице было в одном if на каждый входной НЕТЕРМИНАЛ.
Тут уже стоит вспомнить ту фишку современных процессоров, что если они правильно предсказали ветвление, то if будет бесплатен. А ветвление "предсказывается" по предыдущему его результату. Итого, уже на второй if в мегабайтной их последовательности (когда долго протягивается только одна или только две альтернативы) — совершенно бесплатен.
Ну а если больше альтернатив — то тут уже всего больше, появляется косвенность, получается проход for() по списку, получается заметное снижение скорости парсинга. Но я уже напоминал, что трафик нетерминалов резко меньше трафика терминалов. В моей предметной области — в десяток с лишним раз, отсюда такие низкие цифры разницы:
подключение парсера к работающему лексеру даёт в среднем 5-10% проседания производительности.
Плюс участки с неоднозначностями довольно коротки, опять повторюсь.
=========
А твои "быстрее лексера" — это спекуляция и нечистоплотность.
Дословно было сказано "на уровне лексера".
Re[16]: Опциональные типы
Здравствуйте, WolfHound, Вы писали:
WH>Но похоже ничего кроме трёпа от него так и не будет. Видимо показывать просто нечего.
Показываю.
Вот есть таблица переходов лексера. Она однозначна, в том смысле, что по каждому входному символу из этой таблицы есть ровно один переход.
Алгоритм парсинга по такой таблице, уверен, тебе понятен.
А теперь представим, что есть неоднозначность, которую можно разресолвить лишь "когда-нибудь потом". Из таблицы для такого разборщика по данному символу идёт список следующих состояний. На каждую альтернативу ты заводишь по новой "копии" текущего состояния парсера. Всё копировать не надо — цепочка предыдущего разбора будет общая для всех новых альтернатив. В какой-то момент по текущему символу есть переходы не у всех альтернативных веток. У кого нет перехода (переход в ошибку) — те ветки отмирают. Если отмерли все ветки или в конце разбора будет более одной ветки — это ошибка во входной цепочке. Всё.
Далее.
Известно, что для класса регулярных грамматик (которые растут только справа или только слева) такую недетерминированную таблицу можно привести через известные несколько алгоритмов к детерминированной. Для случая леволинейной грамматики (а грамматики для лексера записывают почти всегда именно в этой форме) получим эдакий LR(0) разбор. 0 — потому что нет альтернатив, т.е. нет рекурсий/иерархий/дерева разбора, вернее дерево разбора имеет всегда константную вложенность — ровно 1, т.н. любая LR-"свертка" — это уже и есть конечный допустимый символ, это и есть выход лексера. Поэтому, если ты понимаешь, как работает автоматный лексер, то ты уже почти понимаешь как работает LR-разбор — в его случае "свернутая" цепочка нетерминалов заменяется другим нетерминалом и идёт разбор уже от него. Т.е. лексер выплёвывает нетерминал "куда-то наверх", а LR-парсер — себе же.
Итого, LR-разбор — это иерархия банальных тупейших лексеров, именно так. Т.е. каждая вложенность — это вызов эдакого "низлежащего лексера".
Например, в C#
Кстате, именно поэтому часто можно встретить scanerless GLR-парсер, бо а смысл выделять какой-то специальный уровень под автоматную грамматику, если у нас и так на каждом уровне иерархии зачастую идёт исключительно автоматная грамматика?
А если грамматика растёт как справа, так и слева и даже одновременно, то она уже не относится к классу регулярных — это контекстно-свободные грамматики и привести в общем случае подобную недетерминированную таблицу к детерминированной нельзя. Но можно же по такой таблице парсить! Но когда на длительном участке входных цепочек на каждом шаге будет однозначный переход, то на таких участках будет в точности повторение алгоритма лексера по затратности. Вот и всё кино, собсно.
Большинство языков, даже С+, на более 90% своих цепочках однозначны, т.е. участки параллельного протягивания нескольких вариантов обычно весьма и весьма коротки.
==============
Дальше наблюдения насчёт применимости алгоритма.
Я приводил сравнения — док-ты EDI бывают слишком неоднозначны, в сравнении с языками программирования. Например, конкретный прикладной идентификатор т.н. "цикла" (или что это именно цикл, а не альтернативная ветка, где идут несколько фиксированных полей, таких же как в одной из альтернатив в нефиксированном цикле) можно распознать только спустя несколько мегабайт данных. Именно поэтому любые алгоритмы с откатами и мемоизациями показывали себя именно в этом сценарии не плохо, а очень плохо.
А когда в случае EDI обычно идёт протягивание в среднем не более 2-х одновременных альтернативных веток парсера на такие "далекие расстояния", то параллельный алгоритм парсинга напрашивается сам собой.
В итоге, по результатам исследования своей предметной области я ВСЕГДА протягивал две непосредственные альтернативы + список дополнительных. Изначально шел сразу список, но это давало косвенность +1 на каждом шаге, к тому же на каждом участке получается цикл по списку, даже если у нас всего одна альтернатива. Затем я ввел одну непосредственную альтернативу + список остальных — стало лучше. В итоге лучший результат получил на двух непосредственных альтернативах + список остальных.
В итоге, в случае однозначных цепочек (т.е. когда работает лишь первая альтенатива) у меня всё отличие от алгоритма работы лексера по детерминированной таблице было в одном if на каждый входной НЕТЕРМИНАЛ.
Тут уже стоит вспомнить ту фишку современных процессоров, что если они правильно предсказали ветвление, то if будет бесплатен. А ветвление "предсказывается" по предыдущему его результату. Итого, уже на второй if в мегабайтной их последовательности (когда долго протягивается только одна или только две альтернативы) — совершенно бесплатен.
Ну а если больше альтернатив — то тут уже всего больше, появляется косвенность, получается проход for() по списку, получается заметное снижение скорости парсинга. Но я уже напоминал, что трафик нетерминалов резко меньше трафика терминалов. В моей предметной области — в десяток с лишним раз, отсюда такие низкие цифры разницы:
Плюс участки с неоднозначностями довольно коротки, опять повторюсь.
=========
А твои "быстрее лексера" — это спекуляция и нечистоплотность.
Дословно было сказано "на уровне лексера".
WH>Но похоже ничего кроме трёпа от него так и не будет. Видимо показывать просто нечего.
Показываю.
Вот есть таблица переходов лексера. Она однозначна, в том смысле, что по каждому входному символу из этой таблицы есть ровно один переход.
Алгоритм парсинга по такой таблице, уверен, тебе понятен.
А теперь представим, что есть неоднозначность, которую можно разресолвить лишь "когда-нибудь потом". Из таблицы для такого разборщика по данному символу идёт список следующих состояний. На каждую альтернативу ты заводишь по новой "копии" текущего состояния парсера. Всё копировать не надо — цепочка предыдущего разбора будет общая для всех новых альтернатив. В какой-то момент по текущему символу есть переходы не у всех альтернативных веток. У кого нет перехода (переход в ошибку) — те ветки отмирают. Если отмерли все ветки или в конце разбора будет более одной ветки — это ошибка во входной цепочке. Всё.
Далее.
Известно, что для класса регулярных грамматик (которые растут только справа или только слева) такую недетерминированную таблицу можно привести через известные несколько алгоритмов к детерминированной. Для случая леволинейной грамматики (а грамматики для лексера записывают почти всегда именно в этой форме) получим эдакий LR(0) разбор. 0 — потому что нет альтернатив, т.е. нет рекурсий/иерархий/дерева разбора, вернее дерево разбора имеет всегда константную вложенность — ровно 1, т.н. любая LR-"свертка" — это уже и есть конечный допустимый символ, это и есть выход лексера. Поэтому, если ты понимаешь, как работает автоматный лексер, то ты уже почти понимаешь как работает LR-разбор — в его случае "свернутая" цепочка нетерминалов заменяется другим нетерминалом и идёт разбор уже от него. Т.е. лексер выплёвывает нетерминал "куда-то наверх", а LR-парсер — себе же.
Итого, LR-разбор — это иерархия банальных тупейших лексеров, именно так. Т.е. каждая вложенность — это вызов эдакого "низлежащего лексера".
Например, в C#
Вот эта изолированная цепочка относится к классу регулярных грамматик и соответственно её LR-парсинг столь же эффективен, да еще по точно такому же алгоритму по такой же таблице. На входе будет 8 символов-нетерминалов, полученных от лексера, на выходе — нетерминал, означающий заголовок описания класса.public class MyClass : Base1, Base2 {
Кстате, именно поэтому часто можно встретить scanerless GLR-парсер, бо а смысл выделять какой-то специальный уровень под автоматную грамматику, если у нас и так на каждом уровне иерархии зачастую идёт исключительно автоматная грамматика?
А если грамматика растёт как справа, так и слева и даже одновременно, то она уже не относится к классу регулярных — это контекстно-свободные грамматики и привести в общем случае подобную недетерминированную таблицу к детерминированной нельзя. Но можно же по такой таблице парсить! Но когда на длительном участке входных цепочек на каждом шаге будет однозначный переход, то на таких участках будет в точности повторение алгоритма лексера по затратности. Вот и всё кино, собсно.
Большинство языков, даже С+, на более 90% своих цепочках однозначны, т.е. участки параллельного протягивания нескольких вариантов обычно весьма и весьма коротки.
==============
Дальше наблюдения насчёт применимости алгоритма.
Я приводил сравнения — док-ты EDI бывают слишком неоднозначны, в сравнении с языками программирования. Например, конкретный прикладной идентификатор т.н. "цикла" (или что это именно цикл, а не альтернативная ветка, где идут несколько фиксированных полей, таких же как в одной из альтернатив в нефиксированном цикле) можно распознать только спустя несколько мегабайт данных. Именно поэтому любые алгоритмы с откатами и мемоизациями показывали себя именно в этом сценарии не плохо, а очень плохо.
А когда в случае EDI обычно идёт протягивание в среднем не более 2-х одновременных альтернативных веток парсера на такие "далекие расстояния", то параллельный алгоритм парсинга напрашивается сам собой.
В итоге, по результатам исследования своей предметной области я ВСЕГДА протягивал две непосредственные альтернативы + список дополнительных. Изначально шел сразу список, но это давало косвенность +1 на каждом шаге, к тому же на каждом участке получается цикл по списку, даже если у нас всего одна альтернатива. Затем я ввел одну непосредственную альтернативу + список остальных — стало лучше. В итоге лучший результат получил на двух непосредственных альтернативах + список остальных.
В итоге, в случае однозначных цепочек (т.е. когда работает лишь первая альтенатива) у меня всё отличие от алгоритма работы лексера по детерминированной таблице было в одном if на каждый входной НЕТЕРМИНАЛ.
Тут уже стоит вспомнить ту фишку современных процессоров, что если они правильно предсказали ветвление, то if будет бесплатен. А ветвление "предсказывается" по предыдущему его результату. Итого, уже на второй if в мегабайтной их последовательности (когда долго протягивается только одна или только две альтернативы) — совершенно бесплатен.
Ну а если больше альтернатив — то тут уже всего больше, появляется косвенность, получается проход for() по списку, получается заметное снижение скорости парсинга. Но я уже напоминал, что трафик нетерминалов резко меньше трафика терминалов. В моей предметной области — в десяток с лишним раз, отсюда такие низкие цифры разницы:
подключение парсера к работающему лексеру даёт в среднем 5-10% проседания производительности.
Плюс участки с неоднозначностями довольно коротки, опять повторюсь.
=========
А твои "быстрее лексера" — это спекуляция и нечистоплотность.
Дословно было сказано "на уровне лексера".