About Teletype
Join
P
@pascalabcnet
June 11, 2023

Пишем интерпретатор на PascalABC.NET. Синтаксический анализатор. Часть 2. Реализуем конкретный язык Simple

Этот текст - продолжение публикации https://teletype.in/@pascalabcnet/Parse1, в которой описывался базовый класс парсера языка программирования.

Следующая статья - https://teletype.in/@pascalabcnet/Parse3

Итак, мы хотим создать язык программирования. Какие конструкции в нем будут?

Программа будет состоять из последовательности операторов, разделенных символом "точка с запятой". Среди операторов языка: оператор присваивания (в т.ч. расширенный - такой как +=), условный оператор, оператор цикла while и оператор вызова процедуры. В выражениях присутствуют операции сложения, умножения, сравнения и логические "и" и "или".

Как записать, какие конструкции есть в языке? Для этого используется грамматика языка программирования, содержащая набор правил, описывающих каждую конструкцию языка.

Правила описываются на специальном языке, получившим название "формы Бэкуса-Наура". Например, правило

Statement := Assign | ProcCall | IfStatement

говорит о том, что оператор языка это присваивание или вызов процедуры или условный оператор или оператор цикла while.

Здесь | - специальный значок, используемый как операция "или" для правил.

К другим специальным значкам относятся * - повторить 0 или более раз, [] - необязательная часть. Например:

ExprList := Expr (',' Expr)*

означает, что список выражений - это выражение, после которого может идти запятая и выражение, повторенные 0 или более раз. А правило

IfStatement := if Expr then Statement [else Statement]

означает, что ветка else может отсутствовать.

Наконец, просто символы берутся в апострофы чтобы не перепутать их со специальными символами.

Грамматика языка Simple

Program := StatementList
StatementList := Statement (';' Statement)*
Statement := Assign | ProcCall | IfStatement | WhileStatement 
  | BlockStatement 
Assign := Id ('=' | '+=' | '-=' | '*=' | '/=') Expr 
ProcCall := Id '(' ExprList ')
FuncCall := Id '(' ExprList ')
WhileStatement := while Expr do Statement
IfStatement := if Expr then Statement [else Statement]
BlockStatement := '{' StatementList '}' 
Expr := Comp (CompOp Comp)*
CompOp := '<' | '>' | '<=' | '>=' | '==' | '!='
Comp := Term (AddOp Term)*
AddOp := '+' | '-' | '||'
Term := Factor (MultOp Factor)*
MultOp := '*' | '/' | '&&'
Factor := IntNum | DoubleNum | FuncCall | '(' Expr ') 
ExprList := Expr (',' Expr)*

Как видим, слева от значка := находится имя конструкции, а справа - то, через что она выражается. Слова, присутствующие в левой части конструкции называются нетерминалами - это подчеркивает, что они зависят от других слов в правой части, среди которых могут быть другие нетерминалы и терминалы (конструкции, которые распознаются лексическим анализатором - например, идентификаторы или числовые константы). Например, в правиле

ProcCall := Id '(' ExprList ')

Id в правой части является терминалом, а ExprList - нетерминалом, определение которого дано ниже.

Отметим также, что грамматика языка программирования обязательно содержит рекурсивные правила. Например, оператор - это If, по веткам then и else которого также идут операторы.

Реализация парсера

Что будет делать парсер? Он будет строить дерево разбора программы или абстрактное синтаксическое дерево (AST-дерево). Название "абстрактное" подчеркивает тот факт, что это дерево отражает структуру программы, но информация о синтаксисе конкретного языка программирования в нем отсутствует. Таким образом, разные синтаксически языки программирования могут быть преобразованы в AST-дерево единой структуры.

Парсер, который распознает программу, удовлетворяющую нашей грамматике, реализуем в виде класса Parser - наследника класса ParserBase. Он будет состоять из методов, имя каждого из которых будет совпадать с именем нетерминала в левой части правила. Таким образом, количество методов будет совпадать с количеством нетерминалов.

Каждый метод реализуем в виде функции, возвращающей поддерево программы, соответствующее распознанному правилу.

