LR (л) LR (1) преобразование грамматики

Question

Я смущен следующим quote из Википедии:

Другими словами, если язык был достаточно разумным, чтобы позволить эффективный один проход парсера он может быть описан грамматикой LR (k). И эта грамматика всегда может быть механически преобразована в эквивалентную (но большую) грамматику LR (1) в . Таким образом, метод парсинга LR (1) был, в теории, , достаточно мощным, чтобы обрабатывать любой разумный язык. В практики, естественные грамматики для многих языков программирования близко к LR (1). [Править]

Это означает, что генератор синтаксических анализаторов, как bison, является очень мощным (так как он может обрабатывать LR(k) грамматики), если вы можете преобразовать грамматику LR(k) в грамматику LR(1). Есть ли некоторые примеры этого или рецепт того, как это сделать? Я хотел бы знать об этом, так как у меня конфликт смены/сокращения в моей грамматике, но я думаю, что это потому, что это грамматика LR(2) и хотел бы преобразовать ее в грамматику LR(1). Боковой вопрос: C++ необоснованный язык, так как я читал, что bison -генерированные парсеры не могут его разобрать.

Answer 1

Для ссылки на алгоритме общего назначения, чтобы найти заслон LR(1) грамматику в LR(k) грамматики см Real-world LR(k > 1) grammars?

Алгоритм общего назначения производит довольно большие грамматики; на самом деле, я уверен, что получившийся КПК такого же размера, как и у LR(k) КПК. Однако, в частности, можно найти более простые решения. При этом применяется общий принцип: вам необходимо отложить решение о сдвиге/сокращении, безоговорочно переместившись до тех пор, пока решение не будет принято с помощью одного контрольного токена.

Один пример: Is C#'s lambda expression grammar LALR(1)?

Не зная более подробную информацию о вашей грамматике, я не могу помочь больше.

Что касается C++, то вещи, из-за которых сложно разобрать, являются препроцессор и некоторые угловые случаи при разборах шаблонов (и лексинга). Тот факт, что разбор выражения зависит от «вида» (а не типа) символа (в контексте, в котором происходит символ), делает точный синтаксический анализ с бизоном сложным. [1] «Необоснованный» - это оценочное суждение, которое мне не нравится; конечно, поддержка инструмента (например, точные синтаксические колоризаторы и вкладчики-дополнения) была бы простой с другой грамматикой, но доказательством является то, что не так сложно писать (или даже читать) хороший код на C++.

---

Примечание:

[1] Классический сложно синтаксического анализ, который также относится к C, является (a)*b, который представляет собой отливку из разыменования, если a представляет собой тип, и в противном случае умножение. Если бы вы записали его в контексте: c/(a)*b, было бы ясно, что AST не может быть сконструирован, не зная, является ли это литой или продуктом, поскольку это влияет на форму АСТ,

Более C++-специфичный выпуск: x<y>(z) (или x<y<z>>(3)), которые анализируют (и, возможно, токенизировать) по-разному в зависимости от того, является ли x шаблоном или нет.