Синтаксический анализ
Синтакси́ческий ана́лиз (или разбор, жарг. па́рсинг ← англ. parsing) в лингвистике и информатике — процесс сопоставления линейной последовательности лексем (слов, токенов) естественного или формального языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно применяется совместно с лексическим анализом.
Синтаксический анализатор (жарг. па́рсер ← англ. parser) — это программа или часть программы, выполняющая синтаксический анализ.
В ходе синтаксического анализа исходный текст преобразуется в структуру данных, обычно — в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки.
Как правило, результатом синтаксического анализа является синтаксическое строение предложения, представленное либо в виде дерева зависимостей, либо в виде дерева составляющих, либо в виде некоторого сочетания первого и второго способов представления.
Область применения
Всё что угодно, имеющее «синтаксис», поддается автоматическому анализу.
- Языки программирования — разбор исходного кода языков программирования, в процессе трансляции (компиляции или интерпретации);
- Структурированные данные — данные, языки их описания, оформления и т. д. Например, XML, HTML, CSS, JSON, ini-файлы, специализированные конфигурационные файлы и т. п.;
- Построение индекса в поисковой системе;
- SQL-запросы (DSL-язык);
- Математические выражения;
- Регулярные выражения (которые, в свою очередь, могут использоваться для автоматизации лексического анализа);
- Формальные грамматики;
- Лингвистика — естественные языки. Например, машинный перевод и другие генераторы текстов.
- Извлечение данных веб-страниц — веб-скрейпинг, является частным случаем парсинга.
Типы алгоритмов
- Нисходящий парсер (англ. top-down parser) — продукции грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов.
- Метод рекурсивного спуска
- LL-анализатор
- [англ.] (англ. bottom-up parser) — продукции восстанавливаются из правых частей, начиная с токенов и заканчивая стартовым символом.
- LR-анализатор
- GLR-парсер
Восстановление после ошибок
Простейший способ реагирования на некорректную входную цепочку лексем — завершить синтаксический анализ и вывести сообщение об ошибке. Однако часто оказывается полезным найти за одну попытку синтаксического анализа как можно больше ошибок. Именно так ведут себя трансляторы большинства распространённых языков программирования.
Таким образом, перед обработчиком ошибок синтаксического анализатора стоят следующие задачи:
- он должен ясно и точно сообщать о наличии ошибок;
- он должен обеспечивать быстрое восстановление после ошибки, чтобы продолжать поиск других ошибок;
- он не должен существенно замедлять обработку корректной входной цепочки.
Ниже описаны наиболее известные стратегии восстановления после ошибок.
Восстановление в режиме паники
При обнаружении ошибки синтаксический анализатор пропускает входные лексемы по одной, пока не будет найдена одна из специально определённого множества синхронизирующих лексем. Обычно такими лексемами являются разделители, например: ;, ) или }. Набор синхронизирующих лексем должен определять разработчик анализируемого языка. При такой стратегии восстановления может оказаться, что значительное количество символов будут пропущены без проверки на наличие дополнительных ошибок. Данная стратегия восстановления наиболее проста в реализации.
Восстановление на уровне фразы
Иногда при обнаружении ошибки синтаксический анализатор может выполнить локальную коррекцию входного потока так, чтобы это позволило ему продолжать работу. Например, перед точкой с запятой, отделяющей различные операторы в языке программирования, синтаксический анализатор может закрыть все ещё не закрытые круглые скобки. Это более сложный в проектировании и реализации способ, однако в некоторых ситуациях, он может работать значительно лучше восстановления в режиме паники. Естественно, данная стратегия бессильна, если настоящая ошибка произошла до точки обнаружения ошибки синтаксическим анализатором.
Продукции ошибок
Знание наиболее распространённых ошибок позволяет расширить грамматику языка продукциями, порождающими ошибочные конструкции. При срабатывании таких продукций регистрируется ошибка, но синтаксический анализатор продолжает работать в обычном режиме.
Средства разработки анализаторов
Отдельные этапы разработки и построения трансляторов могут быть автоматизированы и выполнены компьютером.
Вот некоторые из наиболее известных средств разработки анализаторов:
- ANTLR — генератор парсеров
- Bison — генератор парсеров
- Coco/R — генератор сканера и парсера
- — парсер
- JavaCC — генератор парсеров для языка Java
- — генератор парсеров
- Lex — генератор сканеров
- Ragel — генератор встраиваемых парсеров
- — генератор парсеров
- SYNTAX
- [англ.]
- UltraGram
- VivaCore
- Yacc — генератор парсеров
См. также [англ.].
См. также
- Компилятор компиляторов
- Синтаксически управляемая трансляция
- Регулярные выражения
Примечания
- Тим Джонс М. Извлечение информация из Интернета при использовании языка Ruby. (22 мая 2014). Дата обращения: 13 декабря 2019. Архивировано 13 декабря 2019 года.
- 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.
Ссылки
- Трансляция кода (рус.)
Для улучшения этой статьи желательно: |
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Синтаксический анализ, Что такое Синтаксический анализ? Что означает Синтаксический анализ?
Sintaksi cheskij ana liz ili razbor zharg pa rsing angl parsing v lingvistike i informatike process sopostavleniya linejnoj posledovatelnosti leksem slov tokenov estestvennogo ili formalnogo yazyka s ego formalnoj grammatikoj Rezultatom obychno yavlyaetsya derevo razbora sintaksicheskoe derevo Obychno primenyaetsya sovmestno s leksicheskim analizom Sintaksicheskij analizator zharg pa rser angl parser eto programma ili chast programmy vypolnyayushaya sintaksicheskij analiz Primer razbora vyrazheniya s preobrazovaniem ego struktury iz linejnoj v drevovidnuyu V hode sintaksicheskogo analiza ishodnyj tekst preobrazuetsya v strukturu dannyh obychno v derevo kotoroe otrazhaet sintaksicheskuyu strukturu vhodnoj posledovatelnosti i horosho podhodit dlya dalnejshej obrabotki Kak pravilo rezultatom sintaksicheskogo analiza yavlyaetsya sintaksicheskoe stroenie predlozheniya predstavlennoe libo v vide dereva zavisimostej libo v vide dereva sostavlyayushih libo v vide nekotorogo sochetaniya pervogo i vtorogo sposobov predstavleniya Oblast primeneniyaVsyo chto ugodno imeyushee sintaksis poddaetsya avtomaticheskomu analizu Yazyki programmirovaniya razbor ishodnogo koda yazykov programmirovaniya v processe translyacii kompilyacii ili interpretacii Strukturirovannye dannye dannye yazyki ih opisaniya oformleniya i t d Naprimer XML HTML CSS JSON ini fajly specializirovannye konfiguracionnye fajly i t p Postroenie indeksa v poiskovoj sisteme SQL zaprosy DSL yazyk Matematicheskie vyrazheniya Regulyarnye vyrazheniya kotorye v svoyu ochered mogut ispolzovatsya dlya avtomatizacii leksicheskogo analiza Formalnye grammatiki Lingvistika estestvennye yazyki Naprimer mashinnyj perevod i drugie generatory tekstov Izvlechenie dannyh veb stranic veb skrejping yavlyaetsya chastnym sluchaem parsinga Tipy algoritmovNishodyashij parser angl top down parser produkcii grammatiki raskryvayutsya nachinaya so startovogo simvola do polucheniya trebuemoj posledovatelnosti tokenov Metod rekursivnogo spuska LL analizator angl angl bottom up parser produkcii vosstanavlivayutsya iz pravyh chastej nachinaya s tokenov i zakanchivaya startovym simvolom LR analizator GLR parserVosstanovlenie posle oshibokProstejshij sposob reagirovaniya na nekorrektnuyu vhodnuyu cepochku leksem zavershit sintaksicheskij analiz i vyvesti soobshenie ob oshibke Odnako chasto okazyvaetsya poleznym najti za odnu popytku sintaksicheskogo analiza kak mozhno bolshe oshibok Imenno tak vedut sebya translyatory bolshinstva rasprostranyonnyh yazykov programmirovaniya Takim obrazom pered obrabotchikom oshibok sintaksicheskogo analizatora stoyat sleduyushie zadachi on dolzhen yasno i tochno soobshat o nalichii oshibok on dolzhen obespechivat bystroe vosstanovlenie posle oshibki chtoby prodolzhat poisk drugih oshibok on ne dolzhen sushestvenno zamedlyat obrabotku korrektnoj vhodnoj cepochki Nizhe opisany naibolee izvestnye strategii vosstanovleniya posle oshibok Vosstanovlenie v rezhime paniki Pri obnaruzhenii oshibki sintaksicheskij analizator propuskaet vhodnye leksemy po odnoj poka ne budet najdena odna iz specialno opredelyonnogo mnozhestva sinhroniziruyushih leksem Obychno takimi leksemami yavlyayutsya razdeliteli naprimer ili Nabor sinhroniziruyushih leksem dolzhen opredelyat razrabotchik analiziruemogo yazyka Pri takoj strategii vosstanovleniya mozhet okazatsya chto znachitelnoe kolichestvo simvolov budut propusheny bez proverki na nalichie dopolnitelnyh oshibok Dannaya strategiya vosstanovleniya naibolee prosta v realizacii Vosstanovlenie na urovne frazy Inogda pri obnaruzhenii oshibki sintaksicheskij analizator mozhet vypolnit lokalnuyu korrekciyu vhodnogo potoka tak chtoby eto pozvolilo emu prodolzhat rabotu Naprimer pered tochkoj s zapyatoj otdelyayushej razlichnye operatory v yazyke programmirovaniya sintaksicheskij analizator mozhet zakryt vse eshyo ne zakrytye kruglye skobki Eto bolee slozhnyj v proektirovanii i realizacii sposob odnako v nekotoryh situaciyah on mozhet rabotat znachitelno luchshe vosstanovleniya v rezhime paniki Estestvenno dannaya strategiya bessilna esli nastoyashaya oshibka proizoshla do tochki obnaruzheniya oshibki sintaksicheskim analizatorom Produkcii oshibok Znanie naibolee rasprostranyonnyh oshibok pozvolyaet rasshirit grammatiku yazyka produkciyami porozhdayushimi oshibochnye konstrukcii Pri srabatyvanii takih produkcij registriruetsya oshibka no sintaksicheskij analizator prodolzhaet rabotat v obychnom rezhime Sredstva razrabotki analizatorovOtdelnye etapy razrabotki i postroeniya translyatorov mogut byt avtomatizirovany i vypolneny kompyuterom Vot nekotorye iz naibolee izvestnyh sredstv razrabotki analizatorov ANTLR generator parserov Bison generator parserov Coco R generator skanera i parsera parser JavaCC generator parserov dlya yazyka Java generator parserov Lex generator skanerov Ragel generator vstraivaemyh parserov generator parserov SYNTAX angl UltraGram VivaCore Yacc generator parserov Sm takzhe angl Sm takzheKompilyator kompilyatorov Sintaksicheski upravlyaemaya translyaciya Regulyarnye vyrazheniyaPrimechaniyaTim Dzhons M Izvlechenie informaciya iz Interneta pri ispolzovanii yazyka Ruby neopr 22 maya 2014 Data obrasheniya 13 dekabrya 2019 Arhivirovano 13 dekabrya 2019 goda Ela Kumar Natural Language Processing I K International Pvt Ltd 2011 P 100 ISBN 978 93 80578 77 4 LiteraturaA Aho Dzh Ulman Teoriya sintaksicheskogo analiza perevoda i kompilyacii T 1 Per s angl V N Agafonova pod red V M Kurochkina M Mir 1978 614 s A Aho Dzh Ulman Teoriya sintaksicheskogo analiza perevoda i kompilyacii T 2 Per s angl A N Biryukova i V A Serebryakova pod red V M Kurochkina M Mir 1978 487 s Alfred V Aho Monika S Lam Ravi Seti Dzheffri D Ulman Kompilyatory principy tehnologii i instrumentarij Compilers Principles Techniques and Tools 2 e izd M 2008 ISBN 978 5 8459 1349 4 Robin Hanter Osnovnye koncepcii kompilyatorov The Essence of Compilers M 2002 256 s ISBN 5 8459 0360 2 SsylkiTranslyaciya koda rus Dlya uluchsheniya etoj stati zhelatelno Proverit dostovernost ukazannoj v state informacii Na stranice obsuzhdeniya dolzhny byt poyasneniya Ispravit statyu soglasno stilisticheskim pravilam Vikipedii Prostavit snoski vnesti bolee tochnye ukazaniya na istochniki Pozhalujsta posle ispravleniya problemy isklyuchite eyo iz spiska parametrov Posle ustraneniya vseh nedostatkov etot shablon mozhet byt udalyon lyubym uchastnikom
