Лекция: Атрибутные грамматики
Атрибутные грамматики, впервые предложенные Д. Кнутом, в идеале призваны контролировать смысловую корректность формальных грамматик. Смысл обычно задается операционно или декларативно.
Атрибутные грамматики позволяют работать с атрибутами — (дополнительными) характеристиками, которые приписываются операторам и операндам.
В примерах грамматики с синтезируемыми атрибутами (восходящие грамматики) и наследуемыми атрибутами (нисходящие грамматики).
Пусть дан фрагмент грамматики:
S ® T | T * T | (T)
T ® T + T | T * T | a | b | c | d
Тогда дерево вывода и пример атрибутной грамматики с синтезируемыми атрибутами (здесь с числовыми типами) будет:
| r * i ® r + -
a b c d r r i i i — integer r — real |
S
T * T
T + T T — T
Пример наследуемых атрибутов приведен на следующем рисунке:
x:= if A then b else C
:=
i
x if i r®i
A B C
b r i
YACC
yacc — программа синтаксического анализа (yet another compile of compiles).
Также как и lex– ‘она начально была написана, как команда для ОС UNIX.
Часто эти команды используются совместно.