Синтаксичні діаграми автоматних мов і реалізація распознавателей на їх основі

1. Вступ
2. Основні позначення в регулярних виразах
3. Приклади регулярних виразів
4. Альтернативні позначення в регулярних виразах
5. Таблиця відповідності регулярних виразів і автоматних граматик
6. Синтаксична діаграма для цілого зі знаком
7. Програма розпізнавання цілого зі знаком по синтаксичної діаграмі
8. Основні завдання (5 балів)
9. Додаткові завдання (5 балів)
10. Додаткові складні завдання

Наша взаимовыгодная связь https://banwar.org/

До основній сторінці курсу

Вступ

Для опису лексем використовуються регулярні вирази.

Регулярні вирази тісно пов'язані з автоматними граматиками: за будь-яку автоматної граматики можна записати еквівалентну їй регулярний вираз і навпаки. Еквівалентність розуміється в тому сенсі що мови, ними породжувані, будуть збігатися.

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

Основні позначення в регулярних виразах

Регулярний вираз над алфавітом Σ - це

1. a - окремий символ з алфавіту Σ
2. ε - порожній ланцюжок
3. Якщо R і Q - регулярні вирази, то RQ - регулярний вираз, що є конкатенацией ланцюжків, породжуваних R і Q
4. Якщо R і Q - регулярні вирази, то R | Q - регулярний вираз, що є ланцюжком, що породжується або R, або Q
5. Якщо R - регулярний вираз, то R * - повторення R нуль і більше разів
6. Якщо R - регулярний вираз, то R + - повторення R один і більше разів. Очевидно, що R + = RR *
7. Якщо R - регулярний вираз, то (R) - таке ж регулярне вираз

Приклади регулярних виразів

Ціле зі знаком:

(+ | - |) ц +

ідентифікатор:

б (б | ц) *

Альтернативні позначення в регулярних виразах

В цьому випадку * і + не використовуються

Таблиця відповідності регулярних виразів і автоматних граматик

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

Синтаксична діаграма для цілого зі знаком

Програма розпізнавання цілого зі знаком по синтаксичної діаграмі

Правило. При розборі черговий конструкції перший символ вже повинен бути лічений за допомогою NextCh.

// Розбір цілого зі знаком за допомогою синтаксичних діаграм var ch: Char; pos: integer; procedure error (); begin writeln ( '^': pos); writeln ( 'Помилка в символі', ch); halt; end; procedure NextCh; begin read (ch); pos + = 1; end; begin NextCh; if ch in [ '+', '-'] then NextCh; if char. IsDigit (ch) then NextCh else error; while char. IsDigit (ch) do NextCh; if ch <> # 13 then error; writeln ( 'розпізнати ціле число'); end.

Основні завдання (5 балів)

Реалізувати програму на PascalABC.NET або C #.

Скласти синтаксичну діаграму, реалізувати по ній распознаватель і виконати зазначені семантичні дії для наступних лексем

1. Реалізувати в програмі семантичні дії по накопиченню в рядку розпізнаного цілого числа і перетворенню його в ціле в кінці розбору (при зустрічі завершального символу). Семантичні дії слід додавати перед кожним викликом NextCh крім першого. (1 бал)
2. Ідентифікатор. (1 бал)
3. Ціле зі знаком, що починається з цифри 0. (1 бал)
4. Чергуються літери і цифри, що починаються з літери. (1 бал)
5. Список букв, розділених символом, або; Як семантичного дії повинно бути накопичення списку букв в списку і висновок цього списку в кінці програми. (1 бал)

Додаткові завдання (5 балів)

Скласти синтаксичну діаграму, реалізувати по ній распознаватель і виконати зазначені семантичні дії для наступних лексем

1. Список цифр, розділених одним або декількома пропусками. Як семантичного дії повинно бути накопичення списку цифр в списку і висновок цього списку в кінці програми (1 бал).
2. Лексема виду aa12c23dd1, в якій чергуються групи букв і цифр, в кожній групі не більше 2 елементів. Як семантичного дії необхідно накопичити цю лексему в вигляді рядка (1 бал).
3. Речовий з десятковою крапкою 123.45678 (1 бал).
4. Лексема виду 'рядок', всередині апострофів відсутня символ '(1 бал).
5. Лексема виду / * коментар * /, всередині коментаря не може зустрітися послідовність символів * / (1 бал).

Додаткові складні завдання

1. Лексема виду Id1.Id2.Id3 (кількість ідентифікаторів може бути довільним).