Комбинированные анализаторы, разделяющие грамматику и конструкцию AST

Ответ 1

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

При создании парсера я использую два разных дерева синтаксиса:

• Конкретное дерево синтаксиса или CST: это текстовая форма текста и имеет соответствие 1:1 с текстом. Все, что появляется в тексте, также появится в КНТ.

• Абстрактное синтаксическое дерево или AST: это необязательно имеет соответствие 1:1 с текстом, поскольку ненужные текстовые данные (такие как фигурные скобки, пунктуация и т.д.) были удалены и не появляются в AST.

Таким образом, получение из входного текста в AST имеет два шага: первый шаг - проанализировать входную строку в CST; второй шаг - преобразовать КНТ в АСТ, отбрасывая ненужные детали.

• String -> CST Здесь я использую комбинаторы парсеров. Я не делаю никаких манипуляций с древовидной структурой на этом этапе. Структура CST полностью определяется используемыми комбинаторами. Каждый комбинатор создает поддеревье определенной формы, которое я никогда не изменяю на этом этапе. Никаких действий, связанных с комбинаторами, не существует, поэтому определение грамматики является чистым и не содержит никакой информации об AST.

• CST -> AST Здесь я массирую дерево синтаксического разбора, извлекая важный материал, игнорируя остальные. Кроме того, я часто выполняю контекстно-зависимые проверки (например: проверка того, что определение функции не содержит повторяющихся имен параметров), сохраняя эти данные вне фактического этапа синтаксического анализа.

Пример: здесь JSON-анализатор, который я построил с помощью этого метода:

• общие комбинаторы парсеров

• комбинатор для создания узлов CST

• фактический парсер JSON, который создает CST

Ответ 2

Ну, в принципе, все ваши трансформации АСТ имеют определенный тип. Вы можете определить их все в другом месте и использовать их из определения грамматики. Это прояснит ситуацию. Кроме того, вы можете определить свои определения грамматики как функции "пропустить по имени", которые оцениваются по вызову, а затем использовать их из вашего преобразования.

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

Ответ 3

Было бы здорово иметь грамматику, близкую к человеку, прямо "создающую" источник парсера...

Интересно, что такое грамматика, близкая к человеку?

Как отделить определение грамматики от преобразования в узлах AST?

У вас есть рукописный паттерн Packrat.

Я мог ошибаться, но я понимаю этот вопрос как запрос использовать независимое определение грамматики для создания парсера. Затем используйте этот синтаксический анализатор, чтобы получить синтаксическое дерево анализируемого источника.

Итак, грамматик может быть грамматикой EBNF или PEG или CFG или "вашей собственной", верно?

В любом случае...

• Давайте начнем с "отдельного определения грамматики", например. EBNF.
• Затем вам понадобится парсер для грамматики, например. a EBNFParser.
• Анализ грамматики с результатами парсера является внутренней структурой этой грамматики: синтаксическим деревом.

• Учитывая синтаксическое дерево для допустимой грамматики, вы можете вернуть список ассоциаций с ключами (как метаидентификаторы) и приложить к ним правила грамматики.

  foreach grammar key add matching grammar rule

• Это означает, что вам нужно выбрать правило грамматики, идентифицированное с помощью RuleName, и добавить его правило в "Constructed Parser".

• В конце: у вас есть "Constructed Parser", собранный из отдельных "правил грамматики", способных анализировать источник, определенный данной грамматикой.

• Разбор источника, дает вам дерево синтаксиса для источника.

Pass 1

Grammar -> GrammarParser -> GrammarTree -> GrammarRules -> ConstructedParserForGrammar

Pass 2

Source -> ConstructedParserForGrammar -> Syntax Tree -> Transformations...

Другими словами: его довольно головоломка для перехода от BNF к автоматически созданному парсеру Packrat.

Ответ 4

Поскольку это commit

https://github.com/scala/scala-parser-combinators/commit/33792d3380791ddafb41760604857d2fc43e54e1

Опубликовать здесь https://enear.github.io/2016/03/31/parser-combinators/ lexes в конкретное дерево синтаксиса сначала (lexing), а затем впоследствии выдает AST.

Я оставляю его здесь, потому что он добавляет пример принятому ответу.