Как определить, является ли грамматика LR (п), LL (п)

Question

Для языка, который не LL(1) или LR(1), как можно попытаться выяснить, если какое-то число n существует такое, что грамматика может быть LL(n) или LR(n)?

Вы проверяете, соответствует ли грамматика LR(0), канонической коллекции LR(0). Тогда, если предположить, что это не LR(0), вы можете проверить, является ли это LR(1), введя символ lookahead. Мои простые рассуждения говорят мне, что для проверки того, является ли это LR(2) или нет, вы, вероятно, должны заставить lookahead содержать следующие два символа вместо одного. Для LR(3) вам необходимо учитывать три символа и т. Д.

Даже если это так, несмотря на то, что я сомневаюсь в этом, я изо всех сил пытаюсь понять, как можно попытаться определить (или даже дать понять) n, или его отсутствие, для которых конкретная грамматика может быть LR(n) и/или LL(n), без предварительной инкрементности от арбирования LR(m) вверх.

Answer 1

1. Если язык является LR (к) для некоторого к > 1, то LR (1). (Конечно, это неверно для грамматики). То есть, если у вас есть грамматика LR (k) для языка, вы можете механически построить грамматику LR (1), которая позволяет восстановить исходное дерево разбора , Это не относится к LL (k); LL (k) языки являются строгим подмножеством LL (k +1) языков.

2. тест вы предлагаете действительно позволит вам решить, будет ли грамматика является LR (к) для некоторого заданного к (или LL (к)). К сожалению, нет способа узнать наименьшую возможную величину k, кроме того, что вы предлагаете, и нет никакой гарантии, что поиск когда-либо закончится.

3. Хотя проблема сложна (или невозможна) в общем случае, ее часто можно ответить на конкретные грамматики, рассмотрев возможные действительные преемники состояния грамматики, которые проявляют конфликты.

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

Большой класс грамматик, где это произойдет, - это набор неоднозначных грамматик. Двусмысленная грамматика не может быть LR (k) (или LL (k)) для любого k. Опять же, вопрос о том, является ли грамматика неоднозначным, не разрешима, но существуют эффективные эвристики, некоторые из которых включены в коммерческие продукты.

Опять же, часто бывает легко найти двусмысленности в реальных граммах, либо путем визуального осмотра (как указано выше), либо путем подачи большого количества достоверных текстов в парсер GLR (например, тот, который был получен зубром), до тех пор, пока сообщается о двусмысленности.(В качестве альтернативы вы можете перечислить действительные тексты из грамматики с помощью алгоритма прямой перемотки вперед и посмотреть, будет ли текст дважды отображаться в перечислении.)

Вот несколько возможных вопросов SO, иллюстрирующих методы анализа. Я уверен, что их больше.

A yacc shift/reduce conflict on an unambiguous grammar

Bison reduce/reduce situation

yacc shift-reduce for ambiguous lambda syntax

How to understand and fix conflicts in PLY