Ця стаття не містить . (липень 2013) |
Низхідний синтаксичний аналіз — один з методів визначення приналежності вхідного рядка деякій формальній мові, описаній LL(k)-граматикою. Це клас алгоритмів лексичного аналізу, де правила формальної граматики розкриваються, починаючи зі стартового символу до отримання потрібної послідовності токенів.
Ідея методу
Для кожного нетермінального символу K будується функція, яка для будь-якого вхідного слова x робить дві речі:
- Знаходить найбільший початок z слова x, здатний бути початком виводжуваного з K слова
- Визначає, чи є початок z виводжуваним з K
Така функція має задовольняти такі критерії:
- зчитувати із ще необробленого вхідного потоку максимальний початок A, який є початком деякого слова, виводжуваного з K
- визначати чи є A вивідним з K або просто невивідним початком виводжуваного з K слова
У випадку, якщо такий початок зчитати не вдається (і коректність функції для нетермінала K доведена), тоді вхідні дані не відповідають мові, і потрібно зупинити розбір.
Розбір містить у собі виклики описаних вище функцій. Якщо для зчитаного нетермінала є складене правило, тоді при його розборі будуть викликані інші функції для розбору терміналів, що входять в нього. Дерево викликів, починаючи із самої«верхньої» функції еквівалентно дереву розбору.
Найбільш простий і «людяний» варіант створення аналізатора, що використовує метод рекурсивного спуску, - безпосереднє програмування за кожним правилом вводу для нетерміналів граматики.
Умови застосування
Нехай в даній формальній граматиці N — скінченна множина нетермінальних символів; Σ — скінченна множина термінальних символів, тоді метод рекурсивного спуску можна застосувати тільки, якщо кожне правило цієї граматики має такий вигляд:
- або
, де
, і це єдине правило виводу для цього нетермінала
- або
для всіх
Алгоритми низхідного розбору
![]() | Це незавершена стаття про інформаційні технології. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
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 lipen 2013 Nizhidnij sintaksichnij analiz odin z metodiv viznachennya prinalezhnosti vhidnogo ryadka deyakij formalnij movi opisanij LL k gramatikoyu Ce klas algoritmiv leksichnogo analizu de pravila formalnoyi gramatiki rozkrivayutsya pochinayuchi zi startovogo simvolu do otrimannya potribnoyi poslidovnosti tokeniv Ideya metoduDlya kozhnogo neterminalnogo simvolu K buduyetsya funkciya yaka dlya bud yakogo vhidnogo slova x robit dvi rechi Znahodit najbilshij pochatok z slova x zdatnij buti pochatkom vivodzhuvanogo z K slova Viznachaye chi ye pochatok z vivodzhuvanim z K Taka funkciya maye zadovolnyati taki kriteriyi zchituvati iz she neobroblenogo vhidnogo potoku maksimalnij pochatok A yakij ye pochatkom deyakogo slova vivodzhuvanogo z K viznachati chi ye A vividnim z K abo prosto nevividnim pochatkom vivodzhuvanogo z K slova U vipadku yaksho takij pochatok zchitati ne vdayetsya i korektnist funkciyi dlya neterminala K dovedena todi vhidni dani ne vidpovidayut movi i potribno zupiniti rozbir Rozbir mistit u sobi vikliki opisanih vishe funkcij Yaksho dlya zchitanogo neterminala ye skladene pravilo todi pri jogo rozbori budut viklikani inshi funkciyi dlya rozboru terminaliv sho vhodyat v nogo Derevo viklikiv pochinayuchi iz samoyi verhnoyi funkciyi ekvivalentno derevu rozboru Najbilsh prostij i lyudyanij variant stvorennya analizatora sho vikoristovuye metod rekursivnogo spusku bezposerednye programuvannya za kozhnim pravilom vvodu dlya neterminaliv gramatiki Umovi zastosuvannyaNehaj v danij formalnij gramatici N skinchenna mnozhina neterminalnih simvoliv S skinchenna mnozhina terminalnih simvoliv todi metod rekursivnogo spusku mozhna zastosuvati tilki yaksho kozhne pravilo ciyeyi gramatiki maye takij viglyad abo A a displaystyle A rightarrow alpha de a S N displaystyle alpha subset Sigma cup N i ce yedine pravilo vivodu dlya cogo neterminala abo A a1a1 a2a2 anan displaystyle A rightarrow a 1 alpha 1 a 2 alpha 2 a n alpha n dlya vsih i 1 2 n ai aj i j a S N displaystyle i 1 2 n a i neq a j i neq j alpha subset Sigma cup N Algoritmi nizhidnogo rozboruRekursivnij nizhidnij parser LL parser Ce nezavershena stattya pro informacijni tehnologiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi