Как преобразовать парсер PEG в двусмысленный?

Question

Насколько я понимаю, большинство языков не содержат контекста с некоторыми исключениями. Например, a * b может стоять за type * pointer_declaration или умножать на C++. Что происходит, зависит от контекста, значения первого идентификатора. Другим примером является name производство в VHDL

enum_literal ::= char_literal | identifer 
physical_literal ::= [num] unit_identifier 
func_call ::= func_identifier [parenthized_args] 
array_indexing ::= arr_name (index_expr) 
name ::= func_call | physical_literal | enum_litral | array_indexing 

Вы видите, что синтаксические формы различны, но они могут совпадать, если дополнительные параметры опущены, как f, это подставка для func_call, physical_literal, как 1 метр с дополнительным количество 1 подразумеваемый или enum_literal.

Говоря о дизайнерах плагинов Scala, я получил образование, чтобы знать, что вы строите AST, чтобы переоценить его при изменении зависимостей. Нет необходимости повторно разбирать файл, если у вас есть его AST. AST также стоит отображать содержимое файла. Но AST недействителен, если грамматика является контекстно-зависимой (предположим, что f была функцией, определенной в другом файле, но позже пользователь перепрофилировал ее в enum literal или undefined). AST изменяет в этом случае. AST изменяется при каждом изменении зависимостей. Другой вариант, который я прошу оценить и дать мне знать, как это сделать, заключается в создании неоднозначного АСТ.

Насколько я знаю, комбинаторы парсеров PEG kind. They hide the ambiguity by returning you the first matched production и f будут соответствовать вызову функции, потому что это первая альтернатива в моей грамматике. Я прошу комбинатора, что вместо того, чтобы вернуться к первому успеху, он переходит к следующей альтернативе. В конце концов, он вернет мне список всех подходящих альтернатив. Это вернет мне двусмысленность.

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

После того, как неоднозначный узел разобран и неоднозначность результатов возвращается, я хотел бы, чтобы синтаксический анализатор сходился, потому что я хотел бы продолжить синтаксический анализ за пределами name, и я не хочу анализировать до конца файла после каждой двусмысленности. Ситуация осложняется такими ситуациями, как f(10), которая может быть вызовом функции с единственным аргументом или вызовом функции с нулевым значением, которые возвращают массив, который затем индексируется. Таким образом, f (10) может соответствовать названию двумя способами: либо func_call напрямую, либо рекурсивно, как arr_indexing -> name ~ (expr). Таким образом, это не будет двусмысленно, как несколько параллельных правил, таких как fcall | literal. Некоторые ветви могут быть длиннее 1 парсера до повторного схождения, например fcall ~ (expr) | fcall.

Как бы вы решили его решить? Можно ли добавить неоднозначный комбинатор в PEG?

Answer 1

Сначала вы утверждаете, что «большинство языков не являются контекстуальными за некоторыми исключениями», это не совсем так. При разработке компьютерного языка мы в основном стараемся сохранить его как можно более свободным от контекста, поскольку CFG являются стандартом де-факто для этого. Это облегчит большую работу. Однако это не всегда возможно, и многие ^[?] языков зависят от фазы семантического анализа, чтобы устранить любые возможные двусмысленности.

Комбинированные компоненты обычно не используют формальную модель; ПГС, с другой стороны, являются формализмом для грамматик, как и CFG. В последнее десятилетие несколько человек решили использовать ПЭГ над CFG из-за двух фактов: ПЭГ, по дизайну, недвусмысленны, и они всегда могут анализироваться в линейном времени. Библиотека комментаторов синтаксического анализатора может использовать ПЭГ как основной формализм, но может также использовать CFG или даже не использовать.

PEGs привлекательны для разработки компьютерных языков, потому что мы обычно не хотим обрабатывать двусмысленности, что трудно (или даже невозможно) избежать при использовании CFG. И из-за этого они могут анализироваться O (n) раз, используя динамическое программирование (так называемый парсер parrat). It's not simple to "add ambiguities to them" for a few reasons, most importantly because the language they recognize depend on the fact that the options are deterministic, which is used for example when checking for lookahead. Это не так просто, как «просто выбрать первый выбор». Например, вы могли бы определить PEG:

S = "a" S "a"/"aa" 

Какие только разобрать последовательности N «в», где N является степенью 2. Таким образом, он распознает последовательность 2, 4, 8, 16, 32, 64 и т. Д., Буква «a». Добавляя неоднозначность, как CFG, вы бы узнали любое четное число «a» (2, 4, 6, 8, 10 и т. Д.), , которое является другим языком.

Чтобы ответить на ваш вопрос,

Как бы вы о ее решении? Можно ли добавить неоднозначный комбинатор в PEG?

Прежде всего, я должен сказать, что это, вероятно, не очень хорошая идея. Если вы хотите сохранить двусмысленность в AST, вы, скорее всего, должны использовать парсер CFG.

Можно, например, сделать парсер для полиэтиленгликоль, который похож на анализатор для boolean grammars, но тогда нашего асимптотическое время синтаксического анализа будет расти из О (п) О (п), сохраняя все альтернативы живыми сохраняя тот же язык. И мы фактически теряем обе хорошие вещи о ПЭГе сразу.

Другим способом было бы хранить парсер парсер в памяти и передавать его таблицу для обработки семантики из АСТ. Не очень хорошая идея, так как это будет означать большой объем памяти.

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