Методические указания (1114907), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Д) строки, выделенные полужирным шрифтом, такие как id или if.

1. Эти символы являются нетерминалами:

А) прописные буквы из начала алфавита, такие как A, B, C;

Б) буква S, которая обычно обозначает стартовый символ;

В) имена из строчных букв, выделенные курсивом, такие как stmt или expr.

1. Прописные буквы из конца алфавита, такие как X, Y, Z, представляют грамматические символы, т е либо терминалы, либо нетерминалы.

1. Строчные буквы из конца алфавита, такие как u, v, …, z, обозначают строки терминалов.

1. Строчные греческие буквы, такие как α, β, µ, представляют строки грамматических символов. Таким образом, в общем виде продукция может быть записана как А → α, в которой одиночный нетерминал А располагается справа от стрелки, а строка грамматических символов α – справа от стрелки.

1. Если А → α₁, A → α₂, …, A → α_k представляют собой продукции с А в левой части, то можем записать А → α₁| α₂| …| α_k. Мы называем α₁, α₂, …, α_k альтернативами А.

2. Если иное не указано явно, левая часть первой продукции является стартовым символом.

1. Продукция - →.

Классификация грамматик и я зыков по Хомскому

(грамматики классифицируются по виду их правил вывода)

Тип 0:

Грамматика G = (VT, VN, P, S), называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики).

Тип 1:

Грамматика G = (VT, VN, P, S), называется неукорачивающей грамматикой, если каждое правило Р имеет вид α → β, где α € (VTﮟVN)⁺, β € (VTﮟVN)⁺ и | α| <= | β|.

Грамматика G = (VT, VN, P, S), называется контекстно-зависимой (КЗ), если каждое правило из Р имеет вид α → β, где α = ξ₁А ξ₂; β = ξ₁γ ξ₂; А € VN; γ € (VTﮟVN)⁺; ξ₁, ξ₂ € (VTﮟVN)*.

Тип 2:

Грамматика G = (VT, VN, P, S), называется контекстно-свободной (КС), если каждое правило из Р имеет вид А → β, где А € VN, β € (VTﮟVN)⁺.

Грамматика G = (VT, VN, P, S), называется укорачивающей контекстно-свободной (УКС), если каждое правило из Р имеет вид А → β, где А € VN, β € (VTﮟVN)*.

Тип 3:

Грамматика G = (VT, VN, P, S), называется праволинейной, если каждое правило из Р имеет вид А → tB либо А →t, где А € VN, В € VN, t € VN.

Грамматика G = (VT, VN, P, S), называется леволинейной, если каждое правило из Р имеет вид А→ Bt либо А →t, где А € VN, В € VN, t € VN.

Алгоритм «Устранение левой рекурсии»

Вход. Грамматика G без циклов и ε-продукций.

Выход. Эквивалентная грамматика без левой рекурсии.

Метод. Применить алгоритм устранения левой рекурсии. Результирующая грамматика без левой рекурсии может иметь ε-продукции.

1. Расположить нетерминалы в некотором порядке А₁, А₂, ..., А_n

2. for i:=1 to n do begin

for j:=1 to i-1 do begin

Заменить каждую продукцию вида A_i → A_jγ

Продукциями А →δ_1γ| δ_2γ| …| δ_kγ

Где А_j А →δ₁| δ₂| …| δ_k – все текущие А_j – продукции

End

Устранить непосредственную левую рекурсию

Среди А_i – продукций

End

Алгоритм «Левая факторизация грамматики»

Вход. Грамматика G.

Выход. Эквивалентная левофакторизованная грамматика

Метод. Для каждого нетерминала А находим наидлиннейший префикс α, общий для двух или большего числа альтернатив. Если α≠ε, т е имеется нетривиальный общий префикс, заменим все продукции А→αβ₁| αβ₂| …| αβ_n| γ, где γ представляет все альтернативы, не начинающиеся с α, продукциями

А →αА’| γ

A’→ β₁| β₂| …| β_n

Здесь А’ – новый нетерминал. Выполняем это преобразование до тех пор, пока никакие две альтернативы не будут иметь общий префикс.

Условие:

1. По описанию языка построить порождающую грамматику.

2. Определить тип построенной грамматики и свойства.

3. Построить для трех примеров деревья разбора.

4. Если грамматика является леворекурсивной, то устранить её.

5. Если грамматика является не левофакторизованной, то левофакторизовать.

6. Для модифицированной грамматики построить деревья разбора по тем же примерам что и в п.3

Варианты:

Пример построения КС-грамматики:

1. Дано описание языка: <E> ::= <E> ‘+’ <E> | <E> ‘*’ <E> | ‘(‘ <E> ‘)’ | ‘i’

2. Построим грамматику о описанию языка:

1. Грамматика является контекстно-свободной (КС), потому что символы левой части - нетерминалы, а символы правой части – терминалы или нетерминалы.

2. Построим для трех примеров деревья разбора

1. i+ (i+i)

1. (i+i)*(i+i)+i

1. i*i+i*(i+i)

1. Грамматика является леворекурсивной. Преобразуем грамматику.

α₁=+Е β₁=(Е)

Характеристики

Список файлов книги