Приклад. - раздел Программирование, Методические указания к выполнению лабораторных работ по курсу ПСП Маємо Граматику: R = {I®Aia,
I®Bad, I®C, ...
Маємо граматику: R = {I®aIa,
I®bAd, I®c, A®cBd, A®aAd, B®dAf },
знаходимо, що тут непродуктивними є символи А і B.Після виключення правил, що містять непродуктивні символи, одержуємо граматику:
R' = {I ®a I a,
I® c}.
6.3. Визначення недосяжних символів
Символ хÎ VтÈVA називається недосяжним у КВ-граматиці Г, якщо х не з'являється в жодному виведеному ланцюжку.
Розглядаючи правила граматики, можна помітити , що якщо нетермінал у лівій частині правила є досяжним , то і всі символи правої частини є досяжними. Це властивість правил є основою процедури виявлення недосяжних символів, який можна записати так:
1. Створити одноелементний список, що складається з початкового символу граматики І.
2. Якщо знайдене правило, ліва частина якого вже мається в списку, то включити до списку всі символи, що містяться в його правій частині.
3. Якщо на кроці 2 нові нетермінали в список більше не додаються, то отримано список усіх досяжних нетерміналів, а нетермінали, що не потрапили в список, є недосяжними.
Умови задач.
1. Змінні цілого типу. Оператор вводу.
2. Змінні символьного типу. Оператор виводу.
3. Масиви чисел .
4. Оператор циклу з параметром.
5. Оператор циклу с передум
Граматика типу 1
Граматики типу 1, яка називають також контекстно-залежними граматиками, не допускають використання будь-яких правил. Правила висновку в таких граматиках повинні ма
Граматика типу 2
Граматики типу 2 називають контекстно-вільними або безконтекстними граматиками ( КВ-граматики чи Б-граматики). Правила висновку таких грамати
ПОБУДОВА ПРАВИЛ ГРАМАТИКИ
Основою створення правил граматики є спосіб виділення структури заданої множини ланцюжка . Цей спосіб передбачає ділення ланцюжка на частини таким чином, щоб виявити частини, які повторюються , і я
Алгоритм побудови правил граматики
1. Виписати кілька прикладів із заданої множині ланцюжків.
2. Проаналізувати структуру ланцюжків, виділяючи початок і кінець, де повторюються символи чи групи символів.
3. Ввести
Приклад.
Маємо граматику:
R = { I ®aIb,
I ®c, A ®bI, A ®a },
знаходимо, що A є недосяжним символом.
КВ-граматика називається приведено
Приклад
Маємо граматику:
R={
E ® E + T | T ,
T ® T *F | F,
F ® (E ) | a}.
Правило E ® E + T | T перетворимо в пр
Виключення ланцюгових правил
Правило граматики виду A ® B, де A,B ÎVA, називається ланцюговим.Для КВ-граматики Г, що містить ланцюгові
LL(1) - граматики
Розділені і слаборозделені граматики являються підкласом граматик більш загального виду, що називаються LL(1) граматиками. Граматика називається LL(1) граматикою
· права частина кожного пр
Побудова магазинного автомата
Для граматик, що задовольняють умовам LL(1) граматик, справедливо наступне твердження:
Для кожної LL(1) граматики можна побудувати детермінований магазинний автомат М, що допускає мова, по
Приклад 1.
1. Побудувати спадний розпізнавач для оператору присвоювання арифметичного виразу. Арифметичний вираз містить: ідентифікатори і, :=, (, ), ; . Кількість вкладених дужок не обмежена.
1. Буд
Приклад 2.
Побудувати спадний розпізнавач для оператору виводу write або writeln. Оператор може містити в дужках список операторів і і коментарів ‘t ‘.
1. Будуємо правила граматики
&n
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов