{–}
      program Branch;
      {–}
      { Constant Declarations }
      const TAB = ^I;
      CR = ^M;
      {–}
      { Variable Declarations }
      var Look : char; { Lookahead Character }
      Lcount: integer; { Label Counter }
      {–}
      { Read New Character From Input Stream }
      procedure GetChar;
      begin
      Read(Look);
      end;
      {–}
      { Report an Error }
      procedure Error(s: string);
      begin
      WriteLn;
      WriteLn(^G, 'Error: ', s, '.');
      end;
      {–}
      { Report Error and Halt }
      procedure Abort(s: string);
      begin
      Error(s);
      Halt;
      end;
      {–}
      { Report What Was Expected }
      procedure Expected(s: string);
      begin
      Abort(s + ' Expected');
      end;
      {–}
      { Match a Specific Input Character }
      procedure Match(x: char);
      begin
      if Look = x then GetChar
      else Expected('''' + x + '''');
      end;
      {–}
      { Recognize an Alpha Character }
      function IsAlpha(c: char): boolean;
      begin
      IsAlpha := UpCase(c) in ['A'..'Z'];
      end;
      {–}
      { Recognize a Decimal Digit }
      function IsDigit(c: char): boolean;
      begin
      IsDigit := c in ['0'..'9'];
      end;
      {–}
      { Recognize an Addop }
      function IsAddop(c: char): boolean;
      begin
      IsAddop := c in ['+', '-'];
      end;
      {–}
      { Recognize White Space }
      function IsWhite(c: char): boolean;
      begin
      IsWhite := c in [' ', TAB];
      end;
      {–}
      { Skip Over Leading White Space }
      procedure SkipWhite;
      begin
      while IsWhite(Look) do
      GetChar;
      end;
      {–}
      { Get an Identifier }
      function GetName: char;
      begin
      if not IsAlpha(Look) then Expected('Name');
      GetName := UpCase(Look);
      GetChar;
      end;
      {–}
      { Get a Number }
      function GetNum: char;
      begin
      if not IsDigit(Look) then Expected('Integer');
      GetNum := Look;
      GetChar;
      end;
      {–}
      { Generate a Unique Label }
      function NewLabel: string;
      var S: string;
      begin
      Str(LCount, S);
      NewLabel := 'L' + S;
      Inc(LCount);
      end;
      {–}
      { Post a Label To Output }
      procedure PostLabel(L: string);
      begin
      WriteLn(L, ':');
      end;
      {–}
      { Output a String with Tab }
      procedure Emit(s: string);
      begin
      Write(TAB, s);
      end;
      {–}
      { Output a String with Tab and CRLF }
      procedure EmitLn(s: string);
      begin
      Emit(s);
      WriteLn;
      end;
      {–}
      { Parse and Translate a Boolean Condition }
      procedure Condition;
      begin
      EmitLn('<condition>');
      end;
      {–}
      { Parse and Translate a Math Expression }
      procedure Expression;
      begin
      EmitLn('<expr>');
      end;
      {–}
      { Recognize and Translate an IF Construct }
      procedure Block(L: string); Forward;
      procedure DoIf(L: string);
      var L1, L2: string;
      begin
      Match('i');
      Condition;
      L1 := NewLabel;
      L2 := L1;
      EmitLn('BEQ ' + L1);
      Block(L);
      if Look = 'l' then begin
      Match('l');
      L2 := NewLabel;
      EmitLn('BRA ' + L2);
      PostLabel(L1);
      Block(L);
      end;
      Match('e');
      PostLabel(L2);
      end;
      {–}
      { Parse and Translate a WHILE Statement }
      procedure DoWhile;
      var L1, L2: string;
      begin
      Match('w');
      L1 := NewLabel;
      L2 := NewLabel;
      PostLabel(L1);
      Condition;
      EmitLn('BEQ ' + L2);
      Block(L2);
      Match('e');
      EmitLn('BRA ' + L1);
      PostLabel(L2);
      end;
      {–}
      { Parse and Translate a LOOP Statement }
      procedure DoLoop;
      var L1, L2: string;
      begin
      Match('p');
      L1 := NewLabel;
      L2 := NewLabel;
      PostLabel(L1);
      Block(L2);
      Match('e');
      EmitLn('BRA ' + L1);
      PostLabel(L2);
      end;
      {–}
      { Parse and Translate a REPEAT Statement }
      procedure DoRepeat;
      var L1, L2: string;
      begin
      Match('r');
      L1 := NewLabel;
      L2 := NewLabel;
      PostLabel(L1);
      Block(L2);
      Match('u');
      Condition;
      EmitLn('BEQ ' + L1);
      PostLabel(L2);
      end;
      {–}
      { Parse and Translate a FOR Statement }
      procedure DoFor;
      var L1, L2: string;
      Name: char;
      begin
      Match('f');
      L1 := NewLabel;
      L2 := NewLabel;
      Name := GetName;
      Match('=');
      Expression;
      EmitLn('SUBQ #1,D0');
      EmitLn('LEA ' + Name + '(PC),A0');
      EmitLn('MOVE D0,(A0)');
      Expression;
      EmitLn('MOVE D0,-(SP)');
      PostLabel(L1);
      EmitLn('LEA ' + Name + '(PC),A0');
      EmitLn('MOVE (A0),D0');
      EmitLn('ADDQ #1,D0');
      EmitLn('MOVE D0,(A0)');
      EmitLn('CMP (SP),D0');
      EmitLn('BGT ' + L2);
      Block(L2);
      Match('e');
      EmitLn('BRA ' + L1);
      PostLabel(L2);
      EmitLn('ADDQ #2,SP');
      end;
      {–}
      { Parse and Translate a DO Statement }
      procedure Dodo;
      var L1, L2: string;
      begin
      Match('d');
      L1 := NewLabel;
      L2 := NewLabel;
      Expression;
      EmitLn('SUBQ #1,D0');
      PostLabel(L1);
      EmitLn('MOVE D0,-(SP)');
      Block(L2);
      EmitLn('MOVE (SP)+,D0');
      EmitLn('DBRA D0,' + L1);
      EmitLn('SUBQ #2,SP');
      PostLabel(L2);
      EmitLn('ADDQ #2,SP');
      end;
      {–}
      { Recognize and Translate a BREAK }
      procedure DoBreak(L: string);
      begin
      Match('b');
      EmitLn('BRA ' + L);
      end;
      {–}
      { Recognize and Translate an «Other» }
      procedure Other;
      begin
      EmitLn(GetName);
      end;
      {–}
      { Recognize and Translate a Statement Block }
      procedure Block(L: string);
      begin
      while not(Look in ['e', 'l', 'u']) do begin
      case Look of
      'i': DoIf(L);
      'w': DoWhile;
      'p': DoLoop;
      'r': DoRepeat;
      'f': DoFor;
      'd': DoDo;
      'b': DoBreak(L);
      else Other;
      end;
      end;
      end;
      {–}
      { Parse and Translate a Program }
      procedure DoProgram;
      begin
      Block('');
      if Look <> 'e' then Expected('End');
      EmitLn('END')
      end;
      {–}
      { Initialize }
      procedure Init;
      begin
      LCount := 0;
      GetChar;
      end;
      {–}
      { Main Program }
      begin
      Init;
      DoProgram;
      end.
      {–}

Введение

План

Грамматика

Операторы отношений

Исправление грамматики

      Проблема, с которой мы столкнулись, возникает потому, что наше определение и арифметических и булевых показателей позволяет использовать выражения в скобках. Так как определения рекурсивны, мы можем закончить с любым числом уровней скобок и синтаксический анализатор не может знать с каким видом выражения он имеет дело.
      Решение просто, хотя и приводит к глубоким изменениям нашей грамматики. Мы можем разрешить круглые скобки только в одном виде показателей. Способ сделать это значительно изменяется от языка к языку. Это то место, где не существует соглашения или договора способного нам помочь.
      Когда Никлаус Вирт разработал Паскаль, его желанием было ограничить количество уровней приоритета (меньше подпрограмм синтаксического анализа, в конце концов). Так операторы OR и исключающее OR рассматриваются просто как Addop и обрабатываются на уровне математического выражения. Аналогично AND рассматривается подобно Mulop и обрабатывается с Term. Уровни приоритета:

      Заметьте, что имеется только один набор синтаксических правил, применимый к обоим видам операторов. Тогда согласно этой грамматике выражения типа:
      x + (y AND NOT z) DIV 3
      являются совершенно допустимыми. И, фактически, они таковыми являются... настолько, насколько синтаксический анализатор в этом заинтересован. Паскаль не позволяет смешивать арифметические и логические переменные, и подобные вещи скорее перехватываются на семантическом уровне, когда придет время генерировать для них код, чем на синтаксическом уровне.
      Авторы C взяли диаметрально противоположный метод: они обрабатывают операторы как разные и C имеет что-то гораздо более похожее на наши семь уровней приоритета. Фактически, в C имеется не менее 17 уровней! Дело в том, что C имеет также операторы '=', '+=' и их родственников '<<', '>>', '++', '–' и т.д. Как ни странно, хотя в C арифметические и булевые операторы обрабатываются раздельно, то переменные нет... в C нет никаких булевых или логических переменных, так что логическая проверка может быть сделана на любом целочисленном значении.
      Мы сделаем нечто среднее. Я склонен обычно придерживаться Паскалевского подхода, так как он кажется самым простым с точки зрения реализации, но это приводит к некоторым странностям, которые я никогда очень сильно не любил, как например в выражении:
      IF (c >= 'A') and (c <= 'Z') then ...
      скобки обязательны. Я никогда не мог понять раньше почему, и ни мой компилятор, ни любой человек также не объясняли этого достаточно хорошо. Но сейчас мы все можем видеть, что оператор «and», имеющий приоритет как у оператора умножения, имеет более высокий приоритет, чем у операторов отношения, поэтому без скобок выражение эквивалентно:
      IF c >= ('A' and c) <= 'Z' then
      что не имеет смысла.
      В любом случае, я решил разделить операторы на различные уровни, хотя и не столько много как в C.
      <b-expression> ::= <b-term> [<orop> <b-term>]*
      <b-term> ::= <not-factor> [AND <not-factor>]*
      <not-factor> ::= [NOT] <b-factor>
      <b-factor> ::= <b-literal> | <b-variable> | <relation>
      <relation> ::= | <expression> [<relop> <expression]
      <expression> ::= <term> [<addop> <term>]*
      <term> ::= <signed factor> [<mulop> factor]*
      <signed factor>::= [<addop>] <factor>
      <factor> ::= <integer> | <variable> | (<b-expression>)
      Эта грамматика приводит к тому же самому набору семи уровней, которые я показал ранее. Действительно, это почти таже самая грамматика... я просто исключил заключенное в скобки b-выражение как возможный b-показатель и добавил отношение как допустимую форму b-показателя.
      Есть одно тонкое, но определяющее различие, которое заставляет все это работать. Обратите внимание на квадратные скобки в определении отношения. Это означает, что relop и второе выражение являются необязательными.
      Странным последствием этой грамматики (которое присутствует и в C) является то, что каждое выражения потенциально является булевым выражение. Синтаксический анализатор всегда будет искать булевское выражение, но «уладит» все до арифметического. Честно говоря, это будет замедлять синтаксический анализатор потому что он должен пройти через большее количество вызовов процедур. Это одна из причин, почему компиляторы Паскаля обычно быстрее выполяют компиляцию, чем компиляторы C. Если скорость для вас – больное место, придерживайтесь синтаксиса Паскаля.

Синтаксический анализатор