http://esyr.org/wiki/%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8E_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_26_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29?action=history&feed=atomВведение в теорию построения оптимизирующих компиляторов, 02 лекция (от 26 сентября) - История изменений2024-03-29T11:20:26ZИстория изменений этой страницы в викиMediaWiki 1.11.0http://esyr.org/w/index.php?title=%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8E_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_26_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29&diff=3848&oldid=prevESyr01: Отмена правки № 1397 участника 212.112.242.89 (обсуждение)2008-02-03T17:35:37Z<p>Отмена правки № 1397 участника <a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:Contributions/212.112.242.89" title="Служебная:Contributions/212.112.242.89">212.112.242.89</a> (<a href="/w/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:212.112.242.89&action=edit" class="new" title="Обсуждение участника:212.112.242.89">обсуждение</a>)</p>
<a href="http://esyr.org/w/index.php?title=%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8E_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_26_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29&diff=3848&oldid=1397">(Различия между версиями)</a>ESyr01http://esyr.org/w/index.php?title=%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8E_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_26_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29&diff=1397&oldid=prev212.112.242.89: Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. ==
We at EbaumsWorld consider you as disgrace of human race.
Your faggotry level exceeded any imaginab...»2008-02-02T15:16:15Z<p>Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...»</p>
<a href="http://esyr.org/w/index.php?title=%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8E_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_26_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29&diff=1397&oldid=123">(Различия между версиями)</a>212.112.242.89http://esyr.org/w/index.php?title=%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8E_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_26_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29&diff=123&oldid=prevESyr01: 1 версий2007-11-13T14:42:54Z<p>1 версий</p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black;">Версия 14:42, 13 ноября 2007</td>
</tr>
</table>ESyr01http://esyr.org/w/index.php?title=%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8E_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_26_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29&diff=122&oldid=prev2kan: опечатка2006-12-13T01:04:31Z<p>опечатка</p>
<p><b>Новая статья</b></p><div><P STYLE="margin-bottom: 0cm">Оптимизация компиляторов 26.09.06</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Для автоматической генерации<br />
синтаксических анализаторов существуют специальные программы, такие<br />
как уacc/bison. yacc &ndash; yet anpther compiler compiler, первая<br />
статья, в которй он упоминается &ndash; Johnson, 1974.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">К 70 годам теория синтаксического<br />
анализа была разработана достаточно хорошо. Один из столпов &mdash;<br />
Кнут.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">КС-грамматика: O(n^3), O(n^2)/ Это<br />
недоспустимо по скорости, посему нужны граматики, у которых анализ<br />
проводится за линейное время &ndash; грамматики, разбор которых<br />
проводится методом рекурсивного спуска (LL(1)). Также есть, но не<br />
будут раззматриваться (LR(1), LALR(1))</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Метод рекурсивного спуска &ndash;<br />
начинаем с S и постпенно спускаемся вниз, раскрывая альтернативы,<br />
доходя до листьев дерева разбора. Если рассмотреть это в терминах<br />
цепочки, то есть уже просмотренная часть цепочки A=a1...an,<br />
просмотренная часть &ndash; a1...a(p-1)<BR>, текущий символ, которфый<br />
доступен &ndash; ap, дальше &ndash; непростмотренная часть. При<br />
нисходящем рек спуске необходимо определить по текущемц символу и<br />
просомтренной части, как разобрать оставшуюся часть, выбрать одну из<br />
альтернатив. В большинстве ситуаций отдного символа из входного<br />
текста недостаточно, в этом случае говорят о LL(K) &ndash;<br />
грамматиках, в которых заглядывается не на 1, а на К симвлов вперед.<br />
Но в современных ЯП есть типовые ситуации, которые не разбираются ни<br />
при каких К. Поэтому нужно расширять язык, в соответствии с<br />
извращениями &ndash; заглядывать на n симоволов вперёд, вычисление<br />
предикатов и т. д. <br />
</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">У LR-анализаторов подход другой.<br />
Начинаем с терминала и поднимаемся к S. Работает так &ndash; есть<br />
разобранная часть, есть текущий символ, доступный для чтения, и есть<br />
непросомотренная часть дальше. Состояние автомата, то есть та часть<br />
цепочки, коотрую он успел просомотреть, имеется в виде стека, то есть<br />
есть некооторый стек. На стеке находтся продукты переработ\ки<br />
исходного текста, в частности, терминальбные и нетерм симоволы. На<br />
основании очсередного символа атвтомат может произвксти одно из<br />
четырёх действий:</P><br />
<OL><br />
<LI><P STYLE="margin-bottom: 0cm">Shift &ndash; сдвиг. Добавляем<br />
очередной симвлол в стек</P><br />
<LI><P STYLE="margin-bottom: 0cm">Reduce. Берём некоторую часть из<br />
того, что просмотрели (она лежит в стеке). Для этой части должно<br />
существовать некоторое правило в грамматике, и заменяем их на<br />
нетерм, соотв правилу (A1A2A3 -&gt; A, если есть правило A =<br />
A1A2A3). Отличие от LL анализа в том, что в нём альтернативы<br />
начинаются с ap, в LR же ap есть последний символ альтернативы. И<br />
замена на нетерминал производится, когда все символы альтернативы<br />
уже накопились, поэтому класс LR(1) языков шире класса LL(1), более<br />
того, он его включает в себя. Более того, Кнут доказал, что LR(1)<br />
эквивалентен LL(k). В LR есть стек, идут замены, и постепенно<br />
сворачиваем входную цепочку. Сам по себе разбор, то есть определение<br />
принадлежности имеет мало смысла, в процессе разбора нужно делать<br />
что-то ещё, например, построение дерева разбора. Возможно,<br />
одновременно с этим будет работать интерпретатор, строиться таблицы<br />
и т д. Понятно,Ю чот выполнение семант действий возможно только вл<br />
время erduce. В этом случае в момент замены можно выполнять<br />
произвольные действия, У автомата есть свой стек, и есть стек<br />
пользоваьтельских элементов, и семант дейчствие, выполняемое при<br />
свёртке, этому сем действию доступны аттрибуты, соответствующие<br />
частям правила, и после замены в стеке аттрибутов останется новый<br />
аттрибут. A:=f(a1,a2,a3). Никаких других действий во время разбора <br />
быть не может. Такая схема аттрибутных вычислений называется<br />
S-аттрибутированными грамматиками. При LR разборе идём снизу вверх,<br />
при этой замене можно выполнять произвольные действия, при этом<br />
аттрибуты заменяются соответственно.</P><br />
</OL><br />
<P STYLE="margin-bottom: 0cm">Пример:</P><br />
<P STYLE="margin-bottom: 0cm">Как же это реализуется в инструменте,<br />
который мы будем рассматривать? Основной секцией файла описания языка<br />
является секция описания грамматики. <br />
</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">%{</P><br />
<P STYLE="margin-bottom: 0cm">С-код</P><br />
<P STYLE="margin-bottom: 0cm">%}</P><br />
<P STYLE="margin-bottom: 0cm">Произвольные декларации, необходимые<br />
для работы анализатора</P><br />
<P STYLE="margin-bottom: 0cm">%%</P><br />
<P STYLE="margin-bottom: 0cm">грамматика. В виде</P><br />
<P STYLE="margin-bottom: 0cm">L : R1 | R2 | R3</P><br />
<P STYLE="margin-bottom: 0cm">Эта запись эквивалентна <br />
</P><br />
<P STYLE="margin-bottom: 0cm">L : R1</P><br />
<P STYLE="margin-bottom: 0cm">L : R2</P><br />
<P STYLE="margin-bottom: 0cm">L : R3</P><br />
<P STYLE="margin-bottom: 0cm">Произвольные действия могут выполнятся<br />
после записи альтернативы, т е <br />
</P><br />
<P STYLE="margin-bottom: 0cm">L : R1 {};</P><br />
<P STYLE="margin-bottom: 0cm">%%</P><br />
<P STYLE="margin-bottom: 0cm">С-код</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Первый прагматический аспект: интерфейс<br />
с лексическим анализатором. Это то как, парсер будет получать символ<br />
от анализатора. Бизон обычно получает очередной символ от int<br />
yylex(), причём</P><br />
<P STYLE="margin-bottom: 0cm">0 &ndash; EOF</P><br />
<P STYLE="margin-bottom: 0cm">1-255 &ndash; соотв символы ASCII</P><br />
<P STYLE="margin-bottom: 0cm">всё, что больше 257 можно использовать<br />
для объявления сложных лексем. <br />
</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Кроме того, объявляется yylval, куда<br />
анализатор может записывать различную информацию. <br />
</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Как определить тип yylval? Простейший<br />
способ &ndash; в разделе кода поределить тип YYSTYPE, то есть yylval<br />
имеет тип YYSTYPE. Тогда дополнительная информация будет этого типа,<br />
И все промежуточные вычисления будут этого типа. <br />
</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Вторая альтернатива &ndash;<br />
использовать директиву %union. Она означает то де самое, что и union<br />
на языке Си, которая превратится в соответствующий union в<br />
результирующем файле. <br />
</P><br />
<P STYLE="margin-bottom: 0cm">%union {</P><br />
<P STYLE="margin-bottom: 0cm">struct ichinfo i; - селекторы полей,<br />
которые распознаются бизоном, и которые можно использовать</P><br />
<P STYLE="margin-bottom: 0cm">struct valinfo v;</P><br />
<P STYLE="margin-bottom: 0cm">struct treeinfo t;</P><br />
<P STYLE="margin-bottom: 0cm">}</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Требуются ещё константы для составных<br />
лексем языка. В частности, если есть ключевые слова, нужно по<br />
константе на ключ слово, нужны спец константы для составных<br />
разделителей, нужны спец константы для идентификаторо, чисел и т. д.<br />
Соотв, нужно в разделе деклараций описать вс етипы клексем, которые<br />
будут использоваться.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Есть директива %ещлут? С помощью<br />
Которой перечисляются все декларации. <br />
</P><br />
<P STYLE="margin-bottom: 0cm">%token TOK_INT</P><br />
<P STYLE="margin-bottom: 0cm">Если используется %union, то нужно явно<br />
указывать селектор. И должны явно использоваться только определённые<br />
типы.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Второй вариант (более интересный): <br />
</P><br />
<P STYLE="margin-bottom: 0cm">%token TOK_VOID &laquo;void&raquo;</P><br />
<P STYLE="margin-bottom: 0cm">Тогда в грамматике можно использовать<br />
не константу, а строку. И читабельность грамматики резко повышается.<br />
Теперь можно писать</P><br />
<P STYLE="margin-bottom: 0cm">type : TOK_INT | &laquo;void&raquo;</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Если мы хотим задать то поле, с которым<br />
%token будет работать по умолчанию, то мы можем указать</P><br />
<P STYLE="margin-bottom: 0cm">%token &lt;t&gt; TOK_FOR &laquo;for&raquo;</P><br />
<P STYLE="margin-bottom: 0cm">Этим говорим, что везде, где<br />
исподльзуется TOK_FOR, мы используем поле t. <br />
</P><br />
<P STYLE="margin-bottom: 0cm">Все константы попадают в .h файл и<br />
будут использоваться. <br />
</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Предположим есть некоторе правило:</P><br />
<P STYLE="margin-bottom: 0cm">stmt: &laquo;it&raquo; '(' expr ')'<br />
stmt | if '(' expr ')' &laquo;else&raquo; stmt</P><br />
<P STYLE="margin-bottom: 0cm">LR грамматике совершенно всё равно, что<br />
начала одинаковые.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">На момент reduce в стеке лежат все<br />
элементы, пронуерованные с 1, причём для правил нумерация<br />
независимая. В стеке аттрибутов находятся значения типа yystype, и к<br />
ним можно обращаться, используя $n, где n &ndash; номер лексемы, т е<br />
$1 - &laquo;if&raquo;, $2 - '(', и т д. Соответственно, с этими<br />
долларами мы можем делать всё, что хотим &ndash; строить дерево,<br />
вычислять... Результат всего будет записываться в переменную $$. <br />
</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Пример (простой): Как выглядит<br />
вычисление выражения:</P><br />
<P STYLE="margin-bottom: 0cm">%{</P><br />
<P STYLE="margin-bottom: 0cm">#define YYSTYPE double</P><br />
<P STYLE="margin-bottom: 0cm">%}</P><br />
<P STYLE="margin-bottom: 0cm">%token TOK_NUM</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">%%</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">expr &laquo; expr '+' expr1 {$$ = $1 +<br />
$3}</P><br />
<P STYLE="margin-bottom: 0cm"> | expr '-' expr1 {$$ = $1 - $3}</P><br />
<P STYLE="margin-bottom: 0cm"> | expr1 {$$ = $1}</P><br />
<P STYLE="margin-bottom: 0cm">expr1 : expr1 '*' expr2 {$$ = $1 * $3}</P><br />
<P STYLE="margin-bottom: 0cm"> | expr1 '*' expr2 {$$ = $1 / $3}</P><br />
<P STYLE="margin-bottom: 0cm"> | expr2 {$$ = $1}</P><br />
<P STYLE="margin-bottom: 0cm">expr2 : TOK_NUM {$$ = $1}</P><br />
<P STYLE="margin-bottom: 0cm"> | '(' expr ')' {$$ = $2}</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">// - (Чернов) Вы нажали волшебную<br />
кнопочку? - Нет, а что? - Просто зашумело что-то...</P><br />
<P STYLE="margin-bottom: 0cm">//Всякие спецэффекты, типа деления на<br />
ноль, я не учитываю...</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Это леворекурсивные выражения. A = AC |<br />
C</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Они убивают LL наповал. <br />
</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Для LR ЛР-выражения предпочтительный. <br />
</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Как будет работать автомат с отчки<br />
правой рекурсии?</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">CCCCCCCCC</P><br />
<OL><br />
<LI><P STYLE="margin-bottom: 0cm">Сдвигает C</P><br />
<LI><P STYLE="margin-bottom: 0cm">Сдвигает C</P><br />
</OL><br />
<P STYLE="margin-bottom: 0cm">...</P><br />
<P STYLE="margin-bottom: 0cm">Когда дошли до конца, Можем делать<br />
замену. И делаем её, пока в стеке не останется одно А.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Левая рекурсия:</P><br />
<P STYLE="margin-bottom: 0cm">Сразу делаем замену A=C, потом A=AC,<br />
потом...</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">В случае правой рекурсии стек достигает<br />
максимальной длины, в левой рекурсии замена идёт сразу.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">В случае правой рекурсии будет<br />
неправильная ассоциативность.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Понятно, что отнюдь не всегда можно<br />
вычислить значение выражения. Можно также строить дерево разбора. К<br />
сожалению, як и бизон деревья сами не строят, и это надо делать<br />
вручную.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">В дереве имеется несколько типов<br />
объектов.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Сейчас мы сами опишем тип, который<br />
будет использоваться при анализе</P><br />
<P STYLE="margin-bottom: 0cm">Struct parseinfo</P><br />
<P STYLE="margin-bottom: 0cm">{</P><br />
<P STYLE="margin-bottom: 0cm"> int tag; - всевозможные типы лексем и<br />
узлов деревьев</P><br />
<P STYLE="margin-bottom: 0cm"> double val; - значение</P><br />
<P STYLE="margin-bottom: 0cm"> struct parseinfo * left, * right;</P><br />
<P STYLE="margin-bottom: 0cm">}</P><br />
<P STYLE="margin-bottom: 0cm">#define YYSTYPE struct parseinfo *</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">В чём будет заключаться работа<br />
анализатора? Вместо вычислений будем строить дерево.</P><br />
<P STYLE="margin-bottom: 0cm">expr &laquo; expr '+' expr1 { ... }</P><br />
<P STYLE="margin-bottom: 0cm"> | expr '-' expr1 { ... }</P><br />
<P STYLE="margin-bottom: 0cm"> | expr1 {$$ = $1}</P><br />
<P STYLE="margin-bottom: 0cm">expr1 : expr1 '*' expr2 {$$ =<br />
make_tree(MODE_MUL, $1, $3); }</P><br />
<P STYLE="margin-bottom: 0cm"> | expr1 '*' expr2 { ... }</P><br />
<P STYLE="margin-bottom: 0cm"> | expr2 {$$ = $1}</P><br />
<P STYLE="margin-bottom: 0cm">expr2 : TOK_NUM {$$ = $1}</P><br />
<P STYLE="margin-bottom: 0cm"> | '(' expr ')' {$$ = $2}</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">После анализа будет доступен корень<br />
дерева разбора, с которым мы можем делать всё, что захотим.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">То, что строится здесь, это не совсем<br />
дерево разбора. Например, для a+b*c деревом разбора было бы, реально<br />
же хотелось бы строить немного сокращённое дерево, что мы и строим.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">В более сложных случаях (if) для ифа<br />
будет переменное количество сыновей. Как строить деревья разбора в<br />
этом случае? Есть три подхода:</P><br />
<OL><br />
<LI><P STYLE="margin-bottom: 0cm">Каждый элемент хранит ссылку вниз<br />
и ссылку вправо. Плюсы: фиксированный размер структуры. Минусы &ndash;<br />
долго ходить по ссылкам. Кроме того, есть такой минус: рассмотрим<br />
for: &laquo;for&raquo; '(' [expr] ';' [expr] ';' [expr] ')' stmt.<br />
Некорректно оно из-за квадратных скобок. Первый вариант &ndash;<br />
написать 8 варианто. Второй &ndash; добавить expropt : expr {$$=$1;}<br />
| {$$=0;}. В этом случае построение дерева резко усложняется.<br />
Появляется много пустых листьев, которые нельзя игнорировать.</P><br />
<LI><P STYLE="margin-bottom: 0cm">Можно строить структуры, у которых<br />
все потенциальные поддеревья, которы еопименованы. То есть:</P><br />
</OL><br />
<P STYLE="margin-bottom: 0cm">struct ifstmt</P><br />
<P STYLE="margin-bottom: 0cm">{</P><br />
<P STYLE="margin-bottom: 0cm"> struct expr * expr;</P><br />
<P STYLE="margin-bottom: 0cm"> struct stmt *stmtthen;</P><br />
<P STYLE="margin-bottom: 0cm"> struct stmt *stmtelse;</P><br />
<P STYLE="margin-bottom: 0cm">}</P><br />
<P STYLE="margin-bottom: 0cm">Плюсы &ndash; все потенциальные<br />
поддеревья доступны по имени. Поджидает следующая засада &ndash;<br />
начнётся невогласование типов в большом количестве. Вторая засада &ndash;<br />
есть дерево и надо просто его обойти. В этом случае простейшая<br />
процедура обхода превратится в огромный свитч, ибо каждый тип узла<br />
надо рассматривать отдельно. Ещё один недостаток &ndash; структура<br />
имеет переменный размер.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Мнение Чернова: в компиляторе<br />
виртуальные функции не нужны. Ибо всё по ним размазывается.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<OL START=3><br />
<LI><P STYLE="margin-bottom: 0cm">В каждой вершине хранить массив<br />
ссылок. <br />
</P><br />
</OL><br />
<P STYLE="margin-bottom: 0cm">Есть два варианта &ndash; сильно<br />
извращённый вариант и не сильно извращённый вариант</P><br />
<P STYLE="margin-bottom: 0cm">struct node</P><br />
<P STYLE="margin-bottom: 0cm">{</P><br />
<P STYLE="margin-bottom: 0cm">int tag;</P><br />
<P STYLE="margin-bottom: 0cm">int n;</P><br />
<P STYLE="margin-bottom: 0cm">struct node ** p;</P><br />
<P STYLE="margin-bottom: 0cm">}</P><br />
<P STYLE="margin-bottom: 0cm">Более извращённый вариант:</P><br />
<P STYLE="margin-bottom: 0cm">struct node</P><br />
<P STYLE="margin-bottom: 0cm">{</P><br />
<P STYLE="margin-bottom: 0cm">int tag;</P><br />
<P STYLE="margin-bottom: 0cm">int n;</P><br />
<P STYLE="margin-bottom: 0cm">struct node * p[0];</P><br />
<P STYLE="margin-bottom: 0cm">}</P><br />
<P STYLE="margin-bottom: 0cm">С ним работать чуть сложнее, но меньше<br />
на одно выделение памяти.</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">Какие возникают вопросы:</P><br />
<OL><br />
<LI><P STYLE="margin-bottom: 0cm">Управление памятью</P><br />
<LI><P STYLE="margin-bottom: 0cm">Ошибки и восстановление после<br />
ошибок</P><br />
</OL><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<P STYLE="margin-bottom: 0cm">//При ошибке завершать работу и<br />
говорить &laquo;Извините, не смогла&raquo;. Ну, не смогла, так не<br />
смогла.</P><br />
<P STYLE="margin-bottom: 0cm">//Восстановление после ошибок &ndash;<br />
чёрная магия</P><br />
<P STYLE="margin-bottom: 0cm">//Что делать, когда грамматика не<br />
грамматится?</P><br />
<P STYLE="margin-bottom: 0cm"><BR><br />
</P><br />
<OL START=3><br />
<LI><P STYLE="margin-bottom: 0cm">Конфликты в грамматиках.</P><br />
<LI><P STYLE="margin-bottom: 0cm">Что <br />
</P><br />
</OL><br />
<br />
<br />
{{Введение в теорию построения оптимизирующих компиляторов}}<br />
{{Lection-stub}}</div>2kan