Синтакси́чний ана́ліз (па́рсинг) (англ. parsing) — в інформатиці це процес аналізу вхідної послідовності символів, з метою розбору граматичної структури згідно із заданою формальною граматикою. Синтаксичний аналізатор (англ. parser) — це програма або частина програми, яка виконує синтаксичний аналіз.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWtMMlJpTDFCaGNuTnBibWN0WlhoaGJYQnNaUzV3Ym1jdk1qSXdjSGd0VUdGeWMybHVaeTFsZUdGdGNHeGxMbkJ1Wnc9PS5wbmc=.png)
Під час синтаксичного аналізу текст оформлюється у структуру даних, зазвичай — в дерево, яке відповідає синтаксичній структурі вхідної послідовності й добре підходить для подальшої обробки. Зазвичай синтаксичні аналізатори працюють у два етапи: на першому ідентифікуються осмислені токени (виконується лексичний аналіз), на другому створюється дерево розбору.
Мови програмування
Синтаксичний аналізатор
Синтаксичний аналізатор — це програмний компонент, який приймає вхідні дані (часто текст) і створює структуру даних — часто дерево розбору, абстрактне дерево синтаксису або іншу ієрархічну структуру — забезпечує структурне представлення вводу, перевіряє правильність синтаксису в процесі. Аналізу можуть передувати або слідувати інші кроки, або їх можна об'єднати в один крок. Аналізатору часто передує окремий лексичний аналізатор, який створює токени з послідовності введених символів; Крім того, їх можна об'єднати у [en]. Аналізатори можуть бути запрограмовані вручну або автоматично, або напівавтоматично генератором парсерів. Розбір допомагає шаблону, який виробляє відформатований вихід. Вони можуть використовуватись у різних ділянках, але часто з'являються разом, наприклад, пара [en]/[en], або як вхідний (аналіз вхідних даних) та вихідний етапи (створення кінцевого коду) компілятора.
Вхідними даними для синтаксичного аналізатора часто є текст деякою комп'ютерною мовою, але також може бути текстом природною мовою або менш структурованими текстовими даними, в цьому випадку, як правило, витягуються лише окремі частини тексту, а не дерево розбору. Параметри відрізняються від дуже простих функцій, таких як scanf, до складних програм, таких як інтерфейс компілятора або HTML-аналізатор веббраузера. Важливий клас простий синтаксичний аналіз виконується за допомогою регулярних виразів, в яких група регулярних виразів визначає регулярну мову та двигун регулярного виразу, автоматично генеруючи аналізатор для цієї мови, що дозволяє узгодити шаблон та вилучення тексту. В інших контекстах регулярні вирази замість цього використовуються перед розбором, як етап лексизації, вихід якого потім використовується аналізатором.
Використання аналізаторів залежить від вхідних даних. У випадку з мовами даних часто використовується синтаксичний аналізатор як функція читання файлів у програмі, наприклад, читання в HTML або XML-тексті; ці приклади є мовами розмітки даних. У випадку мов програмування є компонентом компілятора або інтерпретатора, який аналізує початковий код мови комп'ютерного програмування для створення певної форми внутрішнього представлення; аналізатор є ключовим кроком в інтерфейсі компілятора. Мови програмування, як правило, вказуються в термінах [en], оскільки для них можуть бути написані швидкі та ефективні аналізатори. Для компіляторів сам аналіз може бути виконаний за один прохід або кілька проходів — див. [en] і .
Майбутні недоліки компілятора з одним прохідним процесом значною мірою можуть бути вирішені шляхом додавання виправлень, коли передбачається виправлення впродовж прямого переходу, а виправлення застосовуються у зворотньому напрямку, коли поточний сегмент програми є таким, що має бути завершений. Прикладом, коли такий механізм виправлення може бути корисним, є формальним твердженням GOTO, де вказівник GOTO невідомий, доки не буде пройдено сегмент програми. У такому випадку застосування виправлення буде відкладено, доки не буде визначено куди вказує GOTO. Очевидно, що відсталий GOTO не вимагає виправлення.
Контекстні граматики обмежені тією мірою, в якій вони можуть виразити всі вимоги до мови. Неформально причиною є те, що пам'ять в такій мові обмежена. Граматика не запам'ятовує існування конструкції над довільним введенням; це необхідно для мови, в якій, наприклад, ім'я повинно бути оголошено, перш ніж може бути посилання на нього. Однак більш потужні граматики, які можуть обійти це обмеження, не можуть бути ефективно розібрані. Таким чином, загальною стратегією є створення аналізатора для контекстно-вільної граматики, який приймає потрібні конструкції мови (тобто він приймає деякі недійсні конструкції); пізніше, небажані конструкції можуть бути відфільтровані на етапі семантичного аналізу (контекстного аналізу).
Наприклад, в Python такий синтаксичний код:
x = 1 print(x)
Такий код, однак, є синтаксично правильним з погляду контекстної граматики, яка дає дерево синтаксису з тією ж структурою, що і попередня, але є синтаксично недійсною з погляду контекстно-залежної граматики, яка вимагає, щоб змінні були ініціалізовані раніше використання:
x = 1 print(y)
Замість того, щоб аналізувати на етапі парсингу, це відбувається шляхом перевірки значень в дереві синтаксису, отже, як частина семантичного аналізу: контекстно-залежний синтаксис на практиці часто більш легко аналізується, ніж семантика.
Огляд процесу
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODRMemhtTDFCaGNtTmxjbDlHYkc5M2JsOXViM0p0TG5OMlp5OHhPREJ3ZUMxUVlYSmpaWEpmUm14dmQyNWZibTl5YlM1emRtY3VjRzVuLnBuZw==.png)
Наведений нижче приклад демонструє загальний випадок розбору комп'ютерної мови з двома рівнями граматики: лексичної та синтаксичної.
Перший етап — генерація токенів або лексичний аналіз, за допомогою яких потік вхідних символів поділяється на значущі символи, визначені граматикою регулярні вирази. Наприклад, програма калькулятора буде отримувати на вхід, такий рядок "12 * (3 + 4)^2
" і розділити його на токени 12
, *
, (
, 3
, +
, 4
, )
, ^
, 2
, кожен з яких є значущим символом в контексті арифметичного виразу. Лексери міститимуть правила, які вказують на те, що символи *
, +
, ^
, (
і )
позначають початок нового токену, так що незначні токени типу"12*
" або "(3
" не будуть створені).
Наступним етапом є парсинг чи синтаксичний аналіз, який перевіряє, чи токени утворюють допустимий вираз. Це, як правило, робиться з посиланням на контекстну граматику, яка рекурсивно визначає компоненти, які можуть скласти вираз та порядок їх появи. Проте не всі правила, що визначають мови програмування, можуть бути виражені контекстно-вільними граматиками, наприклад, дійсність типу та правильне декларування ідентифікаторів. Ці правила можуть бути формально виражені [en].
Заключна фаза — це семантичний аналіз або парсинг, який розробляє наслідки тільки що підтвердженого вираження та вживання відповідних заходів. У випадку калькулятора чи інтерпретатора дія полягає в оцінці виразу або програми, а компілятор, з іншого боку, генерує якийсь код. Атриматичні граматики також можуть бути використані для визначення цих дій.
Типи аналізаторів
Завдання аналізатора по суті полягає в тому, щоб визначити, як вхід можна отримати з початкового символу граматики. Це можна зробити по суті двома способами:
- Низхідний синтаксичний аналіз — аналіз згори донизу можна розглядати як спробу знайти найбільший початок z слова x, що може бути початком слова, що виводиться, шляхом пошуку в синтаксичному дереві за допомогою розгорнення згори донизу заданих формальних правил граматики. Токени читаються зліва направо. Інклюзивний вибір використовується для задоволення багатозначності шляхом розширення всіх альтернативних правих правил граматики.
- [en] — Синтаксичний аналізатор може початися з введення та спробувати переписати символ на його початку. Інтуїтивно, синтаксичний аналізатор намагається знайти найдовші основні елементи, потім елементи, що містять їх, і так далі. [en] є прикладами аналізаторів знизу вгору. Іншим терміном, що використовують для цього типу аналізатора, є [en], синтаксичний аналіз.
LL-аналізатор та рекурсивний спуск є прикладами аналізаторами згори-вниз, які не можуть враховувати [en]. Хоча вважалося, що прості реалізації синтаксичного аналізу зверху вниз не можуть враховувати пряму та непряму ліву рекурсію і можуть вимагати експоненціального часу та просторово складності під час аналізу неоднозначних контекстно-вільних граматик, складніші алгоритми для розбору зверху вниз створюються Frost, Hafiz, і Callaghan, які враховують багатозначність і ліва рекурсія в поліноміальному часі і які генерують поліноміальне представлення потенційно експоненціального числа дерев розбору. Їхній алгоритм здатний виготовити як ліві, так і правомірні похідні вхідних даних щодо цієї контекстно-вільної граматики.
Примітки
- Example Domain. www.example.com. Процитовано 24 листопада 2017.
- Aho, A.V., Sethi, R. and Ullman, J.D. (1986) « Compilers: principles, techniques, and tools.» Publishing Co., Inc. Boston, MA, USA.
- Frost, R., Hafiz, R. and Callaghan, P. (2007) « Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars .» 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109—120, June 2007, Prague.
- Frost, R., Hafiz, R. and Callaghan, P. (2008) « Parser Combinators for Ambiguous Left-Recursive Grammars.» 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167—181, January 2008, San Francisco.
Див. також
- Формальні граматики
- Алгоритм Ерлі
- Алгоритм сортувальної станції
- Рекурсивний спуск
- Парсери мови Java
- Поверхнево-синтаксичний аналіз
Інструменти розробки синтаксичних аналізаторів
Ця стаття не містить . (квітень 2013) |
![]() | Це незавершена стаття про інформаційні технології. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U Vikipediyi ye statti pro inshi znachennya cogo termina Sintaksichnij rozbir Sintaksi chnij ana liz pa rsing angl parsing v informatici ce proces analizu vhidnoyi poslidovnosti simvoliv z metoyu rozboru gramatichnoyi strukturi zgidno iz zadanoyu formalnoyu gramatikoyu Sintaksichnij analizator angl parser ce programa abo chastina programi yaka vikonuye sintaksichnij analiz Priklad rozboru virazu v derevo Pid chas sintaksichnogo analizu tekst oformlyuyetsya u strukturu danih zazvichaj v derevo yake vidpovidaye sintaksichnij strukturi vhidnoyi poslidovnosti j dobre pidhodit dlya podalshoyi obrobki Zazvichaj sintaksichni analizatori pracyuyut u dva etapi na pershomu identifikuyutsya osmisleni tokeni vikonuyetsya leksichnij analiz na drugomu stvoryuyetsya derevo rozboru Movi programuvannyaSintaksichnij analizator Sintaksichnij analizator ce programnij komponent yakij prijmaye vhidni dani chasto tekst i stvoryuye strukturu danih chasto derevo rozboru abstraktne derevo sintaksisu abo inshu iyerarhichnu strukturu zabezpechuye strukturne predstavlennya vvodu pereviryaye pravilnist sintaksisu v procesi Analizu mozhut pereduvati abo sliduvati inshi kroki abo yih mozhna ob yednati v odin krok Analizatoru chasto pereduye okremij leksichnij analizator yakij stvoryuye tokeni z poslidovnosti vvedenih simvoliv Krim togo yih mozhna ob yednati u en Analizatori mozhut buti zaprogramovani vruchnu abo avtomatichno abo napivavtomatichno generatorom parseriv Rozbir dopomagaye shablonu yakij viroblyaye vidformatovanij vihid Voni mozhut vikoristovuvatis u riznih dilyankah ale chasto z yavlyayutsya razom napriklad para en en abo yak vhidnij analiz vhidnih danih ta vihidnij etapi stvorennya kincevogo kodu kompilyatora Vhidnimi danimi dlya sintaksichnogo analizatora chasto ye tekst deyakoyu komp yuternoyu movoyu ale takozh mozhe buti tekstom prirodnoyu movoyu abo mensh strukturovanimi tekstovimi danimi v comu vipadku yak pravilo vityaguyutsya lishe okremi chastini tekstu a ne derevo rozboru Parametri vidriznyayutsya vid duzhe prostih funkcij takih yak scanf do skladnih program takih yak interfejs kompilyatora C abo HTML analizator vebbrauzera Vazhlivij klas prostij sintaksichnij analiz vikonuyetsya za dopomogoyu regulyarnih viraziv v yakih grupa regulyarnih viraziv viznachaye regulyarnu movu ta dvigun regulyarnogo virazu avtomatichno generuyuchi analizator dlya ciyeyi movi sho dozvolyaye uzgoditi shablon ta viluchennya tekstu V inshih kontekstah regulyarni virazi zamist cogo vikoristovuyutsya pered rozborom yak etap leksizaciyi vihid yakogo potim vikoristovuyetsya analizatorom Vikoristannya analizatoriv zalezhit vid vhidnih danih U vipadku z movami danih chasto vikoristovuyetsya sintaksichnij analizator yak funkciya chitannya fajliv u programi napriklad chitannya v HTML abo XML teksti ci prikladi ye movami rozmitki danih U vipadku mov programuvannya ye komponentom kompilyatora abo interpretatora yakij analizuye pochatkovij kod movi komp yuternogo programuvannya dlya stvorennya pevnoyi formi vnutrishnogo predstavlennya analizator ye klyuchovim krokom v interfejsi kompilyatora Movi programuvannya yak pravilo vkazuyutsya v terminah en oskilki dlya nih mozhut buti napisani shvidki ta efektivni analizatori Dlya kompilyatoriv sam analiz mozhe buti vikonanij za odin prohid abo kilka prohodiv div en i Majbutni nedoliki kompilyatora z odnim prohidnim procesom znachnoyu miroyu mozhut buti virisheni shlyahom dodavannya vipravlen koli peredbachayetsya vipravlennya vprodovzh pryamogo perehodu a vipravlennya zastosovuyutsya u zvorotnomu napryamku koli potochnij segment programi ye takim sho maye buti zavershenij Prikladom koli takij mehanizm vipravlennya mozhe buti korisnim ye formalnim tverdzhennyam GOTO de vkazivnik GOTO nevidomij doki ne bude projdeno segment programi U takomu vipadku zastosuvannya vipravlennya bude vidkladeno doki ne bude viznacheno kudi vkazuye GOTO Ochevidno sho vidstalij GOTO ne vimagaye vipravlennya Kontekstni gramatiki obmezheni tiyeyu miroyu v yakij voni mozhut viraziti vsi vimogi do movi Neformalno prichinoyu ye te sho pam yat v takij movi obmezhena Gramatika ne zapam yatovuye isnuvannya konstrukciyi nad dovilnim vvedennyam ce neobhidno dlya movi v yakij napriklad im ya povinno buti ogolosheno persh nizh mozhe buti posilannya na nogo Odnak bilsh potuzhni gramatiki yaki mozhut obijti ce obmezhennya ne mozhut buti efektivno rozibrani Takim chinom zagalnoyu strategiyeyu ye stvorennya analizatora dlya kontekstno vilnoyi gramatiki yakij prijmaye potribni konstrukciyi movi tobto vin prijmaye deyaki nedijsni konstrukciyi piznishe nebazhani konstrukciyi mozhut buti vidfiltrovani na etapi semantichnogo analizu kontekstnogo analizu Napriklad v Python takij sintaksichnij kod x 1 print x Takij kod odnak ye sintaksichno pravilnim z poglyadu kontekstnoyi gramatiki yaka daye derevo sintaksisu z tiyeyu zh strukturoyu sho i poperednya ale ye sintaksichno nedijsnoyu z poglyadu kontekstno zalezhnoyi gramatiki yaka vimagaye shob zminni buli inicializovani ranishe vikoristannya x 1 print y Zamist togo shob analizuvati na etapi parsingu ce vidbuvayetsya shlyahom perevirki znachen v derevi sintaksisu otzhe yak chastina semantichnogo analizu kontekstno zalezhnij sintaksis na praktici chasto bilsh legko analizuyetsya nizh semantika Oglyad procesu Shema roboti sintaksichnogo analizatoru Navedenij nizhche priklad demonstruye zagalnij vipadok rozboru komp yuternoyi movi z dvoma rivnyami gramatiki leksichnoyi ta sintaksichnoyi Pershij etap generaciya tokeniv abo leksichnij analiz za dopomogoyu yakih potik vhidnih simvoliv podilyayetsya na znachushi simvoli viznacheni gramatikoyu regulyarni virazi Napriklad programa kalkulyatora bude otrimuvati na vhid takij ryadok 12 3 4 2 i rozdiliti jogo na tokeni 12 3 4 2 kozhen z yakih ye znachushim simvolom v konteksti arifmetichnogo virazu Lekseri mistitimut pravila yaki vkazuyut na te sho simvoli i poznachayut pochatok novogo tokenu tak sho neznachni tokeni tipu 12 abo 3 ne budut stvoreni Nastupnim etapom ye parsing chi sintaksichnij analiz yakij pereviryaye chi tokeni utvoryuyut dopustimij viraz Ce yak pravilo robitsya z posilannyam na kontekstnu gramatiku yaka rekursivno viznachaye komponenti yaki mozhut sklasti viraz ta poryadok yih poyavi Prote ne vsi pravila sho viznachayut movi programuvannya mozhut buti virazheni kontekstno vilnimi gramatikami napriklad dijsnist tipu ta pravilne deklaruvannya identifikatoriv Ci pravila mozhut buti formalno virazheni en Zaklyuchna faza ce semantichnij analiz abo parsing yakij rozroblyaye naslidki tilki sho pidtverdzhenogo virazhennya ta vzhivannya vidpovidnih zahodiv U vipadku kalkulyatora chi interpretatora diya polyagaye v ocinci virazu abo programi a kompilyator z inshogo boku generuye yakijs kod Atrimatichni gramatiki takozh mozhut buti vikoristani dlya viznachennya cih dij Tipi analizatorivZavdannya analizatora po suti polyagaye v tomu shob viznachiti yak vhid mozhna otrimati z pochatkovogo simvolu gramatiki Ce mozhna zrobiti po suti dvoma sposobami Nizhidnij sintaksichnij analiz analiz zgori donizu mozhna rozglyadati yak sprobu znajti najbilshij pochatok z slova x sho mozhe buti pochatkom slova sho vivoditsya shlyahom poshuku v sintaksichnomu derevi za dopomogoyu rozgornennya zgori donizu zadanih formalnih pravil gramatiki Tokeni chitayutsya zliva napravo Inklyuzivnij vibir vikoristovuyetsya dlya zadovolennya bagatoznachnosti shlyahom rozshirennya vsih alternativnih pravih pravil gramatiki en Sintaksichnij analizator mozhe pochatisya z vvedennya ta sprobuvati perepisati simvol na jogo pochatku Intuyitivno sintaksichnij analizator namagayetsya znajti najdovshi osnovni elementi potim elementi sho mistyat yih i tak dali en ye prikladami analizatoriv znizu vgoru Inshim terminom sho vikoristovuyut dlya cogo tipu analizatora ye en sintaksichnij analiz LL analizator ta rekursivnij spusk ye prikladami analizatorami zgori vniz yaki ne mozhut vrahovuvati en Hocha vvazhalosya sho prosti realizaciyi sintaksichnogo analizu zverhu vniz ne mozhut vrahovuvati pryamu ta nepryamu livu rekursiyu i mozhut vimagati eksponencialnogo chasu ta prostorovo skladnosti pid chas analizu neodnoznachnih kontekstno vilnih gramatik skladnishi algoritmi dlya rozboru zverhu vniz stvoryuyutsya Frost Hafiz i Callaghan yaki vrahovuyut bagatoznachnist i liva rekursiya v polinomialnomu chasi i yaki generuyut polinomialne predstavlennya potencijno eksponencialnogo chisla derev rozboru Yihnij algoritm zdatnij vigotoviti yak livi tak i pravomirni pohidni vhidnih danih shodo ciyeyi kontekstno vilnoyi gramatiki PrimitkiExample Domain www example com Procitovano 24 listopada 2017 Aho A V Sethi R and Ullman J D 1986 Compilers principles techniques and tools Publishing Co Inc Boston MA USA Frost R Hafiz R and Callaghan P 2007 Modular and Efficient Top Down Parsing for Ambiguous Left Recursive Grammars 10th International Workshop on Parsing Technologies IWPT ACL SIGPARSE Pages 109 120 June 2007 Prague Frost R Hafiz R and Callaghan P 2008 Parser Combinators for Ambiguous Left Recursive Grammars 10th International Symposium on Practical Aspects of Declarative Languages PADL ACM SIGPLAN Volume 4902 2008 Pages 167 181 January 2008 San Francisco Div takozhFormalni gramatiki Algoritm Erli Algoritm sortuvalnoyi stanciyi Rekursivnij spusk Parseri movi Java Poverhnevo sintaksichnij analiz Instrumenti rozrobki sintaksichnih analizatoriv ANTLR Bison JavaCC REBOL uCalc Fast Math Parser uCalc Language Builder 1 Yacc Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno kviten 2013 Ce nezavershena stattya pro informacijni tehnologiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi