Програмне моделювання скінчених перетворювачів

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Національний університет “Львівська політехніка”

Кафедра прикладної математики

Курсова робота

з дисципліни: Дискретна математика

Програмне моделювання скінчених перетворювачів

ЗМІСТ

ВСТУП

1. ТЕОРЕТИЧНІ ЗАСАДИ ЛЕКСИЧНОГО АНАЛІЗУ В ПРОГРАМУВАННІ

1.1 Сутність лексичного аналізу

1.2 Мова розширення регулярних виразів

1.3 Прямий та непрямий лексичні аналізи

2. ПРОГРАМНЕ МОДЕЛЮВАННЯ СКІНЧЕНИХ ПЕРЕТВОРЮВАЧІВ

ВИСНОВКИ

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

ДОДАТОК

ВСТУП

Щороку кількість програмних продуктів стрімко зростає. Це зумовлено великим попитом на комп'ютерну техніку та інші пристрої, де використовуються спеціалізовані програми та утиліти, також зростає складність самих програм та програмно-технічних пристроїв (комплексів). Чим складніше програмне забезпечення (ПЗ), тим важче перевірити повноту та несуперечливість вимог технічного завдання на його розробку. Процес розробки технічного завдання детально описано в практичних рекомендаціях зі специфікації програмного забезпечення. В процесі розробки технічного завдання часто допускаються помилки при формуванні функційних та не функційних вимог.

При вивченні мов програмування важливими є лексичний аспект. Процедурні мови програмування орієнтовані перш за все на опис (визначення) алгоритмів, тобто по суті використовуються для побудови процедур обробки даних. До таких мов ми відносимо всім відомі мови програмування, такі як Pascal, Fortran, C та ін.

Непроцедурні мови програмування на відміну від процедурних неявно визначають процедури обробки даних. Частіше всього такі мови використовуються для побудови завдань на обробку даних. При цьому, при допомозі інструкцій непроцедурної мови програмування визначається що необхідно зробити з даними і явно не визначається як (при допомозі яких алгоритмів) необхідно розв'язати задачу. До непроцедурних мов програмування ми відносимо командні мови операційних систем, мови управління в пакетах прикладних програм та ін.

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

Актуальність полягає в тому, що для розв'язання задачі перевірки технічного завдання на розробку програмного забезпечення чи програмно-технічного комплексу на повноту, несуперечливість, відповідність вимогам та стандартам предметної галузі необхідно провести аналіз відомих методів лексичного аналізу та розробити метод лексичного аналізу, що дозволяє проводити аналіз технічного завдання на розробку ПЗ з урахуванням функціональних та не функціональних вимог.

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

Відповідно до мети, завданнями роботи є:

1. Описати сутність лексичного аналізу.

2. Дослідити мову розширення регулярних виразів.

3. Охарактеризувати прямий та непрямий лексичні аналізи.

4. Визначити особливості програмного моделювання скінчених перетворювачів.

Об'єктом дослідження є лексичний аналіз мови програмного моделювання.

Предмет дослідження - особливості мови розширення регулярних виразів в контексті лексичного аналізу мови програмного моделювання.

Методи дослідження. В ході написання роботи були використані методи добору, систематизації та класифікації зібраного матеріалу, описовий і порівняльно-типологічний методи, метод аналізу процесу та продуктів діяльності, методи конкретизації, систематизації і узагальнення.

1. ТЕОРЕТИЧНІ ЗАСАДИ ЛЕКСИЧНОГО АНАЛІЗУ В ПРОГРАМУВАННІ

1.1 Сутність лексичного аналізу

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

Існує велика кількість лексичних аналізаторів та методів лексичного аналізу, але доцільно розглядати методи, що дозволяють описати мову якою буде складатися технічне завдання. Виділимо наступні методи лексичного аналізу, які задовольняють нашим вимогам:

- метод лексичного аналізу, що використовує формальні граматики Хомського;

- метод лексичного аналізу, що базується на link граматиці.

Модифікований метод лексичного аналізу на основі правосторонньої граматики Хомського. Для розв'язання задачі перевірки технічного завдання на розробку програмного забезпечення на повноту, несуперечливість, відповідність вимогам предметної області та стандартам необхідно розробити комбінований метод лексичного аналізу, який буде в себе включати Граматики Хомського, Link-граматику, оскільки кожен окремо взятий метод лексичного аналізу не дозволяє в повній мірі вирішити цю задачу.

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

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

З метою підвищення ефективності розв'язання задачі оцінки повноти, несуперечливості та відповідності технічного завдання стандартам, визначення дотримання вимог та правил з предметної галузі проектування ПЗ, чи в повній мірі та несуперечливо визначені функційні та нефункційні вимоги, доцільним є розроблення модифікованого методу лексичного аналізу, що базується на використанні граматик Хомського та Link-граматики.

Проведемо порівняння методів лексичного аналізу на предмет вирішення задачі перевірки технічного завдання на розробку програмного забезпечення чи програмно-технічного комплексу на повноту, несуперечливість, відповідність вимогам та стандартам предметної галузь. Лексичний аналізатор технічних завдань повинен відповідати наступним вимогам:

- проводити морфологічний аналіз слів;

- виділяти термінальні символи;

- проводити синтаксичний аналіз;

- ідентифікувати функційні та нефункційні вимоги.

Виділимо основні переваги та недоліки кожного з методів, які представимо у таблиці 1.1.

програмне моделювання скінчений перетворювач

Таблиця 1.1

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

№	Характеристики	Лексичний аналіз з використанням граматик Хомського	Лексичний аналіз з використанням Link граматики
1	Морфологічний аналіз слів	Не підтримується	Підтримується
2	Поділ на термінальні та нетермінальні символи	Підтримується	Не підтримується
3	Синтаксичний аналіз	Підтримується	Підтримується
4	Ідентифікація функційних та нефункційних вимог	Не підтримується	Не підтримується
5	Правосторонні граматики	Підтримується	Підтримується
6	Контекстновільні граматики	Підтримується	Підтримується
7	Контекстнозалежні граматики	Підтримується	Не підтримується
8	Граматики загального виду	Підтримується	Не підтримується
9	Задання граматики регулярними виразами	Підтримується	Немає засобів
10	Використання детермінованих та недетермінованих автоматів з магазинною пам'яттю	Підтримується	Не підтримується
11	Дерева виводу	Підтримується	Немає засобів
12	Визначення зв'язків між словами	Немає засобів	Підтримується
13	Збір статистичної інформації по зв'язках між словами у тексті	Немає засобів	Підтримується
14	Словник з правилами сполучення слів	Не підтримується	Підтримується

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

Призначення: перетворення вхідного тексту програми з формату зовнішнього представлення в машинноорієнтований формат - послідовність лексем.

Лексема - це ланцюжок літер елементарний об'єкт програми, що несе певний семантичний зміст. В подальшому кожну лексему будемо представляти як пару (<клас_лексеми, ім'я_лексеми>)

В більшості мов програмування для визначення класів лексем достатньо скінчених автоматів.

1.2 Мова розширення регулярних виразів

Серед різних методів автоматизації опрацювання текстової інформації, прискорення пошуку, заміни окремих символів чи їх сукупностей регулярні вирази посідають одне з найважливіших місць. Регулярні вирази - це формальна мова пошуку й здійснення маніпуляцій з підрядками в тексті, що ґрунтується на використанні мета символів. За іншим визначенням, це форма стандартного запису текстових даних, що використовується в автоматах зі скінченною кількістю станів.

Існує чимала кількість визначень (і серед них важко виділити єдино правильне) поняття мови. Зокрема, Ноам Хомський називає мову «множиною (скінченною або нескінченною) речень, кожне з яких має скінченну довжину і побудоване зі скінченної множини елементів». Очевидно, що регулярні вирази відповідають цьому визначенню й можуть бути детерміновані як метамова або спосіб описання будь-якої мови-об'єкта.

На сьогодні сформувалося кілька версій РВ. Попри ідентичність основних правил та метасимволів, вони відрізняються підтримуваними платформами (наприклад UNIX, Perl), інтерпретацією окремих шаблонів та синтаксисом. Зокрема, розрізняють т.зв. базові регулярні вирази, або стандартні регулярні вирази для UNIX - використовують умовно застарілий синтаксис, залишаючись при цьому - з огляду на те, що вони з'явилися першими, - сумісними з різними сучасними платформами.

Регулярні вирази можуть допомогти вирішувати такі завдання аналізу тексту:

- автоматичний морфологічний аналіз тексту;

- лематизація;

- лінгвістичне дешифрування;

- аналітико-синтетичне опрацювання документів;

- інформаційний пошук;

- завдання обчислювальної лексикографії;

- лінгвістичні квантитативні дослідження загалом;

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

Конкретнішими завданнями можна назвати, наприклад:

- сортування слів, знайдених у тексті;

- обчислення частотності використання слів;

- одержання доступу до довільних фрагментів тексту;

- статистичне вимірювання лексичної різноманітності мови;

- автоматична побудова графіка на основі видобутої з тексту інформації;

- знаходження загальних контекстів для різних слів;

- розпізнавання граматики мови програмування;

- організація підсвічування синтаксису мови програмування;

- ведення діалогу ЕОМ з користувачем тощо.

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

У регулярних виразах використовуються звичайні (літерали) та спеціальні символи (метасимволи).

Більшість символів у регулярному виразі представляють самі себе, за винятком спеціальних символів [ ] \ ^ $. | ? * + () {}, перед якими може стояти символ «\» (обернений слеш) для представлення їх самих як символів тексту - так зване «екранування». Можна «екранувати» цілу послідовність символів, помістивши її між метасимволом \Q і \E. Для вказування меж регулярних виразів (РВ) традиційно використовується символ / (слеш), при цьому сам він не входить до РВ, а для позначення меж текстових рядків використовуються лапки «». Таким чином, РВ /a\.?/ відповідає рядку тексту «a.» або «a»; /a\\\\b/ - «a\\b»; /a\[F\]/ - «a[F]»; /\Q+-*/\E/ - «+-*/».

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

Часто використовується послідовність /.*/ для позначення будь-якої кількості будь-яких символів між двома частинами регулярного виразу. Символьні класи в поєднанні з квантифікатори дозволяють встановлювати відповідності з реальними текстами: стовпцями цифр, телефонами, поштовими адресами, елементами HTML-розмітки тощо. Якщо символи { } не утворюють квантифікатор, їхнє спеціальне значення ігнорується.

У деяких реалізаціях квантифікаторам у регулярних виразах відповідає максимально довгий рядок із можливих (квантифікатори є жадібними, англ. greedy). В окремих випадках це може виявитися проблемою.

Наприклад, часто очікують, що вираз (<.*>) знайде в тексті теги HTML. Однак, якщо в тексті є більше одного HTML-тега, то цьому виразу відповідає цілий рядок, що містить безліч тегів: <p>Сторінка <b>Курси</b> містить навчальний матеріал з різних тем.</p>.

Є два шляхи вирішення цієї проблеми:

1. Враховувати символи, що не відповідають бажаному зразку (<[^>]*> для описаного вище випадку).

2. Визначити квантифікатор як нежадібний (ледачий, англ. lazy) - більшість реалізацій РВ дозволяють це зробити, додавши після нього знак питання.

Використання ледачих квантифікаторів може спричинити зворотну проблему, коли виразу відповідає занадто короткий,зокрема, порожній рядок.

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

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

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

Зазвичай підтримується до 9 нумерованих підрядків з номерами від 1 до 9, але деякі інтерпретатори дозволяють працювати з більшою кількістю. Згодом у межах одного регулярного виразу можна використовувати позначення від 1 до 9 для перевірки на збіг з раніше знайденим підрядком.

