Я знаком с синтаксическими анализаторами LR(1), которые обычно преподаются на традиционных курсах компиляторов. Я знаю, что парсеры LR(2) существуют, но я никогда не видел ни одного сконструированного ранее.
Как устроен парсер LR(2)? Чем он отличается от парсера LR(1)?
Во многих отношениях парсер LR(2) работает аналогично парсеру LR(1). Он отслеживает самое правое порождение в обратном порядке, поддерживает стек, выполняет операции сдвига и сокращения в стеке, имеет состояния, состоящие из наборов элементов LR и т. д. Однако есть несколько основных отличий:
Чтобы объяснить, как это работает, давайте возьмем пример LR(2)-грамматики. (Эта грамматика получена из грамматики, упомянутой в отличном ответе @rici на этот предыдущий вопрос).
S → RS | R
R → абТ
T → aT | c | ε
Чтобы построить наш синтаксический анализатор LR(2) для этой грамматики, мы начнем, как обычно, с дополнения грамматики произведением формы S' → S:
S' → S
S → RS | R
R → абТ
T → aT | c | ε
Теперь приступим к созданию конфигурационных наборов. Начнем, как и в парсере LR(1), с продукции S' → S. Это показано здесь:
(1)
S' -> .S [$$]
Обратите внимание, что опережающий просмотр равен $$, что указывает на две копии маркера конца потока. В традиционном синтаксическом анализаторе LR(1) (или SLR(1), или LALR(1)) у нас был бы опережающий просмотр $, всего одна копия маркера конца потока.
Теперь мы начинаем расширять другие элементы в этом конфигурационном наборе. Так как у нас есть производства S → RS и S → R, мы добавляем эти элементы:
(1)
S' -> .S [$$]
S -> .R [$$] // New
S -> .RS [$$] // New
Теперь давайте начнем следить за тем, что будет дальше. Как и в синтаксическом анализаторе LR(1), поскольку здесь перед нетерминальной буквой R стоят точки, нам нужно их расширить. Как и при синтаксическом анализе LR(1), при этом нам нужно будет определить, какие прогнозы использовать. Мы начнем с расширения элемента S -> .R [$$], например:
(1)
S' -> .S [$$]
S -> .R [$$]
S -> .RS [$$]
R -> .abT [$$] // New
Далее, давайте расширим параметр S -> .RS [$$]. Это интересный случай. Нам нужно определить, каким будет прогноз для обнаруженных здесь произведений R. В синтаксическом анализаторе LR(1) это можно найти, просматривая ПЕРВЫЙ набор оставшейся части продукции. В синтаксическом анализаторе LR(2), поскольку у нас есть две лексемы просмотра вперед, мы должны искать набор FIRST2, который является обобщением наборов FIRST, в котором перечислены строки длины два, которые могут появиться в начале производства, а не строки длины один, которые могут появиться там. В нашем случае FIRST2(S) = {ab} (понимаете, почему?), поэтому имеем следующее:
(1)
S' -> .S [$$]
S -> .R [$$]
S -> .RS [$$]
R -> .abT [$$]
R -> .abT [ab] // New
На данный момент мы закончили расширять первый набор настроек. Пришло время подумать о том, что бы мы сделали, если бы в следующий раз увидели других персонажей. К счастью, в данном случае это довольно просто, поскольку первым символом любой строки, созданной этой грамматикой, должен быть a. Итак, давайте посмотрим, что произойдет, если мы встретим a:
(2)
R -> a.bT [$$]
R -> a.bT [ab]
Кажется, пока все в порядке. Что произойдет, если мы увидим здесь b? Это приведет нас к этому месту:
(3)
R -> ab.T [$$]
R -> ab.T [ab]
Здесь есть два элемента LR(2), у которых есть точки перед нетерминалом, поэтому нам нужно расширить их. Давайте начнем с расширения их для R -> ab.T [$$], указав следующее:
(3)
R -> ab.T [$$]
R -> ab.T [ab]
T -> .aT [$$] // New
T -> .c [$$] // New
T -> . [$$] // New
Далее мы расширим производство для R -> ab.T [ab]:
(3)
R -> ab.T [$$]
R -> ab.T [ab]
T -> .aT [$$]
T -> .c [$$]
T -> . [$$]
T -> .aT [ab] // New
T -> .c [ab] // New
T -> . [ab] // New
Это заполняет этот конфигурационный набор. Это первый раз, когда мы нашли некоторые элементы сокращения, которые были завершены (здесь T -> . с двумя разными прогнозами). У нас также есть некоторые сменные предметы здесь. Таким образом, мы должны спросить: у нас здесь конфликт сдвига/уменьшения или конфликт уменьшения/уменьшения?
Начнем с уменьшения/уменьшения конфликтов. Как и в случае синтаксического анализа LR(1), у нас возникает конфликт редукции/свертки, когда есть два разных элемента редукции (элементы с точкой в конце) с одним и тем же опережением. Здесь у нас есть два разных элемента сокращения, но у них разные прогнозы. Это означает, что у нас все в порядке на фронте уменьшения/уменьшения.
Теперь интересный случай. Есть ли здесь какие-либо конфликты сдвига/уменьшения? Здесь все немного отличается от синтаксического анализа LR(1). Как и в случае синтаксического анализа LR(1), мы смотрим на все элементы сдвига в нашем наборе (элементы с точкой перед терминалом) и все элементы сокращения в нашем наборе (элементы с точкой в конце). Мы смотрим, есть ли какие-либо конфликты:
T -> .aT [$$] // Shift
T -> .c [$$] // Shift
T -> . [$$] // Reduce
T -> .aT [ab] // Shift
T -> .c [ab] // Shift
T -> . [ab] // Reduce
Вопрос, однако, в том, как здесь выглядит конфликт сдвига/уменьшения. В синтаксическом анализаторе LR(2) у нас есть две лексемы просмотра вперед, на которых мы основываем наше решение о сдвиге или уменьшении. В случае элементов сокращения легко увидеть, к чему приведут два токена просмотра вперед — это двухсимвольный просмотр вперед в скобках. С другой стороны, рассмотрим элемент смены T -> .c [ab]. Что такое двухсимвольный просмотр вперед, в котором мы будем выполнять сдвиг? В случае парсера LR(1) мы просто сказали бы, что точка стоит перед c, поэтому мы смещаемся на c, но здесь этого недостаточно. Вместо этого мы бы сказали, что опережающий просмотр, связанный с этим элементом смены, равен ca, причем c исходит из самого производства, а a исходит из первого символа предпросмотра элемента.
Аналогично рассмотрим элемент смены T -> .aT [$$]. Нам нужны два символа просмотра вперед, и мы можем легко увидеть один из них (a после точки). Чтобы получить второе, мы должны посмотреть, что T может произвести. Есть три производства для T: одно заменяет T на ε, другое заменяет T на aT и третье заменяет T на c. Это означает, что любая строка, которая может быть получена из T, начинается либо с a, либо с c, либо является пустой строкой. В результате элемент T -> .aT [$$] говорит нам сдвинуться, когда мы видим либо ac, либо aa (что мы получили бы от a и c), либо a$ (что мы получили бы, если бы использовали продукцию T → ε, тогда взял один из символов $ из обычного просмотра вперед.
В более общем смысле, следуя той же общей процедуре — используя терминал(ы) после точки, терминалы в предварительном наборе для элемента и символы, которые могут появляться в начале любых строк, полученных из будущих нетерминалов, — мы можем вычислить двухсимвольный просмотр вперед, который мы используем, чтобы определить, когда нужно сдвинуться. В частности, у нас осталось это:
(3)
R -> ab.T [$$]
R -> ab.T [ab]
T -> .aT [$$] // Shift on aa, ac, a$
T -> .c [$$] // Shift on c$
T -> . [$$] // Reduce on $$
T -> .aT [ab] // Shift on aa, ac
T -> .c [ab] // Shift on ca
T -> . [ab] // Reduce on ab
К счастью, здесь нет конфликтов сдвиг/свертка, потому что каждый двухсимвольный просмотр вперед говорит нам делать что-то другое.
Глядя за точку, чтобы определить, когда нужно сдвинуться, это что-то новое для синтаксического анализа LR(2), которое появляется в синтаксическом анализе LR(k > 1), но не LR(1). При синтаксическом анализе LR(1) нам просто нужно посмотреть на терминал за точкой. При синтаксическом анализе LR(2), поскольку нам нужно больше символов, чтобы определить, что делать, мы должны вычислить вторичную точку вперед для каждого элемента смены. В частности, точечный просмотр вперед определяется следующим образом:
В постановке A → α.tω [γ], где t — терминал, упреждающая точка — это множество всех строк длины 2, которые могут появиться в начале строки, производной от tωγ. Другими словами, произведение A → α.tω [γ] имеет точечный просмотр вперед, равный FIRST2(tωγ).
Имея все это в виду, мы можем построить полный синтаксический анализатор LR(2) и описать действия, связанные с каждым состоянием. Общий синтаксический анализатор LR(2) выглядит следующим образом:
(1)
S' -> .S [$$] // Go to 10
S -> .R [$$] // Go to 8
S -> .RS [$$] // Go to 8
R -> .abT [$$] // Shift on ab, go to (2)
R -> .abT [ab] // Shift on ab, go to (2)
(2)
R -> a.bT [$$] // Shift on ba, bc, b$, go to (3)
R -> a.bT [ab] // Shift on ba, bc, go to (3)
(3)
R -> ab.T [$$] // Go to 7
R -> ab.T [ab] // Go to 7
T -> .aT [$$] // Shift on aa, ac, a$, go to (4)
T -> .c [$$] // Shift on c$, go to (5)
T -> . [$$] // Reduce on $$
T -> .aT [ab] // Shift on aa, ac, go to (4)
T -> .c [ab] // Shift on ca, go to (5)
T -> . [ab] // Reduce on ab
(4)
T -> a.T [$$] // Go to 6
T -> a.T [ab] // Go to 6
T -> . [$$] // Reduce on $$
T -> .aT [$$] // Shift on aa, ac, a$, go to (4)
T -> .c [$$] // Shift on c$, go to (5)
T -> . [ab] // Reduce on ab
T -> .aT [ab] // Shift on aa, ac, go to (4)
T -> .c [ab] // Shift on ca, go to (5)
(5)
T -> c. [$$] // Reduce on $$
T -> c. [ab] // Reduce on ab
(6)
T -> aT. [$$] // Reduce on $$
T -> aT. [ab] // Reduce on ab
(7)
R -> abT. [$$] // Reduce on $$
R -> abT. [ab] // Reduce on ab
(8)
S -> R. [$$] // Reduce on $$
S -> R.S [$$] // Go to 9
S -> .RS [$$] // Go to 8
S -> .R [$$] // Go to 8
R -> .abT [$$] // Shift on ab, go to (2)
R -> .abT [ab] // Shift on ab, go to (2)
(9)
S -> RS. [$$] // Reduce on $$
(10)
S' -> S. [$$] // Accept on $$
Итак, теперь у нас есть парсер LR(2) для этой грамматики. Все, что осталось сделать сейчас, это закодировать это как действие и таблицу перехода, подобно тому, что мы делаем для синтаксического анализатора LR(1).
Как и следовало ожидать, таблица действий для синтаксического анализатора LR(2) отличается от таблицы действий для синтаксического анализатора LR(1) тем, что она задается поиском вперед, задаваемым двумя символами, а не одним символом. Это означает, что таблица действий будет намного больше для парсера LR(2), чем для парсера LR(1). Вот как это выглядит здесь:
state | aa | ab | ac | a$ | ba | bb | bc | b$ | ca | cb | cc | c$ | $$
------+----+----+----+----+----+----+----+----+----+----+----+----+----
1 | | S | | | | | | | | | | |
------+----+----+----+----+----+----+----+----+----+----+----+----+----
2 | | | | | S | | S | S | | | | |
------+----+----+----+----+----+----+----+----+----+----+----+----+----
3 | S | R | S | S | | | | | S | | | S | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
4 | S | R | S | S | | | | | S | | | S | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
5 | | R | | | | | | | | | | | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
6 | | R | | | | | | | | | | | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
7 | | R | | | | | | | | | | | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
8 | | S | | | | | | | | | | | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
9 | | | | | | | | | | | | | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
10 | | | | | | | | | | | | | A
Как вы можете видеть, каждая запись здесь просто говорит, следует ли сдвинуть или уменьшить. На практике каждый элемент сокращения будет помечен тегом производства, для которого вы на самом деле выполняете сокращение, но, гм, мне было лень это печатать.
В таблице синтаксического анализа LR(1) вы обычно комбинируете эту таблицу с таблицей перехода, указывающей, куда идти после просмотра каждого символа. Виной тому случайное стечение обстоятельств. В синтаксическом анализаторе LR(1) размер опережающего просмотра равен 1, что согласуется с тем фактом, что таблица перехода говорит, куда вы должны перейти, увидев следующий символ. В синтаксическом анализаторе LR(2) решение о сдвиге или уменьшении зависит от двух символов просмотра вперед, но выбор того, куда идти дальше после чтения еще одного символа ввода, зависит только от одного символа. То есть, даже если у вас есть два маркера просмотра вперед, чтобы решить, делать ли это, вы перемещаете только один символ за раз. Это означает, что таблица перехода для анализатора LR(2) очень похожа на таблицу перехода для анализатора LR(0) или LR(1) и показана здесь:
state | a | b | c | $ | S | R | T
-------+-----+-----+-----+-----+-----+-----+-----
1 | 2 | | | | 10 | 8 |
-------+-----+-----+-----+-----+-----+-----+-----
2 | | 3 | | | | |
-------+-----+-----+-----+-----+-----+-----+-----
3 | 4 | | 5 | | | | 7
-------+-----+-----+-----+-----+-----+-----+-----
4 | 4 | | 5 | | | | 6
-------+-----+-----+-----+-----+-----+-----+-----
5 | | | | | | |
-------+-----+-----+-----+-----+-----+-----+-----
6 | | | | | | |
-------+-----+-----+-----+-----+-----+-----+-----
7 | | | | | | |
-------+-----+-----+-----+-----+-----+-----+-----
8 | 2 | | | | 9 | 8 |
-------+-----+-----+-----+-----+-----+-----+-----
9 | | | | | | |
-------+-----+-----+-----+-----+-----+-----+-----
10 | | | | | | |
Итак, резюмируя:
Интересно, что когда вы знаете, как построить анализатор LR(2), вы можете обобщить идею построения анализатора LR(k) для любого k ≥ 2. посмотрим на все большие и большие значения k.
На практике синтаксические анализаторы LR(2) редко используются из-за размера их таблиц действий и того факта, что они обычно имеют гораздо больше состояний, чем синтаксический анализатор LR(1) из-за увеличенного просмотра вперед. Но все же стоит, ИМХО, посмотреть, как они работают. Это дает вам общее представление о том, как работает анализ LR.
Надеюсь это поможет!
Огромная благодарность за @AProgrammer ответ на сайте cs.stackexchange.com о точечном просмотре вперед и элементном просмотре, который помог мне лучше понять, как работают точечные прогнозы и какова их цель!
Если вы хотите прочитать исходную статью о синтаксическом анализе LR(k), в которой подробно описаны полные правила синтаксического анализа LR(k), ознакомьтесь с книгой Дона Кнута «Перевод языков слева направо». .
