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

В рамках первой лабораторной работы вам необходимо реализовать по сути 3 небольших модуля на Javascript:
  • Модуль чтения Json файлов через XMLHttpRequest
  • Модуль парсинга JSON строки в объектную модель (можно пользоваться системным JSON.parse());
  • Модуль поиска лексем в строке, написанной на входном языке программирования (согласно индивидуальному заданию студента);
  • Модуль вывода необходимой информации (входная строка, таблица лексем, распознанные лексемы) в окно браузера.

Общая схема лексического анализатора

Необходимо написать свою функцию парсинга JSON (за дополнительные баллы) или воспользоваться системной JSON.parse(), а также функцию поиска лексем в программе на входном языке.

Json парсер

В рамках лабораторных работ вы можете реализовать свой собственный парсер JSON за дополнительные баллы. Это факультативное задание. А именно повторить функционал стандартной функции JSON.parse()

Сериализацию реализовывать не надо. Ваша функция parse должна принимать на вход строку с JSON, а на выходе должна генерировать объектную модель из представленного JSON (см. рисунок выше). Посмотреть, как работает стандартная функция JSON.parse() можно здесь

Пример парсера json можно скачать следующим образом:

git clone https://github.com/douglascrockford/JSON-js.git

Для самостоятельной реализации JSON парсера достаточно изучить главы 11 и 13 из книги Выразительный Javascript

Естественно написать надо так, чтобы уметь объяснить на отчете, что и как делал. Поэтому бездумная копипаста до добра не доведет.

Таблица лексем в формате JSON

JSON парсер получает на вход таблицу лексем в виде текстовой строки, внутреннее содержимое которой описано в формате JSON. Ниже приводится пример такой таблицы для языка Милан (упрощенный Pascal). Просьба разобраться с полями этого JSON, т.к. бездумное копирование приведет к провалу на отчете. Я за вас написал многие регулярки, но вы должны отлично понимать их значение.

{
  "indentation": {
    "regex": "(\s*)",
    "skip": true
  },
  "keywords": {
    "regex": "\b([a-z]{2,})\b",
    "list": {
      "var_lex": "var",
      "while_lex": "while",
      "begin_lex": "begin",
      "end_lex": "end",
      "if_lex": "if",
      "then_lex": "then",
      "else_lex": "else",
      "do_lex": "do",
      "for_lex": "for",
      "to_lex": "to",
      "read_lex": "read",
      "write_lex": "write",
      "and_lex": "and",
      "or_lex": "or",
      "integer_lex": "integer",
      "string_lex": "string" 
    }
  },
  "ident": {
    "regex": "\b([_a-zA-Z]\w*)\b",
    "link": "arrayOfIdent" 
  },
  "digit_const": {
    "regex": "\b(\d+)\b",
    "link": "arrayOfConst" 
  },
  "string_const": {
    "regex": "\"(.*)\"",
    "link": "arrayOfConst" 
  },
  "one_line_comment": {
    "regex": "\/\/(.*)$",
    "skip": true
  },
  "multi_line_comment": {
    "regex": "\/\*([\s\S]*?)\*\/",
    "skip": true
  },  
  "operators": {
    "regex": "([-=+\*\/&\|!>:<]{1,2})",
    "list": {
      "and": "&&",
      "or": "||",
      "greater_or_eq": ">=",
      "less_or_eq": "<=",
      "not_equal": "!=",
      "assing": ":=",
      "plus": "+",
      "minus": "-",
      "mult": "*",
      "div": "/",
      "equal": "=",
      "greater": ">",
      "less": "<",
      "not": "!" 
    }
  },
  "separators": {
    "regex": "([[\])(:,;.]{1})",
    "list": {
      "open_parentheses": "(",
      "close_parentheses": ")",
      "open_bracket": "[",
      "close_bracket": "]",
      "semicolon": ";",
      "colon": ":",
      "comma": ",",
      "point": "." 
    }
  }
}

Ниже предложен более оптимизированный вариант таблицы лексем. Он лучше подходит для синтаксического анализа и позволяет учитывать приоритет операций.

