Определение и реализация средств лексического и синтаксического анализа являлись важным доменом исследования в информатике. Эта работа привела к созданию генераторов лексического и синтаксического анализа lex и yacc. Команды camllex camlyacc, которые мы представим в этой главе, являются их достойными наследниками. Два указанных инструмента стали de–facto стандартными, однако существуют другие средства, как например потоки или рациональные (регулярные) выражения из библиотеки Str, которые могут быть достаточны для простых случаев, там где не нужен мощный анализ.
Необходимость подобных инструментов особенно чувствовалась в таких доменах, как компиляция языков программирования. Однако и другие программы могут с успехом использовать данные средства: базы данных, позволяющие определять запросы или электронная таблица, где содержимое ячейки можно определить как результат какой–нибудь формулы. Проще говоря, любая программа, в которой взаимодействие с пользователем осуществляется при помощи языка, использует лексический и синтаксический анализ.
Возьмем простой случай. ASCII формат часто используется для хранения данных, будь то конфигурационный системный файл или данные табличного файла. Здесь, для использования данных, необходим лексический и синтаксический анализ.
Обобщая, скажем что лексический и синтаксический анализ преобразует линейный поток символов в данные с более богатой структурой: последовательность слов, структура записи, абстрактное синтаксическое дерево программы и т.д.
У каждого языка есть словарный состав (лексика) и грамматика, которая описывает каким образом эти составные объединяются (синтаксис). Для того, чтобы машина или программа могли корректно обрабатывать язык, этот язык должен иметь точные лексические и синтаксические правила. У машины нет “тонкого чувства” для того чтобы правильно оценить двусмысленность натуральных языков. По этой причине, к машине необходимо обращаться в соответствии с четкими правилами, в которых нет исключений. В соответствии с этим, понятия лексики и семантики получили формальные определения, которые будут кратко представлены в данной главе.
Данная глава знакомит нас со средствами лексического и синтаксического анализа, которые входят в дистрибутив Objective CAML. Обычно, синтаксический анализ следует за лексическим. В первой части мы узнаем о простом инструменте лексического анализа из модуля Genlex. После этого ознакомимся с формализмом рациональных выражений и тем самым рассмотрим более детально определение множества лексических единиц. А так же проиллюстрируем их реализацию в модуле Str и инструменте ocamllex. Во второй части мы определим грамматику и рассмотрим правила создания фраз языка. После этого рассмотрим два анализа фраз: восходящий и нисходящий. Они будут проиллюстрированы использованием Stream и ocamlyacc. В приведенных примерах используется контекстно–независимая грамматика. Здесь мы узнаем как реализовать контекстный анализ при помощи Stream. В третьей части мы вернемся к интерпретатору BASIC (см. стр ??) и при помощи ocamllex и ocamlyacc добавим лексические и синтаксические функции анализа языка.
Синтаксический анализ это предварительный и необходимый этап обработки последовательностей символов: он разделяет этот поток в последовательность слов, так называемых лексические единицы или лексемы.
В данном модуле имеется элементарное средство для анализа символьного потока. Для этого используются несколько категорий предопределенных лексических единиц. Эти категории различаются по типу:
Таким образом мы можем разузнать в потоке символов целое число (конструктор Int) и получить его значение (аргумент конструктора int). Распознаваемые символы и строки подчиняются следующим общепринятым соглашением: строка окружена символами (“), а символ окружен ('). Десятичное число представлено либо используя запись с точкой (например 0.01), либо с мантиссой и экспонентой (на пример 1E-2). Кроме этого остались конструкторы Kwd и Ident.
Конструктор Ident предназначен для определения идентификаторов. Идентификатором может быть имя переменной или функции языка программирования. Они состоят из какой угодно последовательности букв и цифр, могут включать символ подчеркивания (_) или апостроф ('). Данная последовательность не должна начинаться с цифры. Любая последовательность следующих операндов тоже будет считаться идентификатором: +,∗,> или −. И наконец, конструктор Kwd определяет категорию специальных идентификаторов или символов.
Категория ключевых слова — единственная из этого множества, которую можно сконфигурировать. Для того, чтобы создать лексический анализатор, воспользуемся следующей конструкцией, которой необходимо передать список ключевых слов на место первого аргумента.
Тем самым получаем функцию, которая принимает на вход поток символов и возвращает поток лексических единиц (с типом token).
Таким образом, мы без труда реализуем лексический анализатор для интерпретатора BASIC. Объявим множество ключевых слов:
При помощи данного множества, определим функцию лексического анализа:
Приведенная функция line_lexer, из входящего потока символов создает поток соответствующих лексем.
Мы также можем реализовать лексический анализ “в ручную” используя потоки.
В следующем примере определен лексический анализатор арифметических выражений. Функции lexer передается поток символов из которого она создает поток лексических единиц с типом lexeme Stream.t1. Символы пробел, табуляция и переход на новую строку удаляются. Для упрощения, мы не будем обрабатывать переменные и отрицательны целые числа.
Функция lexint предназначена для анализа той части потока символов, которая соответствует числовой постоянной. Она вызывается, когда функция lexer встречает цифры. В этом случае функция lexint поглощает все последовательные цифры и выдает соответствующее значение полученного числа.
Оставим ненадолго практику и рассмотрим проблему лексических единиц с теоретической точки зрения.
Лексическая единица является словом. Слово образуется при конкатенации элементов алфавита. В нашем случае алфавитом является множество символов ASCII.
Теоретически, слово может вообще не содержать символов (пустое слово2) или состоять из одного символа.
Теоретические исследования конкатенации элементов алфавита для образования лексических элементов (лексем) привели к созданию простого формализма, известного как рациональные выражения.
Рациональные выражения позволяют определить множества слов. Пример такого множества: идентификаторы. Принцип определения основан на некоторых теоретико–множественный операциях. Пусть M и N два множества слов, тогда мы можем определить:
Один единственный символ ассоциируется с одноэлементным множеством. В таком случае выражение a∣ b∣ c описывает множество состоящее из трех слов a, b и c. Существует более компактная запись: [abc]. Так как наш алфавит является упорядоченным (по порядку кодов ASCII), можно определить интервал. Например, множество цифр запишется как [0−9]. Для группировки выражений можно использовать скобки.
Для того, чтобы использовать в записи сами символы–операторы, как обычные символы, необходимо ставить перед ними обратную косую черту: \. Например множество (\∗)∗ обозначает множество последовательностей звездочек.
Пусть существует множество из цифр (0,1,2,3,4,5,6,7,8,9), символы плюс (+) и минус (−), точки (.) и буквы E. Теперь мы можем определить множество чисел num. Назовем integers множество определенное выражением [0−9]+. Множество неотрицательных чисел unum определяется так:
| integers?(.integers)?(E(\+|−)?integers)? |
Множество отрицательных и положительных чисел записывается:
| unum | −unum или −?unum |
Теперь, после того как множество выражений определено, остается проблема распознавания принадлежности строки символов или одной из ее подстрок этому множеству. Для решения данной задачи необходимо реализовать программу обработки выражений, которая соответствует формальным определениям множества. Для рациональных выражений такая обработка может быть автоматизированна. Подобная автоматизация реализована в модуле Genlex из библиотеки Str и инструментом ocamllex, которые будут представлены в следующих двух параграфах.
В данном модуле имеется абстрактный тип regexp и функция regexp. Указанный тип представляет рациональные выражения, а функция трансформирует рациональное выражение, представленное в виде строки символов, в абстрактное выражение.
Модуль Str содержит несколько функций, которые используют рациональные выражения и манипулируют символьными строками. Синтаксис рациональных выражений библиотеки Str приведен в таблице 10.1.
. любой символ, кроме \ ∗ ноль или несколько экземпляров предыдущего выражения + хотя бы один экземпляр предыдущего выражения ? ноль или один экземпляр предыдущего выражения [..] множество символов интервал записывается при помощи − (пример [0−9]) дополнение записывается при помощи ^ (пример [^A−Z]) ^ начало строки не путать с дополнением ^ $ конец строки ∣ вариант (..) группировка в одно выражение можно ссылаться на это выражение i числовая константа i ссылается на i–ый элемент группированного выражения \ забой, используется для сопоставления зарезервированных символов в рациональных выражениях
Table 10.1: Рациональные выражения.
В следующем примере напишем функцию, которая переводит дату из английского формата во французский. Предполагается, что входной файл состоит из строк, разбитых на поля данных и элементы даты разделяются точкой. Определим функцию, которая из полученной строки (линия файла), выделяет дату, разбивает ее на части, переводит во французских формат и тем самым заменяет старую дату на новую.
ocamllex — это лексический генератор созданный для Objective CAML по модели lex, написанном на языке C. При помощи файла, описывающего элементы лексики в виде множества рациональных выражений, которые необходимо распознать, он создает файл–исходник на Objective CAML. К описанию каждого лексического элемента можно привязать какое–нибудь действие, называемое семантическое действие. В полученном коде используется абстрактный тип lexbuf из модуля Lexing. В данном модуле также имеется несколько функций управления лексическими буферами, которые могут быть использованы программистом для того чтобы определить необходимые действия.
Обычно, файлы, описывающие лексику, имеют расширение .mll. Для того, чтобы из файла lex_file.mll получить файл на Objective CAML, необходимо выполнить следующую команду:
После этого, мы получим файл lex_file.ml, содержащий код лексического анализатора. Теперь, данный файл можно использовать в программе на Objective CAML. Каждому множеству правил анализа соответствует функция, которая принимает лексический буфер (типа Lexing.lexbuf) и затем возвращает значение, определенное семантическим действием. Значит, все действия для определенного правила должны создавать значение одного и того же типа.
Формат у файла для ocamllex следующий:
Части “заголовок” и “продолжение–и–конец” не являются обязательными. Здесь вставляется код Objective CAML, определяющий типы данных, функции и т.д. необходимые для обработки данных. В последней части используются функции, которые используют правила анализа множества лексических данных из средней части. Серия объявлений, которая предшествует определению правил, позволяет дать имя некоторым рациональным выражениям. Эти имена будут использоваться в определении правил.
Вернемся к нашему интерпретатору BASIC и усовершенствуем тип возвращаемых лексических единиц. Таким образом, мы можем воспользоваться функцией lexer, (см. стр. ??) которая возвращает такой же тип результата (lexeme), но на входе она получает буфер типа Lexing.lexbuf.
{
let string_chars s =
String.sub s 1 ((String.length s)-2) ;;
}
let op_ar = ['-' '+' '*' '\%' '/']
let op_bool = ['!' '\&' '|']
let rel = ['=' '<' '>']
rule lexer = parse
[' '] { lexer lexbuf }
| op_ar { Lsymbol (Lexing.lexeme lexbuf) }
| op_bool { Lsymbol (Lexing.lexeme lexbuf) }
| "<=" { Lsymbol (Lexing.lexeme lexbuf) }
| ">=" { Lsymbol (Lexing.lexeme lexbuf) }
| "<>" { Lsymbol (Lexing.lexeme lexbuf) }
| rel { Lsymbol (Lexing.lexeme lexbuf) }
| "REM" { Lsymbol (Lexing.lexeme lexbuf) }
| "LET" { Lsymbol (Lexing.lexeme lexbuf) }
| "PRINT" { Lsymbol (Lexing.lexeme lexbuf) }
| "INPUT" { Lsymbol (Lexing.lexeme lexbuf) }
| "IF" { Lsymbol (Lexing.lexeme lexbuf) }
| "THEN" { Lsymbol (Lexing.lexeme lexbuf) }
| '-'? ['0'-'9']+ { Lint (int_of_string (Lexing.lexeme lexbuf)) }
| ['A'-'z']+ { Lident (Lexing.lexeme lexbuf) }
| '"' [^ '"']* '"' { Lstring (string_chars (Lexing.lexeme lexbuf)) }
После обработки данного файла командой ocamllex получим функцию lexer типа Lexing.lexbuf -> lexeme. Далее, мы рассмотрим каким образом подобные функции используются в синтаксическом анализе (см. стр. ??).
Благодаря лексическому анализу, мы в состоянии разбить поток символов на более структурированные элементы: лексические элементы. Теперь необходимо знать как правильно объединять эти элементы в синтаксически корректные фразы какого–нибудь языка. Правила синтаксической группировки определены посредством грамматических правил. Формализм, произошедший из лингвистики, был с успехом перенят математиками, занимающимися теориями языков, и специалистами по информатике. На странице ?? мы уже видели пример грамматики для языка BASIC. Здесь мы снова вернемся к этому примеру, чтобы более углубленно ознакомится с базовыми концепциями грамматики.
Говоря формальным языком, грамматика основывается на четырех элементах:
| Line | ::= | integer Instruction |
Одна и та же компонента может быть порождена несколькими способами. В этом случае варианты разделяются символом ∣:
| Instruction | ::= | LET variable = Instruction |
| ∣ | GOTO integer | |
| ∣ | PRINT Expression | |
| etc |
С помощью порождающих правил можно определить принадлежит ли последовательность лексем языку.
Рассмотрим простой язык, описывающий арифметические выражения:
| Exp | ::= | integer | (R1) |
| ∣ | Exp + Exp | (R2) | |
| ∣ | Exp * Exp | (R3) | |
| ∣ | (Exp) | (R4) |
здесь (R1) (R2) (R3) (R4) имена правил. По окончании лексического анализа выражение 1*(2+3) становится последовательностью следующих лексем:
| integer * (integer + integer) |
Для того, чтобы проанализировать эту фразу и убедиться в том что она принадлежит языку арифметических выражений, воспользуемся правилами справа налево: если часть выражения соответствует правому члену какого–нибудь правила, мы заменяем это выражение соответствующим левым членом. Этот процесс продолжается до тех пор, пока выражение не будет редуцировано до аксиомы. Ниже представлен результат такого анализа3:
| integer * (integer + integer) | (R1) | Exp * (integer + integer) |
| (R1) | Exp * (Exp + integer) | |
| (R1) | Exp * (Exp + Exp) | |
| (R2) | Exp * (Exp) | |
| (R4) | Exp * Exp | |
| (R3) | Exp |
Начиная с последней линии, которая содержит лишь Exp и следуя стрелкам, можно определить каким образом было полученное выражение исходя из аксиомы Exp. Соответственно данная фраза является правильно сформированной фразой языка арифметических выражений, определенного грамматикой.
Преобразование грамматики в программу, способную распознать принадлежность последовательности лексем языку, который определен грамматикой, является более сложной проблемой, чем проблема использования рациональных приложений. Действительно, в соответствии с математическим результатом любое множество (слов), определенное формализмом рациональных выражений, может быть определено другим формализмом: детерминированные конечные автоматы. Такие автоматы легко реализуются программами, принимающими поток символов. Подобный результат для грамматик в общем не существует. Однако, имеются пробные (?) (weaker) результаты устанавливающие эквивалентность между определенными классами грамматик и более богатыми автоматами: стековый автомат (pushdown automata). Здесь мы не станем вдаваться в детали этих результатов, ни в точное определение таких автоматов. Однако, мы можем определить какие классы грамматики могут использоваться в средствах генерации синтаксических анализаторов или для реализации напрямую анализатора.
Расчленение выражения 1*(2+3) в предыдущем параграфе не является единственным: мы с таким же успехом могли бы начать редуцирование integer, то есть воспользоваться правилом (R2) редуцирования 2+3. Эти два способа распознавания являются двумя типами анализа: восходящий анализ (справа налево) и нисходящий слева направо. Последний анализ легко реализуется при помощи потоков лексем модуля Stream. Средство ocamlyacc использует восходящий анализ, при котором применяется стек, как это уже было проиллюстрировано синтаксическим анализатором программ на Бэйсике. Выбор анализа не просто дело вкуса, в зависимости от используемой для спецификации языка формы грамматики, можно или нет применять нисходящий анализ.
Каноническим примером нисходящего анализа является префиксная запись арифметических выражений, определяемая как:
| Exp | ::= | integer |
| ∣ | + Exp Exp | |
| ∣ | * Exp Exp |
В данном случае достаточно знать первую лексему, для того чтобы определить какое правило может быть использовано. При помощи подобной предсказуемости нет необходимости явно управлять стеком, достаточно положиться на рекурсивный вызов анализатора. И тогда при помощи Genlex и Stream очень просто написать программу реализующую нисходящий анализ. Функция infix_of из полученного префиксного выражения возвращает его инфиксный эквивалент:
Однако не стоит забывать о некоторой примитивности лексического анализа. Советуем периодически добавлять пробелы между различными лексическими элементами.
Синтаксический анализ при помощи потоков предсказуем, он облагает грамматику двумя условиями:
Грамматика арифметических выражений, приведенная на стр. ??, не подходит для нисходящего анализа: они не удовлетворяют ни одному из условий. Для того, чтобы применить нисходящий анализ необходимо переформулировать грамматику таким образом, чтобы удалить левую рекурсию и неопределенность правил. Вот полученный результат:
| Expr | ::= | Atom NextExpr | |
| NextExpr | ::= | + | Atom |
| ∣ | + | Atom | |
| ∣ | - | Atom | |
| ∣ | * | Atom | |
| ∣ | / | Atom | |
| ∣ | є | ||
| Atom | ::= | integer | |
| ∣ | (Expr) |
Заметьте использование пустого слова є в определении NextExpr. Оно необходимо, если мы хотим чтобы просто целое число являлось выражением.
Следующий анализатор есть просто перевод вышеуказанной грамматики в код. Он реализует абстрактное синтаксическое дерево арифметических выражений.
Сложность использования нисходящего анализа заключается в том, что грамматика должна быть очень ограниченной формы. Если язык выражен естественно с использованием левой рекурсии (как в инфиксных выражениях), то не всегда легко определить эквивалентную грамматику, то есть определяющую такой же язык, которая бы удовлетворяла требованиям нисходящего анализа. По этой причине, средства yacc и ocamlyacc реализуют восходящий анализ, который разрешает определение более естественных грамматик. Однако, мы увидим, что даже в этом случае существуют ограничения.
Мы уже вкратце представили на странице ?? принципы восходящего анализа: продвинутся (shift) и сократить (reduce). После каждого подобного действия, состояние стека изменяется. Из этой последовательности можно вывести правила грамматики, в случае если грамматика это позволяет, как в примере с нисходящим анализом. Опять же, сложности возникают из–за неопределенности правил, когда невозможно выбрать между продвинутся или сократить. Проиллюстрируем действие восходящего анализа и его недостатки на все тех же арифметических выражениях в постфиксном и инфиксном написании.
Упрощенная постфиксная грамматика арифметических выражений выглядит так:
| Exp | ::= | integer | (R1) |
| ∣ | Exp Exp + | (R2) | |
| ∣ | Exp Exp * | (R3) |
Данная грамматика является двойственной по отношению к префиксной: для того чтобы точно знать какое правило следует применить, необходимо дождаться окончания анализа. В действительности анализ подобных выражений схож с вычислением при помощи стека. Только вместо проталкивания результата вычисления, проталкиваются грамматические символы. Если в начале стек пустой, то после того как ввод закончен, необходимо получить стек содержащий лишь нетерминальную аксиому. Приведем изменение стека: если мы продвигаемся, то проталкивается текущий нетерминальный символ; если сокращаем, то первые символы стека соответствуют правому члену (в обратном порядке) правила и тогда мы заменяем эти элементы соответствующими нетерминальными элементами.
В таблице 10.2 приведен восходящий анализ выражения 1 2 + 3 * 4 +. Считываемая лексическая единица подчеркивается для более удобного чтения. Конец потока помечается символом $.
Действие Вход Стек 12+3*4+$ [] Сдвиг 2+3*4+$ [1] Сократить (R1) 2+3*4+$ [Exp] Сдвиг +3*4+$ [2 Exp] Сократить (R1) +3*4+$ [Exp Exp] Сдвиг, Сократить (R2) 3*4+$ [Exp] Сдвиг, Сократить (R1) *4+$ [Exp Exp] Сдвиг, Сократить (R3) 4+$ [Exp] Сдвиг, Сократить (R1) +$ [Exp Exp] Сдвиг, Сократить (R2) $ [Exp]
Table 10.2: Восходящий анализ.
Вся трудность перехода от грамматики к программе распознающей язык заключается в определении действия, которое необходимо применить. Проиллюстрируем эту проблему на трех примерах, приводящих к трем неопределенностям.
Первый пример есть грамматика выражений использующих операцию сложения:
| E0 | ::= | integer | (R1) |
| ∣ | E0 + E0 | (R2) |
Неопределенность данной грамматики проявляется при использовании правила R2. Предположим следующую ситуацию:
| Действие | Вход | Стек |
| : | ||
| + | E0 + E0… | |
| : |
В подобном случае невозможно определить необходимо сдвинуть и протолкнуть в стек + или сократить в соответствии с правилом (R2) оба E0 и присутствующий в стеке + . Подобная ситуация называется конфликтом сдвиг–сокращение (shift/reduce). Она является следствием того, что выражение integer + integer + integer может быть получено деривацией справа двумя способами.
Первый вариант:
| E0 | (R2) | E0 + E0 |
| (R1) | E0 + integer | |
| (R2) | E0 + E0 + integer |
Второй вариант:
| E0 | (R2) | E0 + E0 |
| (R2) | E0 + E0 + E0 | |
| (R1) | E0 + E0 + integer |
Выражения, полученные двумя деривациями, могут показаться одинаковыми с точки зрения вычисления выражения,
(integer + integer) + integer и integer + (integer + integer)
но разными для конструкции синтаксического дерева (см. рис. 5.2 на стр. ??)
Второй пример грамматики, порождающей конфликт между сдвиг–сокращение, содержит такую же неопределенность: явное заключение в скобки. Но в отличии от предыдущего случая, выбор сдвиг–сокращение изменяет смысл выражения. Пусть есть грамматика:
| E1 | ::= | integer | (R1) |
| ∣ | E1 + E1 | (R2) | |
| ∣ | E1 * E1 | (R3) |
Здесь мы снова получаем предыдущий конфликт как в случае с + так и для *, но к этому добавляется другой, между + и *. Опять же, одно и то же выражение может быть получено двумя способами, так как у него существует две деривации справа:
integer + integer * integer
Первый вариант:
| E1 | (R3) | E1 * E1 |
| (R1) | E1 * integer | |
| (R2) | E1 + E1 * integer |
Второй вариант:
| E1 | (R2) | E1 + E1 |
| (R2) | E1 + E1 * E1 | |
| (R1) | E1 + E1 * integer |
В данном выражении обе пары скобок имеют разный смысл:
(integer + integer) * integer ≠ integer + (integer * integer)
Подобную проблему, мы уже встречали в выражениях Basic (см. стр. ??). Она была разрешена при помощи приоритетов, которые присваиваются операторам: сначала редуцируется правило (R3), затем (R2), что соответствует заключению в скобки произведения.
Данную проблему выбора между + и * можно решить изменив грамматику. Для того, введем два новых терминальных символа: член T (term) и множитель F (factor). Отсюда получаем:
| E | ::= | E + T | (R1) |
| | | T | (R2) | |
| T | ::= | T * F | (R3) |
| | | F | (R4) | |
| F | ::= | integer | (R5) |
После этого, единственный способ получить integer + integer * integer: посредством правила (R1).
Третий и последний случай касается условных конструкций языка программирования. На пример в Pascal существует две конструкции: if .. then и if .. then .. else. Пусть существует следующая грамматика:
| Instr | ::= | if EXP then Instr | (R1) |
| − | if EXP then Instr else Instr | (R2) | |
| − | etc… |
И в следующей ситуации:
Невозможно определить соответствуют ли элементы стека правила (R1) и в этом случае необходимо сократить или соответствуют первому Instr правила (R2) и тогда необходимо сдвинуть.
Кроме конфликтов сдвиг–сокращение, восходящий анализ вызывает конфликт сокращение–сокращение.
Мы представим здесь инструмент ocamlyacc, который использует подобную технику может встретить указанные конфликты.
Принцип действия ocamlyacc схож с ocamlex: из входного файла, содержащего грамматику, в которой каждое правило связанно с семантическим действием, генерируется два файла Objective CAML с расширением .ml и .mli. Эти файлы содержат функции и интерфейс синтаксического анализа.
Файл для ocamlyacc с синтаксическим описанием заканчивается расширением .mly и имеет следующий формат:
| %{ | |
| заголовок | |
| %} | |
| декларации | |
| %% | |
| правила | |
| %% | |
| продолжение–и–конец |
Формат правил следующий:
| нетерминальный символ | : | символ…символ | {семантическое действие} |
| | | … | ||
| нетерминальный символ | : | символ…символ | {семантическое действие} |
| ; |
Символ может быть либо терминальным либо нет. Роль частей “заголовок” и “продолжение–и–конец” такая же как и у ocamllex, с разницей в том, что заголовок не виден лишь правилам, но не декларациям. В частности, это означает что загрузка модулей (open) не учитывается в декларациях и следовательно типы должны быть известны.
Семантическое действие это куски кода на Objective CAML, которые выполняются при редуцировании связанного с ним правила. В теле действия можно ссылаться на компоненты правого члена правила. Они нумеруются справа налево начиная с 1. Для того, чтобы ссылаться на первый компонент нужно использовать $1, на второй $2 и так далее.
Нетерминальные аксиомы грамматики объявляются в декларативной части входного файла:
Для каждой из них будет создана своя функция анализа. В декларативной части всегда необходимо указывать возвращаемый тип функции.
Тип output-type должен быть известен.
Warning
Нетерминальные символы становятся именем функций анализа, поэтому они не
должны начинаться с заглавной буквы, которая зарезервирована для конструкторов.
Грамматические правила ссылаются на лексические единицы, которые в являются терминальными символами правил.
Лексема(ы) объявляется следующим способом:
Некоторые лексические единицы, например идентификаторы, являются множеством символьных строк. Когда обнаруживается подобный идентификатор, мы бы хотели получить эту символьную строку. Для этого необходимо указать лексическому анализатору, что эти лексемы имеют привязанное значение, окружив тип значения < и >.
Warning
После того, как данные объявления обработаны ocamlyacc, они
превращаются в конструкторы типа token. Они должны обязательно
начинается с заглавной буквы.
У нас есть возможность использовать строки символов как неявные терминальные
символы.
И в данном случае нет надобности объявлять необходимый символ: они напрямую обрабатываются синтаксическим анализатором, без прохода через лексический. Однако, мы не советуем подобный метод, из соображений единообразия объявлений.
Мы уже видели, что немало конфликтов, возникающих про нисходящем анализе, появляются из неявных правил ассоциативности какого–нибудь оператора или из–за конфликта приоритетов между операторами. Для разрешения подобных конфликтов, можно объявить правила ассоциативности по умолчанию (слева направо, справа налево или никакое) для операторов, а так же приоритет. В приведенном ниже объявлении, указано, что операторы + (лексема PLUS) и * (MULT) ассоциативные справа и что у оператора * приоритет выше, чем у +, потому что MULT объявлен после PLUS.
Операторы объявленные на одной линии, имеют одинаковые приоритеты.
Команда ocamlyacc распознает две следующие опции:
Можно связать оба инструмента ocamllex и ocamlyacc таким образом, чтобы поток символов, превращенный в поток лексем стал входными данными для синтаксического анализатора. Для этого, тип lexeme должен быть известен обоим инструментам. Этот тип определен в файлах с расширением .mli и .ml, созданных ocamlyacc при помощи деклараций токенов из соответствующего файла с расширением .mly. Файл .mll вводит (import) указанный тип, ocamllex переводит данный файл в функцию Objective CAML с типом Lexing.lexbuf -> lexeme. В примере на стр. ?? иллюстрируется указанное взаимодействие и описываются различные этапы компиляции.
Анализаторы, генерируемые ocamlyacc, обрабатывают языки, порождаемые контекстно–независимой грамматикой. Анализ потока лексем не зависит от синтаксических значений, которые уже были проанализированы. Данное утверждение неверно для языка L, представленного следующей формулой:
здесь A,B и C терминальные символы. Мы записали wCw (где w∈(A∣ B)*), а не просто (A∣ B)*C(A∣ B)*, для того чтобы получить такою же слово слева и справа от C.
Для анализа слова из языка L, необходимо хранить в памяти, то что было до символа C, чтобы убедиться, что после следует тоже самое. Далее представим решение данной проблемы. Идея алгоритма состоит в создании функции, которая анализирует поток и точно распознает часть слова, которое находится до возможного нахождения C.
Создадим тип:
Функция parse_w1 создает функцию запоминающую первое w в виде списка функций анализирующих неделимый поток (то есть для одного токена):
Результатом функций, созданных parse_w1, является строка символов, содержащая проанализированную синтаксическую единицу.
Из списка, созданного предыдущей функцией, функция parse_w2 формирует в одну функцию анализа:
Результатом применения parse_w2 будет подслово w. По своей конструкции, функция parse_w2 распознает лишь подслова пройденные функцией parse_w1.
Воспользуемся возможностью называть промежуточные результаты потока и напишем функцию распознавания слов языка L:
Ниже представлены два примера, в первом мы получаем слово вокруг C, а во втором получаем ошибку, так как слова вокруг C разные.
Теперь, используя совместно ocamllex и ocamlyacc, заменим функцию parse для Бэйсика, приведенную на странице ??, на функции полученные при помощи файлов спецификации лексики и синтаксиса языка.
Для этого, мы не сможем воспользоваться типами лексических единиц, в таком виде как они были определены. Необходимо определить более точные типы, чтобы различать операторы, команды и ключевые слова.
Так же, нам понадобится изолировать в отдельном файле basic_types.mli декларации типов, относящиеся к абстрактному синтаксису. В нем будут содержатся декларации типа sentences, а так же других типы необходимые этому.
Данный файл содержит вызовы деклараций типов абстрактного синтаксиса и две функции перевода строк символов в их эквивалент абстрактного синтаксиса.
Здесь содержится три части: декларация лексем, декларация правил ассоциативности и приоритетов, декларация аксиомы line, которая соответствует анализу линии программы или команды.
Ниже представлены лексические единицы:
Имена деклараций говорят сами за себя и они описаны в файле basic_lexer.mll (см. стр. ??).
Правила приоритета операторов схожи со значениями, которые определяются функциями priority_uop и priority_binop, которые были определенны грамматикой Бейсика (см. стр. ??).
Символ Lop необходим для обработки унарных минусов. Он не является терминальным символом, а “псевдо–терминальным”. Благодаря этому, получаем перегрузку операторов, когда в двух случаях использования одного и того же оператора, приоритет меняется в зависимости от контекста. Мы вернемся к этому случаю, когда будем рассматривать правила грамматики.
Здесь нетерминальной аксиомой является line. Полученная функция возвращает дерево абстрактного синтаксиса, которое соответствует проанализированной линии.
Грамматика делится на 3 нетерминальных элемента: line для линии, inst для инструкции и exp для выражений. Действия, которые привязаны к каждому правилу лишь создают соответствующую часть абстрактного синтаксиса.
Данные правила не нуждаюся в особых комментариях, кроме следующего:
Это правило касается использования унарного минуса -. Ключевое слово %prec означает, что указанная конструкция получает приоритет от Lop (в данном случае наивысший).
Лексический анализ содержит лишь одно множество: lexer, которое точно соответствует старой функции lexer (см. стр. ??).
Семантическое действие, которое связано с распознаванием лексических единиц, возвращает результат соответствующего конструктора. Необходимо загрузить файл синтаксических правил, так как в нем декларируется тип лексических единиц. Добавим так же функцию, которая удаляет кавычки вокруг строк.
{
open Basic_parser ;;
let string_chars s = String.sub s 1 ((String.length s)-2) ;;
}
rule lexer = parse
[' ' '\t'] { lexer lexbuf }
| '\n' { Leol }
| '!' { Lneg }
| '&' { Land }
| '|' { Lor }
| '=' { Lequal }
| '%' { Lmod }
| '+' { Lplus }
| '-' { Lminus }
| '*' { Lmult }
| '/' { Ldiv }
| ['<' '>'] { Lrel (Lexing.lexeme lexbuf) }
| "<=" { Lrel (Lexing.lexeme lexbuf) }
| ">=" { Lrel (Lexing.lexeme lexbuf) }
| "REM" [^ '\n']* { Lrem (Lexing.lexeme lexbuf) }
| "LET" { Llet }
| "PRINT" { Lprint }
| "INPUT" { Linput }
| "IF" { Lif }
| "THEN" { Lthen }
| "GOTO" { Lgoto }
| "RUN" { Lcmd (Lexing.lexeme lexbuf) }
| "LIST" { Lcmd (Lexing.lexeme lexbuf) }
| "END" { Lcmd (Lexing.lexeme lexbuf) }
| ['0'-'9']+ { Lint (int_of_string (Lexing.lexeme lexbuf)) }
| ['A'-'z']+ { Lident (Lexing.lexeme lexbuf) }
| '"' [^ '"']* '"' { Lstring (string_chars (Lexing.lexeme lexbuf)) }
Заметьте, что нам пришлось изолировать символ =, который используется одновременно в выражениях и приравниваниях.
Для двух рациональных выражений необходимо привести определенные объяснения.
Линия комментариев соответствует выражению ("REM" ['
n']*), где
за ключевым словом REM следует какое угодно количество символов и
затем перевод строки. Правило, которое соответствует символьным строкам,
('"' ['"']* '"'), подразумевает последовательность символов,
отличных от “ и заключенных в кавычки “.
Компиляция должна быть реализована в определенном порядке. Это связано с взаимозависимостью деклараций лексем. Поэтому в нашем случае, необходимо выполнить команды в следующем порядке:
После чего получим файлы basic_lexer.cmo и basic_parser.cmo, которые можно использовать в нашей программе.
Теперь, у нас есть весь необходимый арсенал, для того чтобы переделать программу.
Удалим все типы и функции параграфов “лексический анализ” (стр. ??) и “синтаксический анализ” (стр. ??) для программы Бэйсик. Также в функции one_command заменим выражение:
на
Заметьте, что необходимо поместить в конце линии символ конца '
n',
который был удален функцией input_line. Это необходимо, потому что
данный символ используется для указания конца командной линии
(Leol).
В данной главе были описаны различные средства лексического и синтаксического анализа Objective CAML. По порядку описания:
При помощи инструментов ocamllex и ocamlyacc мы переделали синтаксический анализ Бэйсика, который проще поддерживать, чем анализатор представленный на стр. ??.