Конспект лекций «Методы построения компиляторов»

Грамматики

Контекстно свободные грамматики. Определение. Терминалы, нетерминалы, символы. Продукции. Стартовый символ.

Обозначения

a,b,c, ... - терминалы
u,v,w,x,y,z - строки терминалов
A,B,C, ... - нетерминалы
α,β,γ, ... - строки нетерминалов

Пример. Грамматика арифметических выражений.

E → E+E | E*E | (E) | -E | id

Порождение (вывод).

Обозначения

=>
=>*
=>+

Опр. Сентенциальной формой (цепочкой) грамматики называется строка, которая может быть выведена из стартового символа.

Опр. Предложением грамматики называется сентенциальная форма, состоящая из одних терминалов.

Опр. Языком L(G) грамматики G называется множество всех ее предложений.

Левое, правое порождение. Примеры.

Обозначения

=>(lm)
=>(lm)*
=>(rm)+

Дерево разбора строки грамматики. В отличие от порождения, из него исключена информация о порядке вывода.

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

Пример неоднозначной грамматики.

stmt → if expr then stmt
     | if expr then stmt else stmt
     | other  

Леворекурсивные грамматики, их проблемы. Алгоритм устранения левой рекурсии.

Синтаксический анализ

Понятие синтаксического анализатора.

Нисходящие (top-down) и восходящие (bottom-up) синтаксические анализаторы

Нисходящий анализ

Опр. Синтаксический анализатор, работающий методом рекурсивного спуска и не требующий откатов, называется предиктивным синтаксическим анализатором.