Современная электронная библиотека ModernLib.Net

Давайте создадим компилятор!

ModernLib.Net / Программирование / Креншоу Джек / Давайте создадим компилятор! - Чтение (стр. 6)
Автор: Креншоу Джек
Жанр: Программирование

 

 


      Переименуйте текущую процедуру BoolTerm в NotFactor, и введите следующую новую версию BoolTerm. Заметьте, что она намного более простая, чем числовая версия, так как здесь нет эквивалента деления.
      {–}
      { Parse and Translate a Boolean Term }
      procedure BoolTerm;
      begin
      NotFactor;
      while Look = '&' do begin
      EmitLn('MOVE D0,-(SP)');
      Match('&');
      NotFactor;
      EmitLn('AND (SP)+,D0');
      end;
      end;
      {–}
      Теперь мы почти дома. Мы транслируем сложные булевые выражения, хотя только и для постоянных значений. Следующий шаг – учесть NOT. Напишите следующую процедуру:
      {–}
      { Parse and Translate a Boolean Factor with NOT }
      procedure NotFactor;
      begin
      if Look = '!' then begin
      Match('!');
      BoolFactor;
      EmitLn('EOR #-1,D0');
      end
      else
      BoolFactor;
      end;
      {–}
      И переименуйте предыдущую процедуру в BoolFactor. Теперь испытайте компилятор. К этому времени синтаксический анализатор должен обрабатывать любое булевое выражение, которое вы позаботитесь ему подкинуть. Работает? Отлавливает ли он неправильно сформированные выражения?
      Если вы следили за тем, что мы делали в синтаксическом анализаторе для математических выражений вы знаете что далее мы расширили определение показателя для включения переменных и круглых скобок. Мы не должны делать это для булевого показателя, потому что об этих маленьких вещах позаботится наш следующий шаг. Необходима только одна дополнительная строка в BoolFactor, чтобы позаботиться об отношениях:
      {–}
      { Parse and Translate a Boolean Factor }
      procedure BoolFactor;
      begin
      if IsBoolean(Look) then
      if GetBoolean then
      EmitLn('MOVE #-1,D0')
      else
      EmitLn('CLR D0')
      else Relation;
      end;
      {–}
      Вы могли бы задаться вопросом, когда я собираюсь предоставить булевские переменные и булевские выражения в скобках. Отвечаю: никогда. Помните, ранее мы убрали их из грамматики. Прямо сейчас я собираюсь кодировать грамматику, которую мы уже согласовали. Сам компилятор не может видеть разницы между булевыми переменными или выражениями и арифметическими переменными или выражениями... все это будет обрабатываться в Relation в любом случае.
      Конечно, понадобится некоторый код для Relation. Однако, я не чувствую себя комфортно, добавляя еще код, не проверив сперва тот, который мы уже имеем. Так что давайте сейчас просто напишем фиктивную версию Relation, которая ничего не делает за исключением того, что съедает текущий символ и выводит небольшое сообщение:
      {–}
      { Parse and Translate a Relation }
      procedure Relation;
      begin
      WriteLn('<Relation>');
      GetChar;
      end;
      {–}
      ОК, наберите этот код и испытайте его. Все старые дела все еще должны работать... у вас должна быть возможность генерировать код для AND, OR и NOT. Кроме того, если вы наберете любой алфавитный символ, вы должны получить небольшой заменитель <Relation>, где должен быть булев показатель. Вы получили это? Отлично, тогда давайте перейдем к полной версии Relation.
      Чтобы получить ее, тем не менее, сначала мы должны положить небольшое основание. Вспомните, что отношение имеет форму:
      <relation> ::= | <expression> [<relop> <expression]
      Так как у нас появился новый вид операторов, нам также понадобится новая логическая функция для ее распознавания. Эта функция показана ниже. Из-за ограничения в один символ, я придерживаюсь четырех операторов, которые могут быть закодированы такими символами («не равно» закодировано как "#").
      {–}
      { Recognize a Relop }
      function IsRelop(c: char): Boolean;
      begin
      IsRelop := c in ['=', '#', '<', '>'];
      end;
      {–}
      Теперь вспомните, что мы используем нуль или -1 в регистре D0 для представления логического значения и также то, что операторы цикла ожидают, что будет установлен соответствующий флаг. При реализации всего этого для 68000 все становится немного сложным.
      Так как операторы цикла выполняются только по флажкам, было бы хорошо (а также довольно эффективно) просто установить эти флажки и совсем ничего не загружать в D0. Это было бы прекрасно для циклов и ветвлений, но запомните, что отношения могут быть использованы везде, где могут быть использованы булевы показатели. Мы можем сохранять его результат в булевой переменной. Так как мы не можем знаеть пока как будет использоваться результат, мы должны учесть оба случая.
      Сравнение числовых данных достаточно просто... 68000 имеет команду для этого... но она устанавливает флажки а не значение. Более того, всегда будут устанавливаться те же самые флажки (ноль если равно, и т.д.), в то время, как нам необходим по-разному установленный флажок нуля для каждого различного оператора отношения.
      Решение заключается в инструкции Scc процессора 68000, которая устанавливает значение байта в 0000 или FFFF (забавно как это работает!) в зависимости от результата определенного условия. Если мы сделаем байтом результата регистр D0, мы получим необходимое логическое значение.
      К сожалению, имеется одно заключительное осложнение: в отличие от почти всех других команд в наборе 68000, Scc не сбрасывает флажки условий в соответствии с сохраняемыми данными. Поэтому мы должны сделать последний шаг, проверить D0 и установить соответствующим образом флажки. Это должно быть похоже на оборот вокруг луны для получения того, что мы хотим: мы сначала выполняем проверку, затем проверяем флажки, чтобы установить данные в D0, затем тестируем D0 чтобы установить флажки снова. Это окольный путь, но это самый простой способ получить правильные флажки и, в конце концов, это всего лишь пара инструкций.
      Я мог бы упомянуть здесь, что эта область, по моему мнению, показывает самые большие различия между эффективностью вручную написанного на ассемблере и сгенерированного компилятором кода. Мы уже видели, что мы теряем эффективность при арифметических операциях, хотя позже я планирую показать вам как ее немного улучшить. Мы также видели, что управляющие конструкции сами по себе могут быть реализованы довольно эффективно... обычно очень сложно улучшить код, сгенерированный для IF или WHILE. Но практически каждый компилятор, который я когда-либо видел, генерирует ужасный код, по сравнению с ассемблером, для вычисления булевых функций и особенно отношений. Причина как раз в том, о чем я упомянул выше. Когда я пишу код на ассемблере, я двигаюсь вперед и выполняю проверку наиболее удобным для меня способом, и затем подготавливаю ветвление так чтобы переход был выполнен на нужную ветку. Фактически, я «подстраиваю» каждое ветвление под ситуацию. Компилятор не может сделать этого (практически) и он также не может знать, что нам не нужно сохранять результат проверки как булевскую переменную. Поэтому он должен генерировать код по очень строгим правилам и часто заканчивает сохранением результата как булевой переменной, которая никогда не будет использована для чего-либо.
      В любом случае мы теперь готовы рассмотреть код для Relation. Он показан ниже с сопровождающими процедурами:
      {–}
      { Recognize and Translate a Relational «Equals» }
      procedure Equals;
      begin
      Match('=');
      Expression;
      EmitLn('CMP (SP)+,D0');
      EmitLn('SEQ D0');
      end;
      {–}
      { Recognize and Translate a Relational «Not Equals» }
      procedure NotEquals;
      begin
      Match('#');
      Expression;
      EmitLn('CMP (SP)+,D0');
      EmitLn('SNE D0');
      end;
      {–}
      { Recognize and Translate a Relational «Less Than» }
      procedure Less;
      begin
      Match('<');
      Expression;
      EmitLn('CMP (SP)+,D0');
      EmitLn('SGE D0');
      end;
      {–}
      { Recognize and Translate a Relational «Greater Than» }
      procedure Greater;
      begin
      Match('>');
      Expression;
      EmitLn('CMP (SP)+,D0');
      EmitLn('SLE D0');
      end;
      {–}
      { Parse and Translate a Relation }
      procedure Relation;
      begin
      Expression;
      if IsRelop(Look) then begin
      EmitLn('MOVE D0,-(SP)');
      case Look of
      '=': Equals;
      '#': NotEquals;
      '<': Less;
      '>': Greater;
      end;
      EmitLn('TST D0');
      end;
      end;
      {–}
      Теперь этот вызов Expression выглядит знакомым! Вот где редактор вашей системы оказывается полезным. Мы уже генерировали код для Expression и его близнецов на предыдущих уроках. Теперь вы можете скопировать их в ваш файл. Не забудьте использовать односимвольную версию. Просто чтобы быть уверенным, я продублировал арифметические процедуры ниже. Если вы наблюдательны, вы также увидите, что я их немного изменил чтобы привести в соответствие с последней версией синтаксиса. Эти изменения не являются необходимыми, так что вы можете предпочесть оставить все как есть до тех пор, пока не будете уверены, что все работает.
      {–}
      { Parse and Translate an Identifier }
      procedure Ident;
      var Name: char;
      begin
      Name:= GetName;
      if Look = '(' then begin
      Match('(');
      Match(')');
      EmitLn('BSR ' + Name);
      end
      else
      EmitLn('MOVE ' + Name + '(PC),D0');
      end;
      {–}
      { Parse and Translate a Math Factor }
      procedure Expression; Forward;
      procedure Factor;
      begin
      if Look = '(' then begin
      Match('(');
      Expression;
      Match(')');
      end
      else if IsAlpha(Look) then
      Ident
      else
      EmitLn('MOVE #' + GetNum + ',D0');
      end;
      {–}
      { Parse and Translate the First Math Factor }
      procedure SignedFactor;
      begin
      if Look = '+' then
      GetChar;
      if Look = '-' then begin
      GetChar;
      if IsDigit(Look) then
      EmitLn('MOVE #-' + GetNum + ',D0')
      else begin
      Factor;
      EmitLn('NEG D0');
      end;
      end
      else Factor;
      end;
      {–}
      { Recognize and Translate a Multiply }
      procedure Multiply;
      begin
      Match('*');
      Factor;
      EmitLn('MULS (SP)+,D0');
      end;
      {–}
      { Recognize and Translate a Divide }
      procedure Divide;
      begin
      Match('/');
      Factor;
      EmitLn('MOVE (SP)+,D1');
      EmitLn('EXS.L D0');
      EmitLn('DIVS D1,D0');
      end;
      {–}
      { Parse and Translate a Math Term }
      procedure Term;
      begin
      SignedFactor;
      while Look in ['*', '/'] do begin
      EmitLn('MOVE D0,-(SP)');
      case Look of
      '*': Multiply;
      '/': Divide;
      end;
      end;
      end;
      {–}
      { Recognize and Translate an Add }
      procedure Add;
      begin
      Match('+');
      Term;
      EmitLn('ADD (SP)+,D0');
      end;
      {–}
      { Recognize and Translate a Subtract }
      procedure Subtract;
      begin
      Match('-');
      Term;
      EmitLn('SUB (SP)+,D0');
      EmitLn('NEG D0');
      end;
      {–}
      { Parse and Translate an Expression }
      procedure Expression;
      begin
      Term;
      while IsAddop(Look) do begin
      EmitLn('MOVE D0,-(SP)');
      case Look of
      '+': Add;
      '-': Subtract;
      end;
      end;
      end;
      {–}
      Теперь вы получили что-то... синтаксический анализатор, который может обрабатывать и арифметику и булеву алгебру и их комбинации через использование операторов отношений. Я советую вам сохранить копию этого синтаксического анализатора в безопасном месте для будущих обращений, потому что на нашем следующем шаге мы собираемся разделить его.

