Как я должен идти о создании простого парсера LR?

Question

Я пытаюсь создать простой анализатор LR для типа файла шаблона (конфигурации), который будет использоваться для генерации некоторых других файлов. Я читал и читал о парсерах LR, но я просто не могу этого понять! Я понимаю, что есть стек разбора, стек состояний и таблица разбора. Токены считываются в стек синтаксического анализа, и когда правило сопоставляется, токены смещаются или уменьшаются в зависимости от таблицы синтаксического анализа. Это продолжается рекурсивно до тех пор, пока все токены не будут сокращены, а затем синтаксический анализ завершен.

Проблема в том, что я не знаю, как сгенерировать таблицу разбора. Я прочитал довольно много описаний, но язык технический, и я просто не понимаю его. Может кто-нибудь сказать мне, как я поступил бы по этому поводу?

Кроме того, как я могу хранить вещи, как правила моей грамматики?

http://codepad.org/oRjnKacH - это пример файла, который я пытаюсь проанализировать, пытаясь найти грамматику для ее языка.

Я никогда не делал этого раньше, поэтому просто ищу совета, спасибо.

Answer 1

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

Основная причина использования парсера, управляемого таблицами, заключается в том, что он позволяет вам написать (довольно) небольшой объем кода, который манипулирует таблицей и т. Д., Который почти полностью универсален (то есть работает для любого парсера). Затем вы кодируете все, что касается конкретной грамматики, в форму, которой легко управлять компьютером (т. Е. Некоторые таблицы).

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

Например, вы обычно начинаете с создания NFA, которая представляет собой большую таблицу - обычно одна строка для каждого состояния анализатора и один столбец для каждого возможного. В каждой ячейке вы кодируете следующее состояние, которое необходимо ввести при запуске в этом состоянии, а затем получаете этот вход. Большинство из этих переходов в основном пустые (то есть они просто говорят, что ввод не разрешен, когда вы находитесь в этом состоянии).

Затем вы проходите через все это и следуете некоторым довольно простым правилам, чтобы собрать наборы состояний NFA вместе, чтобы стать состоянием в DFA. Правила достаточно просты, так что их довольно легко запрограммировать в компьютер, но вы должны повторить их для каждой ячейки в таблице NFA и вести практически идеальный учет, чтобы получить DFA, который работает правильно .

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

Answer 2

нужно прочитать про ANTLR

Answer 3

Классическим решением является комбинация lex / yacc:

http://dinosaur.compilertools.net/yacc/index.html

Или, как их называет GNU - flex / bison.

редактирование:

В Perl есть Parse :: RecDescent, который является анализатором рекурсивного спуска, но он может работать лучше для простой работы.

Answer 4

Я посмотрел на определение вашего файлового формата, хотя мне не хватает некоторого контекста, почему вам нужен именно LR-парсер, моей первой мыслью было почему бы не использовать существующие форматы, такие как xml или json. Переход по маршруту parsergenerator обычно сопряжен с высокими начальными затратами, которые не окупятся за простые данные, которые вы хотите проанализировать.

Как сказал Пол, lex / yacc - это вариант, вы также можете взглянуть на Boost :: Spirit .

Я не работал ни с одним, год назад написал гораздо больший парсер, использующий QLALR людьми из Qt / Nokia. Когда я исследовал синтаксические анализаторы, этот, хотя и очень недокументированный, имел наименьшую площадь для запуска (только 1 инструмент), но он не поддерживает лексический анализ. IIRC Я не мог понять поддержку C ++ в ANTLR в то время.

Вид на 10 000 миль. В общем, вы смотрите на два компонента - лексер, который принимает входные символы и превращает их в токены высшего порядка. Для работы с токенами ваше грамматическое описание будет содержать правила, обычно вы включаете в них некоторый код, этот код будет выполняться при совпадении правила. Генератор компилятора (например, yacc) возьмет ваше описание правил и код и превратит его в скомпилированный код. Если вы не делаете это вручную, вы не будете сами манипулировать столами.

Answer 5

Ну, вы не можете понять это как

"Функция A1 выполняет f для объекта B, затем функция A2 выполняет g для D и т. Д."

это больше похоже на

"Функция A выполняет действие {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o или p или no-op} и сдвигает / уменьшает определенное количество объектов {1-1567} в заголовке стека типа {B, C, D, E, F или G} и содержащих его объектов до N уровней, которые могут иметь типы {H, I, J, K или L и т.д.} в определенных комбинациях согласно списку правил "

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

Вы МОЖЕТЕ написать это с нуля. Вы также можете покрасить стены кисточкой для ресниц. Вы можете интерпретировать таблицу данных во время выполнения. Вы также можете поставить Sleep (1000); операторы в вашем коде каждая вторая строка. Не то чтобы я тоже пробовал.

Компиляторы сложны. Отсюда генераторы компилятора.

EDIT

Вы пытаетесь определить токены с точки зрения содержимого в самом файле.

Я предполагаю, что причина, по которой вы «не хотите использовать регулярные выражения», заключается в том, что вы хотите иметь возможность доступа к информации о номере строки для различных токенов в пределах блока текста, а не только для блока текста в целом. Если номера строк для каждого слова не нужны, и целые блоки помещаются в память, я был бы склонен смоделировать весь блок в скобках в качестве токена, поскольку это может увеличить скорость обработки. В любом случае вам понадобится пользовательская функция yylex. Начните с создания файла с lex с фиксированными маркерами "[" и "]" для начала и конца содержимого, затем заморозьте его и измените его, чтобы получать обновленные данные о том, какие маркеры искать из кода yacc.