Редактирование: Атрибутные транслирующие грамматики

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
  
 
Часто, осуществляя разбор, мы хотим извлечь какие-то данные или произвести какие-то действия, а не просто выяснить, разбирается ли текст в данной грамматике.
 
Часто, осуществляя разбор, мы хотим извлечь какие-то данные или произвести какие-то действия, а не просто выяснить, разбирается ли текст в данной грамматике.
Вообще говоря, сначала можно получить [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора|дерево разбора]], а потом уже, обходя его, выполнять эти действия.
+
Вообще говоря, сначала можно получить дерево разбора, а потом уже, обходя его, выполнять эти действия.
 
В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда его просто слишком расточительно хранить в памяти целиком.
 
В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда его просто слишком расточительно хранить в памяти целиком.
 
В связи с этим хочется какие-то действия производить уже на этапе разбора.
 
В связи с этим хочется какие-то действия производить уже на этапе разбора.
Строка 7: Строка 7:
 
Например, мы хотим не только построить дерево разбора для арифметических выражений, а ещё и вычислить значение этого выражения. Возможно, даже не строя само дерево разбора.
 
Например, мы хотим не только построить дерево разбора для арифметических выражений, а ещё и вычислить значение этого выражения. Возможно, даже не строя само дерево разбора.
 
   
 
   
Такой подход называется '''синтаксически управляемой трансляцией'''.
+
Такой подход называется '''Синтаксически управляемой трансляцией'''.
  
 
==Синтаксически управляемая трансляция==
 
==Синтаксически управляемая трансляция==
Строка 13: Строка 13:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Синтаксически управляемое определение''' ''(англ. syntax-directed definition)'' является [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|контекстно-свободной]] грамматикой с атрибутами и правилами. Атрибуты связаны с грамматическими символами, а правила — с продукциями.  
+
'''Синтаксически управляемое определение''' (СУО) является [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|контекстно-свободной]] грамматикой с атрибутами и правилами. Атрибуты связаны с грамматическими символами, а правила — с продукциями.  
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Синтаксически управляемая трансляция''' ''(англ. syntax-directed translation)'' {{---}} это трансляция, при которой в [[Предиктивный_синтаксический_анализ| процессе разбора]] строки сразу выполняются какие-то действия, без использования промежуточного представления в виде дерева разбора.
+
'''Синтаксически управляемая трансляция''' {{---}} это трансляция, при которой в [[Предиктивный_синтаксический_анализ| процессе разбора]] строки сразу выполняются какие-то действия, без использования промежуточного представления в виде дерева разбора.
 
}}
 
}}
  