Метод MainProgram

Основная программа представляет собой последовательность операторов, после которой идет признак конца файла. Реализуем это правило следующим методом:

function MainProgram: StatementNode; 
begin
  Result := StatementList();
  Requires(TokenType.EOF);
end;

Эта функция реализует правило

Program := StatementList

Тело функции MainProgram состоит из вызова функции StatementList(), которая строит поддерево для последовательности операторов и возвращает его. В конце мы проверяем, что после последовательности операторов идет признак конца файла. Для этого мы используем вызов Requires(TokenType.EOF). Напомним, что Requires требует, чтобы следующим терминалом был TokenType.EOF - если это не так, то кидается исключение, являющееся синтаксической ошибкой.

Метод StatementList

Последовательность операторов задается правилом

StatementList := Statement (';' Statement)*

Реализуем его следующим методом:

function StatementList: StatementNode;
begin
  // stat (; stat)*
  var stl := new StatementListNode;
  stl.Add(Statement());
  Check(TokenType.Semicolon,TokenType.Eof);
  while IsMatch(TokenType.Semicolon) do
    stl.Add(Statement());
  Result := stl;      
end;

Здесь мы возвращаем из метода сконструированный узел StatementListNode. Вначале мы создаем в переменной stl пустой StatementListNode. Затем согласно правилу

StatementList := Statement (';' Statement)*

первым в правой части идет нетерминал Statement, поэтому вызываем соответствующий ему метод (он будет определен позднее) и добавляем результат этого метода - поддерево оператора - в список stl.

После Statement может идти либо точка с запятой либо конец файла. Проверим это:

Check(TokenType.Semicolon,TokenType.Eof);

Далее в правиле

StatementList := Statement (';' Statement)*

у нас идет необязательная часть ';' Statement, которая может либо отсутствовать либо повторяться какое-то количество раз.

Реализуем такое поведение циклом while:

  while IsMatch(TokenType.Semicolon) do
    stl.Add(Statement());

