Синтаксический анализ

Синтакси́ческий ана́лиз (или разбор) (жарг. па́рсинг (заимств. из англ. термин parsing)) в лингвистике и информатике — процесс сопоставления линейной последовательности лексем (слов, токенов) естественного или формального языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно применяется совместно с лексическим анализом.

Синтаксический анализатор (жарг. па́рсер (англ. parser)) — это программа или часть программы, выполняющая синтаксический анализ.

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

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

Область применения

Всё что угодно, имеющее «синтаксис», поддается автоматическому анализу.

Языки программирования — разбор исходного кода языков программирования, в процессе трансляции (компиляции или интерпретации);
Структурированные данные — данные, языки их описания, оформления и т. д. Например, XML, HTML, CSS, JSON, ini-файлы, специализированные конфигурационные файлы и т. п.;
Построение индекса в поисковой системе;
SQL-запросы (DSL-язык);
Математические выражения;
Регулярные выражения (которые, в свою очередь, могут использоваться для автоматизации лексического анализа);
Формальные грамматики;
Лингвистика — естественные языки. Например, машинный перевод и другие генераторы текстов.

Типы алгоритмов

Нисходящий парсер (англ. top-down parser) — продукции грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов.
- Метод рекурсивного спуска
- LL-анализатор
Восходящий парсер (англ. bottom-up parser) — продукции восстанавливаются из правых частей, начиная с токенов и кончая стартовым символом.
- LR-анализатор
- GLR-парсер

Восстановление после ошибок

Простейший способ реагирования на некорректную входную цепочку лексем — завершить синтаксический анализ и вывести сообщение об ошибке. Однако часто оказывается полезным найти за одну попытку синтаксического анализа как можно больше ошибок. Именно так ведут себя трансляторы большинства распространённых языков программирования.

Таким образом перед обработчиком ошибок синтаксического анализатора стоят следующие задачи:

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

Ниже описаны наиболее известные стратегии восстановления после ошибок.

Восстановление в режиме паники

При обнаружении ошибки синтаксический анализатор пропускает входные лексемы по одной, пока не будет найдена одна из специально определенного множества синхронизирующих лексем. Обычно такими лексемами являются разделители, например: ;, ) или }. Набор синхронизирующих лексем должен определять разработчик анализируемого языка. При такой стратегии восстановления может оказаться, что значительное количество символов будут пропущены без проверки на наличие дополнительных ошибок. Данная стратегия восстановления наиболее проста в реализации.

Восстановление на уровне фразы

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

Продукции ошибок

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

Средства разработки анализаторов

Некоторые из наиболее известных средств разработки анализаторов^[1]:

ANTLR — генератор парсеров
Bison — генератор парсеров
Coco/R — генератор сканера и парсера
GOLD — парсер
JavaCC — генератор парсеров для языка Java
Lemon Parser — генератор парсеров
Lex — генератор сканеров
Ragel — генератор встраиваемых парсеров
Spirit Parser Framework — генератор парсеров
SYNTAX
Syntax Definition Formalism^[en]
UltraGram
VivaCore
Yacc — генератор парсеров

См. также сравнение генераторов парсеров^[en].

Напишите отзыв о статье "Синтаксический анализ"

Примечания

↑ Ela Kumar. Natural Language Processing. — I. K. International Pvt Ltd, 2011. — P. 100. — ISBN 978-93-80578-77-4.

Литература

А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Т. 1. Пер. с англ. В.Н. Агафонова под ред. В. М. Курочкина. М.: Мир, 1978. 614 с.
А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Т. 2. Пер. с англ. А.Н. Бирюкова и В.А. Серебрякова под ред. В. М. Курочкина. М.: Мир, 1978. 487 с.
Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4.
Робин Хантер. Основные концепции компиляторов = The Essence of Compilers. — М.: «Вильямс», 2002. — С. 256. — ISBN 5-8459-0360-2.

Ссылки

[chernykh.net/content/view/221/234/ Трансляция кода ] (рус.)

Отрывок, характеризующий Синтаксический анализ

