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

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

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

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

править:

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

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

Я предполагаю, что одностороннее исключение Microsoft stdlib также включает передачу char * в std:: copy .

Я полагаю, что некоторые его части имеют некоторые достоинства ( fopen () затрагивает глобальные ERRNO , так что это не потоковая безопасность), но другие решения не кажутся очень рациональными. (Я бы сказал, что они взяли слишком большую часть на все это. Должны быть уровни, такие как non-threadsafe, non-checkable и т.д.)

Я бы рекомендовал прочитать MS-doc по каждой функции, если вы хотите знать проблемы о каждом случае, хотя это довольно хорошо документировано, почему каждая функция имеет это предупреждение, и причина обычно отличается в каждом случае.

Вы правы, что расширение наступает перед боксом, который, в свою очередь, наступает перед var-args.

Но вы, похоже, рассматриваете первый метод как callMethod (Integer i) , а не callMethod (Integer... i) . Поскольку оба метода используют var-args, существует приоритет tie . То есть ни один не соответствует критериям одного бокса, но оба соответствуют критериям var-args.

Помните, что это незаконно, чтобы расширить, затем коробка (хотя я сделал некоторые исследования, прежде чем опубликовать этот ответ и обнаружил, что это IS законно, чтобы сделать коробку, а затем расширить). Аналогично, вы не получите коробку, то var-args поведение; компилятор пропускает прямо на шаг var-args и видит два метода, которые принимают var-args.

EDIT: Я должен пояснить, что вы получите поведение box-then-var-args, если нет двусмысленности. Другими словами, если существует только один callMethod () , и требуется Integer... i , вы получите « Обертка ».

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

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

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

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

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

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

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

"Функция 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.

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

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

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

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