Рассматривается лексический анализатор для языка арифметических выражений, включающего переменные и функции. Из общих соображений, выделяются следующие токены:
<токен> ::= <шаблон>
number ::= /[0-9]+(\.[0-9]*)?([eE][+-]?[0-9]+)?/
operator ::= /[+*/^-]/
id ::= /[a-z_][a-z_0-9]*/
lparen ::= /\(/
rparen ::= /\)/
comma ::= /,/Упражнение 1. Постройте ДКА лексического анализа для токена id.
Упражнение 2. Постройте ДКА лексического анализа для токена number.
В результате построения ДКА для всех токенов и объединения их общим начальным состоянием, получим следующий ДКА:
| состояние | символ | новое состояние |
|---|---|---|
| 0 | [a-z_] | 7 |
| 0 | ( | 8 |
| 0 | ) | 9 |
| 0 | , | 10 |
| 0 | [+*/^-] | 6 |
| 0 | [0-9] | 1 |
| 1 | [0-9] | 1 |
| 1 | . | 2 |
| 1 | [eE] | 3 |
| 2 | [0-9] | 2 |
| 2 | [eE] | 3 |
| 3 | [+-] | 4 |
| 3 | [0-9] | 5 |
| 4 | [0-9] | 5 |
| 5 | [0-9] | 5 |
| 7 | [a-z_0-9] | 7 |
| состояние | токен |
|---|---|
| 1 | number |
| 2 | number |
| 5 | number |
| 6 | operator |
| 7 | id |
| 8 | lparen |
| 9 | rparen |
| 10 | comma |
Упражнениe 3. Реализуйте аналогичный лексический анализатор на любимом языке программирования. Пробельные символы используются как разделитель – между любыми двумя лексемами может быть произвольное число пробельных символов, но они не могут встречаться внутри лексем. Т.е. 1234 + соответствует лексемам 1234, +; в то же время 12 34 должно интерпретироваться как две лексемы 12 и 34.
Обработку пробелов можно реализовать ad-hoc, как специальный случай в начальном состоянии, либо добавить шаблон / +/, но не создавать для него токены.
Пример реализации этого лексического анализатора на языке Haskell доступен по адресу https://github.com/lierdakil/compilers-course3/blob/master/Lexer.lhs или в читаемой форме здесь
Пример реализации на языке C++:
https://github.com/lierdakil/compilers-course3/blob/cpp/lexer.h
https://github.com/lierdakil/compilers-course3/blob/cpp/lexer.cpp
Упражнение 4. Добавьте обработку лексических ошибок в Ваш анализатор. При обнаружении лексической ошибки анализатор должен прекращать разбор и выводить сообщение типа “обнаружен неожиданный символ x при разборе шаблона y”.
Примеры ввода/вывода лексического анализатора
| Ввод | Вывод |
|---|---|
| 667.22 | (Number, 6.6722e2) |
| 22.18E+10 | (Number, 2.218e11) |
| 37e-99 | (Number, 3.7e-98) |
| 40. | (Number, 40.0) |
| 362e+80 | (Number, 3.62e82) |
| 2.010 | (Number, 2.010) |
| 35E+35 | (Number, 3.5e36) |
| 53.353e-13 | (Number, 5.3353e-12) |
| 9 | (Number, 9.0) |
| 9.e0 | (Number, 9.0) |
| + | (Operator, ‘+’) |
| * | (Operator, ’*’) |
| / | (Operator, ‘/’) |
| ^ | (Operator, ‘^’) |
| - | (Operator, ‘-’) |
| ( | (LParen) |
| ) | (RParen) |
| , | (Comma) |
| hm | (Identifier, “hm”) |
| ocn4wx | (Identifier, “ocn4wx”) |
| o | (Identifier, “o”) |
| qkg | (Identifier, “qkg”) |
| j8w26h | (Identifier, “j8w26h”) |
| lsuec51v | (Identifier, “lsuec51v”) |
| gipgb4 | (Identifier, “gipgb4”) |
| giocqic | (Identifier, “giocqic”) |
| qic | (Identifier, “qic”) |
| qe2315 | (Identifier, “qe2315”) |
| 123efg | (Number, 1.23e2); (Identifier, “efg”) |
| 1+2*3,var | (Number, 1.0); (Operator, ‘+’); (Number, 2.0); (Operator, *); (Number, 3); (Comma); (Identifier, “var”) |
| 123e1 | (Number, 1.23e3) |
| 123 e1 | (Number, 1.23e2); (Identifier, “e1”) |
| 123e+ | (Number, 1.23e2); (Identifier, “e”); (Operator, “+”) |