Объединение с управляющими конструкциями

      Сейчас давайте возвратимся назад к файлу который мы создали ранее и который выполняет синтаксический анализ управляющих конструкций. Помните небольшие фиктивные процедуры Condition и Expression? Теперь вы знаете, что в них должно находиться!
      Я предупреждаю вас, вы собираетесь сделать некоторые творческие изменения, поэтому потратьте ваше время и сделайте это правильно. Вы должны скопировать все процедуры из анализатора логики от Ident до BoolExpression в синтаксический анализатор управляющих конструкций. Вставьте их в текущей позиции Condition. Затем удалите эту процедуру, так же как и фиктивную Expression. Затем замените каждый вызов Condition на обращение к BoolExpression. Наконец скопируйте процедуры IsMulop, IsOrOp, IsRelop, IsBoolean, и GetBoolean на место. Этого достаточно.
      Откомпилируйте полученную программу и протестируйте ее. Так как мы не использовали эту программу некоторое время, не забудьте, что мы использовали односимвольные токены для IF, WHILE и т.д. Также не забудьте, что любая буква, не являющаяся ключевым словом, просто отображается на экране как блок.
      Попробуйте:
      ia=bxlye
      что означает «IF a=b X ELSE Y ENDIF».
      Что вы думаете? Работает? Попробуйте что-нибудь еще.