Атомарне групування вигляду (?>Шаблон), так само як групування без зворотного зв'язку, не створює зворотних зв'язків. На відміну від нього, таке групування забороняє повертатися назад у рядку, якщо частина шаблону вже знайдена. Наприклад, у рядку «abccaxcc» регулярний вираз /a(?>bc|b|x)cc/ знайде тільки «abccaxcc», але не «abccaxcc», оскільки варіант з x знайдений, інші будуть проігноровані. Атомарне групування виконується ще швидше, ніж групування без зворотного зв'язку, і зберігає процесорний час при виконанні решти виразу, оскільки забороняє перевірку будь-яких інших варіантів всередині групи, коли один варіант вже знайдений. Це дуже корисно при оптимізації груп з безліччю різних варіантів.

Якщо потрібно знайти рядок, у якому зустрічається одне з кількох слів, то достатньо використовувати РВ з альтернативами, а саме: вираз /^.*\b(один|два|три)\b.*$/ знайде усі рядки, що будуть містити будь-яке зі слів «один», «два» або «три». Першим зворотним покликанням буде знайдене в рядку слово. Якщо рядок міститиме два або усі три слова, то тільки останнє з них (крайнє справа) потрапить у комірку пам'яті як перше зворотне покликання. Це тому, що зірка * вмикає «жадібний» пошук. Якщо зробити першу зірку «ледачою», як у РВ /^.*?\b(один|два|три)\b.*$/,то зворотне покликання міститиме перше слово зліва.

Якщо рядок повинен містити всі три потрібні слова, то слід використати інструмент перегляду вперед. РВ /^(?=.*?\bодин\b)(?=.*?\bдва\b)(?=.*?\bтри\b).*$/ знайде тільки такі рядки з тексту, що містять усі три слова - «один», «два» і «три».

Всі три вказані у цьому РВ перегляди вперед повинні бути успішними, щоб рядок загалом відповідав умові РВ. Зверніть увагу, що замість власне слова, наприклад, /\bодин\b/, в умові перегляду вперед можна використати будь-який складніший РВ.

Якщо потрібно, щоб рядок не містив певного тексту, слід використовувати негативний перегляд вперед. Так, РВ /^((?!bодин\b).)*$/ знайде цілий рядок, що не містить слова «один». Потрібно звернути увагу на те, що для попереднього прикладу з використанням позитивного перегляду вперед, повторено разом негативний перегляд вперед і крапку, оскільки для позитивного перегляду вперед потрібно лише знайти місце в тексті, де РВ спрацює, а для негативного перегляду вперед треба перевірити всі без винятку позиції символу в рядку. Іншими словами, слід переконатися, що РВ не дає позитивного результату пошуку всюди, а не тільки в якомусь одному місці.

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

1.3 Прямий та непрямий лексичні аналізи

Існують наступні методи лексичного аналізу: непрямий і прямий лексичний аналіз.

Непрямий лексичний аналіз або лексичний аналіз з поверненнями полягає в послідовній перевірці версій про класи лексем. Якщо перевірка поточної версії не підтверджується, то відбувається повернення назад по ланцюжку символів і здійснюється перевірка наступної версії. Аналіз чергової лексеми починається з запуску автомата, розташованого першим. Він читає перший символ оброблюваного підланцюжка. Далі йде розпізнавання лексеми, у результаті чого читаються n символів. Поточним символом стає . Якщо версія про лексему підтверджується, то сканер видає її і завершує роботу. Його наступний запуск починається з читання символу , що знову передається першому автомату. Якщо ж автомат не може розпізнати лексему, то він видає сигнал відмови у блок управління та активізує наступний за пріоритетом автомат.

Блок управління здійснює повернення до символу

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

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

На основі вище описаних методів лексичного аналізу працюють лексичні аналізатори Lex, Flex, Bison.

Лексичний аналіз з використанням link граматик. Link граматики належать до класу контекстновільних граматик. Для опису мови граматикою використовуються зв'язки (link). На рис. 1.3 наведено приклад формування зв'язків між словами.