{
  "indentation": {
    "regex": "(\s+)",
    "skip": true
  },
  "keywords": {
    "regex": "([a-z]{2,})\b",
    "list": {
      "self": [
        "var", "begin", "end", "while", "do", "if", "then", "else",
        "for", "to", "read", "write", "integer", "string" 
      ],
      "logic_operator": ["and", "or"]
    }
  },
  "ident": {
    "regex": "([_a-zA-Z]\w*)\b",
    "link": "arrayOfIdent",
    "name": "ident" 
  },
  "digit_const": {
    "regex": "(\d+)\b",
    "link": "arrayOfConst",
    "name": "digit_const" 
  },
  "string_const": {
    "regex": "\"(.*)\"",
    "link": "arrayOfConst",
    "name": "string_const" 
  },
  "one_line_comment": {
    "regex": "\/\/(.*)\n",
    "skip": true
  },
  "multi_line_comment": {
    "regex": "\/\*([\s\S]*?)\*\/",
    "skip": true
  },  
  "operators": {
    "regex": "([-=+\*\/>:<]{1,2})",
    "list": {
      "self": [":="],
      "comparison_operator": [">=", "<=", "<>", "=", ">", "<"],      
      "plus_minus": ["+", "-"],
      "mult_div": ["*", "/"]
    }
  },
  "separators": {
    "regex": "([)(:,;.]{1})",
    "list": {
      "self": ["(", ")", ";", ":", ",", "."]
    }
  }
}

Для своей программы вы напишете подобную таблицу лексем своего входного языка.

Теперь краткое небольшое пояснение.

Такие поля как "keywords", "indentation" и другие с этого же уровня просто группируют лексемы. В каждом таком поле содержится объект, внутри которого обязательно есть поле "regex", содержащее регулярное выражение. Также может быть поле "list", которое содержит уже конкретный список лексем, которые позволяют выделить существующие лексемы из всего потока токенов, идентифицированных регулярным выражением.

Обращаю внимание на то, что в JSON важен порядок объявления. Именно он задает приоритет лексем. Чем выше описание лексемы, тем выше ее приоритет перед другими. Приоритет необходим поскольку регулярные выражения для одного типа лексем могут идентифицировать лексемы, которые на самом деле принадлежат к другому типу. Например регулярное выражение для идентификаторов однозначно идентифицирует все ключевые слова. Поэтому необходимо ключевые слова объявить до идентификаторов.

Функция JSON.parse() считывает содержимое JSON последовательно и создает объектную модель в том же порядке, что она была определена в JSON. Затем при проверке вхождения лексем в строку с программой на входном языке необходимо перебирать все свойства JSON-таблицы лексем через цикл for..in. По стандарту данный цикл перебирает свойства объектов в том порядке, в котором они были определены в данном объекте. Именно эта особенность позволяет нам устанавливать приоритет лексем. Более подробно об этом можно почитать здесь

Поля "indentation", "one_line_comment", "multi_line_comment" описывают отступы и комментарии. Внутри есть вложенное свойство "skip", которое говорит лексическому анализатору, что попадающие под регулярки конструкции необходимо пропускать. Для некоторых языков, например для Python, отступы не надо пропускать, т.к. они носят иерархическую роль. Соответственно, можно предусмотреть функционал для лексического анализатора, при котором отступы будут учитываться при поиске лексем.

Поля "ident", "digit_const", "string_const" обозначают идентификаторы и константы. Внутри у них есть поле "link", которое ссылается на массив идентификаторов или констант. Эти массивы должны генерироваться в процессе работы анализатора. Название массивов должно совпадать с заданным в поле "link".

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

Передача таблицы лексем в программу анализатора

Для передачи таблицы лексем в виде текстового файла в транслятор можно воспользоваться специальным объектом XMLHttpRequest. Подробнее об этом написано в статье XMLHttpRequest для загрузки конфигов в JavaScript. Кроме того, т.к. регулярки в созданном на основе JSON объекте таблицы лексем представляют собой обыкновенные текстовые строки, то непосредственно перед лексическим анализом необходимо преобразовать эти строковые поля Regex в аналогичные регулярные выражения с помощью конструктора new RegExp(...) и сохранить обратно в поля Regex объекта таблицы лексем.