Добавление присваиваний

      Раз у нас уже есть подпрограммы для выражений, мы могли бы также заменить «блоки» настоящими операциями присваивания. Мы уже делали это прежде, поэтому это не будет слишком трудно. Прежде, чем сделать этот шаг, однако, мы должны исправить кое-что еще.
      Скоро мы обнаружим, что наши однострочные «программы», которые мы здесь пишем, будут ограничивать наш стиль. В настоящее время у нас нет способа вылечить это, потому что наш компилятор не распознает символы конца строки, возврат каретки (CR) и перевод строки (LF). Поэтому перед продвижением дальше давайте заткнем эту дыру.
      Существует пара способов для работы с CR/LF. Один (подход C/Unix) просто рассматривает их как дополнительные символы пробела и игнорирует их. Фактически это не такой плохой подход, но он приводит к странным результатам для нашего анализатора в его текущем состоянии. Если бы он считывал входной поток из исходного файла как любой уважающий себя настоящий компилятор, не было бы никаких проблем. Но мы считываем входной поток с клавиатуры и ожидаем, что должно что-то произойти, когда мы нажимаем клавишу Return. Этого не произойдет, если мы просто перескакиваем CR и LF (попробуйте это). Поэтому я собираюсь использовать здесь другой метод, который в конечном счете не обязательно является лучшим методом. Рассматривайте его как временную замену до тех пор, пока мы не двинемся дальше.
      Вместо того, чтобы пропускать CR/LF, мы позволим синтаксическому анализатору двигаться вперед и отлавливать их, затем предоставлять их специальной процедуре, аналогичной SkipWhite, которая пропускает их только в определенных «допустимых» местах.
      Вот эта процедура:
      {–}
      { Skip a CRLF }
      procedure Fin;
      begin
      if Look = CR then GetChar;
      if Look = LF then GetChar;
      end;
      {–}
      Теперь добавьте два вызова Fin в процедуру Block следующим образом:
      {–}
      { Recognize and Translate a Statement Block }
      procedure Block(L: string);
      begin
      while not(Look in ['e', 'l', 'u']) do begin
      Fin;
      case Look of
      'i': DoIf(L);
      'w': DoWhile;
      'p': DoLoop;
      'r': DoRepeat;
      'f': DoFor;
      'd': DoDo;
      'b': DoBreak(L);
      else Other;
      end;
      Fin;
      end;
      end;
      {–}
      Теперь вы обнаружите, что можете использовать многострочные «программы». Единственное ограничение в том, что вы не можете отделять токены IF или WHILE от их предикатов.
      Теперь мы готовы включить операторы присваивания. Просто замените вызов Other в процедуре Block на вызов Assignment и добавьте следующую процедуру, скопированную из одной нашей более ранней программы. Обратите внимание, что сейчас Assignment вызывает BoolExpression, поэтому мы можем присваивать логические переменные.
      {–}
      { Parse and Translate an Assignment Statement }
      procedure Assignment;
      var Name: char;
      begin
      Name := GetName;
      Match('=');
      BoolExpression;
      EmitLn('LEA ' + Name + '(PC),A0');
      EmitLn('MOVE D0,(A0)');
      end;
      {–}
      С этими изменениями у вас теперь должна быть возможность писать сносные, реалистично выглядящие программы, подчиненные только нашему ограничению односимвольными токенами. Первоначально я также намеревался избавить вас и от этого ограничения. Однако, это потребует довольно больших изменений того, что мы сделали к этому моменту. Нам нужен настоящий лексический анализатор и это требует некоторых структурных изменений. Это небольшие изменения, которые потребуют чтобы мы выбросили все, что мы сделали к этому времени... при желании это может быть сделано в действительности с минимальными изменениями. Но необходимо такое желание.
      Эта глава и так получилась довольно длинной и она содержит довольно тяжелый материал, поэтому я решил оставить этот шаг до следующего раза, чтобы у вас было немного времени усвоить то, что мы сделали и вы были готовы начать на свежую голову.
      В следующей главе, мы построим лексический анализатор и устраним односимвольный барьер раз и навсегда. Мы также напишем наш первый законченный компилятор, основанный на том, что мы сделали на этом уроке. Увидимся.

