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

Введение

Для описания лексем используются регулярные выражения.

Регулярные выражения тесно связаны с автоматными грамматиками: по любой автоматной грамматике можно записать эквивалентное ей регулярное выражение и наоборот. Эквивалентность понимается в том смысле что языки, ими порождаемые, будут совпадать.

Автоматная грамматика легко переводится на язык синтаксических диаграмм.

Основные обозначения в регулярных выражениях

Регулярное выражение над алфавитом Σ - это

a - отдельный символ из алфавита Σ
ε - пустая цепочка
Если R и Q - регулярные выражения, то RQ - регулярное выражение, являющееся конкатенацией цепочек, порождаемых R и Q
Если R и Q - регулярные выражения, то R | Q - регулярное выражение, являющееся цепочкой, порождаемой либо R, либо Q
Если R - регулярное выражение, то R* - повторение R ноль и более раз
Если R - регулярное выражение, то R+ - повторение R один и более раз. Очевидно, что R+ = RR*
Если R - регулярное выражение, то (R) - такое же регулярное выражение

Примеры регулярных выражений

Целое со знаком:

(+|-|)ц+

Идентификатор:

б(б|ц)*

Альтернативные обозначения в регулярных выражениях

{R} = R*
[R] = (R | ε)

В этом случае * и + не используются

Таблица соответствия регулярных выражений и автоматных грамматик

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

Фрагмент выражения	Участок синтаксической диаграммы	Фрагмент кода
R		if ch = R then NextCh else error;
ε
R ! ε		if ch = R then NextCh;
RQ		if ch = R then NextCh else error; if ch = Q then NextCh else error;
R ! Q		if ch in [R,Q] then NextCh else error;
R+		if ch = R then NextCh else error; while ch = R do NextCh;
R\*		while ch = R do NextCh;
(R)

Синтаксическая диаграмма для целого со знаком

Программа распознавания целого со знаком по синтаксической диаграмме

Правило. При разборе очередной конструкции первый символ уже должен быть считан с помощью NextCh.

public class LexerException : System.Exception
{
    public LexerException(string msg)
        : base(msg)
    {
    }

}

public class Lexer
{

    protected int position;
    protected char currentCh;       // очередной считанный символ
    protected int currentCharValue; // целое значение очередного считанного символа
    protected System.IO.StringReader inputReader;
    protected string inputString;

    public Lexer(string input)
    {
        inputReader = new System.IO.StringReader(input);
        inputString = input;
    }

    public void Error()
    {
        System.Text.StringBuilder o = new System.Text.StringBuilder();
        o.Append(inputString + '\n');
        o.Append(new System.String(' ', position - 1) + "^\n");
        o.AppendFormat("Error in symbol {0}", currentCh);
        throw new LexerException(o.ToString());
    }

    protected void NextCh()
    {
        this.currentCharValue = this.inputReader.Read();
        this.currentCh = (char)currentCharValue;
        this.position += 1;
    }

    public virtual void Parse()
    {

    }
}

public class IntLexer : Lexer
{

    protected System.Text.StringBuilder intString;

    public IntLexer(string input)
        : base(input)
    {
        intString = new System.Text.StringBuilder();
    }

    public override void Parse()
    {
        NextCh();
        if (currentCh == '+' || currentCh == '-')
        {
            NextCh();
        }

        if (char.IsDigit(currentCh))
        {
            NextCh();
        }
        else
        {
            Error();
        }

        while (char.IsDigit(currentCh))
        {
            NextCh();
        }


        if (currentCharValue != -1) // StringReader вернет -1 в конце строки
        {
            Error();
        }

        System.Console.WriteLine("Interger is recognized");

    }
}


public class Program
{
    public static void Main()
    {
        string input = "154216";
        Lexer L = new IntLexer(input);
        try
        {
            L.Parse();
        }
        catch (LexerException e)
        {
            System.Console.WriteLine(e.Message);
        }

    }
}

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

Реализовать программу на PascalABC.NET или C#.

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

Реализовать в программе семантические действия по накоплению в строке распознанного целого числа и преобразованию его в целое в конце разбора (при встрече завершающего символа). Семантические действия следует добавлять перед каждым вызовом NextCh кроме первого. (1 балл)
Идентификатор. (1 балл)
Целое со знаком, начинающееся не с цифры 0.(1 балл)
Чередующиеся буквы и цифры, начинающиеся с буквы.(1 балл)
Список букв, разделенных символом , или ; В качестве семантического действия должно быть накопление списка букв в списке и вывод этого списка в конце программы.(1 балл)

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