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

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

Внимание! Вы не авторизовались на сайте. Ваш 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"
Строка 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|Аннотированное дерево разбора для '''$\mathbf{real}\ id1,\ id2,\ id3$'''|600px]]
Строка 175: Строка 175:
 
==Пример работы с атрибутами в нисходящем разборе==
 
==Пример работы с атрибутами в нисходящем разборе==
 
<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">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">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.
+
Рассмотрим для примера грамматику арифметических выражений с операторами <tex>+\times</tex>, скобками и выводом результата выражениая.
  
 
  grammar Expression;
 
  grammar Expression;
 
  '''@header''' { package ru.ifmo.ctddev.wiki; }  
 
  '''@header''' { package ru.ifmo.ctddev.wiki; }  
 +
 +
Стартовый нетерминал печатает резульат:
 +
s : expr { System.out.println($e.value);};
  
 
Естественным образом можно добавлять действия в продукции, где это нужно. Действия выполняются после предыдущего элемента грамматики и до следующего.
 
Естественным образом можно добавлять действия в продукции, где это нужно. Действия выполняются после предыдущего элемента грамматики и до следующего.
  
Стартовый нетерминал печатает результат:
+
  expr returns [int val]
  s : expr { System.out.println($expr.val); };
 
 
 
В продукции для нетерминала <code>expr</code> определяется возвращаемое значение (<code>['''int''' val]</code>). Обращение к этому атрибуту имеет вид <code>$expr.value</code>. В фигурных скобках записаны семантические правила.
 
 
 
Разобранные нетерминалы возвращают результат, вычисленный в поддереве(<code>returns [int val]</code>) как свой синтезируемый атрибут, процесс вычисления которого описан в фигурных скобках <code>{ $val = $exprP.val; }</code>.
 
 
 
Наследуемые атрибуты передаются нетерминалу как параметр(<code>exprP[$term.val]</code>).
 
 
 
expr '''returns''' ['''int''' val]
 
 
     : term exprP[$term.val]    { $val = $exprP.val; }
 
     : term exprP[$term.val]    { $val = $exprP.val; }
 
     ;
 
     ;
  
  exprP['''int''' i] '''returns''' ['''int''' val]
+
  exprP[int i] returns [int val]
     :                                             { $val = $i; } <font color="green"> // <tex>\varepsilon</tex>-правило</font>
+
     :                                           { $val = $i; }
     | '+' term expr = exprP[$i + $term.val]        { $val = $expr.val; }
+
     | '+' term e = exprP[$i + $term.val]        { $val = $e.val; }
 
     ;
 
     ;
 
 
  term '''returns''' ['''int''' val]
+
  term returns [int val]
     : fact termP[$fact.val]    { $val = $termP.val; }
+
     : fact termP[$fact.val]    { $val = $termpP.val; }
 
     ;
 
     ;
  
  termP['''int''' i] '''returns''' '''[int''' val]
+
  termP[int i] returns [int val]
     :                                             { $val = $i; }
+
     :                                           { $val = $i; }
     | '*' fact expr = termP[$i * $fact.val]        { $val = $expr.val; }
+
     | '*' fact e = termP[$i * $fact.val]        { $val = $e.val; }
 
     ;
 
     ;
  
  fact '''returns''' ['''int''' val]
+
  fact returns [int val]
 
     : '(' expr ')'                  { $val = $expr.val; }
 
     : '(' expr ')'                  { $val = $expr.val; }
 
     | NUM                          { $val = Integer.parseInt($NUM.text); }
 
     | NUM                          { $val = Integer.parseInt($NUM.text); }
Строка 299: Строка 283:
 
  WS : [ \t \r \n]+ -> skip ;
 
  WS : [ \t \r \n]+ -> skip ;
 
  NUM : [0-9]+ ;
 
  NUM : [0-9]+ ;
 +
 +
 +
В продукции для нетерминала <code>e</code> определяется возвращаемое значение (<code>[Integer value]</code>). Обращение к этому атрибуту имеет вид <code>$e.value</code>. В фигурных скобках записаны семантические правила.
  
 
== Примечания ==
 
== Примечания ==

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

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

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

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