Рис. 1.3 Сполучення слів за змістовними зв'язками

Для link граматики характерні властивості:

- для кожного слова описуються зв'язки, за допомогою яких слова будуть сполучатися в речення;

- після лексичного аналізу для кожного слова проставляються зв'язки з іншими словами з дотриманням лексичної та семантичної структури речення;

- немає явного поділу на складові чи категорії.

В Link граматиці використовується словник, де для кожного слова визначенні всі можливі зв'язки, також вводиться поняття «з'єднувача» (connector), за допомогою з'єднувачів слова сполучаються за змістовними характеристиками.

Нижче наведенні основні типи змістовних зв'язків:

- S використовується для сполучення іменника з дієсловом;

- використовується для сполучення дієслова з об'єктом, який його характеризує;

- A використовується для сполучення прикметника з іменником;

Важливим є порядок розміщення зв'язків між словами у реченні - рис. 1.3.1.



Рис. 1.3.1 Порядок сполучення слів у реченні

Метод лексичного аналізу з використанням link граматик використовує метод динамічного програмування, а саме знаходження оптимальної тріангуляції опуклого многокутника.

Функція PARSE виконує лексичний аналіз тексту з використанням link граматик.

Функція на вхід приймає два слова L і R, та два вказівника l та r. Вказівник l вказує на список слів праворуч від слова L, вказівник r вказує на список слів ліворуч від слова R. Функція COUNT повертає число зв'язків, які можна проставити між словами L та R

Функція PARCE - виконує лексичний аналіз з використанням link граматики. Функція COUNT - виконує підрахунок кількості зв'язків між словами, що знаходяться в межах [L,…,R]. В якості параметрів передаються індекси слів L та R (початок та кінець речення), та два списки із вказівниками l та r, де розміщенні з'єднувачі для кожного слова, які повинні відповідати наступним вимогам:

- зв'язки не повинні перетинатися і мають задовольняти правилам, які визначені у словнику;

- для кожного слова [L,…,R] мають бути жорстко визначенні зв'язки;

- всі зв'язки та з'єднувачі для всіх слів з діапазону [L,…,R] або [L,…,M] i [M+1,…,R] мають відповідати правилу L Ј M<R.

Приклад

Розглянемо кілька абстрактних прикладів. Припустимо, що ідентифікатори - це ланцюжки, складені з чотирьох символів D, F, I і О, за якими повинен слідувати пробіл (b), причому DO і IF - ключові слова, які не є ідентифікаторами і за якими може не слідувати пробіл і не повинні слідувати (безпосередньо) літери D, F, I і О.

Спрощене множина ідентифікаторів (що включає DO і IF) розпізнається кінцевим автоматом, зображеним на рис. 1.3.2, а, ланцюжок DO - автоматом на рис. 1.3.2, б, IF - автоматом на рис. 1.3.2, в. Тут всі автомати детерміновані, проте в загальному випадку це не обов'язково.

Рис. 1.3.2 Автомати лексичного аналізу

