Реферат: Проектирование трансляторов

нетерминальные - порождают. Иначе терминальные символы - это те,

на которых образуются конструкции Lg.

Cентенциальная форма: S => x, х C V+.

Предложение - цепочка терминальных символов, выведенных из

аксиомы: { x │ S => x, x C Vt* }

Пусть w=xuy - сентенциальная форма. Тогда u - фраза для U C

Vn, если S => xUy и U => u. Простая фраза - если U -> u.

Основа - самая левая простая фраза. Существуют леворекурсив-

ные и праворекурсивные грамматики. Различные грамматики могут по-

рождать один и тот же L. Мы можем генерировать синтаксически пра-

вильные сообщения.

<предложение>::=<определение><подлежащее><сказуемое><дополнение>

<определение>::=<голодный>│<большой>

<подлежащее>::=<верблюд>│<слон>│ ...

<сказуемое>::=<съел>│<взял>│ ...

<дополнение>::=<колючку>│<ветку>│ ...

Используя функции порождения строк относительно синтаксиса

этого языка, можно генерировать строки, формально принадлежащие

этому языку, правильные синтаксически, но неверные семантически (

Пример - Глоклая куздра бодланула куздренка).

G1 и G2 эквивалентны, если порождаемые ими языки Lg1 и Lg2

равны. Эквивалентные преобразования грамматик могут быть ис-

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

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

вывода для каждого предложения Lg.

Разбор или синтаксический анализ сентенциальной формы - это

построение вывода и, возможно, синтаксического дерева для нее.

Существуют методы как нисходящего, так и восходящего разбо-

ра (относительно движения по синтаксическому дереву).