После чтения файла JSON с таблицей лексем, его необходимо распарсить, чтобы превратить в дерево объектов, описывающих таблицу лексем. Для этого необходимо использовать стандартную функцию JSON.parse(). Но при попытке распарсить ваши таблицы лексем возникнет ошибка чтения "неизвестный символ". Связано это с тем, что регулярки, которые вы описываете в таблице лексем используют один обратный сэш "\", и JSON.parse() воспринимает идущий после этого слеша символ, как текстовый спецсимвол, типа "\n", что неверно, т.к. в регулярках описываются спецсимволы именно регулярных выражений. Поэтому, чтобы JSON.parse() считал ваши обратные слэши именно как слэши, нужно одинарный слэш в JSON таблицы лексем заменить на двойной. Но в файле JSON это делать некрасиво, поэтому необходимо использовать функцию replace() с двумя параметрами. Т.к. слэши экранируют друг друга, то заменять надо сразу на 4 слэша "\\\\"

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

Лексический анализатор получает на вход (см. рисунок выше):
  • Текстовую строку с программой на входном языке
  • Объектную модель таблицы лексем, распознанную JSON парсером.
На выходе лексический анализатор имеет:
  • Массив с последовательностью лексем из программы на входном языке
  • Массив идентификаторов и массив констант
  • При найденной неизвестной лексеме сообщение об ошибке с номером строки и номером символа, содержащей лексему

Пример массива лексем приведен на рисунке выше. Значениями массива являются названия лексем, либо подмассив с двумя полями. Первое поле содержит слово обозначающее тип идентификатора или константы ("ident", "digit_const", "string_const"). Второе поле содержит ссылку на массив идентификаторов или констант. Например,

[ident, arrayOfIdent[0]]

Массив идентификаторов или массив констант представляет собой двумерный массив:
[[0, "nameVar1"], [1, "nameVar2"], [2, "nameVar3"], ...]

Первым элементом переменной является числовой индекс, а вторым, собственно, само название переменной. При этом, когда мы делаем ссылку на этот массив из массива лексем (напр. [ident, arrayOfIdent[5]]), то по сути мы не копируем значение в массив лексем, а сохраняем в массиве лексем только ссылку на соответствующую переменную в массиве идентификаторов. Как мы все помним, в javascript массивы являются объектами, а объекты мы не копируем, а передаем по ссылке. Таким образом, мы избегаем дублирования информации.

Обратите внимание, что лексический анализатор по сути занимается простым перебором свойств из JSON-таблицы лексем и их сравнением со строкой содержащей программу на входном языке. Все настройки для анализатора задаются в JSON, благодаря чему мы можем через этот JSON описать практически любой входной язык. То есть лексический анализатор получается универсальным, способным обработать любой входной язык. Соответственно, намертво вшивать в код лексического анализатора функции для идентификации какого-то конкретного типа лексем нельзя в силу требования универсальности.

Лексический анализатор представляет собой рекурсивную функцию, которая последовательно сравнивает все регулярки с началом входной строки. Затем когда совпадение найдено, оно записывается в выходной массив, а подстрока соответствующая регулярке отрезается от начала входной строки и оставшаяся строка вновь передается в рекурсию. И так, пока входная строка не останется пустой.

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

Пример работы лексического анализатора

Показаны первые 3 итерации рекурсивной функции , которая ищет лексемы.
str - строка содержащая программу на входном языке
arrayOfIdent - массив идентификаторов. Сюда мы сохраняем все найденные переменные, на которые потом будем просто ссылаться
arrayLexems - массив всех найденных лексем. Просто содержит лексемы в том порядке, в котором они были найдены во входной строке.

P.S. Любые совпадения в названиях переменных с настоящими проектами случайны. Данное руководство составлено в ознакомительных целях. Крайне рекомендуется при разработке проекта руководствоваться здравым смыслом и не копировать все бездумно из данного руководства. Разработка должна быть обязательно своя собственная, соответственно созданные вами алгоритмы и структуры данных должны походить на аналогичные в данном руководстве только отдаленно.

lexer.png (219,584 КБ) Дмитриев Александр, 11.11.2015 04:31

rec.png (170,727 КБ) Дмитриев Александр, 12.11.2015 07:06

Добавить изображение из буфера обмена (Максимальный размер: 20 МБ)