Комбинаторы синтаксического анализатора, разделение грамматики и построение AST

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

Синтаксис указан здесь: https://github.com/hejfelix/Frase/blob/master/src/main/scala/it/vigtig/lambda/ParserLike.scala

Есть одна вещь, которую я не смог решить с помощью реализации: как отделить определение грамматики от преобразования в узлы AST?

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

Как разделить грамматический и специфичный для AST код?


scala abstract-syntax-tree grammar parser-combinators
person Felix    schedule 31.10.2015    source источник

Ответы (4)


arrow_upward
11
arrow_downward

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

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

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

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

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

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

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

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

person Matt Fenwick    schedule 05.11.2015
comment
Это звучит в точности так, как я хочу, но я не уверен, как вы добьетесь 1. У вас есть примеры кода или не могли бы вы пояснить, как бы вы изменили мой код по ссылке в вопросе? - person Felix; 06.11.2015
comment
@Felix - Я добавил пример (к сожалению, он на Javascript, а не на Scala, но принцип тот же). Пожалуйста, дайте мне знать, если я должен объяснить это подробнее - я счастлив сделать это! - person Matt Fenwick; 07.11.2015
comment
@Felix - чтобы сделать это в вашем коде, я бы рекомендовал 1. удалить такие действия, как ^^ { case id ~ _ ~ term => Abstr(id, term) } из парсера, 2. создать новый модуль для преобразования CST в AST. - person Matt Fenwick; 07.11.2015
comment
Не нужно ли тогда явно указывать типы, чтобы получить PackratParsers? - person Felix; 07.11.2015
comment
@ Феликс, это отличный момент, и я еще не думал о нем. Мне нужно подумать об этом еще немного - спасибо, что указали на это! - person Matt Fenwick; 09.11.2015

arrow_upward
2
arrow_downward

Ну, в принципе, все ваши AST-преобразования имеют определенный тип. Вы можете определить их где угодно и использовать их из своего грамматического определения. Это несколько прояснило бы ситуацию. В качестве альтернативы вы можете определить свои грамматические определения как функции «передачи по имени», которые оцениваются при вызове, а затем использовать их из вашего преобразования.

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

person Daniel Langdon    schedule 02.11.2015
comment
Это решение, однако, заставляет определение грамматики явно поддерживать различные AST-преобразования. Как вы думаете, можно ли сделать что-то подобное, предоставляя грамматор без каких-либо преобразований, т.е. все парсеры должны быть просто Parser [String]? - person Felix; 03.11.2015
comment
Зависит от того, какие ссылки какие, как я уже говорил. В обратном направлении такой зависимости нет. Даже в первом направлении, если вы можете сохранить универсальные типы, вы можете использовать трейт, который определяет преобразования, не указывая их (пока). Хотя я не являюсь экспертом в этой области, в прошлый раз, когда я сделал что-то подобное, я использовал LEX & YACC, чтобы сохранить эти части разделяются. С другой стороны, вам придется иметь дело со стандартными функциями языка Scala ... - person Daniel Langdon; 03.11.2015

arrow_upward
1
arrow_downward

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

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

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

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

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

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

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

  • Начнем с отдельного определения грамматики, например EBNF.

  • Тогда вам понадобится синтаксический анализатор грамматики, например EBNFParser.

  • Анализ грамматики с помощью результатов этого синтаксического анализатора представляет собой внутреннюю структуру этой грамматики: дерево синтаксиса.

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

    foreach grammar key add matching grammar rule

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

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

  • Анализируя исходный код, вы получаете синтаксическое дерево для источника.

Пройти 1

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

Пройти 2

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

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

person Jens A. Koch    schedule 06.11.2015

arrow_upward
0
arrow_downward

Поскольку этот коммит

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

Комбинаторы парсеров ссылаются на сообщение, которое точно решает мою проблему. Это, имхо, самый точный ответ на мой вопрос.

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

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

person Felix    schedule 23.03.2017