Лекция 01. Тема Общая характеристика языков программирования высокого уровня

 
<присвоить>:=<выражение>;
Пример 1. 
Пусть требуется описать грамматику для представления языка 
программирования, на котором можно писать программы с тремя 
переменными A, B, C, операторами присваивания “ := “ , арифмитическими 
выражениями со знаками операций “+”, “-” и ключевыми словами begin, 
end.
Грамматика представляется следующим образом:
T={A, B, C, :=, +, - , ; , begin, end}
V={<программа>, <оператор>, <список операторов>, <переменная>, 
<выражение>}
S={<программа>}
P : <программа>

begin

<список операторов>end
< список_операторов > 

< оператор > |< оператор >;
< список_операторов >
 

---

< оператор > 

< переменная > := < выражение >
 
< переменная > 

A | B | C
 
< выражение > 

< переменная > + < переменная > 
 
|< переменная > - < переменная > 
 
| < переменная >
 
Пример порождения в описанной грамматике:
 
< программа > => begin < список_операторов > end
 
=> begin |< оператор >; < список_операторов > end
 
=> begin < переменная >:= < выражение >;< список_операторов 
> end
 
=> begin A := < выражение > ; < список_операторов > end
 
=> begin A := < переменная > + < переменная > ;
 
< список_операторов > end
 
=> begin A := B + < переменная >; < список_операторов > end
 
=> begin A := B + C ; < список_операторов > end
 
=> begin A := B + C ; < оператор > end
 
=> begin A := B + C ; < переменная > := < выражение >end
 
=> begin A := B + C ; В := < выражение >end
 
=> begin A := B + C ; В := < переменная >end
 
=> begin A := B + C ; В := С end
 
Каждая строка вывода называется сентенциальной формой. Здесь 
реализован левосторонний порядок вывода (левое порождение), т.е. 
подстановка формул осуществлялась слева (может быть и правосторонний 
вывод). Сентенциальная форма, в которой присутствуют только лексемы и 
терминалы называется порожденным предложением.
 

---

Лекция 16 
6.3. Синтаксические деревья
Порождения можно представить в виде синтаксического дерева или 
дерева разбора, которое графически показывает, как группируются символы 
(терминалы) в цепочки языка.
Определение. Синтаксическое дерево – это графическое представление 
порождения в виде иерархического списка, в котором:
1. Корень дерева – это стартовый символ грамматики - S.
2. Узлы (вершины) дерева могут быть либо внутренними, т.е. являться 
переменными, принадлежащими множеству V, либо конечными – 
терминалами, которые принадлежат множеству T. При этом внутренние узлы 
всегда имеют наследников, конечные называются листьями дерева и 
потомков не имеют.
3. Если внутренний узел помечен переменой A

V, а ее наследники 
отмечены листьями x
1
,x
2
,…,x
n
, то А является продукцией, порождающей 
цепочку x
1
,x
2
,…,x
n
(А

x
1
,x
2
,…,x
n
), причем x
1
,x
2
,…,x
n
выписаны слева 
направо по дереву.
Пример 2. 
 
Пусть дана грамматика:
 
<присвоить> 

< идентификатор > := <выражение>