Лексический анализ

Введение

      В последней главе я оставил вас с компилятором который должен почти работать, за исключением того, что мы все еще ограничены односимвольными токенами. Цель этого урока состоит в том, чтобы избавиться от этого ограничения раз и навсегда. Это означает, что мы должны иметь дело с концепцией лексического анализатора (сканера).
      Возможно я должен упомянуть, почему нам вообще нужен лексический анализатор... в конце концов до настоящего времени мы были способны хорошо справляться и без него даже когда мы предусмотрели многосимвольные токены.
      Единственная причина, на самом деле, имеет отношение к ключевым словам. Это факт компьютерной жизни, что синтаксис ключевого слова имеет ту же самую форму, что и синтаксис любого другого идентификатора. Мы не можем сказать пока не получим полное слово действительно ли это ключевое слово. К примеру переменная IFILE и ключевое слово IF выглядят просто одинаковыми до тех пор, пока вы не получите третий символ. В примерах до настоящего времени мы были всегда способны принять решение, основанное на первом символе токена, но это больше невозможно когда присутствуют ключевые слова. Нам необходимо знать, что данная строка является ключевым словом до того, как мы начнем ее обрабатывать. И именно поэтому нам нужен сканер.
      На последнем уроке я также пообещал, что мы могли бы предусмотреть нормальные токены без глобальных изменений того, что мы уже сделали. Я не солгал... мы можем, как вы увидите позднее. Но каждый раз, когда я намеревался встроить эти элементы в синтаксический анализатор, который мы уже построили, у меня возникали плохие чувства в отношении их. Все это слишком походило на временную меру. В конце концов я выяснил причину проблемы: я установил программу лексического анализа не объяснив вам вначале все о лексическом анализе, и какие есть альтернативы. До настоящего времени я старательно избегал давать вам много теории и, конечно, альтернативные варианты. Я обычно не воспринимаю хорошо учебники которые дают двадцать пять различных способов сделать что-то, но никаких сведений о том, какой способ лучше всего вам подходит. Я попытался избежать этой ловушки, просто показав вам один способ, который работает.
      Но это важная область. Хотя лексический анализатор едва ли является наиболее захватывающей частью компилятора он часто имеет наиболее глубокое влияние на общее восприятие языка так как эта часть наиболее близка пользователю. Я придумал специфическую структуру сканера, который будет использоваться с KISS. Она соответствует восприятию, которое я хочу от этого языка. Но она может совсем не работать для языка, который придумаете вы, поэтому в этом единственном случае я чувствую, что вам важно знать ваши возможности.
      Поэтому я собираюсь снова отклониться от своего обычного распорядка. На этом уроке мы заберемся гораздо глубже, чем обычно, в базовую теорию языков и грамматик. Я также буду говорить о других областях кроме компиляторов в которых лексических анализ играет важную роль. В заключение я покажу вам некоторые альтернативы для структуры лексического анализатора. Тогда и только тогда мы возвратимся к нашему синтаксическому анализатору из последней главы. Потерпите... я думаю вы найдете, что это стоит ожидания. Фактически, так как сканеры имеют множество применений вне компиляторов, вы сможете легко убедиться, что это будет наиболее полезный для вас урок.