Строка 25: Строка 25:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Атрибут''' ''(англ. attribute)'' {{---}} дополнительные данные, ассоциированные с грамматическими символами. Если $X$ представляет собой символ, а $a$ — один из его атрибутов, то значение $a$ в некотором узле дерева разбора, помеченном $X$, записывается как $X.a$. Если узлы дерева разбора реализованы в виде записей или объектов, то атрибуты $X$ могут быть реализованы как поля данных в записях, представляющих узлы $X$. Атрибуты могут быть любого вида: числами, типами, таблицами ссылок или строками.
+
'''Атрибут''' {{---}} дополнительные данные, ассоциированные с грамматическими символами.Если $X$ представляет собой символ, а $a$ — один из его атрибутов, то значение $a$ в некотором узле дерева разбора, помеченном $X$, записывается как $X.a$. Если узлы дерева разбора реализованы в виде записей или объектов, то атрибуты $X$ могут быть реализованы как поля данных в записях, представляющих узлы $X$. Атрибуты могут быть любого вида: числами, типами, таблицами ссылок или строками.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Дерево разбора, в каждом узле которого атрибуты уже вычислены, называется '''аннотированным''' ''(англ. annotated)'', а процесс вычисления этих атрибутов {{---}} '''аннотированием''' дерева разбора.
+
Дерево разбора, в каждом узле которого атрибуты уже вычислены, называется '''аннотированным''', а процесс вычисления этих атрибутов - '''аннотированием''' дерева разбора.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|id = tr_char
 
 
|definition =
 
|definition =
'''Транслирующий символ''' {{---}} нетерминал, который раскрывается в $\varepsilon$ и в момент раскрытия выполняет связанное с ним действие. Действия пишутся в фигурных скобках рядом с транслирующим символом.
+
'''Транслирующий символ''' {{---}} нетерминал, который раскрывается в $\varepsilon$ и в момент раскрытия выполняет какое-то действие, которое с ним связано. Действия пишутся в фигурных скобках рядом с транслирующим символом.
 
}}
 
}}
  
Строка 44: Строка 43:
 
S \to E \\  
 
S \to E \\  
 
E \to E + T \mid T \\
 
E \to E + T \mid T \\
T \to T * F \mid F \\
+
T \to T \times F \mid F \\
 
F \to n \mid (E)  
 
F \to n \mid (E)  
 +
$
 +
 +
Заметим, что для нисходящего разборщика нужно будет сперва [[Устранение_левой_рекурсии| устранить левую рекурсию]]:
 +
 +
$
 +
S \to E \\
 +
E \to TE' \\
 +
E' \to +TE' \mid \varepsilon \\
 +
T \to FT' \\
 +
T' \to * FT' \mid \varepsilon \\
 +
F \to n \mid (E)
 
$
 
$
  
Строка 52: Строка 62:
  
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Продукция
+
!style="background-color:#EEE"| продукции
 
!style="background-color:#EEE"| Семантические правила
 
!style="background-color:#EEE"| Семантические правила
 
|-
 
|-
Строка 58: Строка 68:
 
|style="background-color:#FFF;padding:2px 30px"| $A.s = B.i \\ B.i = A.s+1$
 
|style="background-color:#FFF;padding:2px 30px"| $A.s = B.i \\ B.i = A.s+1$
 
|}
 
|}
Данные правила циклические: невозможно вычислить ни $A.s$ в узле, ни $B.i$ в дочернем узле, не зная значение другого атрибута.  
+
Данные правила циклические; невозможно вычислить ни $A.s$ в узле, ни $B.i$ в дочернем узле, не зная значение другого атрибута.  
 
Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов.
 
Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов.
 
</wikitex>
 
</wikitex>
Строка 66: Строка 76:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Атрибут''', значение которого зависит от значений атрибутов детей данного узла или от других атрибутов этого узла, то атрибут называется '''синтезируемым''' ''(англ. synthesized attribute)''.
+
'''Атрибут''', значение которого зависит от значений атрибутов детей данного узла или от других атрибутов этого узла, то атрибут называется '''синтезируемым'''.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Грамматика называется '''S-атрибутной''' ''(англ. S-attributed definition)'', если с атрибутами выполняются только операции присваивания значений других атрибутов, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. То есть в грамматике используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх, от листьев к корню.
+
Грамматика называется '''S-атрибутной''', если с атрибутами выполняются только операции присваивания значений других атрибутов, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. То есть в грамматике используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх, от листьев к корню.
 
}}
 
}}
 
</wikitex>
 
</wikitex>
 
===Пример S-атрибутной грамматики===
 
===Пример S-атрибутной грамматики===
 
<wikitex>
 
