Розробка нових алгоритмів реалізації з метою розробки інтелектуальної системи синтаксичного аналізу

 

ЗМІСТ

1 Актуальність задачі розробки інтелектуальної системи синтаксичного аналізу……………………………….……………...................................................3 2 Аналіз сучасних методів для розв’язання задачі розробки інтелектуальної системи синтаксичного аналізу…………………………………………………...4 3 Обґрунтування вибору метода, що буде використаний для розробки інтелектуальної системи синтаксичного аналізу………………………………...6 4 Розробка нових алгоритмів реалізації з метою розробки інтелектуальної системи синтаксичного аналізу……………..……………………………..…..….8 4.1 Проектування інтелектуальної системи синтаксичного аналізу.…….8 4.2 Розробка програмного забезпечення для інтелектуальної системи синтаксичного аналізу………………………….…………………………..12 4.3 Аналіз результатів роботи  програми…………………………………..14 5 Висновки…..…………………………...………..…….……………….………...15 6 Результати наукових досліджень…………..….………………………………16 Список використаних джерел……………...………..…….……….……...……...44

 

 

 

 

 

1 АКТУАЛЬНІСТЬ  ЗАДАЧІ РОЗРОБКИ ІНТЕЛЕКТУАЛЬНОЇ СИСТЕМИ СИНТАКСИЧНОГО АНАЛІЗУ

 

Спроби  формалізувати інтелектуальну діяльність людини привели до постановки фундаментальної  лінгвістичної задачі – моделюванні  її мовної поведінки, тобто побудови кібернетичної моделі природної  мови. Природна мова слугує людині для  вираження її думок і для розуміння  думок інших людей.

Формальні моделі мови, які спочатку розроблялися в теоретичному плані, в останній час є компонентами різних прикладних систем. Будучи реалізовані на комп’ютері, вони входять в якості частин машинного  перекладу, підсистем комутації  з базами даних. Джон Сімонс вважає розробку систем, які здатні розуміти природну мову, «основною метою досліджень в області штучного інтелекту».

Метою роботи є побудова інтелектуальної системи синтаксичного аналізу речень.

Мета  роботи визначає необхідність розв’язання  таких задач:

• формалізація постановки задачі інтелектуального аналізу речень;
• побудова системи інтелектуального аналізу речень.

Об’єктом  дослідження виступає синтаксичний аналіз, як процес зіставлення лінійної послідовності лексем (слів, токенів) мови з його формальною граматикою.

Ціллю дослідження є створення програми – синтаксичного аналізатора, який перетворює вихідний текст у синтаксичну структуру. Під синтаксичною структурою розуміється дерево залежностей, в вузлах якого стоять слова даної природної мови з зазначенням частини мови та граматичних характеристик, а дуги відповідають специфічним для даної мови відношенням синтаксичної залежності.

 

 

2 АНАЛІЗ СУЧАСНИХ МЕТОДІВ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧІ РОЗРОБКИ ІНТЕЛЕКТУАЛЬНОЇ СИСТЕМИ СИНТАКСИЧНОГО АНАЛІЗУ

 

На  сучасному етапі розвитку програмного  та апаратного забезпечення інтелектуальних  систем синтаксичний аналіз відіграє дуже важливу роль. Областю застосування є все, що має «синтаксис»:

• мови програмування - розбір вихідного коду мов програмування, в процесі трансляції (компіляції або інтерпретації);
• структуровані дані - дані, мови їх опису, оформлення і т.д. Наприклад, XML, HTML, CSS, ini-файли, спеціалізовані конфігураційні файли і тому подібне;
• SQL-запити (DSL-мова);
• математичні вирази;
• регулярні вирази (які, у свою чергу, можуть використовуватися для автоматизації лексичного аналізу);
• формальні граматики;
• лінгвістика - людські мови. Наприклад, машинний переклад та інші генератори текстів.

На  сьогоднішній день існує багато алгоритмів, які розв‘язують даний тип  задач:

• метод рекурсивного спуску (Recursive descent parser) - один з методів визначення приналежності вхідного рядка деякій формальній мові, описаній LL(k)-граматикою. Це клас алгоритмів лексичного аналізу, де правила формальної граматики розкриваються, починаючи зі стартового символу до отримання потрібної послідовності токенів;
• LL-аналізатор - це алгоритм синтаксичного аналізу методом рекурсивного спуску для підмножини контекстно-вільних граматик. Він обробляє вхід зліва направо (тому перша буква означає Left), та будує ліворекурсивне виведення рядка (тому його порівнюють з LR аналізатором);
• LR-аналізатор - синтаксичний аналізатор для вихідних кодів програм, написаних на деякій мові програмування, який читає вхідний потік зліва направо і виробляє найбільш праву продукцію контекстно-вільної граматики;
• GLR парсер - Generalized Left-to-right Rightmost derivation parser. Узагальнений висхідний магазинний аналізатор. Розширений алгоритм LR-парсера, призначений для розбору по недетерменірованним і неоднозначним граматикам. Вперше описаний Масару Томіта в 1984 році, його також називають «паралельним парсером» [1].

 