Лексический анализ

      Лексический анализ – это процесс сканирования потока входных символов и разделения его на строки, называемые лексемами. Большинство книг по компиляторам начинаются с этого и посвящают несколько глав обсуждению различных методов построения сканеров. Такой подход имеет свое место, но, как вы уже видели, существуют множество вещей, которые вы можете сделать даже никогда не обращавшись к этому вопросу, и, фактически, сканер, который мы здесь закончим, не очень будет напоминать то, что эти тексты описывают. Причина? Теория компиляторов и, следовательно, программы следующие из нее, должны работать с большинством общих правил синтаксического анализа. Мы же не делаем этого. В реальном мире возможно определить синтаксис языка таким образом, что будет достаточно довольно простого сканера. И как всегда KISS – наш девиз.
      Как правило, лексический анализатор создается как отдельная часть компилятора, так что синтаксический анализатор по существу видит только поток входных лексем. Теоретически нет необходимости отделять эту функцию от остальной части синтаксического анализатора. Имеется только один набор синтаксических уравнений, который определяет весь язык, поэтому теоретически мы могли бы написать весь анализатор в одном модуле.
      Зачем необходимо разделение? Ответ имеет и теоретическую и практическую основы.
      В 1956 Ноам Хомский определил «Иерархию Хомского» для грамматик. Вот они:
      Тип 0. Неограниченные (например Английский язык)
      Тип 1. Контекстно-зависимые
      Тип 2. Контекстно-свободные
      Тип 3. Регулярные.
      Некоторые характеристики типичных языков программирования (особенно старых, таких как Фортран) относят их к Типу 1, но большая часть всех современных языков программирования может быть описана с использованием только двух последних типов и с ними мы и будем здесь работать.
      Хорошая сторона этих двух типов в том, что существуют очень специфические пути для их анализа. Было показано, что любая регулярная грамматика может быть анализирована с использованием частной формы абстрактной машины, называемой конечным автоматом. Мы уже реализовывали конечные автоматы в некоторых их наших распознающих программ.
      Аналогично грамматики Типа 2 (контекстно-свободные) всегда могут быть анализированы с использованием магазинного автомата (конечный автомат, дополненный стеком). Мы также реализовывали эти машины. Вместо реализации явного стека для выполнения работы мы положились на встроенный стек связанный с рекурсивным кодированием и это фактически является предочтительным способом для нисходящего синтаксического анализа.
      Случается что в реальных, практических грамматиках части, которые квалифицируются как регулярные выражения, имеют склонность быть низкоуровневыми частями, как определение идентификатора:
      <ident> ::= <letter> [ <letter> | <digit> ]*
      Так как требуется различные виды абстрактных машин для анализа этих двух типов грамматик, есть смысл отделить эти низкоуровневые функции в отдельный модуль, лексический анализатор, который строится на идее конечного автомата. Идея состоит в том, чтобы использовать самый простой метод синтаксического анализа, необходимый для работы.
      Имеется другая, более практическая причина для отделения сканера от синтаксического анализатора. Мы хотим думать о входном исходном файле как потоке символов, которые мы обрабатываем справа налево без возвратов. На практике это невозможно. Почти каждый язык имеет некоторые ключевые слова типа IF, WHILE и END. Как я упомянул ранее, в действительности мы не можем знать является ли данная строка ключевым словом до тех пор пока мы не достигнем ее конца, что определено пробелом или другим разделителем. Так что мы должны хранить строку достаточно долго для того, чтобы выяснить имеем мы ключевое слово или нет. Это ограниченная форма перебора с возвратом.
      Поэтому структура стандартного компилятора включает разбиение функций низкоуровневого и высокоуровневого синтаксического анализа. Лексический анализатор работает на символьном уровне собирая символы в строки и т.п., и передавая их синтаксическому анализатору как неделимые лексемы. Также считается нормальным позволить сканеру выполнять работу по идентификации ключевых слов.