<wikitex>
Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$ (здесь $\{ADD {{...}} \}$ и $\{MUL {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующие символы]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):
+
Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$:
 +
(Здесь $\{ADD {{...}} \}$ и $\{MUL {{...}} \}$ - транслирующие символы)
  
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
 
!style="background-color:#EEE"| Продукция
 
!style="background-color:#EEE"| Продукция
 
!style="background-color:#EEE"| Семантические правила
 
!style="background-color:#EEE"| Семантические правила
!style="background-color:#EEE"| Пояснения
 
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 30px"| $S \to E$
 
|style="background-color:#FFF;padding:2px 30px"| $S \to E$
 
|style="background-color:#FFF;padding:2px 30px"| $S.val=E.val$
 
|style="background-color:#FFF;padding:2px 30px"| $S.val=E.val$
|style="background-color:#FFF;padding:2px 30px"|
 
 
|-
 
|-
|style="background-color:#FFF;padding:2px 30px"| $E_0 \to E_1 + T\ \{ADD\  res = op_1 + op_2\}$
+
|style="background-color:#FFF;padding:2px 30px"| $val\  E \to E + T\ \{ADD\  res = op_1 + op_2\}$
 
|style="background-color:#FFF;padding:2px 30px"| $ADD.op_1=E_1.val \\ ADD.op_2=T.val \\ E_0.val=ADD.res $
 
|style="background-color:#FFF;padding:2px 30px"| $ADD.op_1=E_1.val \\ ADD.op_2=T.val \\ E_0.val=ADD.res $
|style="background-color:#FFF;padding:2px 30px"| В фигурных скобках {{---}} действия транслирующего символа ADD. $op_1$, $op_2$ и $res$ {{---}} атрибуты транслирующего символа.
 
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 30px"| $E \to T$
 
|style="background-color:#FFF;padding:2px 30px"| $E \to T$
 
|style="background-color:#FFF;padding:2px 30px"| $E.val=T.val$
 
|style="background-color:#FFF;padding:2px 30px"| $E.val=T.val$
|style="background-color:#FFF;padding:2px 30px"|
 
 
|-
 
|-
|style="background-color:#FFF;padding:2px 30px"| $T_0 \to T_1 * F \ \{MUL\  res = op_1 \times op_2\}$
+
|style="background-color:#FFF;padding:2px 30px"| $val\  T \to T \times F \ \{MUL\  res = op_1 * op_2\}$
 
|style="background-color:#FFF;padding:2px 30px"| $MUL.op_1=T.val \\ MUL.op_2=F.val \\ T_0.val=MUL.res$
 
|style="background-color:#FFF;padding:2px 30px"| $MUL.op_1=T.val \\ MUL.op_2=F.val \\ T_0.val=MUL.res$
|style="background-color:#FFF;padding:2px 30px"| В фигурных скобках {{---}} действия транслирующего символа MUL. $op_1$, $op_2$ и $res$ {{---}} атрибуты транслирующего символа.
 
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 30px"| $T \to F$
 
|style="background-color:#FFF;padding:2px 30px"| $T \to F$
 
|style="background-color:#FFF;padding:2px 30px"| $T.val=F.val$
 
|style="background-color:#FFF;padding:2px 30px"| $T.val=F.val$
|style="background-color:#FFF;padding:2px 30px"|
 
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 30px"| $F \to n$
 
|style="background-color:#FFF;padding:2px 30px"| $F \to n$
 
|style="background-color:#FFF;padding:2px 30px"| $F.val=n.val$
 
|style="background-color:#FFF;padding:2px 30px"| $F.val=n.val$
|style="background-color:#FFF;padding:2px 30px"|
 
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 30px"| $F \to (E)$
 
|style="background-color:#FFF;padding:2px 30px"| $F \to (E)$
 
|style="background-color:#FFF;padding:2px 30px"| $F.val=E.val$
 
|style="background-color:#FFF;padding:2px 30px"| $F.val=E.val$
|style="background-color:#FFF;padding:2px 30px"|
 
 
|}
 
