Разбор Shift-разрешения - вопросы

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

Я опишу свое решение (если оно верное, я думаю, что оно может помочь другим людям, пытающимся понять технику), а затем задам дополнительные вопросы. Чтобы избежать недопонимания, я собираюсь использовать следующие стандартные обозначения: , , , и, как в статье, для обозначения правила номер . Тем не менее, я, вероятно, буду использовать другие имена для концепций, чем оригинальная статья.$a, b, c, ... \in T$$A, B, C, ... \in N$$... X, Y, Z \in N \cup T$$\alpha, \beta, \gamma, ... \in \{N \cup T\}^*$$A \xrightarrow{i} \omega$$i$

Также в описании используется отношение эквивалентности .$\kappa_0$

строительство

Внутри автомата разбора есть два вида элементов: простые элементы LR (0) в форме которые я называю элементами сдвига, и элементы в форме который я называю разрешением предметов ; они говорят синтаксическому анализатору выдвинуть символов обратно во входной поток и затем уменьшить на число правил первый символ .$A \xrightarrow{i} \alpha \bullet \beta$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$n$$m$$\beta$

Грамматика дополняется правилом а построение начинается с элемента сдвига в исходном состоянии.$S' \xrightarrow{0} S \$$$S' \xrightarrow{0} \bullet S \$$

Теперь, чтобы построить автомат, определитесь между этими альтернативами для каждого элемента в состоянии :$q$

1. Если элемент является сдвиговым элементом , в автомате произойдет переход , где - первый символ .$A \xrightarrow{i} \alpha \bullet \beta$$q \xrightarrow{X} q'$$X$$\beta$

2. Если элемент является законченным элементом сдвига , добавьте элемент разрешения для каждого правила .$A \xrightarrow{i} \omega \bullet$$B \xrightarrow{j} \alpha A \bullet \beta, i, 0$$B \xrightarrow{j} \alpha A \beta$

3. Если элемент является разрешающим элементом , пусть будет первым символом . Если , добавьте элемент смены для каждого правила . Если другие элементы, кроме имеют качестве точки обзора, добавьте переход к автомату. Каждый элемент разрешения в приведет к элементу разрешения в$A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$\beta$$X \in N$$X \xrightarrow{j} \bullet \omega$$X \xrightarrow{j} \omega$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$q \xrightarrow{X} q'$$C \xrightarrow{i} \alpha \bullet X \beta, m, n$$q$$C \xrightarrow{i} \alpha X \bullet \beta, m, n + 1$$q'$ .

4. Если элемент является разрешающим элементом он не будет содержать никакой информации о перспективах и может быть отброшен, но сначала добавьте разрешающий элемент для каждого правила .$A \xrightarrow{i} \omega \bullet, m, n$$B \xrightarrow{j} \alpha A \bullet \beta, m, n$$B \xrightarrow{j} \alpha A \beta$

Это, конечно, просто набросок; на самом деле, закрытие состояния должно быть сначала рассчитано, и только тогда мы можем иметь дело с переходами / сдвигами и разрешениями.

Преобразование автомата в таблицу разбора с разрешением смены тривиально; просто, как незначительное изменение, авторы статьи интерпретируют разрешение как действие принятия. Учитывая полученный автомат, я посчитал более удобным просто рассматривать сдвиг как действие принятия.$r_{0,0}$$\$$

Вопросов

Во-первых, очевидно, является ли описанный выше процесс правильным.

Второй - об отношениях эквивалентности. Я могу только догадываться, что отношение эквивалентности - это то, что отвечает за решение, какие элементы разрешения вводятся, когда виден законченный элемент смены. кажется, приводит к тому, что поразительно похожи на наборы синтаксических анализаторов LSLR. В статье описывается «более точное отношение эквивалентности» на стр. 11; Есть ли способ интерпретировать это отношение в интуитивно понятных терминах? Известны ли другие отношения?$\kappa$$\kappa_0$$FOLLOW_{LM}$

И последнее - о разрешении конфликтов. В статье хорошо описывается, что является неадекватностью в автомате с разрешением сдвига; Есть ли способ устранения этих недостатков, аналогичный способам разрешения конфликтов в традиционном парсере LR? Может ли что-то вроде разрешения конфликта в стиле yacc посредством приоритета и ассоциативности быть реализовано в генераторе синтаксического анализатора ShRe?

Спасибо, если вы прочитали все это, и любые ответы будут с благодарностью :)

Проверьте, обсуждается ли это в энциклопедии D. Grune, CJH Jacobs, «Техника синтаксического анализа: практическое руководство» (Spinger, 2008). Если нет, возможно, это достаточно похоже на обсуждаемую технику.