Атрибутные транслирующие грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «<wikitex>Часто, осуществляя разбор, мы хотим извлечь какие-то данные или что-то сделать, а не ...»)
 
Строка 24: Строка 24:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Транслирующий символ''' {{---}} нетерминал, который раскрывается в $\varepsilon$ и вместе с раскрытием выполняет какое-то действие, которое с ним связано.
+
'''Транслирующий символ''' {{---}} нетерминал, который раскрывается в $\varepsilon$ и в момент раскрытия выполняет какое-то действие, которое с ним связано. Для простоты действия пишутся в фигурных скобках в том месте, где это нужно.
 
}}
 
}}
  
 +
Для наглядности, на протяжении всей статьи будет рассматривать в качестве примера грамматику для арифметических выражений:
 +
$
 +
E \to T + E \mid T \\
 +
T \to F \times T \mid F \\
 +
F \to n \mid (E)
 +
$
 +
 +
После [[Устранение_левой_рекурсии| устранения левой рекурсии]] имеем следующее:
 +
 +
$
 +
E \to TE' \\
 +
E' \to +TE' \mid \varepsilon \\
 +
T \to FT' \\
 +
T' \to * FT' \mid \varepsilon \\
 +
F \to n \mid (E)
 +
$
 +
 +
 +
Например, атрибутом терминала $n$ будет число, которое он представляет: ($n.val = 123$). Атрибутами нетерминалов будут значения, вычисленные в поддереве.
 +
В процессе трансляции происходит присваивание атрибутов одних элементов грамматики другим элементам грамматики, при этом присваивание может происходить более сложным способом, чем простое копирование. В некоторых случаях могут быть нужны какие-то побочные эффекты, например вывод кода или взаимодействие с глобальным контекстом. Для этого нужны транслирующие символы.
 +
 +
 +
Заменим правило $T \rightarrow T*F$ на следующее: $T \rightarrow T*F\{T_0.val=T_1.val*F.val\}$, где $\{T_0.val=T_1.val*F.val\}$ {{---}} транслирующий символ. Аналогично к  $F \rightarrow n$ добавляется $\{F.val = n.val\}$.
  
  

Версия 15:17, 3 июня 2015

<wikitex>Часто, осуществляя разбор, мы хотим извлечь какие-то данные или что-то сделать, а не просто выяснить, разбирается ли текст в данной грамматике. Вообще говоря, сначала можно получить дерево разборы, а потом уже, обойдя дерево разбора, по нему производить какие-то действия. В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда это дерево слишком расточительно хранить в памяти. В связи с этим хочется какие-то действия производить уже на этапе разбора. Такой подход называется Синтаксически управляемой трансляцией.


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


Определение:
Синтаксически управляемая трансляция — это трансляция, при которой в процессе разбора строки сразу выполняются какие-то действия, не используя промежуточное представление в виде дерева разбора.


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


Определение:
Атрибут — дополнительное поле с данными у терминалов и нетерминалов. (Более строгое определение требует ввести систему типов).


Определение:
Транслирующий символ — нетерминал, который раскрывается в $\varepsilon$ и в момент раскрытия выполняет какое-то действие, которое с ним связано. Для простоты действия пишутся в фигурных скобках в том месте, где это нужно.


Для наглядности, на протяжении всей статьи будет рассматривать в качестве примера грамматику для арифметических выражений: $ E \to T + E \mid T \\ T \to F \times T \mid F \\ F \to n \mid (E) $

После устранения левой рекурсии имеем следующее:

$ E \to TE' \\ E' \to +TE' \mid \varepsilon \\ T \to FT' \\ T' \to * FT' \mid \varepsilon \\ F \to n \mid (E) $


Например, атрибутом терминала $n$ будет число, которое он представляет: ($n.val = 123$). Атрибутами нетерминалов будут значения, вычисленные в поддереве. В процессе трансляции происходит присваивание атрибутов одних элементов грамматики другим элементам грамматики, при этом присваивание может происходить более сложным способом, чем простое копирование. В некоторых случаях могут быть нужны какие-то побочные эффекты, например вывод кода или взаимодействие с глобальным контекстом. Для этого нужны транслирующие символы.


Заменим правило $T \rightarrow T*F$ на следующее: $T \rightarrow T*F\{T_0.val=T_1.val*F.val\}$, где $\{T_0.val=T_1.val*F.val\}$ — транслирующий символ. Аналогично к $F \rightarrow n$ добавляется $\{F.val = n.val\}$.



</wikitex>