Конечные автоматы и альтернативы

      Я упомянул, что регулярные выражения могут анализироваться с использованием конечного автомата. В большинстве книг по компиляторам а также в большинстве компиляторов, вы обнаружите, что это применяется буквально. Обычно они имеют настоящую реализацию конечного автомата с целыми числами, используемыми для определения текущего состояния и таблицей действий, выполняемых для каждой комбинации текущего состояния и входного символа. Если вы пишите «front end» для компилятора, используя популярные Unix инструменты LEX и YACC, это то, что вы получите. Выход LEX – конечый автомат, реализованный на C плюс таблица действий, соответствующая входной грамматике данной LEX. Вывод YACC аналогичен... исскуственный таблично-управляемый синтаксический анализатор плюс таблица, соответствующая синтаксису языка.
      Однако это не единственный вариант. В наших предыдущих главах вы много раз видели, что возможно реализовать синтаксические анализаторы специально не имея дела с таблицами, стеками и переменными состояния. Фактически в пятой главе я предупредил вас, что если вы считает себя нуждающимся в этих вещах, возможно вы делаете что-то неправильно и не используете возможности Паскаля. Существует в основном два способа определить состояние конечного автомата: явно, с номером или кодом состояния и неявно, просто на основании того факта, что я нахожусь в каком-то определенном месте кода (если сегодня вторник, то это должно быть Бельгия). Ранее мы полагались в основном на неявные методы, и я думаю вы согласитесь, что они работают здесь хорошо.
      На практике может быть даже не обязательно иметь четко определенный лексический анализатор. Это не первый наш опыт работы с многосимвольными токенами. В третьей главе мы расширили наш синтаксический анализатор для их поддержки и нам даже не был нужен лексический анализатор. Причиной было то, что в узком контексте мы всегда могли сказать просто рассматривая единственный предсказывающий символ, имеем ли мы дело с цифрой, переменной или оператором. В действительности мы построили распределенный лексический анализатор, используя процедуры GetName и GetNum.
      Имея ключевые слов мы не можем больше знать с чем мы имеем дело до тех пор, пока весь токен не будет прочитан. Это ведет нас к более локализованному сканеру, хотя, как вы увидите, идея распределенного сканера все же имеет свои достоинства.

