Может ли это быть проанализировано парсером LALR(1)?

Question

Я пишу парсер в Bison для языка, который имеет следующие конструкции, среди прочего:

• Само отправка: [identifierarguments]
• рассылка: [expression, identifierarguments]
• нарезка строк: expression[expression,expression] - похоже на Python.

arguments список выражений через запятую, который также может быть пустым Все вышеперечисленное тоже является выражением. Моя проблема в том, что я не уверен, как разобрать оба [method [other_method]] а также [someString[idx1, idx2].toInt] или если это возможно сделать с помощью парсера LALR(1).

Чтобы быть более точным, давайте возьмем следующий пример: [a[b]] (вызов метода a с результатом метода b). Когда он достигнет состояния [a, [b]] (взгляд второй [), он не будет знать, следует ли уменьшить a (который уже был сокращен до identifier) чтобы expression потому что что-то вроде a[b,c] может последовать (который сам может быть уменьшен до expression и продолжить со второй конструкции сверху) или оставить ее identifier (и сдвинуть его), потому что список arguments будет следовать (например, [b] в этом случае).

Этот конфликт сдвига / уменьшения вызван тем, как я выразил эту грамматику, или невозможно проанализировать все эти конструкции с помощью анализатора LALR(1)?

И, более общий вопрос, как можно доказать, что язык является / не разбирается парсером определенного типа?

Answer 1

Предполагая, что ваша грамматика однозначна (а та часть, которую вы описываете, кажется), лучше всего указать %glr-parser, Поскольку в большинстве случаев правильный анализ будет выполняться только после нескольких токенов, накладные расходы не должны быть заметны, и преимущество заключается в том, что вам не нужно усложнять ни грамматику, ни конструкцию AST.

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

Доказать, что язык не является LR(1), было бы сложно, и я подозреваю, что это было бы невозможно, потому что язык, вероятно, распознаваем с помощью анализатора LALR(1). (Невозможно сказать, не видя всей грамматики, хотя.) Но синтаксический анализ (вне теории CS) должен создать правильное дерево разбора, чтобы быть полезным, и вид модификаций, требуемых для создания грамматики LR, также изменит AST, требующий исправления после разбора. Трудно создать правильную пружину AST из-за разницы в приоритетности

a[b[c],d]

а также

[a[b[c],d]]

В первом (подмножестве) случае b привязывается к списку аргументов [c] и запятая имеет меньший приоритет; в конце, b[c] а также d братья и сестры дети среза. Во втором случае (вызов метода) запятая является частью списка аргументов и связывается более тесно, чем приложение метода; b, [c] а также d братья и сестры в методе приложения. Но вы не можете определить форму дерева разбора до сколь угодно длинного ввода (так как d может быть любое выражение).

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

Небольшой пункт для дальнейшего использования: CFG - это не просто инструмент программирования; они также служат для четкой передачи рассматриваемой грамматики. Нирмально, если вы хотите описать свой язык, вам лучше использовать четкий CFG, чем пытаться описать неформально. Конечно, значимые нетерминальные имена помогут, и несколько примеров никогда не повредят, но суть грамматики заключается в формальном описании и опущении, что затрудняет "помощь" для других.