Синтаксический анализ методом рекурсивного спуска

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

E -> E + T | E - T | T
T -> T * F | T / F | F
F -> V ^ F | V
V -> ( E ) | id | number | - V

Здесь символами +,- и т.д. обозначены соответствующие операторы (различные случаи токена operator). Круглые скобки соответствуют токенам lparen и rparen.

Эта грамматика является леворекурсивной. Так, например, в левой позиции продукции нетерминала E находится нетерминал E. Чтобы эффективно применять эту грамматику для нисходящего разбора, следует устранить левую рекурсию. Здесь это достаточно легко сделать, поскольку левая рекурсия только прямая.

Упражнение 1. Устраните левую рекурсию.

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

E  -> T E'
E' -> + T E' | - T E' | ε
T  -> F T'
T' -> * F T' | / F T' | ε
F  -> V ^ F | V
V  -> ( E ) | id | number | - V

Символом ε обозначена, как обычно, пустая строка.

Дополнительно для этой грамматики следует произвести левую факторизацию: обе продукции нетерминала F начинаются с нетерминала V, поэтому сделать выбор в пользу одной из них по предпросмотру первого токена невозможно.

Упражнение 2. Произведите левую факторизацию.

После устранения левой рекурсии и левой факторизации, получаем следующую грамматику:

E  -> T E'
E' -> + T E' | - T E' | ε
T  -> F T'
T' -> * F T' | / F T' | ε
F  -> V F'
F' -> ^ F | ε
V  -> ( E ) | id | number | - V

Эту грамматику уже можно непосредственно использовать для реализации нисходящего синтаксического анализатора, либо используя метод рекурсивного спуска, либо пользуясь формализмом LL(1).

Упражнениe 3. Реализуйте синтаксический анализатор (рекурсивный или LL(1)) для этой грамматики на любимом языке программирования. Анализатор должен возвращать синтаксическое дерево соответствующего выражения.

Пример реализации синтаксического анализатора методом рекурсивного спуска на языке Haskell доступен по адресу https://github.com/lierdakil/compilers-course3/blob/master/RecursiveParser.lhs или в читаемой форме здесь

Упражнение 4. Реализуйте простой интерпретатор, вычисляющий значение, соответствующее синтаксическому дереву.

Пример реализации интерпретатора на языке Haskell доступен по адресу https://github.com/lierdakil/compilers-course3/blob/master/SimpleInterpreter.lhs или в читаемой форме здесь

Пример реализации на языке C++:
https://github.com/lierdakil/compilers-course3/blob/cpp/parser.h
https://github.com/lierdakil/compilers-course3/blob/cpp/parser.cpp

Примеры ввода/вывода для синтаксического анализатора:

Input: 123
Output:
Tree: 123.0
Value: 123.0
-------------------
Input: 123e123
Output:
Tree: 1.23e+125
Value: 1.23e+125
-------------------
Input: 123+456
Output:
Tree: +(123.0, 456.0)
Value: 579.0
-------------------
Input: 123/123
Output:
Tree: /(123.0, 123.0)
Value: 1.0
-------------------
Input: 123+(123-123)
Output:
Tree: +(123.0, -(123.0, 123.0))
Value: 123.0
-------------------
Input: -1+2/3
Output:
Tree: +(neg(1.0), /(2.0, 3.0))
Value: -0.33333333333333337
-------------------
Input: 2*(3+4)
Output:
Tree: *(2.0, +(3.0, 4.0))
Value: 14.0
-------------------
Input: (3+4)*2
Output:
Tree: *(+(3.0, 4.0), 2.0)
Value: 14.0
-------------------
Input: (((((2)))))
Output:
Tree: 2.0
Value: 2.0
-------------------
Input: 4*4+1
Output:
Tree: +(*(4.0, 4.0), 1.0)
Value: 17.0
-------------------
Input: 1+2*3/2
Output:
Tree: +(1.0, /(*(2.0, 3.0), 2.0))
Value: 4.0
-------------------
Input: 2/2+1-2
Output:
Tree: -(+(/(2.0, 2.0), 1.0), 2.0)
Value: 0.0
-------------------
Input: (((2))
Output:
Expected token Tok_rp, but got TokenType.eof
-------------------
Input: 1+
Output:
No alternative matched while parsing nonterminal F:TokenType.eof
-------------------
Input: 3-1*/3
Output:
No alternative matched while parsing nonterminal F:TokenType.Tok_div
-------------------
Input: 1++2
Output:
No alternative matched while parsing nonterminal F:TokenType.Tok_add
-------------------
Input: --2
Output:
Tree: neg(neg(2.0))
Value: 2.0
-------------------
Input: ---2
Output:
Tree: neg(neg(neg(2.0)))
Value: -2.0
-------------------
Input: +4
Output:
No alternative matched while parsing nonterminal F:TokenType.Tok_add
-------------------
Input: 4+
Output:
No alternative matched while parsing nonterminal F:TokenType.eof
-------------------
Input: (1+2)*((3+3)/3))
Output:
Expected token eof, but got TokenType.Tok_rp
-------------------
Input: 2//2
Output:
No alternative matched while parsing nonterminal F:TokenType.Tok_div
-------------------
Input: pi*4^2
Output:
Tree: *(pi, ^(4.0, 2.0))
Value: 50.26548245743669
-------------------
Input: 2^2^3
Output:
Tree: ^(2.0, ^(2.0, 3.0))
Value: 256.0
-------------------
Input: 2^(2^3)
Output:
Tree: ^(2.0, ^(2.0, 3.0))
Value: 256.0
-------------------
Input: (2^2)^3
Output:
Tree: ^(^(2.0, 2.0), 3.0)
Value: 64.0
-------------------
Input: x+1
Output:
Tree: +(x, 1.0)
Unknown variable x
-------------------
Input: 2^3*7
Output:
Tree: *(^(2.0, 3.0), 7.0)
Value: 56.0
-------------------
Input: 7*2^3
Output:
Tree: *(7.0, ^(2.0, 3.0))
Value: 56.0
-------------------
Input: 1%2
Output:
Unexpected input: %
-------------------
Input: 123e+x
Output:
Expected token eof, but got TokenType.Tok_id
-------------------
Input: 123e+
Output:
Expected token eof, but got TokenType.Tok_id