Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Форми Бекуса-Наура
|
|
Для граматик типу 2 (контекстно вільних), окрім звичайного, є ще інший спосіб подання - форми Бекуса-Наура.
Продукції граматик типу 2 мають у лівій частині один символ (нетермінальний). Замість того, щоб виписувати окремо всі продукції, можна об'єднати в один вираз продукції з однаковими символами у лівій частині. У такому разі замість символу → у продукціях використовують символ:: =. Усі нетермінали в цьому випадку беруть у трикутні дужки 
. Праві частини продукцій в одному виразі відокремлюють одну від одної символом |.
Приклад 9.16. Три продукціїА→ Аа, А→ а та А→ АВ можна зобразити таким одним виразом у формі Бекуса-Наура:
.▲
Приклад 9.17. Знайдемо продукції граматики, якщо у формі Бекуса-Наура вони записані так:
.
Рис. 9.5
Зобразимо дерево виведення у цій граматиці для ланцюжка (х*у)+х.
Для зручності використаємо позначення Е для 
(це буде й початковий символ) та Vдля 
.Тоді правилами перетворення (продукціями граматики) будуть E → (E), Е→ Е+Е, E→ E*EтаE→ Vз першого виразу, а такожV→ х таV→ у з другого виразу. Дерево виведення для ланцюжка (x*y)+ x зображено на рис. 9.5.▲