Создание компилятора языка для .NET Framework - Синтаксический анализатор

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

Анализатор является сердцем компилятора и может существовать во множестве видов и форм. У анализатора Good for Nothing есть несколько задач: он обеспечивает соответствие исходной программы определению языка и обрабатывает ошибки в случае сбоя. Он также создает представление программного синтаксиса в памяти, которое потребляется генератором кода и, наконец, анализатор Good for Nothing решает, какие типы среды выполнения использовать.

Первое что мне нужно сделать – это взглянуть на представление программного синтаксиса в памяти, то есть AST. Затем я рассмотрю код, создающий это дерево из лексем сканера. Формат AST быстр, эффективен, прост в кодировании и может быть многократно просмотрен генератором кода. AST для компилятора Good for Nothing показан на рис. 4.

Быстрый взгляд на определение языка Good for Nothing показывает, что AST более-менее соответствует узлам определения языка из синтаксиса EBNF. Лучше всего представить себе определение языка как инкапсуляцию синтаксиса, где абстрактное древо синтаксиса фиксирует структуру этих элементов.

Существует множество доступных алгоритмов анализа и изучение их всех находится за пределами темы этой статьи. В целом, они отличаются в том, как они проходят поток лексем для создания AST. В моем компиляторе Good for Nothing, я использую нисходящий анализатор, именуемый LL (от Left-to-right, Left-most – «Слева направо, Крайний слева») . Это попросту значит, что он читает текст слева направо и конструирует AST, основываясь на следующей доступной лексеме ввода.

Конструктор для моего класса анализатора просто берет список лексем, созданный сканером:

public Parser(IList<object> tokens)
{
    this.tokens = tokens;
    this.index = 0;
    this.result = this.ParseStmt();
    
    if (this.index != this.tokens.Count)
        throw new Exception("expected EOF");
}

Основная часть анализа выполняется методом ParseStmt, как показано на рис. 5. Он возвращает узел Stmt, который служит корневым узлом дерева и соответствует узлу верхнего уровня определения синтаксиса языка. Анализатор обходит список лексем, используя индекс в качестве текущей позиции и в то же время определяя лексемы, подчиненные узлу Stmt в синтаксисе языка (декларации переменных и назначения, циклы, read_ints и отображения). Если лексему не удается опознать, выдается исключение.

Figure 5 ParseStmt Method Identifies Tokens

private Stmt ParseStmt()
{
    Stmt result;

    if (this.index == this.tokens.Count)
    {
        throw new Exception("expected statement, got EOF");
    }
    if (this.tokens[this.index].Equals("print"))
    {
        this.index++;
        ...
    }
    else if (this.tokens[this.index].Equals("var"))
    {
        this.index++;
        ...
    }
        else if (this.tokens[this.index].Equals("read_int"))
    {
        this.index++;
        ...
    }
    else if (this.tokens[this.index].Equals("for"))
    {
        this.index++;
        ...
    }
    else if (this.tokens[this.index] is string)
    {
        this.index++;
        ...
    }
    else
    {
        throw new Exception("parse error at token " + this.index + 
            ": " + this.tokens[this.index]);
    }
    ...
}

При опознании лексемы, создается узел AST и выполняется дальнейший анализ, запрошенный узлом. Ниже приведен код, необходимый для создания узла AST отображения:

// <stmt> := print <expr>
if (this.tokens[this.index].Equals("print"))
{
    this.index++;
    Print print = new Print();
    print.Expr = this.ParseExpr();
    result = print;
}

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

Рис. 6 приводит код ParseExpr. Он проходит по списку лексем от текущего индекса, определяя лексемы, удовлетворяющие определению выражения для языка. В данном случае, метод просто ищет строки, целые числа и переменные (созданные экземпляром сканера) и возвращает соответствующие узлы AST, представляющие эти выражения.

Figure 6 ParseExpr Performs Parsing of Expression Nodes

// <expr> := <string>
// | <int>
// | <ident>
private Expr ParseExpr()
{
  ...
  if (this.tokens[this.index] is StringBuilder)
  {
    string value = ((StringBuilder)this.tokens[this.index++]).ToString();
    StringLiteral stringLiteral = new StringLiteral();
    stringLiteral.Value = value;
    return stringLiteral;
  }
  else if (this.tokens[this.index] is int)
  {
    int intValue = (int)this.tokens[this.index++];
    IntLiteral intLiteral = new IntLiteral();
    intLiteral.Value = intValue;
    return intLiteral;
  }
  else if (this.tokens[this.index] is string)
  {
    string ident = (string)this.tokens[this.index++];
    Variable var = new Variable();
    var.Ident = ident;
    return var;
  }
  ...
}

Для операторов строк, удовлетворяющих определению синтаксиса языка "<stmt> ; <stmt>", используется узел AST последовательности. Этот узел последовательности содержит два указателя на узлы stmt и формирует основу структуры дерева AST. Ниже подробно приведен код, использованные в случае с последовательностью:

if (this.index < this.tokens.Count && this.tokens[this.index] == 
    Scanner.Semi)
{
    this.index++;

    if (this.index < this.tokens.Count &&
        !this.tokens[this.index].Equals("end"))
    {
        Sequence sequence = new Sequence();
        sequence.First = result;
        sequence.Second = this.ParseStmt();
        result = sequence;
    }
}

Дерево AST, показанное на <Fig>рис. 7</Fig>, является плодом следующего фрагмента кода Good for Nothing:

Рис. 7 Дерево AST helloworld.gfn и трассировка на высоком уровне.

var x = "hello world!";
print x;