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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 44: Строка 44:
 
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)  
 
$
 
$
Строка 89: Строка 89:
 
|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"| $E_0 \to E_1 + 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"| В фигурных скобках - действия транслирующего символа 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$
Строка 95: Строка 95:
 
|style="background-color:#FFF;padding:2px 30px"|  
 
|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"| $T_0 \to T_1 \times F \ \{MUL\  res = op_1 \times 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"| В фигурных скобках - действия транслирующего символа 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$
Строка 146: Строка 146:
  
 
Выпишем продукции (с транслирующими символами) и ассоциируем с ними семантические правила
 
Выпишем продукции (с транслирующими символами) и ассоциируем с ними семантические правила
(здесь $\{ENTRY {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующий символ]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):
+
(здесь $\{ENTRY {{...}} \}$ - [[Атрибутные_транслирующие_грамматики#tr_char|транслирующий символ]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):
  
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
Строка 161: Строка 161:
 
|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.text \\ 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 \to id\ \{ENTRY addtype(key, value)\}$
Строка 168: Строка 168:
 
|}
 
|}
  
Семантическое правило  $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$ для добавления типа каждого идентификатора к его записи в таблице символов (по ключу, определяемому атрибутом $text$).
  
[[Файл: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>
  
 
==Пример работы с атрибутами в нисходящем разборе==
 
==Пример работы с атрибутами в нисходящем разборе==
 
<wikitex>
 
<wikitex>
Рассмотрим работы с атрибутами на примере LL(1)-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Предиктивный_синтаксический_анализ | разборщика]] для нее:
+
Рассмотрим работы с атрибутами на примере $LL(1)$-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Предиктивный_синтаксический_анализ | разборщика]] для нее:
  
 
$
 
$
Строка 185: Строка 185:
 
$
 
$
  
В данной реализации рекурсивные функции от нетерминалов получают на вход (если необходимо) наследуемые атрибуты узла и возвращают вершины дерева разбора, в атрибутах которых записан результат вычислений соответствующего подвыражения. Однако этот код легко изменить, чтобы он только вычислял значение выражения и не строил дерево разбора. Как мы видим, $val$ {{---}} синтезируемый атрибут, $acc$ {{---}} наследуемый атрибут, $ADD$ {{---}} транслирующий символ. Синим подсвечены строки, отвечающие за работу с атрибутами.
+
В данном примере не требуется дерево разбора в явном виде. В данной реализации рекурсивные функции от нетерминалов получают на вход(если необходимо) наследуемые атрибуты узла и возвращают синтезируемые (результат вычислений соответствующего подвыражения). Как мы видим, $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'''
 
  E() : '''Node'''
Строка 199: Строка 191:
 
     '''switch''' (curToken)
 
     '''switch''' (curToken)
 
         '''case''' n, '('  :
 
         '''case''' n, '('  :
             res.addChild(T())           <font color="green">// подвешиваем левого сына</font>
+
             res.addChild(T())
             <font color="blue">temp = res.children["T"].val</font> <font color="green">// атрибут левого сына</font>
+
             <font color="blue">int temp = res.children[T].val
             <font color="blue">Node rightSon = E'(temp)   </font> <font color="green">// отдадим атрибут левого сына правому как наследуемый атрибут</font>
+
             res.addChild(E'(temp)) </font>
            <font color="blue">res.addChild(rightSon)     </font>  <font color="green">// подвешиваем правого сына сына</font>
 
            <font color="blue">res.val = res.children["E'"].val</font>
 
 
             '''break'''
 
             '''break'''
 
         '''default''' :
 
         '''default''' :
 
             <font color="red">error</font>("unexpected char")
 
             <font color="red">error</font>("unexpected char")
 +
    <font color="blue">res.val = E'.val</font>
 
     '''return''' res
 
     '''return''' res
  
Строка 217: Строка 208:
 
             res.addChild(Node("+"))
 
             res.addChild(Node("+"))
 
             res.addChild(T())
 
             res.addChild(T())
             <font color="blue">temp = res.children["T"].val
+
             <font color="blue">int temp = res.children[T].val
             ADD.res = ADD(acc, temp) <font color="green">// ADD проведет вычисления из наследуемого атрибута add и атрибута ребенка "T"</font>
+
             ADD.res = ADD(acc, temp)
             res.addChild(E'(ADD.res)) <font color="green">// результат вычислений будет передан правому ребенку как наследуемый атрибут</font>
+
             res.addChild(E'(ADD.res))
             res.val = res.children["E'"].val</font>
+
             res.val = res.children[E'].val</font>
 
             '''break'''
 
             '''break'''
 
         '''case''' '$', ')' :
 
         '''case''' '$', ')' :
             <font color="blue">res.val = acc</font>
+
             <font color="blue">res.val = acc;</font>
 
             '''break'''
 
             '''break'''
 
         '''default''' :
 
         '''default''' :
Строка 241: Строка 232:
 
             res.addChild(Node("("))
 
             res.addChild(Node("("))
 
             res.addChild(E())
 
             res.addChild(E())
             <font color="blue">rev.val = res.children["E"].val</font>
+
             <font color="blue">rev.val = res.children[E].val</font>
 
             consume(')')
 
             consume(')')
 
             res.addChild(Node(")"))
 
             res.addChild(Node(")"))
Строка 250: Строка 241:
 
Функции для $T$ и $T'$ строятся аналогично.
 
Функции для $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; }
 
 
 
Естественным образом можно добавлять действия в продукции, где это нужно. Действия выполняются после предыдущего элемента грамматики и до следующего.
 
 
 
Стартовый нетерминал печатает результат:
 
s : expr { System.out.println($expr.val); };
 
  
В продукции для нетерминала <code>expr</code> определяется возвращаемое значение (<code>['''int''' val]</code>). Обращение к этому атрибуту имеет вид <code>$expr.value</code>. В фигурных скобках записаны семантические правила.
+
Рассмотрим для примера грамматику арифметических выражений с оператором <tex>+</tex>, <tex>\times</tex>, и выводом результата выражениая.
  
Разобранные нетерминалы возвращают результат, вычисленный в поддереве(<code>returns [int val]</code>) как свой синтезируемый атрибут, процесс вычисления которого описан в фигурных скобках <code>{ $val = $exprP.val; }</code>.
+
Вне продукций грамматики бывает нужно вставить в сгенерированный разборщик(для Java) package, import, а также некоторые поля и методы. Это делается с помощью <code>@header</code> и <code>@members</code>:
  
Наследуемые атрибуты передаются нетерминалу как параметр(<code>exprP[$term.val]</code>).
+
grammar Expr;
 +
'''@header''' { package tools; import java.util.*; }
 +
'''@parser::members''' {
 +
    Map<String, Integer> memory = new HashMap<String, Integer>();
 +
    int eval(int left, int op, int right) {
 +
        ...
 +
    }
 +
}
  
  expr '''returns''' ['''int''' val]
+
Естественным образом можно добавлять действия в продукции, где это нужно:
     : term exprP[$term.val]    { $val = $exprP.val; }
+
  '''stat:''' '''e''' NEWLINE {System.out.println($e.val);}
     ;
+
     | ID '=' '''e''' NEWLINE {memory.put($ID.text, $e.val); System.out.println($ID.text + "=" + $e.val);}  
 +
     | NEWLINE ;
  
exprP['''int''' i] '''returns''' ['''int''' val]
+
Действия выполняются после предыдущего элемента грамматики и до следующего. В данном примере действия добавлены на конце альтернативы, поэтому действие выполнится после того, как разборщик распознает все выражение. Когда разборщик встречает выражение, за которым идет символ новой строки, ему нужно напечатать результат. Когда он встречает присваивание - ему нужно записать имя и значение переменной в память.
    :                                              { $val = $i; } <font color="green"> // <tex>\varepsilon</tex>-правило</font>
 
    | '+' 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]
+
Правило для '''e''' теперь выглядит следующим образом:
    :                                             { $val = $i; }
 
    | '*' fact expr = termP[$i * $fact.val]        { $val = $expr.val; }
 
    ;
 
  
  fact '''returns''' ['''int''' val]
+
  '''e''' '''returns''' [int val]
    : '(' expr ')'                  { $val = $expr.val; }
+
  : a=e op=('*') b=e {$val = eval($a.val, $op.type, $b.val);}
    | NUM                          { $val = Integer.parseInt($NUM.text); }
+
  | 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;} ;
  
Техническая деталь для ANTLR, правила для лексического анализатора:
+
В первой строке здесь определяется возвращаемое значение (<code>[int val]</code>) для нетерминала '''e'''. Это именно тот атрибут, на который ссылается <code>$e.val</code> в примерах выше.
WS : [ \t \r \n]+ -> skip ;
+
Во второй строке, присваивания <code>a=e</code> и <code>b=e</code> иллюстрируют семантические правила, а действие <code>{$val = eval($a.val, $op.type, $b.val);}</code> {{---}} транслирующий символ из определений, которые мы рассматривали в начале статьи.
NUM : [0-9]+ ;
 
  
 
== Примечания ==
 
== Примечания ==

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

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

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

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