Это означает, что пока мы видим во входном потоке точку, мы её пропускаем (это делает метод IsMatsh, считываем вызовом Statement() следующий оператор и добавляем его к списку stl.

В конце мы возвращаем список stl как результат нашей функции StatementList.

Обратим внимание на момент, когда диагностируются ошибки. Ошибки в StatementList явно нигде не инициируются - это значит, что синтаксическое ошибки могут происходить только в функции Statement.

Метод Statement

Метод Statement для оператора - самый сложный, элегантный и раскрывающий суть ручного парсинга.

Что такое оператор? Все виды операторов нашего языка представлены ниже:

id = expr 
id += expr
id(exprlist)
if expr then stat [else stat]
while expr do stat
{ statlist }

Метод Statement будет последовательно проверять лексемы входного потока программы и пытаться понять, какому оператору они соответствуют.

Самым простым является распознавание операторов, которые начинаются с ключевых слов

if expr then stat [else stat]
while expr do stat

Правило

{ statlist }

означает, что оператор может начинаться с символа {

Наконец, в трех правилах

id = expr 
id += expr
id(exprlist)

оператор начинается с терминала Ident.

Итак, оператор в нашем языке начинается с одного из терминалов If, While, '{', Id и ни с какого другого. Сразу проверим это:

Check(|TokenType.Id, TokenType.tkIf, TokenType.tkWhile, TokenType.LBrace|);

Если во входном потоке идет терминал, отличный от данных, то кидается исключение вида: "Ожидался один из следующих терминалов Id, If, While, {, а встречен ...".

При реализации метода Statement нам удобно не вводить промежуточные методы типа IfStat, WhileStat, а распознавать соответствующие конструкции прямо в теле метода Statement.

Условный оператор

Вначале распознаем условный оператор:

if IsMatch(TokenType.tkIf) then
begin
  var cond := Expr();
  Requires(TokenType.tkThen);
  var thenstat := Statement();
  var elsestat := IsMatch(TokenType.tkElse)? Statement() : nil;
  Result := new IfNode(cond,thenstat,elsestat,pos);
end

Если во входном потоке встречается ключевое слово if, то считываем выражение из входного потока методом Expr, и возвращаем его поддерево в переменную cond.

Затем во входном потоке обязательно должно идти ключевое слово then - если да, то мы его пропускаем, в противном случае кидаем исключение.

Далее во входном потоке идет оператор по ветке then - мы его считываем методом Statement и возвращаем в переменной thenstat.

Наконец, если далее во входном потоке идет ключевое слово else, мы его пропускаем и считываем выражение по ветке else в переменную elsestat.

И в заключение мы создаем узел синтаксического дерева IfNode и возвращаем его. Здесь pos - позиция во входном потоке, которую мы запомнили в самом начале метода Statement.

Оператор while

Оператор While распознаётся аналогичным кодом - не будем его особо комментировать.

else if IsMatch(TokenType.tkWhile) then
begin
  // while expr do stat
  var cond := Expr();
  Requires(TokenType.tkDo);
  var stat := Statement();
  Result := new WhileNode(cond,stat,pos);
end

Составной оператор

Составной оператор начинается с символа { , после которого идет последовательность операторов и закрывающий символ }. В результате распознавания составного оператора возвращается поддерево, соответствующее списку операторов:

else if IsMatch(TokenType.LBrace) then
begin
  // { stlist }
  var stl := StatementList();
  Requires(TokenType.RBrace);
  Result := stl;
  Result.Pos := pos;
end

Обратим внимание, что в синтаксическом дереве не хранится информация о виде операторных скобок - конкретный синтаксис в абстрактном синтаксическом дереве не хранится.

Операторы присваивания и вызова процедуры

Эти операторы объединены тем, что начинаются с идентификатора:

id = expr 
id += expr
id(exprlist)

Обработаем эти ветки если предыдущие ветки не были обработаны:

else
begin  
  var id := Ident();
  ...
end

Заполним многоточие. Нетрудно видеть, что после идентификатора может идти лексема = или += или (. В зависимости от этого мы однозначно выбираем первое, второе или третье правило:

if IsMatch(TokenType.Assign) then
begin
  // id = expr
  var ex := Expr();
  Result := new AssignNode(id,ex,pos);
end
else if IsMatch(TokenType.AssignPlus) then
begin
  // id =+ expr
  var ex := Expr();
  Result := new AssignPlusNode(id,ex,pos);
end
else if IsMatch(TokenType.LPar) then
begin
  // id ( exprlist )
  var exlst := ExprList();
  Result := new ProcCallNode(id,exlst,pos);
  Requires(TokenType.RPar);
end

Наконец, если ни одна из указанных лексем не встретилась, кидаем исключение

else ExpectedError(TokenType.Assign,TokenType.AssignPlus,TokenType.LPar);

Всё! Полный код для метода Statement() приведен ниже:

function Statement: StatementNode;
begin
  // id = expr 
  // id += expr
  // id(exprlist)
  // if expr then stat [else stat]
  // while expr do stat
  // { statlist }
  var pos := CurrentToken.Pos;
  Check(|TokenType.Id, TokenType.tkIf, TokenType.tkWhile, TokenType.LBrace|);
  if IsMatch(TokenType.tkIf) then
  begin
    var cond := Expr();
    Requires(TokenType.tkThen);
    var thenstat := Statement();
    var elsestat := IsMatch(TokenType.tkElse)? Statement() : nil;
    Result := new IfNode(cond,thenstat,elsestat,pos);
  end
  else if IsMatch(TokenType.tkWhile) then
  begin
    // while expr do stat
    var cond := Expr();
    Requires(TokenType.tkDo);
    var stat := Statement();
    Result := new WhileNode(cond,stat,pos);
  end
  else if IsMatch(TokenType.LBrace) then
  begin
    // { stlist }
    var stl := StatementList();
    Requires(TokenType.RBrace);
    Result := stl;
    Result.Pos := pos;
  end
  else
  begin  
    // надо просматривать на глубину 2
    var id := Ident(); // Если не идентификатор, то будет ошибка Id ожидался, что неправильно
    if IsMatch(TokenType.Assign) then
    begin
      // id = expr
      var ex := Expr();
      Result := new AssignNode(id,ex,pos);
    end
    else if IsMatch(TokenType.AssignPlus) then
    begin
      // id =+ expr
      var ex := Expr();
      Result := new AssignPlusNode(id,ex,pos);
    end
    else if IsMatch(TokenType.LPar) then
    begin
      // id ( exprlist )
      var exlst := ExprList();
      Result := new ProcCallNode(id,exlst,pos);
      Requires(TokenType.RPar);
    end
    else ExpectedError(TokenType.Assign,TokenType.AssignPlus,TokenType.LPar); // непонятно, что тут писать
  end;
end;

Метод ExprList

Для парсинга последовательности выражений составим метод ExprList, который строится аналогично методу StatementList:

function ExprList(): ExprListNode;
begin
  // expr (',' expr)*
  var lst := new ExprListNode();
  lst.Add(Expr());
  while IsMatch(TokenType.Comma) do
    lst.Add(Expr());
  Result := lst;
end;

Метод Ident

Это - простой метод, который состоит по-существу в создании синтаксического узла IdNode:

function Ident: IdNode;
begin
  var id := Requires(TokenType.Id);
  Result := new IdNode(id.Value as string, id.Pos);
end;

Метод Expr

Оставшиеся методы связаны с разбором выражения. Вот часть грамматики, отвечающая за разбор выражений:

Expr := Comp (CompOp Comp)*
Comp := Term (AddOp Term)*
Term := Factor (MultOp Factor)*
Factor := IntNum | DoubleNum | StringLiteral | '(' Expr ')

Здесь Expr выражается через Comp (операнды операций сравнения), Comp выражается через Term (операнды сложения) и Term выражается через Factor (операнды умножения). Такое построение грамматики выражений хорошо известно - самые низкоприоритетные операции CompOp находятся в первом правиле, а в каждом следующем правиле располагаются всё более приоритетные операции. Таким образом, в нашем языке операции сравнения - самые низкоприоритетные, за ними идут операции сложения и затем операции умножения как самые приоритетные. Например, в выражении

x > 0 && y < 3

первой выполнится операция && как более приоритетная, что неправильно, поэтому в этом выражении следует использовать скобки:

(x > 0) && (y < 3)

Итак, запрограммируем парсинг правила:

Expr := Comp (CompOp Comp)*

Вот код:

function Expr: ExprNode;
begin
  // comp (compop comp)*
  var ex := Comp();
  while At(TokenType.Greater,TokenType.GreaterEqual,TokenType.Less,
    TokenType.LessEqual,TokenType.Equal,TokenType.NotEqual) do
  begin
    var op := Advance;
    var right := Comp();
    ex := new BinOpNode(ex,right,string(op.Value),ex.pos); 
  end;
  Result := ex;
end;

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

Интересно отметить, что синтаксические ошибки если и могут происходить, то только в методе Comp. которым мы и займемся далее.

Метод Comp

Этот метод предназначен для парсинга выражений с операциями сложения и операциями равного с ними приоритета. Он реализует правило грамматики

term (addop term)*

Вот его код:

function Comp: ExprNode;
begin
  // term (addop term)*
  var ex := Term();
  while At(TokenType.Plus,TokenType.Minus,TokenType.tkOr) do
  begin
    var op := Advance;
    var right := Term();
    ex := new BinOpNode(ex,right,string(op.Value),ex.Pos); 
  end;
  Result := ex;
end;

Нетрудно видеть, что структура кода аналогична предыдущему методу.

Здесь следует обратить внимание на порядок создания узлов BinOpNode в случае подряд идущих операций сложения. Например, в выражении

2 + 5 - 3

мы вначале парсим 2 + 5 и формируем из этого выражения первый узел BinOpNode(2,'+',5). Затем мы парсим остаток выражения - 3 и формируем узел BinOpNode так чтобы уже разобранное выражение было первым операндом: 

BinOpNode(BinOpNode(2,'+',5),'-',3)

Это соответствует тому что операции с одним приоритетом выполняются слева направо - такие операции называются левоассоциативными.

Обращаем внимание, что в данном случае ассоциировать операции справа налево и переставлять операнды

BinOpNode(3,'-',BinOpNode(2,'+',5))

является ошибкой.

Метод Term

Метод Term парсит выражения с операциями умножения и одинаковыми с ними по приоритету. Его реализация аналогична предыдущему методу:

function Term(): ExprNode;
begin
  // Factor (multop Factor)*
  var ex := Factor();
  while At(TokenType.Multiply,TokenType.Divide,TokenType.tkAnd) do
  begin
    var op := Advance;
    var right := Factor();
    ex := new BinOpNode(ex,right,string(op.Value),ex.Pos); 
  end;
  Result := ex;
end;

Метод Factor

Данный метод - наиболее интересный в серии методов разбора выражений. Он является конечным - не существует операций в нашем языке выше чем у операций умножения. Операндами у операций умножения выступают целые и вещественные числа, идентификаторы и выражения в скобках:

IntNum | DoubleNum | ProcCall | '(' Expr ')

Приведем код этого метода.

function Factor(): ExprNode;
begin
  var pos := CurrentToken.Pos;
  if At(TokenType.IntNum) then
    Result := new IntNode(integer(Advance.Value),pos)
  else if At(TokenType.DoubleNum) then
    Result := new DoubleNode(real(Advance.Value),pos)
  else if IsMatch(TokenType.LPar) then
  begin  
    // ( expr )
    Result := Expr();
    Requires(TokenType.RPar);
  end
  else if At(TokenType.Id) then
  begin  
    // id
    // id ( exprlist )
    var id := Ident();
    if IsMatch(TokenType.LPar) then
    begin
      var exlst := ExprList();
      Result := new FuncCallNode(id,exlst,id.Pos);
      Requires(TokenType.RPar);
    end
    else Result := id;
  end  
  else SyntaxError(#39;Expected INT or ( or id but {PeekToken.Typ} found',
    PeekToken.Pos);
end;

Мы можем распознать, по какой ветке правила идти, по первой лексеме. Если встреченная лексема - это TokenType.IntNum, то перед нами целое, и надо сформировать узел целого числа, если встречена лексема TokenType.DoubleNum, то формируем узел вещественного числа.

Если встречена открывающая скобка, то мы имеем дело с выражением в скобках: нам надо пропустить открывающую скобку, распарсить последующее выражение и пропустить закрывающую скобку, которая обязательно должна идти после выражения:

  else if IsMatch(TokenType.LPar) then
  begin  
    // ( expr )
    Result := Expr();
    Requires(TokenType.RPar);
  end

Наконец, если перед нами идентификатор, то возможны два варианта: это просто идентификатор и это - вызов функции. Во втором случае после идентификатора идет открывающая скобка, после которой идет список выражений и закрывающая скобка. Парсинг этих конструкций приведен ниже:

  else if At(TokenType.Id) then
  begin  
    // id
    // id ( exprlist )
    var id := Ident();
    if IsMatch(TokenType.LPar) then
    begin
      var exlst := ExprList();
      Result := new FuncCallNode(id,exlst,id.Pos);
      Requires(TokenType.RPar);
    end
    else Result := id;
  end

Наконец, во всех остальных случаях кидаем ошибку:

else SyntaxError(#39;Expected INT or ( or id but {PeekToken.Typ} found',
  PeekToken.Pos);

Всё, метод Factor реализован. Приведем его полный код:

function Factor(): ExprNode;
begin
  var pos := CurrentToken.Pos;
  if At(TokenType.IntNum) then
    Result := new IntNode(integer(Advance.Value),pos)
  else if At(TokenType.DoubleNum) then
    Result := new DoubleNode(real(Advance.Value),pos)
  else if IsMatch(TokenType.LPar) then
  begin  
    // ( expr )
    Result := Expr();
    Requires(TokenType.RPar);
  end
  else if At(TokenType.Id) then
  begin  
    // id
    // id ( exprlist )
    var id := Ident();
    if IsMatch(TokenType.LPar) then
    begin
      var exlst := ExprList();
      Result := new FuncCallNode(id,exlst,id.Pos);
      Requires(TokenType.RPar);
    end
    else Result := id;
  end  
  else SyntaxError(#39;Expected INT or ( or id but {PeekToken.Typ} found',
    PeekToken.Pos);
end;

Полный код парсера

Приведем полный код модуля парсера:

unit ParseUnit;
{$zerobasedstrings}

uses LexUnit, ASTNodes, ParseUnitBase, Common;

type 
  Parser = class(ParserBase)
  public
    function MainProgram: StatementNode; 
    begin
      Result := StatementList();
      Requires(TokenType.EOF);
    end;
    
    function StatementList: StatementNode;
    begin
      // stat (; stat)*
      var stl := new StatementListNode;
      stl.Add(Statement());
      while IsMatch(TokenType.Semicolon) do
        stl.Add(Statement());
      Result := stl;      
    end;
    
    function Statement: StatementNode;
    begin
      // id = expr 
      // id += expr
      // id(exprlist)
      // if expr then stat [else stat]
      // while expr do stat
      // { statlist }
      var pos := CurrentToken.Pos;
      Check(|TokenType.Id, TokenType.tkIf, TokenType.tkWhile, 
        TokenType.LBrace|);
      if IsMatch(TokenType.tkIf) then
      begin
        var cond := Expr();
        Requires(TokenType.tkThen);
        var thenstat := Statement();
        var elsestat := IsMatch(TokenType.tkElse)? Statement() : nil;
        Result := new IfNode(cond,thenstat,elsestat,pos);
      end
      else if IsMatch(TokenType.tkWhile) then
      begin
        // while expr do stat
        var cond := Expr();
        Requires(TokenType.tkDo);
        var stat := Statement();
        Result := new WhileNode(cond,stat,pos);
      end
      else if IsMatch(TokenType.LBrace) then
      begin
        // { stlist }
        var stl := StatementList();
        Requires(TokenType.RBrace);
        Result := stl;
        Result.Pos := pos;
      end
      else
      begin  
        var id := Ident(); 
        if IsMatch(TokenType.Assign) then
        begin
          // id = expr
          var ex := Expr();
          Result := new AssignNode(id,ex,pos);
        end
        else if IsMatch(TokenType.AssignPlus) then
        begin
          // id =+ expr
          var ex := Expr();
          Result := new AssignPlusNode(id,ex,pos);
        end
        else if IsMatch(TokenType.LPar) then
        begin
          // id ( exprlist )
          var exlst := ExprList();
          Result := new ProcCallNode(id,exlst,pos);
          Requires(TokenType.RPar);
        end
        else ExpectedError(TokenType.Assign,TokenType.AssignPlus,
          TokenType.LPar); 
      end;
    end;
    
    function ExprList(): ExprListNode;
    begin
      // expr (',' expr)*
      var lst := new ExprListNode();
      lst.Add(Expr());
      while IsMatch(TokenType.Comma) do
        lst.Add(Expr());
      Result := lst;
    end;
    
    function Ident: IdNode;
    begin
      var id := Requires(TokenType.Id);
      Result := new IdNode(id.Value as string, id.Pos);
    end;
    
    function Expr: ExprNode;
    begin
      // comp (compop comp)*
      var ex := Comp();
      while At(TokenType.Greater,TokenType.GreaterEqual,TokenType.Less,
        TokenType.LessEqual,TokenType.Equal,TokenType.NotEqual) do
      begin
        var op := Advance;
        var right := Comp();
        ex := new BinOpNode(ex,right,string(op.Value),ex.pos); 
      end;
      Result := ex;
    end;
    
    function Comp: ExprNode;
    begin
      // term (addop term)*
      var ex := Term();
      while At(TokenType.Plus,TokenType.Minus,TokenType.tkOr) do
      begin
        var op := Advance;
        var right := Term();
        ex := new BinOpNode(ex,right,string(op.Value),ex.Pos); 
      end;
      Result := ex;
    end;
    
    function Term(): ExprNode;
    begin
      // Factor (multop Factor)*
      var ex := Factor();
      while At(TokenType.Multiply,TokenType.Divide,TokenType.tkAnd) do
      begin
        var op := Advance;
        var right := Factor();
        ex := new BinOpNode(ex,right,string(op.Value),ex.Pos); 
      end;
      Result := ex;
    end;
    
    function Factor(): ExprNode;
    begin
      var pos := CurrentToken.Pos;
      if At(TokenType.IntNum) then
        Result := new IntNode(integer(Advance.Value),pos)
      else if At(TokenType.DoubleNum) then
        Result := new DoubleNode(real(Advance.Value),pos)
      else if IsMatch(TokenType.LPar) then
      begin  
        // ( expr )
        Result := Expr();
        Requires(TokenType.RPar);
      end
      else if At(TokenType.Id) then
      begin  
        // id
        // id ( exprlist )
        var id := Ident();
        if IsMatch(TokenType.LPar) then
        begin
          var exlst := ExprList();
          Result := new FuncCallNode(id,exlst,id.Pos);
          Requires(TokenType.RPar);
        end
        else Result := id;
      end  
      else SyntaxError(#39;Expected INT or ( or id but {PeekToken.Typ} found',
             PeekToken.Pos);
    end;
  end;
  
end.

Основная программа

Теперь напишем основную программу, которая парсит текст программы на нашем языке:

uses LexUnit,ParseUnit,Common;

begin
  var text := 'i = 1; sum = 0; n = 100000000; ' + NewLine +
    'while i<100000000 do { sum += 1/i; i += 1 }; '+ NewLine +
    'Print(sum)'; 
    
  var lex := new Lexer(text);
  try
    var par := new Parser(lex);
    var progr := par.MainProgram;
    Print(progr);
  except
    on e: LexerException do
      OutputError('Lexer error:',e,lex.Lines);
    on e: SyntaxException do
      OutputError('Parser error:',e,lex.Lines);
  end;  
end.

Программа парсится без ошибок и в результате выводится в следующем виде:

([((1),(i)),((0),(sum)),((100000000),(n)),(([((/,(i),(1)),(sum)),((1),(i))]),(<,(100000000),(i))),(([(sum)]),(Print))])

Это не очень информативно, но хоть как-то отражает то, что мы распарсили. В следующей статье мы обсудим, как выводить дерево разбора программы в более читаемом виде.

Реакция на ошибки

У нас хороший парсер, и он правильно реагирует на синтаксические ошибки. Давайте сделаем некоторые ошибки и посмотрим на реакцию парсера.

Ошибка 1

Для программы с пропущенным целым

var text := 'i = ; sum = 0; n = 100000000; ' ;

реакция на ошибку:

i = ; sum = 0; n = 100000000;  
    ^ 
Parser error: (1,5): Expected INT or ( or id but Semicolon found

Ошибка 2

Для программы с пропущенным идентификатором

var text := 'i = 0;  = 0; n = 100000000; ' ;

реакция на ошибку:

i = 0;  = 0; n = 100000000;  
        ^ 
Parser error: (1,9): Id или tkIf или tkWhile или LBrace ожидалось, но Assign найдено

Ошибка 3

Для программы с лишней точкой с запятой

var text := 'i = 0; sum = 0; n = 100000000; ' ;

реакция на ошибку:

i = 0; sum = 0; n = 100000000;  
                              ^ 
Parser error: (1,31): Id или tkIf или tkWhile или LBrace ожидалось, но Eof найдено

Ошибка 4

Для программы с пропущенным do

var text := 'i = 1; sum = 0; n = 100000000; ' + NewLine +
    'while i<100000000  { sum += 1/i; i += 1 }; '+ NewLine +
    'Print(sum)';

реакция на ошибку:

while i<100000000  { sum += 1/i; i += 1 }; 
                   ^ 
Parser error: (2,20): tkDo ожидалось, но LBrace найдено

Как видим, реакция на ошибки - хорошая: показывается место ошибки, встреченная лексема и лексемы, которые должны быть.

@pascalabcnet
June 11, 2023, 08:46
0 views
2 reactions
0 replies
0 reposts