LR (k) парсеры, с k бесконечными, не ограниченные детерминированными языками без контекста

Question

Может ли теоретический синтаксический анализатор LR с бесконечным вниманием анализировать (однозначные) языки, которые можно описать с помощью контекстно-свободной грамматики?

Обычно парсеры LR (k) ограничены детерминированными контекстно-свободными языками. Я думаю, это означает, что всегда должно быть ровно одно правило грамматики, которое может быть применено в настоящее время. Это означает, что в текущем контексте предварительного просмотра допускается не более одного возможного способа синтаксического анализа. В книге «Шаблоны языковой реализации» говорится, что «... синтаксический анализатор недетерминирован - он не может определить, какую альтернативу выбрать». если опережающие установки перекрываются. Напротив, недетерминированный синтаксический анализатор просто выбирает один путь, если существует несколько альтернатив, а затем возвращается к точке принятия решения и выбирает следующую альтернативу, если в определенный момент невозможно продолжить выполнение ранее принятого решения.

Где бы я ни читал определения синтаксических анализаторов LR (k) (например, в Википедии или в Книге Дракона), я всегда читаю что-то вроде: «k - количество жетонов ожидания» или случаи, когда «k> 1», но никогда, если k может быть бесконечным. Разве бесконечный взгляд не будет таким же, как пробовать все альтернативы, пока один не преуспеет?

Может ли быть так, что k считается конечным, чтобы (неявно) отличить LR (k) -парсеры от недетерминированных парсеров?

Answer 1

Вы затрагиваете несколько вопросов, на которые сложно ответить в краткой форме.Тем не менее я попытаюсь.

Прежде всего, что такое "бесконечный взгляд вперед"?Нет книги, описывающей такой парсер.Если у вас есть четкое представление о том, что это такое, вам нужно сначала описать это.Только после этого мы можем обсудить эту тему.В настоящее время теория синтаксического анализа обсуждает только грамматики LR (k), где k конечно.

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

Это неправильно.LR (k) грамматики могут иметь «грамматические конфликты».Книга Дракона кратко упоминает их, не вдаваясь в подробности.«Грамматика может иметь конфликты» означает, что некоторые грамматики не имеют конфликтов, в то время как все остальные грамматики имеют их.Если в грамматике нет конфликтов, то ВСЕГДА существует только одно правило, и ситуация относительно проста.

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

В книге "Шаблоны реализации языка" говорится, что "... синтаксический анализатор недетерминирован - он не может определить, какую альтернативу выбрать. "

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

Практически используются только 2 стратегии разрешения конфликтов.Первый - это разрешение конфликтов в обработчике обратного вызова.Обработчик обратного вызова - обычный код.Программист, который пишет это, проверяет все, что он хочет, так, как он хочет.Этот код только возвращает результат - какое действие предпринять.Для парсера сверху этот обработчик обратного вызова является черным ящиком.Здесь нет теории.

Второй подход называется «возвращением».Идея очень проста.Мы не знаем, куда идти.Хорошо, давайте попробуем все возможные альтернативы.В этом случае все варианты перепробованы.Здесь нет ничего недетерминированного.Существует несколько различных вариантов возврата.

Если этого недостаточно, я могу написать немного больше.

Answer 2

недетерминизм означает, что для получения правильного результата (s!) Конечный автомат считывает токен и затем имеет N> 1 следующих состояний.Вы можете распознать недетерминированный FSM, если узел имеет более одного исходящего ребра с одинаковой меткой.Обратите внимание, что не каждая ветвь должна быть действительной, но FSM не может выбрать только одну.На практике вы можете разветвиться здесь, что приведет к N конечным автоматам, или вы можете полностью попробовать ветвь, а затем возвращаться и пробовать следующую, пока не будет проверен каждый исходящий перенос состояния.