Эксперименты по сканированию

      Прежде чем возвратиться к нашему компилятору, было бы полезно немного поэкспериментировать с общими понятиями.
      Давайте начнем с двух определений, наиболее часто встречающихся в настоящих языках программирования:
      <ident> ::= <letter> [ <letter> | <digit> ]*
      <number ::= [<digit>]+
      (Не забудьте, что "*" указывает на ноль или более повторений условия в квадратных скобках, а "+" на одно и более.)
      Мы уже работали с подобными элементами в третьей главе. Давайте начнем (как обычно) с пустого Cradle. Не удивительно, что нам понадобится новая процедура распознавания:
      {–}
      { Recognize an Alphanumeric Character }
      function IsAlNum(c: char): boolean;
      begin
      IsAlNum := IsAlpha(c) or IsDigit(c);
      end;
      {–}
      Используя ее, давайте напишем следующие две подпрограммы, которые очень похожи на те, которые мы использовали раньше:
      {–}
      { Get an Identifier }
      function GetName: string;
      var x: string[8];
      begin
      x := '';
      if not IsAlpha(Look) then Expected('Name');
      while IsAlNum(Look) do begin
      x := x + UpCase(Look);
      GetChar;
      end;
      GetName := x;
      end;
      {–}
      { Get a Number }
      function GetNum: string;

  • Страницы:
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23