Для виконання даного курсового  проекту було вибрано LR-аналізатор, так як він найбільше підходить  для створення компіляторів. LR –  аналізатор використовує контекстно-вільну граматику - окремий випадок формальної граматики (тип 2 по ієрархії Хомського), у якої ліві частини всіх продукцій  є поодинокими нетерміналами. Сенс терміна «контекстно-вільна» полягає  в тому, що можливість застосувати  продукцію до нетерміналу, на відміну  від загального випадку граматики  Хомського, не залежить від контексту  цього нетермінала [2].

Мова, яка може бути задана контекстно-вільною  граматикою, називається контекстно-вільною  мовою.

               Мова програмування повинна забезпечувати  лаконічну реалізацію              програмного продукту, його ефективне  виконання, принципи об‘єктно-орієнтованого  програмування, легку заміну компонентів  системи. Саме тому для розробки  заданої інтелектуальної системи  виберемо мову програмування  С#.

 

 

3 ОБҐРУНТУВАННЯ ВИБОРУ МЕТОДА, ЩО БУДЕ ВИКОРИСТАНИЙ ДЛЯ РОЗРОБКИ ІНТЕЛЕКТУАЛЬНОЇ СИСТЕМИ СИНТАКСИЧНОГО АНАЛІЗУ

 

Розглянемо  детальніше метод LR – аналізу.

Синтаксис багатьох мов програмування може бути визначений граматикою, яка є LR (1) або близькою до цього, і з цієї причини LR-аналізатори часто використовуються компіляторами для виконання  синтаксичного аналізу вихідних кодів.

Зазвичай  на аналізатор посилаються у зв'язку з ім'ям тієї мови, вихідний код якої він розбирає,  наприклад, «C++ аналізатор»  розбирає вихідні коди мови C++.

LR-аналізатор  може бути створений з контекстно-вільної  граматики програмою, яку називають  генератором синтаксичних аналізаторів, або ж написаний вручну програмістом. Контекстно-вільна граматика класифікується  як LR (k), якщо існує LR (k)-аналізатор  для неї, як визначено генератором  аналізаторів.

Говориться, що LR-аналізатор виконує розбір знизу  вгору, тому що він намагається вивести  продукцію верхнього рівня граматики, будуючи її з листів.

Детерменірована контекстно-вільна мова - це мова, для  якої існує будь-яка LR (k) граматика. Кожна LR (k) граматика може бути автоматично  перетворена в граматику LR (1) для  тієї ж мови, в той час як LR (0) граматика для деяких мов може не існувати. LR (0)-мови є власною підмножиною  детерменірованних мов.

LR-аналізатор  заснований на алгоритмі, що  приводиться в дію таблицею  аналізу, структурою даних, яка  містить синтаксис аналізованої  мови. Таким чином, термін LR-аналізатор  насправді ставиться до класу  аналізаторів, які можуть розібрати  майже будь-яку мову програмування,  для якого надана таблиця аналізу.  Таблиця аналізу створюється  програмою - генератором синтаксичних  аналізаторів.

LR-аналіз  може бути узагальнений як  довільний аналіз контекстно-вільної  мови без втрати продуктивності, навіть для LR (k) граматик. Це відбувається  завдяки тому, що більшість мов  програмування можуть бути виражені LR (k) граматикою, де k - мала константа  (зазвичай 1).

LR-аналіз  може застосовуватися до більшої  кількості мов, ніж LL-аналіз, а  також краще в частині повідомлення  про помилки, тобто він визначає  синтаксичні помилки там, де  вхід не відповідає граматиці,  як можна раніше. На відміну  від цього, LL (k) аналізатори можуть  затримувати визначення помилки  до іншої гілки граматики через  відкати, часто ускладнюючи визначення  місця помилки в місцях загальних  довгих префіксів.

LR-аналізатори  складно створювати вручну і  зазвичай вони створюються генератором  синтаксичних аналізаторів чи  компілятором компіляторів. У залежності  від того, як була створена  таблиця аналізу, ці аналізатори  можуть бути названі простими LR-аналізаторами (SLR), LR-аналізаторами  з попереднім переглядом (LALR) або  канонічними LR-аналізаторами (рис.  3.1). LALR-аналізатор мають велику розпізнавальну здатність, ніж SLR-аналізатори, а канонічні LR-аналізатори велику розпізнавальну здатність, ніж LALR-аналізатори.

 

