Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 15 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

17
3. Разбор цепочек. Распознаватели
Разбор цепочек
Цепочка принадлежит языку, порождаемому грамматикой, только в том
случае, если существует ее вывод из цели этой грамматики. Процесс построе-
ния такого вывода называется разбором.
С практической точки зрения наибольший интерес представляет разбор по
контекстно-свободным (КС и УКС) грамматикам. Их порождающей мощно-
сти достаточно для описания большей части синтаксической структуры языков
программирования. Для различных подклассов КС-грамматик имеются хорошо
разработанные практически приемлемые способы решения задачи разбора.
Вывод цепочки β ∈ (VT)
*
из S ∈ VN в КС-грамматике G = (VT, VN, P, S),
называется левым (левосторонним), если в этом выводе каждая очередная сен-
тенциальная форма получается из предыдущей заменой самого левого нетер-
минала.
Вывод цепочки β ∈ (VT)
*
из S ∈ VN в КС-грамматике G = (VT, VN, P, S),
называется правым (правосторонним), если в этом выводе каждая очередная
сентенциальная форма получается из предыдущей заменой самого правого не-
терминала.
В грамматике для одной и той же цепочки может быть несколько выводов,
эквивалентных в том смысле, что в них в одних и тех же местах применяются
одни и те же правила вывода, но в различном порядке.
Например, для цепочки a+b+a в грамматике G = ({a,b}, {S,T}, {S→T | T+S;
T → a|b}, S) можно построить выводы:
(1) S→T+S→T+T+S→T+T+T→a+T+T→a+b+T→a+b+a
(2) S→T+S→a+S→a+T+S→a+b+S→a+b+T→a+b+a
(3) S→T+S→T+T+S→T+T+T→T+T+a→T+b+a→a+b+a
Здесь (2) – левосторонний вывод, (3) – правосторонний, а (1) не является
ни левосторонним, ни правосторонним. Однако все эти выводы являются экви-
валентными в указанном выше смысле.
Для КС-грамматик можно ввести удобное графическое представление вы-
вода, называемое деревом вывода, причем для всех эквивалентных выводов де-
ревья вывода совпадают.
Определение: дерево называется деревом вывода (или деревом разбора) в
КС-грамматике G = {VT, VN, P, S), если выполнены следующие условия:
1. каждая вершина дерева помечена символом из множества (VN ∪ VT ∪
λ), при этом корень дерева помечен S; листья – символами из (VT ∪ λ);
2. если вершина дерева помечена символом A ∈ VN, а ее непосредствен-
ные потомки – символами a
1
,a
2
,...,a
n
, где каждое a
i
∈ (VT ∪ VN), то A → a
1
a
2
...a
n
– правило вывода в этой грамматике;
3. если вершина дерева помечена символом A ∈ VN, а ее единственный
непосредственный потомок помечен символом λ, то A → λ – правило вывода в
этой грамматике.

Страницы