LINUX.ORG.RU

Лексический анализ:


0

2

Добрый день, ребята! Посоветуйте годность по теме «Предсказывающий парсер» и «Лексический анализ». Конкретно интересует алгоритм реализации, т.к. хочу написать свой, для расширения кругозора.

Ответ на: комментарий от Norgat

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

И там (традиционно для американской школы) чморят LL-грамматики и восхваляют LALR. ТС-у же как раз LL нужна?

Для расширения кругозора - в той же википедии все достаточно подробно написано. Для практической разработки как правило не велосипедят и используют готовые инструменты: flex/re2c/ручной сканер для выделения токенов и bison(yacc)/lemon/whatever для собственно анализа.

А, для сильных духом есть еще boost::spirit и какой-то лексер тоже из буста. Трехэтажные шаблоны, невнятные сообщения об ошибках на 5 страниц и прочий духъ современного С++.

Вот в той же википедии пишут что есть готовый генератор синтаксических анализаторов ANTLR для LL(*) грамматик, но это далеко от мейнстрима

vmx ★★ ()
Ответ на: комментарий от vmx

И там (традиционно для американской школы) чморят LL-грамматики и восхваляют LALR. ТС-у же как раз LL нужна?

Там не просто так гнобяться LL грамматики. http://ru.wikipedia.org/wiki/LR-анализатор

LR-анализ может применяться к большему количеству языков, чем LL-анализ, а также лучше в части сообщения об ошибках, то есть он определяет синтаксические ошибки там, где вход не соответствует грамматике, как можно раньше. В отличие от этого, LL(k) (или, что хуже, даже LL(*)) анализаторы могут задерживать определение ошибки до другой ветки грамматики из-за отката, часто затрудняя определение места ошибки в местах общих длинных префиксов.

Я эту книжку не читал полностью, только пробегал глазами по диагонали. Т.к. у меня большая часть теории была в универе и нам её два семестра разжёвывали довольно подробно, а полное понимание сего безобразия ко мне пришло после реализации алгоритма LALR разбора (довольно жёсткий гад).

ТС'у вообще следует начинать с каких-нибудь комбинационных парсеров, а потом брать всё более сложные алгоритмы.

Norgat ★★★★★ ()
Ответ на: комментарий от Norgat

Спасибо, пацаны! Займусь и проясню эту тему по хардкору!

p37rov ()

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

Хочу сделать ядерный реактор на супер-быстрых предсказывающих электронах.

Подскажите школьные учебники по физике.

pacify ★★★★★ ()
Ответ на: комментарий от pacify

Хочу сделать ядерный реактор на супер-быстрых предсказывающих электронах.

Да ладно какие еще электроны? Помню еще в ДЭ (1961 года) была нарисована точная схема атомной и водородных бомб. Я в юности водородную бомбу делал - наполнил бутылек водородом и поджег его.

XoFfiCEr ★★ ()
Последнее исправление: XoFfiCEr (всего исправлений: 1)

Если хочется создать для Человечества что-то в данном контексте действительно полезное и нужное, то, по моему мнению, можно сделать красивую и изящную реализацию т.н. парсера Эрли. Считается, что этот алгоритм является самым оптимальным по производительности/ресурсоемкости. Кроме того, он не накладывает ограничений на используемую для анализа контекстно-свободную грамматику, позволяя получать все деревья разбора документа, если их несколько - «канонические» парсеры этого не обеспечивают.

illy ()
Ответ на: комментарий от illy

По-моему он был усовершенствован каким-то японцем

pylin ★★★★★ ()
Ответ на: комментарий от pylin

GLR, aka Tomita parsing. Нах не нужен, потому как есть packrat.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.