|}
  
 
В нашем примере видно, что $val$ зависит только от детей в дереве разбора, то есть это синтезируемый атрибут. Результат умножителя ($MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемым(аналогично с сумматором $ADD$).  
 
В нашем примере видно, что $val$ зависит только от детей в дереве разбора, то есть это синтезируемый атрибут. Результат умножителя ($MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемым(аналогично с сумматором $ADD$).  
  
[[Файл:3mul5add4.png|500px|thumb|center|Аннотированное дерево разбора для '''$3*5+4$''']]
+
[[Файл:3mul5add4.png|600px|thumb|center|аннотированное дерево разбора для '''3*5+4''']]
  
 
После такого разбора в $S.val$ будет лежать вычисленное значение выражения. Можно, например сразу напечатать его, добавив к нему правило $\{print(S.val)\}$.
 
После такого разбора в $S.val$ будет лежать вычисленное значение выражения. Можно, например сразу напечатать его, добавив к нему правило $\{print(S.val)\}$.
  
 +
Хотя всегда можно переписать синтаксически управляемое определение таким образом, чтобы использовались только синтезируемые атрибуты, зачастую более удобно и естественно будет воспользоваться также и наследуемыми атрибутами.
 
</wikitex>
 
</wikitex>
  
Строка 125: Строка 129:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Атрибут''', значение которого зависит от значений атрибутов братьев узла или атрибутов родителя, называется '''наследуемым''' ''(англ. inherited attribute)''.  
+
'''Атрибут''', значение которого зависит от значений атрибутов братьев узла или атрибутов родителя, называется '''наследуемым'''.  
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Грамматика называется '''L-атрибутной''' ''(англ. L-attributed definition)'', если значения наследуемых атрибутов зависят только от родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа).
+
Грамматика называется '''L-атрибутной''', если значения наследуемых атрибутов зависят только от родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа).
 
}}
 
}}
 
</wikitex>
 
</wikitex>
 
===Пример L-атрибутной грамматики===
 
===Пример L-атрибутной грамматики===
 
<wikitex>
 
<wikitex>
Для наглядности рассмотрим грамматику объявления переменных
+
Выпишем продукции и ассоциируем с ними семантические правила для грамматики объявления переменных:
(в начале строки идет тип, затем через запятую имена переменных. Примеры строк, разбираемых в ней: '''int a''' или '''real x,y,z''' и подобные):
 
 
 
$
 
D \to TL \\
 
T \to int \mid real \\
 
L \to L,id \mid id
 
$
 
 
 
 
 
Выпишем продукции (с транслирующими символами) и ассоциируем с ними семантические правила
 
(здесь $\{ENTRY {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующий символ]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):
 
  
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
Строка 161: Строка 154:
 
|style="background-color:#FFF;padding:2px 30px"| $T.type = real$
 
|style="background-color:#FFF;padding:2px 30px"| $T.type = real$
 
|-
 
|-
|style="background-color:#FFF;padding:2px 30px"| $L_0 \to L_1,id\ \{ENTRY addtype(key, value)\}$
+
|style="background-color:#FFF;padding:2px 30px"| $L \to L,id\ \{ENTRY addtype(key, value)\}$
|style="background-color:#FFF;padding:2px 30px"| $L_1.inh = L0.inh \\ ENTRY.key=id.text \\ ENTRY.value=L_0.inh$
+
|style="background-color:#FFF;padding:2px 30px"| $L_1.in=L.inh \\ ENTRY.key=id.entry \\ ENTRY.value=L.inh$
 
|-
 
|-
|style="background-color:#FFF;padding:2px 30px"| $L \to id\ \{ENTRY addtype(key, value)\}$
+
|style="background-color:#FFF;padding:2px 30px"| $L.id \to id\ \{ENTRY addtype(key, value)\}$
|style="background-color:#FFF;padding:2px 30px"| $ENTRY.key=id.text \\ ENTRY.value=L.inh$
+
|style="background-color:#FFF;padding:2px 30px"| $ENTRY.key=id.entry \\ ENTRY.value=L.inh$
 
|}
 
|}
  
Семантическое правило  $L.inh = T.type$, связанное с продукцией $D \to TL$, определяет наследуемый атрибут $L.inh$ как тип объявления. Затем приведенные правила распространяют этот тип вниз по дереву разбора с использованием атрибута $L.inh$. Транслирующий символ $ENTRY$, связанный с продукциями для $L$, вызывает процедуру $addtype$ для добавления типа каждого идентификатора к его записи в таблице символов (по ключу, определяемому атрибутом $text$).
+
Семантическое правило  $L.inh = T.type$, связанное с продукцией $D \to TL$, определяет наследуемый атрибут $L.inh$ как тип объявления. Затем приведенные правила распространяют этот тип вниз по дереву разбора с использованием атрибута $L.inh$. Транслирующий символ ENTRY, связанный с продукциями для $L$, вызывает процедуру $addtype$ для добавления типа каждого идентификатора к его записи в таблице символов (по ключу, определяемому атрибутом $entry$).
  
[[Файл:Real_id1,_id2,_id3.png|600px|center|thumb|Аннотированное дерево разбора для '''$\mathbf{real}\ id1,\ id2,\ id3$'''|600px]]
+
[[Файл:Real_id1,_id2,_id3.png|600px|center|thumb|аннотированное дерево разбора для '''real id1, id2, id3'''|600px]]
</wikitex>
 
 
 
==Пример работы с атрибутами в нисходящем разборе==
 
<wikitex>
 
Рассмотрим работы с атрибутами на примере LL(1)-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Предиктивный_синтаксический_анализ | разборщика]] для нее:
 
 
 
$
 
E \to TE' \\
 
E' \to +TE' \mid \varepsilon \\
 
T \to FT' \\
 
T' \to * FT' \mid \varepsilon \\
 
F \to n \mid (E)
 
$
 
 
 
В данной реализации рекурсивные функции от нетерминалов получают на вход (если необходимо) наследуемые атрибуты узла и возвращают вершины дерева разбора, в атрибутах которых записан результат вычислений соответствующего подвыражения. Однако этот код легко изменить, чтобы он только вычислял значение выражения и не строил дерево разбора. Как мы видим, $val$ {{---}} синтезируемый атрибут, $acc$ {{---}} наследуемый атрибут, $ADD$ {{---}} транслирующий символ. Синим подсвечены строки, отвечающие за работу с атрибутами.
 
 
 
Здесь <tex>\mathtt{Node}</tex> {{---}} структура следующего вида:
 
'''struct''' Node
 
    children : '''map<String, Node>'''
 
    name : '''string'''
 
    val : '''int'''                  <font color="green">// атрибут нетерминала</font>
 
    '''function''' addChild('''Node''')    <font color="green">// функция, подвешивающая поддерево к данному узлу</font>
 
 
 
 
 
E() : '''Node'''
 
    Node res = Node("E")
 
    '''switch''' (curToken)
 
        '''case''' n, '('  :
 
            res.addChild(T())            <font color="green">// подвешиваем левого сына</font>
 
            <font color="blue">temp = res.children["T"].val</font> <font color="green">// атрибут левого сына</font>
 
            <font color="blue">Node rightSon = E'(temp)    </font> <font color="green">// отдадим атрибут левого сына правому как наследуемый атрибут</font>
 
            <font color="blue">res.addChild(rightSon)    </font>  <font color="green">// подвешиваем правого сына сына</font>
 
            <font color="blue">res.val = res.children["E'"].val</font>
 
            '''break'''
 
        '''default''' :
 
            <font color="red">error</font>("unexpected char")
 
    '''return''' res
 
 
 
 
 
E'(acc) : '''Node'''
 
    Node res = Node("E'")
 
    '''switch''' (curToken)
 
        '''case''' '+' :
 
            consume('+')
 
            res.addChild(Node("+"))
 
            res.addChild(T())
 
            <font color="blue">temp = res.children["T"].val
 
            ADD.res = ADD(acc, temp)  <font color="green">// ADD проведет вычисления из наследуемого атрибута add и атрибута ребенка "T"</font>
 
            res.addChild(E'(ADD.res)) <font color="green">// результат вычислений будет передан правому ребенку как наследуемый атрибут</font>
 
            res.val = res.children["E'"].val</font>
 
            '''break'''
 
        '''case''' '$', ')' :
 
            <font color="blue">res.val = acc</font>
 
            '''break'''
 
        '''default''' :
 
            <font color="red">error</font>("unexpected char")
 
      '''return''' res
 
 
 
F() : '''Node'''
 
    Node res = Node("F")
 
    '''switch''' (curToken)
 
        '''case''' n :
 
            consume(n)
 
            res.addChild(Node(curToken))
 
            <font color="blue">res.val = n.val</font>
 
            '''break'''
 
        '''case''' '(' :
 
            consume('(')
 
            res.addChild(Node("("))
 
            res.addChild(E())
 
            <font color="blue">rev.val = res.children["E"].val</font>
 
            consume(')')
 
            res.addChild(Node(")"))
 
        '''default''' :
 
            <font color="red">error</font>("unexpected char")
 
    '''return''' res
 
 
 
Функции для $T$ и $T'$ строятся аналогично.
 
 
 
[[Файл:2add3add7.png|600px|center|thumb| Дерево разбора для '''$2\ +\ 3\ +\ 7$''']]
 
 
</wikitex>
 
</wikitex>
  
 
==Атрибуты в ANTLR==
 
==Атрибуты в ANTLR==
  
Общедоступный генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение.  
+
Общедоступный генератора разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение. Рассмотрим для примера грамматику арифметических выражений.
 
 
Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+,\ *</tex>, скобками и выводом результата выражения пример на ANTLR.
 
 
 
grammar Expression;
 
'''@header''' { package ru.ifmo.ctddev.wiki; }
 
  
Естественным образом можно добавлять действия в продукции, где это нужно. Действия выполняются после предыдущего элемента грамматики и до следующего.
+
Вне продукций грамматики бывает нужно вставить в сгенерированный разборщик(для Java) package, import, а также некоторые поля и методы. Это делается с помощью '''@header''' и '''@members''':
  
Стартовый нетерминал печатает результат:
+
grammar Expr;
  s : expr { System.out.println($expr.val); };
+
  @header { package tools; import java.util.*; }
 +
@parser::members {
 +
    Map<String, Integer> memory = new HashMap<String, Integer>();
 +
    int eval(int left, int op, int right) {
 +
        ...
 +
    }
 +
}
  
В продукции для нетерминала <code>expr</code> определяется возвращаемое значение (<code>['''int''' val]</code>). Обращение к этому атрибуту имеет вид <code>$expr.value</code>. В фигурных скобках записаны семантические правила.
+
Естественным образом можно добавлять действия в продукции, где это нужно:
 +
stat: e NEWLINE {System.out.println($e.val);}
 +
    | ID '=' e NEWLINE {memory.put($ID.text, $e.val);}
 +
    | NEWLINE ;
  
Разобранные нетерминалы возвращают результат, вычисленный в поддереве(<code>returns [int val]</code>) как свой синтезируемый атрибут, процесс вычисления которого описан в фигурных скобках <code>{ $val = $exprP.val; }</code>.
+
Действия выполняются после предыдущего элемента грамматики и до следующего. В данном примере действия добавлены на конце альтернативы, поэтому действие выполнится после того, как разборщик распознает все выражение. Когда разборщик встречает выражение, за которым идет символ новой строки, ему нужно напечатать результат. Когда он встречает присваивание - ему нужно записать имя и значение переменной в память.
  
Наследуемые атрибуты передаются нетерминалу как параметр(<code>exprP[$term.val]</code>).
+
Правило для '''e''' теперь выглядит следующим образом:
  
  expr '''returns''' ['''int''' val]
+
  e returns [int val]
    : term exprP[$term.val]     { $val = $exprP.val; }
+
  : a=e op=('*'|'/') b=e {$val = eval($a.val, $op.type, $b.val);}
    ;
+
  | a=e op=('+'|'-') b=e {$val = eval($a.val, $op.type, $b.val);}
 +
  | INT {$val = $INT.int;}
 +
  | ID {
 +
      String id = $ID.text;
 +
      $v = memory.containsKey(id) ? memory.get(id) : 0;
 +
     }
 +
  | '(' e ')' {$val = $e.val;} ;
  
exprP['''int''' i] '''returns''' ['''int''' val]
+
В первой строке здесь определяется возвращаемое значение ('''[int val]''') для нетерминала '''e'''. Это именно тот атрибут, на который ссылается '''$e.val''' в примерах выше.
    :                                              { $val = $i; } <font color="green"> // <tex>\varepsilon</tex>-правило</font>
+
Во второй строке, присваивания '''a=e''' и '''b=e''' иллюстрируют семантические правила, а действие '''{$val = eval($a.val, $op.type, $b.val);}''' {{---}} транслирующий символ из определений, которые мы рассматривали в начале статьи.
    | '+' term expr = exprP[$i + $term.val]        { $val = $expr.val; }
 
    ;
 
 
term '''returns''' ['''int''' val]
 
    : fact termP[$fact.val]    { $val = $termP.val; }
 
    ;
 
 
 
termP['''int''' i] '''returns''' '''[int''' val]
 
    :                                              { $val = $i; }
 
    | '*' fact expr = termP[$i * $fact.val]        { $val = $expr.val; }
 
    ;
 
 
 
fact '''returns''' ['''int''' val]
 
    : '(' expr ')'                  { $val = $expr.val; }
 
    | NUM                          { $val = Integer.parseInt($NUM.text); }
 
    ;
 
 
 
Техническая деталь для ANTLR, правила для лексического анализатора:
 
WS : [ \t \r \n]+ -> skip ;
 
NUM : [0-9]+ ;
 
  
 
== Примечания ==
 
== Примечания ==
Строка 306: Строка 209:
 
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Первое издание. 2003. Стр. 279 {{---}} 305.
 
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Первое издание. 2003. Стр. 279 {{---}} 305.
 
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Второе издание. 2008. Стр. 383 {{---}} 398.
 
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Второе издание. 2008. Стр. 383 {{---}} 398.
* [https://theantlrguy.atlassian.net/wiki/display/ANTLR4/Parser+Rules#ParserRules ANTLR Documentation {{---}} Rule Attribute Definitions]
+
* [https://theantlrguy.atlassian.net/wiki/display/ANTLR4/Parser+Rules#ParserRules {{---}} RuleAttributeDefinitions| ANTLR Documentation - Rule Attribute Definitions]
 
* [http://www.amazon.com/The-Definitive-ANTLR-4-Reference/dp/1934356999| The Definitive ANTLR 4 Reference]
 
* [http://www.amazon.com/The-Definitive-ANTLR-4-Reference/dp/1934356999| The Definitive ANTLR 4 Reference]
 
 
[[Категория: Методы трансляции]]
 
[[Категория: Методы трансляции]]
[[Категория: Нисходящий разбор]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: