Синтаксичний аналізатор контекстно-вільних граматик

1.Синтаксичний аналізатор контекстно-вільних граматик, який має у своєму окладі двійковий лічильник, який відрізняється тим, що містить керуючий вхід, n шин початкових даних, перший і другий елемент "АБО", елемент "І", вхід "Cкидання", n блоків аналізу, кожен з яких має три входи, чотири виходи та інформаційні входи, елемент "АБО-НІ", вихід результату аналізу, причому, і-а шина початкових даних з'єднана з інформаційними входами і-го блока аналізу (і=1...n), керуючий вхід з'єднаний з першим входом першого блока аналізу, вхід "Скидання" з'єднаний з входом "Скидання" двійкового лічильника та третіми входами блоків аналізу, вихід позики двійкового лічильника з'єднаний з другими входами блоків аналізу, перший вихід і-го блока аналізу з'єднаний з і-им входом першого елемента "АБО", другий вихід і-го блока аналізу з'єднаний з і-им входом другого елемента "АБО" (і=1...n), третій вихід j-го блока аналізу з'єднаний з першим входом (j+1)-ro блока аналізу (j=1...n-1), третій вихід n-го блоку аналізу з'єднаний з першим входом елемента "І", вихід першого елемента "АБО" з'єднаний з підсумовувальним входом двійкового лічильника, вихід другого еле A (54) СИНТАКСИЧНИЙ АНАЛІЗАТОР КОНТЕКСТНО-ВІЛЬНИХ ГРАМАТИК 37162 регістр зсуву, комутатор (авторське свідоцтво СРСР № 1290358, кл. G06F15/38, опубл. бюл. №6, 1987). Недоліком відомого пристрою для перетворення виразів у польський інверсний запис є низька швидкодія. Найбільш близьким до пропонованого є синтаксичний аналізатор, який містить вхідний регістр, дешифратор лексичних одиниць, блок керування, дешифратор, блок пам'яті, дешифратор пріоритетів, буферний регістр, двійковий лічильник, дешифратор аксіоми (авторське свідоцтво СРСР №1334149, кл. G06F11/00). Недоліком відомого синтаксичного аналізатора є низька швидкодія, обумовлена виконанням синтаксичного аналізу шляхом послідовного розгляду лексичних одиниць. Тривалість цього процесу К тактів, де К – кількість лексичних одиниць. В основу винаходу поставлено задачу створити синтаксичний аналізатор, в якому нові елементи і відповідні взаємозв'язки дозволили б виконувати синтаксичний аналіз за один такт, тобто з більшою швидкодією. Поставлене завдання вирішується тим, що синтаксичний .аналізатор контекстно вільних граматик, що містить двійковий лічильник, згідно з винаходом, має у своєму складі керуючий вхід, n шин початкових даних, перший і другий елемент "АБО", елемент "І", вхід "Скидання ", n блоків аналізу, кожен з котрих має три входи, чотири виходи та інформаційні входи, елемент "АБО-НІ", вихід результату аналізу, причому, і-а шина початкових даних з'єднана з інформаційними входами і-го блока аналізу (і=1...n), керуючий вхід з'єднаний з першим входом першого блока аналізу, вхід "Cкидання" з'єднаний з входом "Cкидання" двійкового лічильника та третіми входами блоків аналізу, вихід позики двійкового лічильника з'єднаний з другими входами блоків аналізу, перший вихід і-го блока аналізу з'єднаний з і-им входом першого елемента "АБО", другий вихід і-го блока аналізу з'єднаний з і-им входом другого елемента "АБО", (і=1...n), третій вихід j-го блока аналізу з'єднаний з першим входом (j+1)-ro блока аналізу (j=1...n-1), третій вихід n-го блока аналізу з'єднаний з першим входом елемента "І", вихід першого елемента "АБО" з'єднаний з підсумовуючим входом двійкового лічильника, вихід другого елемента "АБО" з'єднаний з віднімаючим входом двійкового лічильника, виходи двійкового лічильника з'єднані з відповідними входами елемента "АБО-НІ", вихід якого з'єднаний з другим входом елемента "І", вихід елемента "І" з'єднаний з виходом результату аналізу, четверті виходи блоків аналізу об¢єднані у вихідну шину (де n – кількість лексем). Поставлене завдання вирішується також тим, що кожен з блоків аналізу містить елемент затримки, перший, другий, третій та четвертий елементи "І", елемент "АБО-НІ", тригер, елемент "НІ", причому група інформаційних входів з'єднана з відповідними входами другого елемента "І" і елемента "АБО-НІ", перший вхід блока аналізу з'єднаний з k+1-м входом другого елемента "І", першим входом третього елемента "І" і, через елемент затримки, з'єднаний з першим входом першого елемента "І" і входом елемента "НІ", вихід якого з'єднаний з першим входом четвертого елемента "І", вихід другого елемента "І" з'єднаний з першим виходом блока аналізу, вихід елемента "АБО-НІ" з'єднаний з другим входом третього елемента "І", вихід якого з'єднаний з другим виходом блока аналізу, другий вхід блока аналізу з'єднаний з другим входом четвертого елемента "І", вихід якого з'єднаний з одиничним входом тригера, інверсний вихід якого з'єднаний з другим входом першого елемента "І" та четвертим виходом блока аналізу, вихід першого елемента "І" з'єднаний з третім виходом блока аналізу, третій вхід з'єднаний з входом "Скидання" тригера. На фіг. 1 представлена функціональна схема синтаксичного аналізатора контекстно-вільних граматик. На фіг. 2 представлена функціональна схема блока аналізу. Синтаксичний аналізатор контекстно-вільних граматик містить керуючий вхід 1, вхід "Скидання" 2, шини початкових даних 3, вихідну шину 4, вихід результату аналізу 5, n блоків аналізу 6, перший елемент "АБО" 7, другий елемент "АБО" 8, елемент "АБО-НІ" 9, двійковий лічильник 10, елемент "І" 11. Елементи схеми синтаксичного аналізатора контекстно-вільних граматик з'єднані таким чином. Керуючий вхід 1 з'єднаний з першим входом першого блока аналізу 6, вхід "Скидання" 2, з'єднаний з входом "Скидання" двійкового лічильника 10 і з третіми входами блоків аналізу 6, і-а шина початкових даних 3 з'єднана з інформаційними входами 1-го блока аналізу 6 (і=1...n), вихід позики двійкового лічильника 10 з'єднаний з другими входами блоків аналізу 6, перший вихід і-го блока аналізу 6 з'єднаний з і-им входом першого елемента 7 "АБО", другий вихід і-го блока аналізу 6 з'єднаний з і-им входом другого елемента "АБО" 8, (і=1...n), третій вихід j-го блока аналізу 6 з'єднаний з першим входом (j+1)-го блока аналізу 6 (j=1...n-1), третій вихід n-го блока аналізу 6 з'єднаний з першим входом елемента "І", вихід першого елемента "АБО" з'єднаний з підсумовуючим входом двійкового лічильника 10, вихід другого елемента "АБО" з'єднаний з віднімаючим входом двійкового лічильника 10, виходи двійкового лічильника 10 з'єднані з відповідними входами елемента "АБО-НІ" 9, вихід якого з'єднаний з другим входом елемента "І" 11, вихід елемента "І" 11 з'єднаний з виходом 5 результату аналізу, четверті виходи блоків аналізу 6 об'єднані у вихідну шину 4. Блок аналізу синтаксичного аналізатора контекстно-вільних граматик містить перший вхід блока аналізу 12, другий вхід блока аналізу 13, третій вхід блока аналізу 14, перший вихід блока аналізу 15, другий вихід блока аналізу 16, третій вихід блока аналізу 17, елемент затримки 18, перший елемент "І" 19, другий елемент "І" 20, елемент "АБО-НІ" 21, тригер 22, третій елемент "І" 23, елемент "Ні" 24, четвертий елемент "І" 25, четвертий вихід блока аналізу 26. Елементи схеми блока аналізу синтаксичного аналізатора контекстно-вільних граматик з'єднані таким чином. Інформаційні входи 3 з'єднані з відповідними входами другого елемента "І" 20 і елемента "АБОНІ" 21, перший вхід 12 блока аналізу з'єднаний з k+1-м входом другого елемента "І" 20, першим 2 37162 входом третього елемента "І" 23, і через елемент затримки 18 з'єднаний з першим входом першого елемента "І" 19 і входом елемента "НІ" 24, вихід якого з'єднаний з першим входом четвертого елемента "І" 25, вихід другого елемента "І" 20 з'єднаний з першим виходом 15 блока аналізу, вихід елемента "АБО-НІ" 24 з'єднаний з другим входом третього елемента "І" 23, вихід якого з'єднаний з другим виходом 16 блока аналізу, другий вхід 13 блока аналізу з'єднаний з другим входом четвертого елемента "І" 25, вихід якого з'єднаний з одиничним входом тригера 22, інверсний вихід якого з'єднаний з другим входом першого елемента "І" 19 та четвертим виходом 26 блока аналізу, вихід першого елемента "І" 19 з'єднаний з третім виходом 17 блока аналізу. Всі елементи пристрою є стандартними елементами обчислювальної техніки і можуть бути виконані по будь-якій відомій схемі. Працює синтаксичний аналізатор контекстновільних граматик таким чином. Контекстно-вільна граматика – це різновид формальної граматики і є засобом формального представлення синтаксису і семантики природних та штучних мов. Сукупність лексичних об'єктів в контекстно-вільній граматиці задається двома класами (алфавітами) символів: термінальними (елементарні одиничні об'єкти) і не-термінальними. При синтаксичному аналізі контекстно-вільної граматики здійснюється граматичний розбір і перевіряється правильність розташування думок в реченні. У даному синтаксичному аналізаторі контекстно-вільних граматик коди лексем подаються на відповідні шини початкових даних З, причому код лексеми "("-11...1, а код лексеми ")"-00...0. На вхід 2 "Скидання" подається імпульс, що встановлює в стан 0…0 двійковий лічильник 10 і через третій вхід 14 блоків аналізу 6 поступає на входи "Скидання" тригерів 22, встановлюючи їх в стан "0". Блоки аналізу 6 при надходженні на перший вхід 12 сигналу "1" проводять аналіз коду лексеми, що поступає, і з усієї безлічі можливих лексем аналізують наявність лексем "(" і ")". Елемент "І" 19 формує на своєму виході сигнал 1, якщо сигнал на вході 12 "1", і якщо код лексеми 11...1, тобто "(", цей сигнал поступає на перший вихід 15 блока аналізу 6. Якщо код лексеми 00...0, тобто ")", то на виході елемента "АБО-НІ" 21 формується сигнал "1", який, при значенні керуючого сигналу на вході 12 "1", відкриває елемент "І" 23 і поступає на другий вихід 16 блока аналізу. Сигнал на першому вході 12 блока аналізу 6 через елемент затримки 18 поступає на вхід елемента "НІ" 24, який відкриває елемент "І" 25, якщо сигнал на другому вході 13 блока аналізу 6 рівний "1" і переводить тригер 22 в стан "1", при цьому на його інверсному виході, з'єднаному з другим входом елемента "І" 19 формується сигнал "0", який закриває елемент "І" 20 і сигнал з першого входу 12 блока аналізу не проходить на третій вихід 17 блока аналізу. По закінченні процесу проходження сигналу в блоці аналізу по стану тригера, 22 (на виході 26) формується інформація про коректність речення. Розглянемо роботу синтаксичного аналізатора контекстно-вільних граматик загалом. Після подачі на керуючий вхід 1 сигналу "1" в блоках аналізу 6 проводиться аналіз кодів лексем. Якщо код лексеми відповідає коду "(", то на першому виході 15 відповідного блока аналізу 6 формується сигнал 1, який поступає через перший елемент "АБО" 7 на підсумовуючий вхід двійкового лічильника 10 і збільшує його вміст на 1. Аналогічно, якщо код лексеми відповідає коду лексеми ")", то на другому виході 15 відповідного блока аналізу формується сигнал "1" і вміст двійкового лічильника 10 зменшується на одиницю. Вказаний процес буде послідовно виконуватися (оскільки сигнал із затримкою розповсюджується послідовно в блоках аналізу), доки вміст двійкового лічильника 10 буде більшим або дорівнює нулю. Якщо вміст двійкового лічильника при аналізі і-ої лексеми стане менше нуля, що відповідає тому, що кількість дужок, що закриваються, більше ніж відкриваються, тобто речення некоректне, при цьому на виході позики двійкового лічильника 10 формується сигнал "1", який надходить на другі входи 13 блоків аналізу 6, переводить триrep 22 в стан "1", при цьому закриваються відповідні елементи "І" 20, і сигнал управління далі не розповсюджується. При цьому на вихідну шину 4 виводиться вміст тригерів 22 відповідних блоків аналізу 6. Через час, рівний n*т, де т – час затримки сигналу, що визначається елементом затримки 18 на виході результату аналізу 5 сформовано значення "1", якщо кількість лексем "(" дсрівнює кількості лексем ")", n – кількість лексем у реченні. Запропонований синтаксичний аналізатор контекстно-вільних граматик є однотактним пристроєм і час аналізу визначається тільки затримкою в елементах схеми і, отже, має більшу швидкодію, ніж відомий пристрій, де задача вирішується за n тактів. 3 37162 Фіг. 1 4 37162 Фіг. 2 __________________________________________________________ ДП "Український інститут промислової власності" (Укрпатент) Україна, 01133, Київ-133, бульв. Лесі Українки, 26 (044) 295-81-42, 295-61-97 __________________________________________________________ Підписано до друку ________ 2001 р. Формат 60х84 1/8. Обсяг ______ обл.-вид. арк. Тираж 50 прим. Зам._______ ____________________________________________________________ УкрІНТЕІ, 03680, Київ-39 МСП, вул. Горького, 180. (044) 268-25-22 ___________________________________________________________ 5