Об'єднаний автомат показаний на рис. 1.3.3. Стан q₂ вказує, що виявлений ідентифікатор. Однак стану {q₁, q₈} і {q₁, q₅} не можна витлумачити однозначно. Вони можуть вказувати на IF або DO відповідно, а можуть лише на те, що з'явився початковий відрізок якогось ідентифікатора, на кшталт DOOF. Щоб вирішити конфлікт, що виник, лексичний аналізатор повинен поглянути на наступний символ. Якщо це D, О, I або F, то перед ними префікс ідентифікатора. Якщо щось інше, в тому числі н пробіл (припустимо, що букв більше, ніж згаданих п'ять), то автомат переходить в новий стан q₉ або q₁₀ і видає сигнал про те, що виявлено ключове слово DO або IF відповідно і воно закінчилося на один символ раніше. Якщо автомат потрапляє в q₂, то він видає сигнал про те, що виявлений ідентифікатор, що закінчується одним символом раніше.



Рис. 1.3.3 Об'єднаний лексичний аналізатор

Важливо відмітити, що так як зазначене розходження проявляється у виході описаного пристрою, а не в стані, то стан q₂, q₉ і q₁₀ можна ототожнити і насправді вони взагалі не будуть представлені в програмній реалізації.

2. ПРОГРАМНЕ МОДЕЛЮВАННЯ СКІНЧЕНИХ ПЕРЕТВОРЮВАЧІВ

Означення скінчених автоматів виглядає наступним чином недетермінований скінчений автомат - це п'ятірка

М = < Q, S, d, , F>, де

- Q = {, ,.., } - скінчена множина станів автомата;

- S = {, ,.., } - скінчена множина вхідних символів (вхідний алфавіт);

- О Q - початковий стан автомата;

- d - відображення множини Q*S в множину P(Q). Відображення d як правило називають функцією переходів;

- F Н Q - множина заключних станів. Елементи з F називають заключними або фінальними станами.

Якщо М - скінчений автомат, то пара (q, w) О Q*S* називається конфігурацією автомата М. Оскільки скінчений автомат - це дискретний пристрій, він працює по тактам. Такт скінченого автомата М задається бінарним відношенням |=, яке визначається на конфігураціях: (,aw) |= (,w), якщо d(, a) містить та для всіх w О S*.

Означення. Скінчений автомат М розпізнає (допускає) ланцюжок w, якщо (, w) |=* (q, e) для деякого q О F, де |=* - рефлексивно-транзитивне замикання бінарного відношення |=.

Означення. Мова, яку допускає автомат М (розпізнає автомат М) L(M)={ w | w О S* та (, w) |=* (q, e), q О F }

На практиці, при визначенні скінченого автомата М, використовують декілька способів визначення функції d, наприклад:

- це табличне визначення d;

- діаграма проходів скінченого автомата.

Табличне визначення функції d - це таблиця М(,), де О S, О Q, тобто М(,) = { |, О d(,) }

Діаграма переходів скінченого автомата М - це невпорядкований граф G(V, P), де V - множина вершин графа, а P - множина орієнтованих дуг, причому з вершини у вершину веде дуга позначена , коли Оd(,).

В подальшому при програмуванні скінчених автоматів важливо мати справу з так званими «мінімальними автоматами».

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

Очевидною перевагою програмної реалізації скінчених автоматів наведеним вище способом є простота визначення інформаційних масивів даних: alphabet - вхідний алфавіт автомата, sigma - таблиця переходів автомата, finish - масив імен заключних станів. Серед недоліків реалізації наведеної вище програми яскраво виділяється один - досить великі затрати пам'яті для таблиці sigma.

Очевидно, що матриця sigma сильно розріджена, тобто більшість її елементів має значення ERROR. В такому випадку при реалізації скінчених автоматів, кількість станів яких вимірюється десятками, та як вхідний алфавіт розглядається вся кодова таблиця ЕОМ (255 символів), то затрати оперативної пам'яті будуть занадто великі.

ВИСНОВКИ

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

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

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

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

В більшості формалізмів, якщо існує регулярний вираз, що описує задану множину, тоді існує нескінченна кількість варіантів, які описують цю множину

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

Для створення стилю ефективного програмування необхідно виконати відбір задач за критерієм частоти їх появи у розробці веб-застосувань. Аналіз лексем у різних проектах з відкритим кодом надає можливість відслідковувати частоту появи задач і обирати найпопулярніші задачі при створенні стилю ефективного програмування.

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

Існують такі інструменти лексичного аналізу, як «Lex» чи «Flex», «Yacc» чи «Bison», що можуть бути використані при створенні власних аналізаторів в інших мовах програмування.

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Баранов А. Н. Введение в прикладную лингвистику [Текст] / А. Н.Баранов. - М.: Едиториал УРСС, 2003. - 360 с.

2. Бек Д. Введение в системное программирование. - М.: Мир, 2008. - 289 с.

3. Волошин В. Г. Комп'ютерна лінгвістика: Навчальний посібник [Текст] / В. Г. Волошин. - Суми: ВТД «Університетська книга», 2004. - 382 с.

4. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, Том 1. Москва: Мир, 1978. - 612 с.

5. Кльоц Ю. П. Лексичний аналізатор технічних завдань на розробку критичного програмного забезпечення / Ю. П. Кльоц, В. С. Шевцов. - Труди XII МНПК «Сучасні інформаційні та електронні технології». - 2011 - С. 109.

6. Кузьмин А. Я. Лексический анализ. - М.: Наука, 2010. - 244 с.

7. Лебедев В. Н. Введение в системы программирования. - М.: Статистика, 2011. - 357 с.

8. Марчук Ю. Н. Основы компьютерной лингвистики [Текст] / Ю. Н. Марчук. - М.: Народный учитель, 2010. - 320 с.

9. Партико З. В. Прикладна і комп'ютерна лінгвістика: Вступ до спеціальності [Текст] / З. В. Партико. - Львів: Афіша, 2008. - 224 с.

10. Пратт Т. Языки программирования: разработка и реализация. - М.: Мир, 2009. - 361 с.

11. Усольцев В. Л. Лекционный курс «Компьютерное моделирование». - М.: Знания, 2010. - 297 с.

12. Форта Бен. Освой самостоятельно регулярные выражения. 10 минут на урок. - М.: «Вильямс», 2005. - 184 с.

13. Фридл Дж. Регулярные выражения [Текст] / Дж. Фридл. - СПб: Питер, 2011. - 352 с.

14. Хомский Н. Синтаксические структуры [Текст] / Н. Хомский // Новое в лингвистике. - Вып. 2. - М.: Издательство иностранной литературы, 2008. - 528 с.

ДОДАТОК 1

#include "stdafx.h"

#include <cstdlib>

#include <iostream>

#include <stdio.h>

using namespace std;

int main(int argc, char *argv[])

{

FILE *fp;

char c, fname[15], strichka[255], pidstroka[5], itog[4];

int i = 0, j, result = 0, flag = 0, l;

int mass[6][3] = { { 1,0,0 },{ 2,4,0 },{ 3,3,0 },{ 3,3,1 },{ 5,0,0 },{ 2,3,0 } };

puts("VVedit imya failu s vhidnoiu strichkoiu:");

cin>> fname;

if ((fp = fopen(fname, "r")) == NULL)

{

cout << "Fail ne znaideno";

getchar();

return 1;

}

while ((c = getc(fp))!= EOF)

{

flag = 1;

if ((c!= 'a') && (c!= 'b'))

{

cout << "simvol = " << c << " ne pidhodyt. Fail povynen mistyty tilky symvoli 'a' i 'b'.\n";

break;

}

else if (c == 'a')

{

j = mass[i][1];

if ((j == 3) && (i!= 3))

{

result = mass[j][3];

strcpy(pidstroka, "aaa");

}

i = j;

l = strlen(strichka);

strichka[l] = c;

strichka[l + 1];

}

else

{

j = mass[i][2];

if ((j == 3) && (i!= 3))

if (i == 2)

{

result = mass[j][3];

strcpy(pidstroka, "aab");

}

else

{

result = mass[j][3];

strcpy(pidstroka, "abab");

}

i = j;

l = strlen(strichka);

strichka[l] = c;

strichka[l + 1];

}

}

fclose(fp);

if ((flag == 0) || (result == 0))

strcpy(itog, "NET");

else

strcpy(itog, "DA");

if (flag == 1)

{

puts("VVedit imya failu kuda zapysaty resultat:");

cin >> fname;

if ((fp = fopen(fname, "w")) == NULL)

{

cout << "Fail ne naiden";

getchar();

return 1;

}

fputs("Vhidna strichka:\n", fp);

fputs(strichka, fp);

fputs(itog, fp);

fputs(pidstroka, fp);

fclose(fp);

}

system("PAUSE");

return EXIT_SUCCESS;

}

Размещено на Allbest.ru

...