– А то как же? – отвечал солдат. – Ведь она не помилует. Она шмякнет, так кишки вон. Нельзя не бояться, – сказал он, смеясь.
Несколько солдат с веселыми и ласковыми лицами остановились подле Пьера. Они как будто не ожидали того, чтобы он говорил, как все, и это открытие обрадовало их.
– Наше дело солдатское. А вот барин, так удивительно. Вот так барин!
– По местам! – крикнул молоденький офицер на собравшихся вокруг Пьера солдат. Молоденький офицер этот, видимо, исполнял свою должность в первый или во второй раз и потому с особенной отчетливостью и форменностью обращался и с солдатами и с начальником.
Перекатная пальба пушек и ружей усиливалась по всему полю, в особенности влево, там, где были флеши Багратиона, но из за дыма выстрелов с того места, где был Пьер, нельзя было почти ничего видеть. Притом, наблюдения за тем, как бы семейным (отделенным от всех других) кружком людей, находившихся на батарее, поглощали все внимание Пьера. Первое его бессознательно радостное возбуждение, произведенное видом и звуками поля сражения, заменилось теперь, в особенности после вида этого одиноко лежащего солдата на лугу, другим чувством. Сидя теперь на откосе канавы, он наблюдал окружавшие его лица.
К десяти часам уже человек двадцать унесли с батареи; два орудия были разбиты, чаще и чаще на батарею попадали снаряды и залетали, жужжа и свистя, дальние пули. Но люди, бывшие на батарее, как будто не замечали этого; со всех сторон слышался веселый говор и шутки.
– Чиненка! – кричал солдат на приближающуюся, летевшую со свистом гранату. – Не сюда! К пехотным! – с хохотом прибавлял другой, заметив, что граната перелетела и попала в ряды прикрытия.
– Что, знакомая? – смеялся другой солдат на присевшего мужика под пролетевшим ядром.
Несколько солдат собрались у вала, разглядывая то, что делалось впереди.
– И цепь сняли, видишь, назад прошли, – говорили они, указывая через вал.
– Свое дело гляди, – крикнул на них старый унтер офицер. – Назад прошли, значит, назади дело есть. – И унтер офицер, взяв за плечо одного из солдат, толкнул его коленкой. Послышался хохот.
– К пятому орудию накатывай! – кричали с одной стороны.
– Разом, дружнее, по бурлацки, – слышались веселые крики переменявших пушку.
– Ай, нашему барину чуть шляпку не сбила, – показывая зубы, смеялся на Пьера краснорожий шутник. – Эх, нескладная, – укоризненно прибавил он на ядро, попавшее в колесо и ногу человека.
– Ну вы, лисицы! – смеялся другой на изгибающихся ополченцев, входивших на батарею за раненым.
– Аль не вкусна каша? Ах, вороны, заколянились! – кричали на ополченцев, замявшихся перед солдатом с оторванной ногой.
– Тое кое, малый, – передразнивали мужиков. – Страсть не любят.
Пьер замечал, как после каждого попавшего ядра, после каждой потери все более и более разгоралось общее оживление.
Как из придвигающейся грозовой тучи, чаще и чаще, светлее и светлее вспыхивали на лицах всех этих людей (как бы в отпор совершающегося) молнии скрытого, разгорающегося огня.
Пьер не смотрел вперед на поле сражения и не интересовался знать о том, что там делалось: он весь был поглощен в созерцание этого, все более и более разгорающегося огня, который точно так же (он чувствовал) разгорался и в его душе.
В десять часов пехотные солдаты, бывшие впереди батареи в кустах и по речке Каменке, отступили. С батареи видно было, как они пробегали назад мимо нее, неся на ружьях раненых. Какой то генерал со свитой вошел на курган и, поговорив с полковником, сердито посмотрев на Пьера, сошел опять вниз, приказав прикрытию пехоты, стоявшему позади батареи, лечь, чтобы менее подвергаться выстрелам. Вслед за этим в рядах пехоты, правее батареи, послышался барабан, командные крики, и с батареи видно было, как ряды пехоты двинулись вперед.
Пьер смотрел через вал. Одно лицо особенно бросилось ему в глаза. Это был офицер, который с бледным молодым лицом шел задом, неся опущенную шпагу, и беспокойно оглядывался.
Ряды пехотных солдат скрылись в дыму, послышался их протяжный крик и частая стрельба ружей. Через несколько минут толпы раненых и носилок прошли оттуда. На батарею еще чаще стали попадать снаряды. Несколько человек лежали неубранные. Около пушек хлопотливее и оживленнее двигались солдаты. Никто уже не обращал внимания на Пьера. Раза два на него сердито крикнули за то, что он был на дороге. Старший офицер, с нахмуренным лицом, большими, быстрыми шагами переходил от одного орудия к другому. Молоденький офицерик, еще больше разрумянившись, еще старательнее командовал солдатами. Солдаты подавали заряды, поворачивались, заряжали и делали свое дело с напряженным щегольством. Они на ходу подпрыгивали, как на пружинах.
Грозовая туча надвинулась, и ярко во всех лицах горел тот огонь, за разгоранием которого следил Пьер. Он стоял подле старшего офицера. Молоденький офицерик подбежал, с рукой к киверу, к старшему.
– Имею честь доложить, господин полковник, зарядов имеется только восемь, прикажете ли продолжать огонь? – спросил он.
– Картечь! – не отвечая, крикнул старший офицер, смотревший через вал.
Вдруг что то случилось; офицерик ахнул и, свернувшись, сел на землю, как на лету подстреленная птица. Все сделалось странно, неясно и пасмурно в глазах Пьера.
Одно за другим свистели ядра и бились в бруствер, в солдат, в пушки. Пьер, прежде не слыхавший этих звуков, теперь только слышал одни эти звуки. Сбоку батареи, справа, с криком «ура» бежали солдаты не вперед, а назад, как показалось Пьеру.
Ядро ударило в самый край вала, перед которым стоял Пьер, ссыпало землю, и в глазах его мелькнул черный мячик, и в то же мгновенье шлепнуло во что то. Ополченцы, вошедшие было на батарею, побежали назад.
– Все картечью! – кричал офицер.
Унтер офицер подбежал к старшему офицеру и испуганным шепотом (как за обедом докладывает дворецкий хозяину, что нет больше требуемого вина) сказал, что зарядов больше не было.
– Разбойники, что делают! – закричал офицер, оборачиваясь к Пьеру. Лицо старшего офицера было красно и потно, нахмуренные глаза блестели. – Беги к резервам, приводи ящики! – крикнул он, сердито обходя взглядом Пьера и обращаясь к своему солдату.
– Я пойду, – сказал Пьер. Офицер, не отвечая ему, большими шагами пошел в другую сторону.
– Не стрелять… Выжидай! – кричал он.
Солдат, которому приказано было идти за зарядами, столкнулся с Пьером.

[Hill2012-1] Ela Kumar. Natural Language Processing. — I. K. International Pvt Ltd, 2011. — P. 100. — ISBN 978-93-80578-77-4.

[1]