Создание_синтаксического_анализатора_простого_языка_программирования

Комментарии к синтаксическому анализатору

Мы пишем синтаксический анализатор методом рекурсивного спуска. Для этого грамматика должна быть праворекурсивной.

Грамматика нашего языка имеет вид:

progr -> block
stlist -> statement ; stlist | statement
statement -> assign | block | cycl
assign -> ID := expr
expr -> ID | INUM
block -> BEGIN stlist END
cycl -> CYCLE expr st

Здесь правило

stlist -> statement ; stlist | statement

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

Примеры правильных программ в данной грамматике:

begin
  a := 2
end

begin
  a := 2;
  cycle a
  begin
    b := a;
    c := 234
  end
end

begin
  b := 2
end

Примеры неправильных программ в данной грамматике:

a := 2;

begin
  b := 2
end.

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

Ошибки, распознаваемые синтаксическим анализатором, называются синтаксическими и выводятся вызовом процедуры syntaxerror.

Отметим также, что приведенный парсер (синтаксический анализатор) не выполняет никаких семантических действий - он только распознает, принадлежит ли программа языку, порождаемому данной грамматикой.

Модуль синтаксического анализатора (парсера)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SimpleLangLexer;

namespace SimpleLangParser
{
    public class ParserException : System.Exception
    {
        public ParserException(string msg)
            : base(msg)
        {
        }

    }

    public class Parser
    {
        private SimpleLangLexer.Lexer l;

        public Parser(SimpleLangLexer.Lexer lexer)
        {
            l = lexer;
        }

        public void Progr()
        {
            Block();
        }

        public void Expr() 
        {
            if (l.LexKind == Tok.ID || l.LexKind == Tok.INUM)
            {
                l.NextLexem();
            }
            else
            {
                SyntaxError("expression expected");
            }
        }

        public void Assign() 
        {
            l.NextLexem();  // пропуск id
            if (l.LexKind == Tok.ASSIGN)
            {
                l.NextLexem();
            }
            else {
                SyntaxError(":= expected");
            }
            Expr();
        }

        public void StatementList() 
        {
            Statement();
            while (l.LexKind == Tok.SEMICOLON)
            {
                l.NextLexem();
                Statement();
            }
        }

        public void Statement() 
        {
            switch (l.LexKind)
            {
                case Tok.BEGIN:
                    {
                        Block(); 
                        break;
                    }
                case Tok.CYCLE:
                    {
                        Cycle(); 
                        break;
                    }
                case Tok.ID:
                    {
                        Assign();
                        break;
                    }
                default:
                    {
                        SyntaxError("Operator expected");
                        break;
                    }
            }
        }

        public void Block() 
        {
            l.NextLexem();    // пропуск begin
            StatementList();
            if (l.LexKind == Tok.END)
            {
                l.NextLexem();
            }
            else
            {
                SyntaxError("end expected");
            }

        }

        public void Cycle() 
        {
            l.NextLexem();  // пропуск cycle
            Expr();
            Statement();
        }

        public void SyntaxError(string message) 
        {
            var errorMessage = "Syntax error in line " + l.LexRow.ToString() + ":\n";
            errorMessage += l.FinishCurrentLine() + "\n";
            errorMessage += new String(' ', l.LexCol - 1) + "^\n";
            if (message != "")
            {
                errorMessage += message;
            }
            throw new ParserException(errorMessage);
        }
   
    }
}

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using SimpleLangParser;
using SimpleLangLexer;

namespace SimpleLangParserTest
{
    class Program
    {
        static void Main(string[] args)
        {
            string fileContents = @"begin
    a := 2;
    cycle a
    begin
        b := a;
        c := 234
    end
end";
            TextReader inputReader = new StringReader(fileContents);
            Lexer l = new Lexer(inputReader);
            Parser p = new Parser(l);
            try
            {
                p.Progr();
                if (l.LexKind == Tok.EOF)
                {
                    Console.WriteLine("Program successfully recognized");
                }
                else
                {
                    p.SyntaxError("end of file was expected");
                }
            }
            catch (ParserException e)
            {
                Console.WriteLine("lexer error: " + e.Message);
            }
            catch (LexerException le)
            {
                Console.WriteLine("parser error: " + le.Message);
            }
        }
    }
}

Основные задания (7 баллов)

Добавить оператор WHILE expr DO statement(в лексический анализатор - добавлять новые ключевые слова) (3 балла)
Добавить оператор FOR ID := expr TO expr DO statement(в лексический анализатор - добавлять новые ключевые слова) (4 балла)

Дополнительные задания (7 баллов)

Добавить оператор IF expr THEN stat ELSE stat (предусмотреть полную и неполную форму оператора) (3 балла)
Добавить грамматику выражений (4 балла)

E ::= T A A ::= ε | + T A | - T A T ::= M B B ::= ε | * M B | / M B M ::= id | num | (E)

Грамматика составлена так, что по ней можно составить ручной анализатор методом рекурсивного спуска.

Provide feedback

Saved searches