Рисунок 3.1 – Схема LR – аналізатора

4 РОЗРОБКА НОВИХ АЛГОРИТМІВ З МЕТОЮ РОЗРОБКИ ІНТЕЛЕКТУАЛЬНОЇ СИСТЕМИ СИНТАКСИЧНОГО АНАЛІЗУ

 

4.1 Проектування інтелектуальної системи синтаксичного аналізу

 

Основним  компонентом інтелектуальної системи  є синтаксичний аналізатор, який є  серцем компілятора і може існувати в безлічі видах і формах. У  аналізатора «ОО» є кілька завдань: він забезпечує відповідність вихідної програми визначення мови і обробляє помилки у разі збою. Він також  створює уявлення програмного синтаксису в пам'яті, яке споживається генератором  коду і, нарешті, аналізатор «ОО» вирішує, які типи середовища виконання використати.

Перше що необхідно зробити - це поглянути  на представлення програмного синтаксису в пам'яті, тобто AST. Потім розглянути код, що створює це дерево з лексем сканера. Формат AST швидкий, ефективний, простий в кодуванні і може бути багаторазово переглянутий генератором  коду.

Визначення  мови:

<stmt> := var <ident> = <expr>

  | <ident> = <expr>

  | for <ident> = <expr> to <expr> do <stmt> end

  | read_int <ident>

  | print <expr>

  | <stmt> ; <stmt>

 

<expr> := <string>

  | <int>

  | <arith_expr>

  | <ident>

 

<arith_expr> := <expr> <arith_op> <expr>

<arith_op> := + | - | * | /

 

<ident> := <char> <ident_rest>*

<ident_rest> := <char> | <digit>

 

<int> := <digit>+

<digit> := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

 

<string> := " <string_elem>* "

<string_elem> := <any char other than ">

У відповідності з зазначеним визначенням  мови, оператор (stmt) може представляти із себе оголошення змінних, призначення, цикли, читання цілих чисел з  командного рядка або друк на екрані - і все це можна вказувати багато разів, розділяючи оператори крапкою  з комою. Вирази (expr) можуть бути рядками, інтегралами, арифметичними виразами або ідентифікаторами. Ідентифікатори (ident) можуть іменуватися з використанням  букви алфавіту в якості першої літери, за якою слідують символи або цифри.  Синтаксис мови надає базові арифметичні  можливості, невелику систему типів  і просту взаємодію з користувачем на основі консолі.

Швидкий погляд на визначення мови «ОО» показує, що AST більш-менш відповідає вузлам визначення мови з синтаксису EBNF. Краще всього уявити собі визначення мови як інкапсуляцію синтаксису, де абстрактне древо синтаксису фіксує структуру цих елементів.

  У компіляторі «ОО», використовується  спадний аналізатор. Це означає,  що він читає текст зліва  направо і конструює AST, ґрунтуючись  на наступній доступній лексемі  введення.

Конструктор класу аналізатора виглядає так:

public Parser(Collections.IList<object> tokens)

{

this.tokens = tokens;

this.index = 0;

this.result = this.ParseStmt();

 

if (this.index != this.tokens.Count)

throw new System.Exception("expected EOF");

}

 

Основна частина аналізу виконується  методом ParseStmt. Він повертає вузол Stmt, який служить кореневим вузлом дерева і відповідає вузлу верхнього  рівня визначення синтаксису мови. Аналізатор обходить список лексем, використовуючи індекс як поточної позиції і в  той же час визначаючи лексеми, підлеглі вузлу Stmt в синтаксисі мови (декларації змінних і призначення, цикли, read_ints і відображення). Якщо лексему не вдається впізнати, видається помилка.

При упізнанні лексеми, створюється  вузол AST і виконується подальший  аналіз, який запросив вузол. Нижче  приведений код, необхідний для створення  вузла AST відображення:

 

     // <stmt> := print <expr>

          // <expr> := <string>

    // | <int>

    // | <arith_expr>

    // | <ident>

if (this.tokens[this.index].Equals("print"))

{

this.index++;

Print print = new Print();

print.Expr = this.ParseExpr();

result = print;}

Тут відбуваються дві події. Лексема  відображення скидається за допомогою  збільшення індексу лічильника, після  чого викликається метод ParseExpr для отримання  вузла Expr, оскільки визначення мови вимагає, щоб за лексемою відображення слідував вираз.

Метод ParseExpr проходить за списком лексем від поточного індексу, визначаючи лексеми, що задовольняють визначенню виразу для мови. У даному випадку, метод просто шукає рядки, цілі числа  і змінні (створені примірником сканера) і повертає відповідні вузли AST, які  представляють ці вирази.