Граматика з фразової структурою

Стильові проблеми
У цій статті відсутня вступ.
Будь ласка, допишіть вступну секцію, коротко розкриває тему статті.

1. Мови та граматики. Основні поняття

Призначення мов і граматик полягає в:

Буква (символ) - простий неподільний знак.

Алфавіт - безліч букв (символів) A = {a, b, c}. Якщо є два алфавіту A і B (підмножина множини A), говорять, що алфавіт B є подалфавітом A, а A в свою чергу - надалфавітом.

Конкатенація - операція злиття символів в мові. Ця операція, по відношенню до алгебраїчним структурам, представляє собою напівгруп або моноід.

Слово ( рядок) - упорядкована сукупність літер в алфавіті. Безліч всіх рядків (включаючи порожню), які можуть бути побудовані з символів алфавіту A, називається замиканням A, і позначається A *. Позитивне замикання A (позначається A +) - безліч A * \ {e}, тобто безліч всіх рядків, які можуть бути побудовані з символів алфавіту A, за винятком порожнього рядка.

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


1.1. Под'язик (розширення) мови

Будь-яка мова в загальному випадку можна трактувати в 3-х зрізах, як:

  • Сукупність букв, слів (пропозицій) разом з накладеними на них обмежують правилами - синтаксичне розгляд ( синтаксис).
  • Інтерпретація пропозицій на предмет "розуміння" пропозицій, тобто розпізнавання зв'язків, у тому числі логічних, між пропозицією і відповідним явищем життя - семантичне розгляд ( семантика).
  • Практичне вплив мови - є прагматизм.

1.2. Граматики

Граматики - найбільш поширений клас описів мов. Опис граматики мови починається з визначення алфавіту, набору термінальних символів з ​​яких складається мова. Після створення алфавіту, необхідно визначити набір обмежуючих правил, ті правила за якими будуть будуватися слова і пропозиції в мові, виду α → β. У лівій і правій частинах цих виразів можуть міститися спеціальні нетермінальні символи. У процесі виведення нетермінальні символи замінюються відповідними термінальними, до повної їх заміни, за допомогою відповідних правил. Кожна граматика повинна містити початковий символ, або " аксіому ", з якої й починається будь-яке слово або пропозицію мови.


2. Граматика з фазовою структурою

Граматика з фазовою структурою - алгебраїчна структура, що складається з впорядкованої четвірки G = (N, T, P, S) і определеной на ній неявно операцією конкатенації.

  • N - кінцеве безліч нетермінальних символів
  • T - не перехресний з N кінцеве безліч термінальних символів
  • P - набір обмежуючих правил (продукцій)
  • S - стартовий (початковий символ)

Приклад Граматикою, що породжує мову {0 n 1 n | n ≥ 0}, є G: G = ({S}, {0,1}, P, S), де P = {S → 0S1, S → ε}.

Поняття виводимості: Якщо αβγ послідовний набір символів мови G, а β → δ правило цієї мови, то αβγ => αδγ (αδγ безпосередньо виведена з αβγ в G).

Ланцюг - послідовне присвоювання нетермінальних символів. Цикл - замкнута ланцюг

x (x ∈ N) - недоступний символ, якщо x нееквівалентен стартовому символу S (x ≠ S) і не існує висновків типу S + → αxβ. Символ називається непродуктивним, якщо не існує рядки γ, такий, що нетермінальний символ не буде привласнений γ (x → γ) Символ називається марним якщо він непродуктивний або недоступний.


3. Список літератури

  • Ахо, Дж. Ульман "Теорія синтаксичного аналізу, перекладу і компіляції", Т.1 "Синтаксичний аналіз", М.: Мир, 1978
  • Р. Хантер "Проектування і конструювання компіляторів", ФиС, 1984

Посилання